Paperlane

no. 16 · Tuesday 17 November 2026

Existence of alternating Hamiltonian paths on specific bicolored point sets

Jan Soukup

math.CO · 10 pp

Abstract

Consider a bicolored point set $P$ in general position in the plane consisting of $n$ blue and $n$ red points. We show that if $P$ can be partitioned into bicolored pairs $(a_i,b_i)$ such that, for every $i$, $a_i$ and $b_i$ have different colors and the sets $P\setminus \{a_i\}$ and $P \setminus \{b_i\}$ have the same order type, then there exists a noncrossing alternating Hamiltonian path on $P$. We also investigate the case when $P$ lies on the circle, and every interval along the circle contains at most $c$ more points of one color than of the other. For $c=2$, we show that there exists a noncrossing alternating Hamiltonian path on $P$. For $c=3$, we show that there exist configurations of points for which the longest noncrossing alternating path on $P$ has size at most $(2-1/25)n + O(1)$.

comments
10 pages, 5 figures
fields
Combinatorics
pdf ↗ page arXiv:2611.19433 ↗