Counting odd cycles in locally dense graphs

Abstract: We prove that for any given

v a r e p s i l o n > 0

and

d i n [0, 1]

, every sufficiently large

(v a r e p s i l o n, d)

-dense graph

G

contains for each odd integer

r

at least

(d^{r} - v a r e p s i l o n) | V (G) |^{r}

cycles of length

r

. Here,

G

being

(v a r e p s i l o n, d)

-dense means that every set

X

containing at least~

v a r e p s i l o n, | V (G) |

vertices spans at least

f r a c 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"odl, and M. Schacht.

Cites Work

Cited In (6)

   Recommendations

This page was built for publication: Counting odd cycles in locally dense graphs