Asymptotic structure of graphs with the minimum number of triangles

DOI10.1017/S0963548316000110zbMATH Open1371.05147arXiv1204.2846OpenAlexW1851625382MaRDI QIDQ5366929FDOQ5366929

Authors: Oleg Pikhurko, Alexander Razborov 

Publication date: 10 October 2017

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

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.

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

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

zbMATH Keywords

asymptotic structure of extremal graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Cites Work

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

Cited In (28)

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

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)