A Note on Embedding Hypertrees
Po‐Shen Loh · The Electronic Journal of Combinatorics · 2009
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2009
Abstract
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.
Open the resolved locator · 10.37236/256
Metadata licence: OpenAlex metadata (CC0)