Induced even cycles in locally sparse graphs

2024/11/19 by Ding, Laihao, Gao, Jun, Liu, Hong +2 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2411.12659

Abstract

A graph G is (c,t)-sparse if for every pair of vertex subsets A,B⊂ V(G) with |A|,|B|≥ t, e(A,B)≤ (1-c)|A||B|. In this paper we prove that for every c>0 and integer ℓ, there exists C>1 such that if an n-vertex graph G is (c,t)-sparse for some t, and has at least C t^1-1/ℓn^1+1/ℓ edges, then G contains an induced copy of C_2ℓ. This resolves a conjecture of Fox, Nenadov and Pham.

Cited by

• C₄-free subgraphs of high degree with geometric applications

Related

• Coloring locally sparse graphs
• Bounds for the independence and chromatic numbers of locally sparse graphs
• Blow-up lemma for cycles in sparse random graphs
• Counting sparse induced subgraphs in locally dense graphs
• Covering cycles in sparse graphs