2023/07/17 by Xiying Du, Du, Xiying, António Girão +7 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2307.08361
openalex publication_date 2023/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that there exists a constant C so that, for all s,k ∈ ℕ, if G has average degree at least kCs3 and does not contain Ks,s as a subgraph then it contains an induced subgraph which is C4-free and has average degree at least k. It was known that some function of s and k suffices, but this is the first explicit bound. We give several applications of this result, including short and streamlined proofs of the following two corollaries. We show that there exists a constant C so that, for all s,k ∈ ℕ, if G has average degree at least kCs3 and does not contain Ks,s as a subgraph then it contains an induced subdivision of Kk. This is the first quantitative improvement on a well-known theorem of Kühn and Osthus; their proof gives a bound that is triply exponential in both k and s. We also show that for any hereditary degree-bounded class F, there exists a constant C=CF so that Cs3 is a degree-bounding function for F. This is the first bound of any type on the rate of growth of such functions. It is open whether there is always a polynomial degree-bounding function.