Charles Explorer logo
🇨🇿

Isomorphic edge disjoint subgraphs of hypergraphs

Publikace na Matematicko-fyzikální fakulta |
2016

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

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