Counting odd cycles in locally dense graphs

DOI10.1016/J.JCTB.2013.12.002zbMATH Open1300.05132arXiv1604.06833OpenAlexW3121868313MaRDI QIDQ401486FDOQ401486

Authors: Christian Reiher 

Publication date: 27 August 2014

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: We prove that for any given $varepsilon>0$ and $din[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 $fracd2,|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.

Full work available at URL: https://arxiv.org/abs/1604.06833

Recommendations

• Tools for counting odd cycles in graphs
• On the local density problem for graphs of given odd-girth
• On the local density problem for graphs of given odd-girth
• scientific article; zbMATH DE number 3931048
• On the local distinguishing numbers of cycles
• Even cycles in graphs with many odd cycles
• Counting cycles in graphs with small excess
• Approximately counting paths and cycles in a graph
• scientific article; zbMATH DE number 1003265
• scientific article; zbMATH DE number 867704

zbMATH Keywords

graph homomorphismsodd cycles\((\varepsilon, d)\)-dense graphsSidorenko's conjecture

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Enumeration in graph theory (05C30) Paths and cycles (05C38) Density (toughness, etc.) (05C42)

Cites Work

• Weak hypergraph regularity and linear hypergraphs
• A Holder Type Inequality for Symmetric Matrices with Nonnegative Entries
• A correlation inequality for bipartite graphs
• Title not available (Why is that?)

Cited In (6)

• Inequalities for doubly nonnegative functions
• On some graph densities in locally dense graphs
• Tools for counting odd cycles in graphs
• On the local density problem for graphs of given odd-girth
• Embedding spanning subgraphs in uniformly dense and inseparable graphs
• Linear configurations containing 4-term arithmetic progressions are uncommon

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q401486)