Publication at Faculty of Mathematics and Physics |
2016
Abstract
We show that any k-uniform hypergraph with n edges contains two isomorphic edge disjoint subgraphs of size (n2/(k+1)) for k=4, 5 and 6. This is best possible up to a logarithmic factor due to an upper bound construction of Erds, 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 O(n2/(k+1)).
Furthermore, our result extends results Erds, Pach and Pyber who also established the lower bound for k=2 (eg. for graphs), and of Gould and Rodl who established the result for k=3. (c) 2016 Wiley Periodicals, Inc. Random Struct.
Alg., 48, 767-793, 2016