Almost all triangle-free triple systems are tripartite

József Balogh, Dhruv Mubayi

Research output: Contribution to journalArticlepeer-review

Abstract

A triangle in a triple system is a collection of three edges isomorphic to {123,124,345}. A triple system is triangle-free if it contains no three edges forming a triangle. It is tripartite if it has a vertex partition into three parts such that every edge has exactly one point in each part. It is easy to see that every tripartite triple system is triangle-free. We prove that almost all triangle-free triple systems with vertex set [n] are tripartite. Our proof uses the hypergraph regularity lemma of Frankl and Rödl [13], and a stability theorem for triangle-free triple systems due to Keevash and the second author [15].

Original languageEnglish (US)
Pages (from-to)143-169
Number of pages27
JournalCombinatorica
Volume32
Issue number2
DOIs
StatePublished - Mar 2012

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Almost all triangle-free triple systems are tripartite'. Together they form a unique fingerprint.

Cite this