Isomorphic edge disjoint subgraphs of hypergraphs1. Issue 4 (12th February 2016)

• Record Type: Journal Article
• Authors: Horn, Paul; Koubek, Václav; Rödl, Vojtěch
• Is Part Of: Random structures & algorithms. Volume 48:Issue 4(2016)
• Page Start: 767
• Page End: 793
• Publication Date: 2016-02-12
• Subjects: subgraphs -- isomorphisms -- self‐similarity -- uniform hypergraphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20635
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We show that any k ‐uniform hypergraph with n edges contains two isomorphic edge disjoint subgraphs of size Ω ˜ ( n 2 / ( k + 1 ) ) for k = 4, 5 and 6. This is best possible up to a logarithmic factor due to an upper bound construction of Erdő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 O ˜ ( n 2 / ( k + 1 ) ) . Furthermore, our result extends results Erdős, Pach and Pyber who also established the lower bound for k = 2 (eg. for graphs), and of Gould and Rödl who established the result for k = 3. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 48, 767–793, 2016