Abstract A well-known theorem of Nikiforov asserts that any graph with a positive Kₑ -density contains a logarithmic blowup of Kᵣ. In this paper, we explore variants of Nikiforov’s result in the following form. Given r, t N, when a positive Kₑ -density implies the existence of a significantly larger (with almost linear size) blowup of Kₜ? Our results include: • For an n -vertex ordered graph G with no induced monotone path P₆, if its complement G has positive triangle density, then G contains a biclique of size (n { n}). This strengthens a recent result of Pach and Tomon. For general k, let g (k) be the minimum r N such that for any n -vertex ordered graph G with no induced monotone P₂₊, if G has positive Kᵣ -density, then G contains a biclique of size <jats: inline-graphic xmlns: xlink="http: //www. w3. org/19
Bradač et al. (Thu,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: