## 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 n2^{t}^{+log2}2 ^{t} cliques, which is sharp apart from the 2^{O}^{(log2 t)} factor. We also prove that the maximum number of cliques in an n-vertex graph with no Kt-subdivision is at most 2^{1.817t}n for sufficiently large t. This improves on the best known exponential constant by Lee and Oum. We conjecture that the optimal bound is 3^{2}t/3+o(t^{)}n, as we proved for minors in place of subdivision in earlier work.

Original language | English (US) |
---|---|

Pages (from-to) | 2556-2582 |

Number of pages | 27 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 34 |

Issue number | 4 |

DOIs | |

State | Published - 2020 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)

## Keywords

- Container method
- Counting cliques
- Forbidden immersion
- Forbidden subdivision