Asymptotic structure of graphs with the minimum number of triangles

DOI10.1017/S0963548316000110MaRDI QIDQ5366929zbMATH OpenOpenAlexFDO

Authors Oleg Pikhurko, Alexander Razborov

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1204.2846

zbMATH Keywords

asymptotic structure of extremal graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

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.

Recommendations

• On the Minimal Density of Triangles in Graphs
• Minimizing the number of triangular edges
• The minimum number of triangles in graphs of given order and size
• The exact minimum number of triangles in graphs with given order and size
• The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs

Cites work

• A problem of Erdős on the minimum number of k-cliques
• Applications of Stein's method for concentration inequalities
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Emergent structures in large networks
• Estimating and understanding exponential random graph models
• Flag algebras
• scientific article; zbMATH DE number 3821782 (Why is no real title available?)
• scientific article; zbMATH DE number 3529891 (Why is no real title available?)
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 3298603 (Why is no real title available?)
• scientific article; zbMATH DE number 3185004 (Why is no real title available?)
• Large networks and graph limits
• Limits of dense graph sequences
• Lower bounds on the number of triangles in a graph
• Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
• Monochromatic triangles in three-coloured graphs
• Nonlinear large deviations
• On a theorem of Rademacher-Turán
• On complete subgraphs of different orders
• On replica symmetry of large deviations in random graphs
• On the Minimal Density of Triangles in Graphs
• On the number of complete subgraphs and circuits contained in graphs
• On the number of pentagons in triangle-free graphs
• On the variational problem for upper tails in sparse random graphs
• Phase transitions in a complex network
• Phase transitions in exponential random graphs
• Quick approximation to matrices and applications
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The asymptotics of large constrained graphs
• The clique density theorem
• The large deviation principle for the Erdős-Rényi random graph
• The minimum size of 3-graphs without a 4-set spanning no or exactly three edges
• The number of cliques in graphs of given order and size
• Triangles in an Ordinary Graph

Cited in

(33)

• Asymptotic number of triangulations with vertices in \(\mathbb{Z}^2\)
• Finitely forcible graph limits are universal
• The minimum number of triangles in graphs of given order and size
• Ensemble equivalence for dense graphs
• Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph
• Minimum number of edges that occur in odd cycles
• Compactness and finite forcibility of graphons
• Singularities in the entropy of asymptotically large simple graphs
• Asymptotic structure of constrained exponential random graph models
• Minimizing the number of triangular edges
• Vertex order in some large constrained random graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• On the Minimal Density of Triangles in Graphs
• scientific article; zbMATH DE number 1305094 (Why is no real title available?)
• Weak regularity and finitely forcible graph limits
• Finitely forcible graphons and permutons
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
• Sharp bounds for decomposing graphs into edges and triangles
• Inducibility and universality for trees
• The exact minimum number of triangles in graphs with given order and size
• Finitely forcible graphons with an almost arbitrary structure
• Asymptotic Structure for the Clique Density Theorem
• Minimizing the number of 5-cycles in graphs with given edge-density
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs
• Typical large graphs with given edge and triangle densities
• Cycles of length three and four in tournaments
• Tripodal structure in undersaturated random graphs
• A note on extremal constructions for the Erdős-Rademacher problem
• New Ramsey multiplicity bounds and search heuristics
• The dimension of the region of feasible tournament profiles
• The dimension of the feasible region of pattern densities
• Cycles of length three and four in tournaments

This page was built for publication: Asymptotic structure of graphs with the minimum number of triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366929)