Small mod-two area cycles in drawings with bounded pairwise intersections
Fix an integer $k \ge 2$. For $n \ge 3$ consider drawings of the complete graph $K_n$ inside the unit square: the vertices are distinct points, each edge is a non-self-intersecting piecewise smooth arc joining its endpoints and avoiding the other vertices, interior intersections of edges are transverse crossings, and any two distinct edges have at most $k$ points in common, a shared endpoint included. A nonzero $\mathbb{F}_2$-cycle is a nonempty set $z$ of edges in which every vertex has even degree; it may be disconnected. Let $A(z)$ be the area of its mod-two interior, the set of points from which a generic path to the unbounded component of the complement of $z$ crosses $z$ an odd number of times; the drawing of $z$ may cross itself. Hubard and Suk constructed drawings of $K_n$ in the unit square, with no bound on the number of meetings of two edges, in which every nonzero $\mathbb{F}_2$-cycle has mod-two interior of area at least $1/4$. For simple drawings, in which two edges meet at most once, at a common endpoint or a proper crossing, Zeng proved that some non-self-intersecting $4$-cycle encloses a face of area $O(1/n)$, improving the bound $O(n^{-1/3})$ of Hubard and Suk.
Problem. Does there exist a function $\varepsilon_k(n)$ with $\varepsilon_k(n) \to 0$ as $n \to \infty$ such that every such drawing of $K_n$ contains a nonzero $\mathbb{F}_2$-cycle $z$ with $A(z) \le \varepsilon_k(n)$? The bound must be uniform over drawings, with $k$ fixed.
Source: Hubard and Suk (2025), Problem 5.1 (Problem 5.4 in arXiv:2212.01311v1), for drawings in which every pair of edges meets a constant number of times. Stated by AIM — Open Applied Problems for nonzero F_2-cycles and a fixed bound k ≥ 2.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- AIM Open Applied Problems, Heilbronn problems, mod-two cycles, topological graphs
References
@article{hubard2025,
author = {Hubard, Alfredo and Suk, Andrew},
title = {Disjoint Faces in Drawings of the Complete Graph and Topological {H}eilbronn Problems},
journal = {Discrete Comput. Geom.},
volume = {74},
number = {4},
year = {2025},
pages = {899--916},
doi = {10.1007/s00454-025-00721-w},
eprint = {2212.01311},
archivePrefix = {arXiv},
}
@article{zeng2025,
author = {Zeng, Ji},
title = {Note on disjoint faces in simple topological graphs},
journal = {J. Combin. Theory Ser. B},
volume = {171},
year = {2025},
pages = {28--35},
doi = {10.1016/j.jctb.2024.11.002},
eprint = {2308.04742},
archivePrefix = {arXiv},
}
@misc{aim-bounded-crossing-heilbronn,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Small mod-two area cycles in drawings with bounded pairwise intersections}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/635-bounded-crossing-heilbronn.md},
note = {Entry 635 at commit 24edaad, 2026-10-15},
}
Resolution claims
Fix a bound on the number of meetings between any two edges of a complete graph drawn in the unit square. We prove that, as the number of vertices tends to infinity, some nonzero mod-two cycle has area tending to zero, uniformly over all such drawings. For at least four vertices the cycle can be chosen to be an abstract …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-18 | Needs verification → Solution claimed | — | Recorded here: AIM @ 24edaad, paper/main.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00781, "Small mod-two area cycles in drawings with bounded pairwise intersections", clopen.solutions.