On the number of cliques in graphs with a forbidden subdivision or immersion

Jacob Fox, Fan Wei

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

How many cliques can a graph on n vertices have with a forbidden substructure? Extremal problems of this sort have been studied for a long time. This paper studies the maximum possible number of cliques in a graph on n vertices with a forbidden clique subdivision or immersion. We prove for t sufficiently large that every graph on n \geq t vertices with no Kt-immersion has at most n2t+log22 t cliques, which is sharp apart from the 2O(log2 t) factor. We also prove that the maximum number of cliques in an n-vertex graph with no Kt-subdivision is at most 21.817tn for sufficiently large t. This improves on the best known exponential constant by Lee and Oum. We conjecture that the optimal bound is 32t/3+o(t)n, as we proved for minors in place of subdivision in earlier work.

Original languageEnglish (US)
Pages (from-to)2556-2582
Number of pages27
JournalSIAM Journal on Discrete Mathematics
Volume34
Issue number4
DOIs
StatePublished - 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Container method
  • Counting cliques
  • Forbidden immersion
  • Forbidden subdivision

Fingerprint

Dive into the research topics of 'On the number of cliques in graphs with a forbidden subdivision or immersion'. Together they form a unique fingerprint.

Cite this