Almost all triple systems with independent neighborhoods are semi-bipartite

József Balogh, Dhruv Mubayi

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1494-1518
Number of pages25
JournalJournal of Combinatorial Theory. Series A
Volume118
Issue number4
DOIs
StatePublished - May 2011

Keywords

  • Independent neighborhoods
  • Semi-bipartite
  • Speed of hypergraph property

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Almost all triple systems with independent neighborhoods are semi-bipartite'. Together they form a unique fingerprint.

Cite this