2023/12/14 by Matthew Jenssen, Jenssen, Matthew, Will Perkins +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2312.09202
openalex publication_date 2023/12/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the typical structure and the number of triangle-free graphs with n vertices and m edges where m is large enough so that a typical triangle-free graph has a cut containing nearly all of its edges, but may not be bipartite. Erdős, Kleitman, and Rothschild showed that almost every triangle-free graph is bipartite. Osthus, Prömel, and Taraz later showed that for m ≥ (1+ε)(√(3))/(4)n3/2√(log n), almost every triangle-free graph on n vertices and m edges is bipartite. Here we give a precise characterization of the distribution of edges within each part of the max cut of a uniformly chosen triangle-free graph G on n vertices and m edges, for a larger range of densities with m=Θ(n3/2 √(log n)). Using this characterization, we describe the evolution of the structure of typical triangle-free graphs as the density changes. We show that as the number of edges decreases below (√(3))/(4) n3/2√(log n), the following structural changes occur in G: -Isolated edges, then trees, then more complex subgraphs emerge as `defect edges', edges within parts of a max cut of G. The distribution of defect edges is first that of independent Erdős-Rényi random graphs, then that of independent exponential random graphs, conditioned on a small maximum degree and no triangles. -There is a sharp threshold for 3-colorability at m ∼ (√(2))/(4) n3/2√(log n) and a sharp threshold between 4-colorability and unbounded chromatic number at m∼(1)/(4)n3/2√(log n). -Giant components emerge in the defect edges at m∼(1)/(4) n3/2√(log n). We use these results to prove asymptotic formulas for the number of triangle-free graphs at these densities. We likewise prove analogous results for the random graph G(n,p) conditioned on triangle-freeness.