The ACO Seminar (2011-2012)

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.