Almost all triple systems with independent neighborhoods are semi-bipartite

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 Erdős–Kleitman–Rothschild theorem to triple systems. oof uses the Frankl–Rödl hypergraph regularity lemma, and stability theorems. Similar results have recently been proved for hypergraphs with various other local constraints.