The maximum number of 10- and 12-cycles in a planar graph

DOI10.1016/J.DISC.2022.113245zbMATH Open1504.05139arXiv2106.02966OpenAlexW3167937992MaRDI QIDQ2099482FDOQ2099482

Authors: Yanyan Li 

Publication date: 23 November 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: For a fixed planar graph $H$, let $operatorname{mathbfN}_{mathcalP}(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. In the case when $H$ is a cycle, the asymptotic value of $operatorname{mathbfN}_{mathcalP}(n,C_m)$ is currently known for $min3,4,5,6,8$. In this note, we extend this list by establishing $operatorname{mathbfN}_{mathcalP}(n,C_{10})sim(n/5{)}^5$ and $operatorname{mathbfN}_{mathcalP}(n,C_{12})sim(n/6{)}^6$. We prove this by answering the following question for $min5,6$, which is interesting in its own right: which probability mass $mu$ on the edges of some clique maximizes the probability that $m$ independent samples from $mu$ form an $m$-cycle?

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

Recommendations

• Discrete Morse theory for the moduli spaces of polygonal linkages, or solitaire on a circle
• Homology of planar polygon spaces
• A perfect Morse function on planar polygon spaces
• A perfect Morse function on planar polygon spaces modulo isometry group
• On the Moduli Space of a Spherical Polygonal Linkage

zbMATH Keywords

maximum likelihood estimatorsplanar graphsgeneralized Turán problems

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Cites Work

• On the number of cycles of lengthk in a maximal planar graph
• The maximum number of paths of length four in a planar graph
• Title not available (Why is that?)
• The maximum number of paths of length three in a planar graph
• Counting paths, cycles, and blow‐ups in planar graphs

Cited In (7)

• A perfect Morse function on planar polygon spaces
• Title not available (Why is that?)
• The maximum number of copies of an even cycle in a planar graph
• Discrete Morse theory for the moduli spaces of polygonal linkages, or solitaire on a circle
• Planar graphs with the maximum number of induced 6-cycles
• A perfect Morse function on planar polygon spaces modulo isometry group
• The maximum number of pentagons in a planar graph

This page was built for publication: The maximum number of 10- and 12-cycles in a planar graph

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