Counting odd cycles in locally dense graphs

Abstract

We prove that for any given $\epsilon >0$ and $d\in [0,1]$, every sufficiently large $(\epsilon ,d)$-dense graph $G$ contains for each odd integer $r$ at least $(d^r-\epsilon )|V(G){|}^r$ cycles of length $r$. Here, $G$ being $(\epsilon ,d)$-dense means that every set $X$ containing at least~$\epsilon |V(G)|$ vertices spans at least $\frac{d}{2}|X{|}^2$ edges, and what we really count is the number of homomorphisms from an $r$-cycle into $G$. The result adresses a question of Y. Kohayakawa, B. Nagle, V. Rödl, and M. Schacht.

Cited by in corpus (1)

• Some advances on Sidorenko's conjecture