Counting odd cycles in locally dense graphs

详细信息    查看全文

• 作者：Christian Reiher ^{Christian.Reiher@uni-hamburg.de" class="auth_mail}
• 关键词：Graph homomorphisms ; (蔚 ; d)(蔚 ; d)-Dense graphs ; Odd cycles ; Sidorenko's conjecture
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：March, 2014
• 年：2014
• 卷：105
• 期：Complete
• 页码：1-5
• 全文大小：204 K

文摘

We prove that for any given and , every sufficiently large -dense graph G contains for each odd integer r at least cycles of length r. Here, being -dense means that every set X containing at least vertices spans at least edges, and what we really count is the number of homomorphisms from an r-cycle into G.

The result addresses a question of Y. Kohayakawa, B. Nagle, V. R枚dl, and M. Schacht.