Printable PDF
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

****************************