TY - JOUR
T1 - Almost all triple systems with independent neighborhoods are semi-bipartite
AU - Balogh, József
AU - Mubayi, Dhruv
N1 - E-mail addresses: [email protected] (J. Balogh), [email protected] (D. Mubayi). 1 Research supported in part by NSF CAREER Grant DMS-0745185 and DMS-0600303, UIUC Campus Research Board Grants 09072 and 11067, and OTKA Grant K76099. 2 Research supported in part by NSF grants DMS 0653946 and 0969092.
PY - 2011/5
Y1 - 2011/5
N2 - The neighborhood of a pair of vertices u, v in a triple system is the set of vertices w such that uvw is an edge. A triple system H is semi-bipartite if its vertex set contains a vertex subset X such that every edge of H intersects X in exactly two points. It is easy to see that if H is semi-bipartite, then the neighborhood of every pair of vertices in H is an independent set. We show a partial converse of this statement by proving that almost all triple systems with vertex sets [n] and independent neighborhoods are semi-bipartite. Our result can be viewed as an extension of the Erdo{double acute}s-Kleitman-Rothschild theorem to triple systems.The proof uses the Frankl-Rödl hypergraph regularity lemma, and stability theorems. Similar results have recently been proved for hypergraphs with various other local constraints.
AB - The neighborhood of a pair of vertices u, v in a triple system is the set of vertices w such that uvw is an edge. A triple system H is semi-bipartite if its vertex set contains a vertex subset X such that every edge of H intersects X in exactly two points. It is easy to see that if H is semi-bipartite, then the neighborhood of every pair of vertices in H is an independent set. We show a partial converse of this statement by proving that almost all triple systems with vertex sets [n] and independent neighborhoods are semi-bipartite. Our result can be viewed as an extension of the Erdo{double acute}s-Kleitman-Rothschild theorem to triple systems.The proof uses the Frankl-Rödl hypergraph regularity lemma, and stability theorems. Similar results have recently been proved for hypergraphs with various other local constraints.
KW - Independent neighborhoods
KW - Semi-bipartite
KW - Speed of hypergraph property
UR - http://www.scopus.com/inward/record.url?scp=79151482883&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79151482883&partnerID=8YFLogxK
U2 - 10.1016/j.jcta.2011.01.006
DO - 10.1016/j.jcta.2011.01.006
M3 - Article
AN - SCOPUS:79151482883
SN - 0097-3165
VL - 118
SP - 1494
EP - 1518
JO - Journal of Combinatorial Theory. Series A
JF - Journal of Combinatorial Theory. Series A
IS - 4
ER -