2010/02/09 by Jozsef Balogh, Balogh, Jozsef, Dhruv Mubayi +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1002.1925
arxiv created 2010/02/09 · arxiv updated 2010/02/26
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 \HH is semi-bipartite if its vertex set contains a vertex subset X such that every edge of \HH intersects X in exactly two points. It is easy to see that if \HH is semi-bipartite, then the neighborhood of every pair of vertices in \HH 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 Erd\H os-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.