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

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

2012-03-13

arxiv.org/abs/1203.2723v1

Mathematics

Combinatorics

35 pages, 12 figures

Scientific paper

Fifty years ago Erd\H{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 $\frac{n}{l-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 $\frac{n}{2}$. In this paper we solve Erd\H{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 Erd\H{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)$.

Affiliated with

Also associated with

No associations

Rating

A problem of Erdős on the minimum number of $k$-cliques does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A problem of Erdős on the minimum number of $k$-cliques, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A problem of Erdős on the minimum number of $k$-cliques will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-143649