pith. sign in

arxiv: 2411.12659 · v1 · pith:AC4UUCXInew · submitted 2024-11-19 · 🧮 math.CO

Induced even cycles in locally sparse graphs

classification 🧮 math.CO
keywords sparseeverygraphinducedvertexconjecturecontainscopy
0
0 comments X
read the original abstract

A graph $G$ is $(c,t)$-sparse if for every pair of vertex subsets $A,B\subset V(G)$ with $|A|,|B|\geq t$, $e(A,B)\leq (1-c)|A||B|$. In this paper we prove that for every $c>0$ and integer $\ell$, 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/\ell}n^{1+1/\ell}$ edges, then $G$ contains an induced copy of $C_{2\ell}$. This resolves a conjecture of Fox, Nenadov and Pham.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.