Jan 26, 3:30pm, Wean 8220

Paul Horn, Harvard

Isomorphic subgraphs in uniform hypergraphs

Paul Horn, Harvard

Isomorphic subgraphs in uniform 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 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.