2009/10/15 by József Balogh, Jozsef Balogh, Balogh, Jozsef +2
Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.0910.2941
arxiv created 2009/10/15 · openalex publication_date 2009/10/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A triple system is cancellative if no three of its distinct edges satisfy A ∪ B=A ∪ C. 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 cancellative. We prove that almost all cancellative triple systems with vertex set [n] are tripartite. This sharpens a theorem of Nagle and Rodl on the number of cancellative triple systems. It also extends recent work of Person and Schacht who proved a similar result for triple systems without the Fano configuration. Our proof uses the hypergraph regularity lemma of Frankl and Rodl, and a stability theorem for cancellative triple systems due to Keevash and the second author.