pith. sign in

arxiv: 1604.06833 · v1 · pith:I6US5HG2new · submitted 2016-04-22 · 🧮 math.CO

Counting odd cycles in locally dense graphs

classification 🧮 math.CO
keywords varepsilondenseleastcycleseveryadressescontainingcontains
0
0 comments X
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.