Short paths in 3-uniform quasi-random hypergraphs

Joanna Polcyn

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 3, page 469-484
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Joanna Polcyn. "Short paths in 3-uniform quasi-random hypergraphs." Discussiones Mathematicae Graph Theory 24.3 (2004): 469-484. <http://eudml.org/doc/270693>.

@article{JoannaPolcyn2004,
abstract = {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.},
author = {Joanna Polcyn},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hypergraph; path; quasi-randomness; strong regularity lemma},
language = {eng},
number = {3},
pages = {469-484},
title = {Short paths in 3-uniform quasi-random hypergraphs},
url = {http://eudml.org/doc/270693},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Joanna Polcyn
TI - Short paths in 3-uniform quasi-random hypergraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 3
SP - 469
EP - 484
AB - 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.
LA - eng
KW - hypergraph; path; quasi-randomness; strong regularity lemma
UR - http://eudml.org/doc/270693
ER -

References

top
  1. [1] B. Bollobás, Random Graphs (Academic Press, London, 1985). 
  2. [2] Y. Dementieva, Equivalent Conditions for Hypergraph Regularity (Ph.D. Thesis, Emory University, 2001). 
  3. [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. Zbl0995.05141
  4. [4] S. Janson, T. Łuczak and A. Ruciński, Random Graphs (Wiley, New York, 2000), doi: 10.1002/9781118032718. 
  5. [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 Zbl0864.05063
  6. [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. Zbl0919.05042
  7. [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. Zbl1091.05009
  8. [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. Zbl1026.05061
  9. [9] V. Rödl, A. Ruciński and E. Szemerédi, A Dirac-type theorem for 3-uniform hypergraphs, submitted. Zbl1082.05057
  10. [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. Zbl0413.05055

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.