Asymptotic Structure of Graphs with the Minimum Number of Triangles

Abstract

We consider the problem of minimizing the number of triangles in a graph of given order and size and describe the asymptotic structure of extremal graphs. This is achieved by characterizing the set of flag algebra homomorphisms that minimize the triangle density.

22 pages; 2 figures

References in corpus (5)

• The Clique Density Theorem
• Phase transitions in a complex network
• On replica symmetry of large deviations in random graphs
• The Asymptotics of Large Constrained Graphs
• Phase transitions in exponential random graphs

Cited by in corpus (17)

• Phase transitions in a complex network
• The Asymptotics of Large Constrained Graphs
• Minimum number of monotone subsequences of length 4 in permutations
• Infinite dimensional finitely forcible graphon
• The exact minimum number of triangles in graphs of given order and size
• Elusive extremal graphs
• Minimizing the number of 5-cycles in graphs with given edge-density
• Asymptotic Structure of Constrained Exponential Random Graph Models
• A new bound for the 2/3 conjecture
• Simple evolving random graphs
• Finitely forcible graph limits are universal
• Densities of 3-vertex graphs
• Finitely forcible graphons with an almost arbitrary structure
• Asymptotic Structure for the Clique Density Theorem
• Finitely forcible graphons and permutons
• The dimension of the feasible region of pattern densities
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs