Almost all triangle-free triple systems are tripartite (Q452822)

For a fixed ``forbidden'' 3-graph \(F\), \(\text{Forb}(n,F)\) denotes the collection of 3-graphs with vertex-set \([n]=\{1,2,\dots,n\}\) which are ``\(F\)-free'', i.e., which contain no copy of \(F\). A 3-graph is 3-partite if its vertices can be partitioned into three disjoint parts so that all edges have exactly one vertex in each part; thus the maximum number of edges in a 3-partite 3-graph on \(n\) vertices is \(s(n) :=\left\lfloor\frac{n}3\right\rfloor \left\lfloor\frac{n+1}3\right\rfloor \left\lfloor\frac{n+2}3\right\rfloor\); \(T(n)\) denotes the number of 3-partite 3-graphs on \([n]\). \(F_5\) denotes the ``3-graph triangle'', having vertices \(\{1,2,3,4,5\}\) and edges \(\{123,124,345\}\); evidently all 3-partite 3-graphs are \(F_5\)-free. Theorem 1: Almost all \(F_5\)-free 3-graphs on \([n]\) are 3-partite. More precisely, there is a constant \(C>0\) such that \(T(n)\leq \left| \text{Forb}\left(n,F_5\right)\right| <\left(1+2^{Cn-\frac{2n^2}{45}}\right)T(n)\). Corollary 1: As \(n\to\infty\), \(\log_2\left| \text{Forb}\left(n,F_5\right)\right| =s(n)+n\log_23+\Theta(\log n)\). From the authors' abstract: ``Our proof uses the hypergraph regularity lemma of Frankl and Rödl [\textit{P.~Frankl and V.~Rödl}, Random Struct. Algorithms 20, 131--164 (2002; Zbl 0995.05141)], and a stability theorem for triangle-free triple systems due to Keevash and the second author [\textit{P.~Keevash and D.~Mubayi}, J. Comb. Theory, Ser. B 92, 163--175 (2004; Zbl 1052.05051)].