Counting odd cycles in locally dense graphs
classification
🧮 math.CO
keywords
varepsilondenseleastcycleseveryadressescontainingcontains
read the original abstract
We prove that for any given $\varepsilon>0$ and $d\in [0,1]$, every sufficiently large $(\varepsilon, d)$-dense graph $G$ contains for each odd integer $r$ at least $(d^r-\varepsilon)|V(G)|^r$ cycles of length $r$. Here, $G$ being $(\varepsilon, d)$-dense means that every set $X$ containing at least~$\varepsilon\,|V(G)|$ vertices spans at least $\tfrac d2\, |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.
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.