ACO The ACO Seminar (2011-2012)

Jan 26, 3:30pm, Wean 8220
Paul Horn, Harvard
Isomorphic subgraphs in uniform hypergraphs


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 is best possible up to a logarithmic factor due to a upper bound construction of Erdos, 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, our result extends results Erdos, Pach and Pyber who also established the lower bound for K = 2 (ie. for graphs), and of Gould and Rodl who established the result for K = 3. In this talk, we'll discuss some of the main ideas of the proof, which is probabilistic, and the obstructions which prevent us from establishing the result for higher values of K.

Back to the ACO home page