Hostname: page-component-6898cfcb55-w5hgh Total loading time: 0 Render date: 2026-11-11T18:37:04.507Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimum Number of k-Cliques in Graphs with Bounded Independence Number

Published online by Cambridge University Press:  01 October 2013

OLEG PIKHURKO and
EMIL R. VAUGHAN
OLEG PIKHURKO
Affiliation:
Mathematics Institute and DIMAP, University of Warwick, Coventry CV4 7AL, UK (e-mail: Pikhurko@warwick.ac.uk)
EMIL R. VAUGHAN
Affiliation:
Centre for Discrete Mathematics, Queen Mary, University of London, London E1 4NS, UK (e-mail: e.vaughan@qmul.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Erdős asked in 1962 about the value of f(n,k,l), the minimum number of k-cliques in a graph with order n and independence number less than l. The case (k,l)=(3,3) was solved by Lorden. Here we solve the problem (for all large n) for (3,l) with 4 ≤ l ≤ 7 and (k,3) with 4 ≤ k ≤ 7. Independently, Das, Huang, Ma, Naves and Sudakov resolved the cases (k,l)=(3,4) and (4,3).

Keywords

Primary 05C35Secondary 90C35

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 6 , November 2013, pp. 910 - 934
Copyright
Copyright © Cambridge University Press 2013 

Footnotes

†

Supported by the European Research Council (grant agreement no. 306493) and the National Science Foundation of the USA (grant DMS-1100215).

References

[1]Alon, N., Fischer, E., Krivelevich, M. and Szegedy, M. (2000) Efficient testing of large graphs. Combinatorica 20 451–476.Google Scholar
[2]Baber, R. and Talbot, J. (2011) Hypergraphs do jump. Combin. Probab. Comput. 20 161–171.Google Scholar
[3]Bollobás, B. (1978) Extremal Graph Theory, Academic Press.Google Scholar
[4]Cummings, J., Král', D., Pfender, F., Sperfeld, K., Treglown, A. and Young, M. (2013) Monochromatic triangles in three-coloured graphs. J. Combin. Theory Ser. B 103 489–503.Google Scholar
[5]Das, S., Huang, H., Ma, J., Naves, H. and Sudakov, B. (2013) A problem of Erdős on the minimum number of k-cliques. J. Combin. Theory Ser. B 103 344–373.Google Scholar
[6]Erdős, P. (1962) On the number of complete subgraphs contained in certain graphs. Magyar Tud. Akad. Mat. Kutató Int. Kőzl. 7 459–464.Google Scholar
[7]Falgas-Ravry, V., Marchant, E., Pikhurko, O. and Vaughan, E. R. (2013) The codegree threshold for 3-graphs with independent neighbourhoods. E-print arXiv.org:1307.0075.Google Scholar
[8]Falgas-Ravry, V. and Vaughan, E. R. (2012) Turán H-densities for 3-graphs. Electron. J. Combin. 19 P40.Google Scholar
[9]Falgas-Ravry, V. and Vaughan, E. R. (2013) Applications of the semi-definite method to the Turán density problem for 3-graphs. Combin. Probab. Comput. 22 21–54.Google Scholar
[10]Goodman, A. W. (1959) On sets of acquaintances and strangers at any party. Amer. Math. Monthly 66 778–783.Google Scholar
[11]Hatami, H., Hladký, J., Král', D., Norine, S. and Razborov, A. (2013) On the number of pentagons in triangle-free graphs. J. Combin. Theory Ser. A 120 722–732.Google Scholar
[12]Hirst, J. (2011) The inducibility of graphs on four vertices. E-print arXiv.org:1109.1592.Google Scholar
[13]Kalbfleisch, J. G. and Stanton, R. G. (1968) On the maximal triangle-free edge-chromatic graphs in three colors. J. Combin. Theory 5 9–20.CrossRefGoogle Scholar
[14]Lorden, G. (1962) Blue-empty chromatic graphs. Amer. Math. Monthly 69 114–120.Google Scholar
[15]Nikiforov, V. (2001) On the minimum number of k-cliques in graphs with restricted number of independence. Combin. Probab. Comput. 10 361–366.CrossRefGoogle Scholar
[16]Nikiforov, V. (2005) The minimum number of 4-cliques in a graph with triangle-free complement. E-print arXiv.org:math/050121.Google Scholar
[17]Pikhurko, O. (2011) The minimum size of 3-graphs without four vertices spanning no or exactly three edges. Europ. J. Combin. 23 1142–1155.Google Scholar
[18]Pikhurko, O. and Vaughan, E. R. (2013) Minimum number of k-cliques in graphs with bounded independence number. E-print arXiv.1203.4393, version 4.Google Scholar
[19]Ramsey, F. P. (1930) On a problem of formal logic. Proc. London Math. Soc. 30 264–286.Google Scholar
[20]Razborov, A. (2007) Flag algebras. J. Symb. Logic 72 1239–1282.Google Scholar
[21]Razborov, A. (2010) On 3-hypergraphs with forbidden 4-vertex configurations. SIAM J. Discrete Math. 24 946–963.Google Scholar
[22]Thomason, A. (2002) The simplest case of Ramsey's theorem. In Paul Erdős and his Mathematics, Vol. 11 of Bolyai Soc. Math. Studies, Springer, pp. 667–695.Google Scholar
[23]Vaughan, E. R. (2013) Flagmatic: A tool for researchers in extremal graph theory. Version 2.0, http://flagmatic.org/.Google Scholar