Skip to content
DraconiticResearch
Search Sources API
194,216 studies31 sourcesUpdated 18 min ago
PreprintarXiv licencearXiv

A sharp asymptotic bound for odd cycles in planar graphs

  • Zhen Liu
  • Chuanshu Wu
Open at sourcePDFDOICite

Abstract

For graphs G and H, let N(G,H) denote the number of unlabeled, not necessarily induced copies of H in G, and let N𝒫(n,H) be the maximum of N(G,H) over all n-vertex planar graphs G. We prove that, for every fixed integer m≥ 3, N𝒫(n,C2m+1)=2m(n/m)m+Om (nm−1/5). The proof uses a sharp weighted cycle--path inequality for edge probability measures on finite complete graphs. This strengthens a conjecture of Heath, Martin, and Wells and, together with their reduction lemma, yields the stated asymptotic formula.

Related

  1. Total-coloring of planar graphs with maximum degree 6 and without prescribed 4-cycles
    Enqiang Zhu, Yangyang Zhou, Jin Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. A Sharp Distributional Lower Bound for Planar Discrepancy
    Aicke Hinrichs
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  3. A Sharp Bound of Crossing Limit Cycle for Planar piecewise linear Systems with a Straight Switching Line
    Zijie Xu, Jiang Yu
    arXivPreprintarXiv licenceFull textAnalysis & PDEsDynamical systemsarXiv
  4. An improved bound for the intersection of two longest cycles in k-connected graphs
    Juan Gutiérrez
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. An improved bound on the treewidth of planar graphs excluding a grid minor
    Wouter Cames van Batenburg, Quentin Claus, Gwenaël Joret +3
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{liu2026sharp,
  title = {{A sharp asymptotic bound for odd cycles in planar graphs}},
  author = {Zhen Liu and Chuanshu Wu},
  howpublished = {arXiv},
  year = {2026},
  month = aug,
  doi = {10.48550/arxiv.2608.13162},
  eprint = {2608.13162},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.13162},
}
RIS
TY  - UNPB
TI  - A sharp asymptotic bound for odd cycles in planar graphs
AU  - Zhen Liu
AU  - Chuanshu Wu
PY  - 2026
DA  - 2026/08/30
PB  - arXiv
DO  - 10.48550/arxiv.2608.13162
UR  - https://arxiv.org/abs/2608.13162
AB  - For graphs G and H, let N(G,H) denote the number of unlabeled, not necessarily induced copies of H in G, and let N_𝒫(n,H) be the maximum of N(G,H) over all n-vertex planar graphs G. We prove that, for every fixed integer m≥ 3, N_𝒫(n,C_2m+1)=2m(n/m)^m+O_m (n^m−1/5). The proof uses a sharp weighted cycle--path inequality for edge probability measures on finite complete graphs. This strengthens a conjecture of Heath, Martin, and Wells and, together with their reduction lemma, yields the stated asymptotic formula.
ER  -