\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Po-Shen Loh}
%
%
\medskip
\noindent
%
%
{\bf A Note on Embedding Hypertrees}
%
%
\vskip 5mm
\noindent
%
%
%
%
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 {\it $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.
\bye