Almost all triple systems with independent neighborhoods are semi-bipartite

preprint2010arXivOpen access

Abstract

The neighborhood of a pair of vertices u,vu,v in a triple system is the set of vertices ww such that uvwuvw is an edge. A triple system $\HH$ is semi-bipartite if its vertex set contains a vertex subset XX such that every edge of $\HH$ intersects XX 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][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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.