Counting odd cycles in locally dense graphs

Original · EN

We prove that for any given ε>0 and d∈ [0,1], every sufficiently large (ε, d)-dense graph G contains for each odd integer r at least (dʳ-ε)|V(G)|ʳ cycles of length r. Here, G being (ε, d)-dense means that every set X containing at least ε|V(G)| vertices spans at least d2 |X|² 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.