Clique density vs blowups
Abstract
Abstract A well-known theorem of Nikiforov asserts that any graph with a positive upper K Subscript r K r $K_{r}$ -density contains a logarithmic blowup of upper K Subscript r K r $K_r$ . In this paper, we explore variants of Nikiforov’s result in the following form. Given r comma t element of double struck upper N r , t ∈ N $r,t\in \mathbb{N}$ , when a positive upper K Subscript r K r $K_{r}$ -density implies the existence of a significantly larger (with almost linear size) blowup of upper K Subscript t K t $K_t$ ? Our results include: • For an n n $n$ -vertex ordered graph upper G G $G$ with no induced monotone path upper P 6 P 6
Fields of Study & Subjects
Limits and Structures in Graph Theory
Graph theory and applications
Commutative Algebra and Its Applications
Publication details
- Journal / source
- Combinatorics Probability Computing
- Publisher
- Cambridge University Press (CUP)
- Volume
- 35
- Issue
- 3
- Pages
- 294–315
- Publication date
- 22 January 2026
- Language
- EN