A note on embedding hypertrees
| dc.creator | Loh, Po-Shen | |
| dc.date | 2009-01-20 | |
| dc.date | 2009-05-26 | |
| dc.date.accessioned | 2026-07-07T13:17:42Z | |
| dc.date.available | 2026-07-07T13:17:42Z | |
| dc.description | A classical result from graph theory is that every graph with chromatic number χ> t contains a subgraph with all degrees at least t, and therefore contains a copy of every t-edge tree. Bohman, Frieze, and Mubayi recently posed this problem for r-uniform hypergraphs. An r-tree is an r-uniform hypergraph with no pair of edges intersecting in more than one vertex, and no sequence of distinct vertices and edges (v_1, e_1, ..., v_k, e_k) with all e_i \ni {v_i, v_{i+1}}, where we take v_{k+1} to be v_1. Bohman, Frieze, and Mubayi proved that χ> 2rt is sufficient to embed every r-tree with t edges, and asked whether the dependence on r was necessary. In this note, we completely solve their problem, proving the tight result that χ> t is sufficient to embed any r-tree with t edges. | |
| dc.description | 4 pages; minor revisions, with updated references | |
| dc.identifier | https://arxiv.org/abs/0901.2988 | |
| dc.identifier | http://arxiv.org/abs/0901.2988 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/231198 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C05, 05C65, 05C35 | |
| dc.title | A note on embedding hypertrees | |
| dc.type | text |