2021/11/20 by Chang, Fan, Han, Jie, Kim, Jaehoon +2
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2111.10512
The following question was proposed by Nenadov and Pehova and reiterated by Knierim and Su: Given integers ℓ,r and n with n∈ rℕ, is it true that every n-vertex graph G with δ(G) ≥ max \ (1)/(2),(r - ℓ)/(r) \n + o(n) and αℓ(G) = o(n) contains a Kr-factor? We give a negative answer for the case when ℓ≥ (3r)/(4) by giving a family of constructions using the so-called cover thresholds and show that the minimum degree condition given by our construction is asymptotically best possible. That is, for all integers r,ℓ with r > ℓ ≥ (3)/(4)r and μ>0, there exist α> 0 and N such that for every n∈ rℕ with n>N, every n-vertex graph G with δ(G) ≥ ( \frac12-\varrhoℓ(r-1) + μ)n and αℓ(G) ≤ αn contains a Kr-factor. Here \varrhoℓ(r-1) is the Ramsey--Turán density for Kr-1 under the ℓ-independence number condition.