A note on embedding hypertrees (Q1028812): Difference between revisions

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.