A problem of Erdős on the minimum number of k-cliques

DOI10.1016/J.JCTB.2013.02.003zbMATH Open1301.05185arXiv1203.2723OpenAlexW2096807443MaRDI QIDQ744160FDOQ744160

Authors: Shagnik Das, Hao Huang, Jie Ma, Humberto Naves, Benny Sudakov 

Publication date: 6 October 2014

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: Fifty years ago ErdH{o}s asked to determine the minimum number of $k$-cliques in a graph on $n$ vertices with independence number less than l. He conjectured that this minimum is achieved by the disjoint union of $l-1$ complete graphs of size $fracnl-1$. This conjecture was disproved by Nikiforov who showed that the balanced blow-up of a 5-cycle has fewer 4-cliques than the union of 2 complete graphs of size $fracn2$. In this paper we solve ErdH{o}s' problem for $(k,l)=(3,4)$ and $(k,l)=(4,3)$. Using stability arguments we also characterize the precise structure of extremal examples, confirming ErdH{o}s' conjecture for $(k,l)=(3,4)$ and showing that a blow-up of a 5-cycle gives the minimum for $(k,l)=(4,3)$.

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

Recommendations

• On the minimum number of \(k\)-cliques in graphs with restricted independence number
• Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
• The number of cliques in graphs of given order and size
• On Erdős's conjecture on multiplicities of complete subgraphs: Lower upper bound for cliques of size 6
• On a conjecture of Erdős for multiplicities of cliques

zbMATH Keywords

minimum number of \(k\)-cliques

Mathematics Subject Classification ID

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

Cites Work

• On the number of pentagons in triangle-free graphs
• On 3-hypergraphs with forbidden 4-vertex configurations
• Hypergraphs do jump
• Title not available (Why is that?)
• Flag algebras
• On the maximum number of five-cycles in a triangle-free graph
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Minimal Density of Triangles in Graphs
• On the minimum number of \(k\)-cliques in graphs with restricted independence number
• Blue-Empty Chromatic Graphs

Cited In (21)

• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• On the maximum density of fixed strongly connected subtournaments
• On the maximum quartet distance between phylogenetic trees
• Sharp bounds for decomposing graphs into edges and triangles
• Decomposing graphs into edges and triangles
• Minimum number of edges that occur in odd cycles
• 2-colorings of complete graphs with a small number of monochromatic \(K_ 4\) subgraphs
• An improved lower bound for multicolor Ramsey numbers and a problem of Erdős
• Independence number of graphs with a prescribed number of cliques
• Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
• On Erdős's conjecture on multiplicities of complete subgraphs: Lower upper bound for cliques of size 6
• Strong forms of stability from flag algebra calculations
• On the densities of cliques and independent sets in graphs
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• Inducibility of directed paths
• On the local structure of oriented graphs -- a case study in flag algebras
• On stability of the Erdős-Rademacher problem
• Asymptotic structure of graphs with the minimum number of triangles
• Semidefinite programming and Ramsey numbers
• On the minimum number of \(k\)-cliques in graphs with restricted independence number
• Compactness and finite forcibility of graphons

This page was built for publication: A problem of Erdős on the minimum number of \(k\)-cliques

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