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

DOI10.1016/J.DISC.2022.113245MaRDI QIDQ2099482zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 23 November 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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?

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

Cites work

• scientific article; zbMATH DE number 3902677 (Why is no real title available?)
• Counting paths, cycles, and blow‐ups in planar graphs
• On the number of cycles of lengthk in a maximal planar graph
• The maximum number of paths of length four in a planar graph
• The maximum number of paths of length three in a planar graph

Cited in

(7)

• The maximum number of copies of an even cycle in a planar graph
• A perfect Morse function on planar polygon spaces modulo isometry group
• scientific article; zbMATH DE number 1536529 (Why is no real title available?)
• The maximum number of pentagons 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

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)