Almost all hypergraphs without Fano planes are bipartite
Yury Person, Mathias Schacht · Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms · 2009
The hypergraph of the Fano plane is the unique 3-uniform hypergraph with 7 triples on 7 vertices in which every pair of vertices is contained in a unique triple. This hypergraph is not 2-colorable, but becomes so on deleting any hyperedge from it. We show that taking uniformly at random a labeled 3-uniform hypergraph H on n vertices not containing the hypergraph of the Fano plane, H turns out to be 2-colorable with probability at least 1 – 2−Ω(n2). For the proof of this result we will study structural properties of Fano-free hypergraphs.