Combinatorics Seminar
When: Sunday, Nov. 7, 10am
Where: Schreiber 309
Speaker: Raphael Yuster, University of Haifa
Title: Asymptotically optimal packing of dense hypergraphs via fractional
decompositions
Abstract:
Let $H_0$ be a fixed hypergraph.
A {\em fractional $H_0$-decomposition} of a hypergraph $H$ is an
assignment of nonnegative real weights to the copies of $H_0$ in $H$
such that for each edge $e \in E(H)$, the sum of the weights of copies
of $H_0$ containing $e$ is precisely one.
Let $k$ and $r$ be positive integers with $k > r > 2$, and let $K_k^r$
denote the complete $r$-uniform hypergraph with $k$ vertices.
We prove that there exists a positive constant $\alpha=\alpha(k,r)$ such
that every $r$-uniform hypergraph with $n$ (sufficiently large) vertices
in which every $(r-1)$-set is contained in at least $n(1-\alpha)$ edges
has a fractional $K_k^r$-decomposition.
Our proof uses several probabilistic arguments and hypergraph coloring
theorems as well as the recently discovered Hall's theorem for
hypergraphs by Aharoni and Haxell.
Application 1:
For the special cases $r=3$, using our result together with a recent
result of Haxell, Nagle and R\"odl we obtain the following
result. For every $3$-uniform hypergraph $H_0$, there exists a positive
constant $\alpha=\alpha(H_0)$ such that
every $3$-uniform hypergraph $H$ with minimum co-degree at least
$(n-2)(1 -\alpha)$
has an $H_0$-packing that covers $|E(H)|(1-o_n(1))$ edges. This extends
the famous seminal result of R\"odl in the case $r=3$, who proved it
for $\alpha=0$.
Application 2:
For the graph-theoretic case, using our result together with a recent
result of Haxell and R\"odl we obtain the following
corollary. For every graph $G_0$, there exists a positive constant
$\alpha=\alpha(G_0)$ such that
every graph $G$ with minimum degree at least $(n-1)(1 -\alpha)$
has a $G_0$-packing that covers $|E(G)|(1-o_n(1))$ edges.
For the case $G_0=K_k$ we get $\alpha > 1/9k^{10}$. This improves an
earlier bound of $10^{-37}k^{-94}$.
For the case $G_0=K_3$ we get $\alpha > 1/10000$. This improves an
earlier bound of $10^{-24}$.