zbMATH — the first resource for mathematics

A note on embedding hypertrees. (English) Zbl 1188.05049
Summary: A classical result from graph theory is that every graph with chromatic number $$\chi > 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 a connected $$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, \ldots, 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 $$\chi > 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 $$\chi > t$$ is sufficient to embed any $$r$$-tree with $$t$$ edges.

MSC:
 05C05 Trees 05C65 Hypergraphs
Full Text: