Department of Mathematics,
University of California San Diego
****************************
Combinatorics Seminar
Paul Horn
Harvard University
Edge disjoint isomorphic subgraphs of hypergraphs
Abstract:
We show that any $k$-uniform hypergraph with $n$ edges contains two edge disjoint subgraphs of size $\tilde{\Omega}(n^{2/(k+1)})$ for $k=4,5$ and $6$. This result is best possible up to a logarithmic factor due to a upper bound construction of Erd\H{o}s, Pach, and Pyber who show there exist $k$-uniform hypergraphs with $n$ edges and with no two edge disjoint isomorphic subgraphs with size larger than $\tilde{O}(n^{2/(k+1)})$. Furthermore, this result extends results Erd\H{o}s, Pach and Pyber who also established the lower bound for $k=2$ (eg. for graphs), and of Gould and R\"odl who established the result for
Host: Jeff Remmel
December 6, 2011
3:00 PM
AP&M 7321
****************************