Frankl and Rödl [3] proved a strong regularity lemma for 3-uniform hypergraphs, based on the concept of δ-regularity with respect to an underlying 3-partite graph. In applications of that lemma it is often important to be able to "glue" together separate pieces of the desired subhypergraph. With this goal in mind, in this paper it is proved that every pair of typical edges of the underlying graph can be connected by a hyperpath of length at most seven. The typicality of edges is defined in terms of graph and hypergraph neighborhoods, and it is shown that all but a small fraction of edges are indeed typical.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1245,
author = {Joanna Polcyn},
title = {Short paths in 3-uniform quasi-random hypergraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {24},
year = {2004},
pages = {469-484},
zbl = {1063.05103},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1245}
}
Joanna Polcyn. Short paths in 3-uniform quasi-random hypergraphs. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 469-484. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1245/
[000] [1] B. Bollobás, Random Graphs (Academic Press, London, 1985).
[001] [2] Y. Dementieva, Equivalent Conditions for Hypergraph Regularity (Ph.D. Thesis, Emory University, 2001).
[002] [3] P. Frankl and V. Rödl, Extremal problems on set systems, Random Structures and Algorithms 20 (2002) 131-164, doi: 10.1002/rsa.10017. | Zbl 0995.05141
[003] [4] S. Janson, T. Łuczak and A. Ruciński, Random Graphs (Wiley, New York, 2000), doi: 10.1002/9781118032718.
[004] [5] J. Komlós, G.N. Sárközy and E. Szemerédi, On the square of a Hamiltonian cycle in dense graphs, Random Structures and Algorithms 9 (1996) 193-211, doi: 10.1002/(SICI)1098-2418(199608/09)9:1/2<193::AID-RSA12>3.0.CO;2-P | Zbl 0864.05063
[005] [6] J. Komlós, G.N. Sárközy and E. Szemerédi, On the Pósa-Seymour conjecture, J. Graph Theory 29 (1998) 167-176. | Zbl 0919.05042
[006] [7] J. Polcyn, V. Rödl, A. Ruciński and E. Szemerédi, Short paths in quasi-random triple systems with sparse underlying graphs, in preparation. | Zbl 1091.05009
[007] [8] B. Nagle and V. Rödl, Regularity properties for triple systems, Random Structures and Algorithms 23 (2003) 264-332, doi: 10.1002/rsa.10094. | Zbl 1026.05061
[008] [9] V. Rödl, A. Ruciński and E. Szemerédi, A Dirac-type theorem for 3-uniform hypergraphs, submitted. | Zbl 1082.05057
[009] [10] E. Szemerédi, Regular partitions of graphs, in: Problèmes en Combinatoire et Théorie des Graphes, Proc. Colloque Inter. CNRS, (J.-C. Bermond, J.-C. Fournier, M. Las Vergnas, D. Sotteau, eds), (1978) 399-401. | Zbl 0413.05055