Publications [#372530] of Fan Wei

Papers Published

1. Fox, J; Wei, F, On the number of cliques in graphs with a forbidden subdivision or immersion, SIAM Journal on Discrete Mathematics, vol. 34 no. 4 (January, 2020), pp. 2556-2582 [doi]
   (last updated on 2025/07/04)

   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+log22 ^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.817tn for sufficiently large t. This improves on the best known exponential constant by Lee and Oum. We conjecture that the optimal bound is 3²t/3+o(t⁾n, as we proved for minors in place of subdivision in earlier work.