Large cliques in graphs with forbidden semi-induced structures

2025/11/17 by Chen, Nannan, Yulai Ma, F. Yang +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Geometric and Algebraic Topology

paper · pdf · doi:10.48550/arxiv.2511.13073

openalex publication_date 2025/11/17 · openalex created_date 2025/11/19 · openalex updated_date 2026/07/28

Abstract

In 2022, Holmsen showed that any graph with at least \( c \binomnr \) \(r\)-cliques but no induced complete r-partite graph K_{2,…, 2} must contain a clique of order \(Ω(c^2^r-1 n)\). In this paper, we study graphs forbidding semi-induced substructures and show that every n-vertex graph G containing at least c\binomnr copies of K_r (for some constant c>0) and forbidding semi-induced substructures, related to K_{2,…, 2}, must contain a clique of order Ω(cn). Our result strengthens Holmsen's bound by improving the dependence on c from c^2^r-1 to linear in c with bounded number of forbidden structures. Furthermore, our approach is naturally linked to the notion of VC-dimension.

Citations

• Induced subgraph density. VI. Bounded VC-dimension
• Large cliques in hypergraphs with forbidden substructures

Related

• Large cliques in hypergraphs with forbidden substructures
• Induced subgraph density. VI. Bounded VC-dimension
• On the number of cliques in graphs with a forbidden subdivision or immersion
• The number of graphs with large forbidden subgraphs
• Large cliques or co-cliques in hypergraphs with forbidden order-size pairs