Asymptotic Structure for the Clique Density Theorem

DOI10.19086/DA.18559zbMath1455.05033arXiv1906.05942OpenAlexW3114961593MaRDI QIDQ5144435

Maryam Sharifzadeh, Oleg Pikhurko, Hong Liu, Jae-Hoon Kim

Publication date: 16 January 2021

Published in: discrete Analysis (Search for Journal in Brave)

Abstract: The famous ErdH{o}s-Rademacher problem asks for the smallest number of $r$-cliques in a graph with the given number of vertices and edges. Despite decades of active attempts, the asymptotic value of this extremal function for all $r$ was determined only recently, by Reiher [Annals of Mathematics, 184 (2016) 683--707]. Here we describe the asymptotic structure of all almost extremal graphs. This task for $r=3$ was previously accomplished by Pikhurko and Razborov [Combinatorics, Probability and Computing, 26 (2017) 138--160].

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

zbMATH Keywords

extremal graph theoryclique density problemasymptotic structure of extremal graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The clique density theorem
• On a theorem of Rademacher-Turán
• Limits of dense graph sequences
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Phases in large combinatorial systems
• Strong forms of stability from flag algebra calculations
• Estimating and understanding exponential random graph models
• An introduction to large deviations for random graphs
• Regularity partitions and the topology of graphons
• The number of cliques in graphs of given order and size
• On the Minimal Density of Triangles in Graphs
• Lower bounds on the number of triangles in a graph
• On complete subgraphs of different orders
• THE EXACT MINIMUM NUMBER OF TRIANGLES IN GRAPHS WITH GIVEN ORDER AND SIZE
• Asymptotic Structure of Graphs with the Minimum Number of Triangles
• Measure Theory
• Flag algebras
• Triangles in an Ordinary Graph

Related Items (1)

THE EXACT MINIMUM NUMBER OF TRIANGLES IN GRAPHS WITH GIVEN ORDER AND SIZE

This page was built for publication: Asymptotic Structure for the Clique Density Theorem