Edit - MathOverflow

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Rev

Required fields*

Noncrossing matchings with no parallel edges

Place $2p$ equally spaced points on a circle, where $p$ is an odd prime. Let $a_p$ be the number of ways to join them in pairs by straight line segments such that

no two segments cross, and
no two segments are parallel.

There are always two such matchings, obtained by pairing adjacent points alternately.

Question. Is $a_p>2$ for every sufficiently large prime $p$?

—-

I ran numerical simulations up to p=47. $$ \begin{array}{c|r||c|r} \underline{p} & \underline{a_p} & \underline{p} & \underline{a_p} \\ 3 & 2 & 23 & 140 \\ 5 & 2 & 29 & 2 \\ 7 & 2 & 31 & 64 \\ 11 & 2 & 37 & 1778 \\ 13 & 2 & 41 & 1314 \\ 17 & 2 & 43 & 2496 \\ 19 & 40 & 47 & 6300 \end{array} $$

Here is a nontrivial example for $n = 19$.

Answer*

First some terminology:
Lets call a chord connecting two adjacent vertices a boundary chords. A non-boundary chord then defines a kind of "corner", which can be nested. The image in the question has three top-level corners, two of which are nested. (This is not a rigorous definition)

I plotted a few simple solutions for small primes and found that depth-2 nested corners seemed to be enough most of the time. I asked chatGPT to find a construction with at most depth-2 corners, and it gave the following construction:

I will describe the construction using a simple encoding of the slopes.

### 1. Encoding the slopes

Label the vertices of the regular $2p$-gon by
$$
0,1,\ldots,2p-1.
$$
In a noncrossing perfect matching, every edge joins an even vertex to an odd vertex. For an edge $\{i,j\}$, define
$$
s(i,j)=\frac{i+j-1}{2}\pmod p.
$$
Two edges are parallel exactly when they have the same value of $s$. Thus we want the $p$ edges to have the $p$ different slopes
$$
0,1,\ldots,p-1.
$$
Suppose now that we construct the matching out of consecutive blocks. For one block, number its vertices locally by $0,1,\ldots,2q-1$. Make a binary word of length $2q$, putting a $1$ in position
$$
\frac{i+j-1}{2}
$$
for every edge $\{i,j\}$ in the block.

For example, the ordinary six-vertex corner
$$
(0,5),(1,2),(3,4)
$$
has slope positions $2,1,3$, and hence word
$$
011100.
$$
If blocks are put consecutively around the polygon, their binary words are simply concatenated. This is because translating both endpoints of an edge by $r$ translates its slope index by $r$.

So a complete matching gives a binary word
$$
Y=Y_0Y_1\cdots Y_{2p-1}
$$
with $p$ ones.

Positions $i$ and $i+p$ represent the same slope modulo $p$. Therefore the matching has no two parallel edges iff exactly one of these two positions is $1$, i.e.
$$
Y_{i+p}=1-Y_i.
$$
Equivalently,
$$
\boxed{Y=X\overline X}
$$
for some binary word $X$ of length $p$, where $\overline X$ denotes bitwise complement.

Thus the geometric problem has become a word-concatenation problem.

### 2. Seven small depth-two blocks

Write
$$
T(q;r_1,\ldots,r_m)
$$
for the following block on $2q$ vertices. Join the first vertex to the last one, and partition the vertices inside this chord consecutively into blocks of sizes
$$
2r_1,\ldots,2r_m.
$$
We only use $r_i=1$ or $3$:

* $r_i=1$ means one boundary edge;
* $r_i=3$ means an ordinary six-vertex corner.

Thus all of these blocks have depth at most $2$.

We need the following seven blocks:
$$
\begin{array}{c|c|c}
\text{name}&\text{block}&\text{slope word}\\ \hline
E&\text{one boundary edge}&10\\
A&T(6;1,1,3)&010101111000\\
B&T(6;3,1,1)&001111010100\\
P&T(7;1,1,1,1,1,1)&01010111010100\\
U&T(7;1,1,1,3)&01010110111000\\
V&T(7;3,1,1,1)&00111011010100\\
D&T(7;3,3)&00111010111000.
\end{array}
$$
For example, $A$ consists of an outer chord on $12$ vertices, with two boundary pairs and then a six-vertex corner inside it.

### 3. Four infinite families

Now concatenate these blocks as follows:

$$
\begin{array}{c|l}
p&\text{blocks}\\ \hline
31+12k&A^{k+1}PB^{k+2}A\\[1mm]
47+12k&A^{k+2}UE^2B^{k+3}ED\\[1mm]
53+12k&A^{k+1}UE^2DE^2B^{k+2}EDE^2D\\[1mm]
61+12k&A^{k+3}E^2VEB^{k+3}DEU .
\end{array}
\label{1}
\tag{1}
$$
Here $k\ge 0$.

The total lengths are respectively
$$
2(31+12k),\quad
2(47+12k),\quad
2(53+12k),\quad
2(61+12k),
$$
so these really are matchings on $2p$ vertices.

Substituting the short binary words above into \eqref{1}, the resulting word is of the form $X\overline X$. Explicitly, if
$$
a=010101111000,
$$
the first halves are
$$
\begin{aligned}
X_{31+12k}
 &=a^{k+1}0101011101010000111,\\
X_{47+12k}
 &=a^{k+2}01010110111000101000111,\\
X_{53+12k}
 &=a^{k+1}01010110111000101000111010111000101000111,\\
X_{61+12k}
 &=a^{k+3}1010001110110101001000111.
\end{aligned}
$$
Hence every slope occurs exactly once.

There is also a simple reason that the construction can be extended by $12$ indefinitely. Put
$$
u=00111,\qquad v=1010100.
$$
Then
$$
B=uv,\qquad \overline A=vu.
$$
Consequently
$$
vB^m=(\overline A)^m v,
$$
which is the word identity behind the $A/B$ repetitions in \eqref{1}. The remaining parts are fixed finite words.

### 4. The two exceptional starting primes

The four progressions in \eqref{1} cover the four possible residue classes of primes modulo $12$, but the $1$ and $5$ classes start a little late. The missing primes are $37$ and $41$.

They have the depth-two constructions
$$
p=37:\qquad AE^2VE BDEU,
$$
and
$$
p=41:\qquad UE^2DE^2BED E^2D.
$$
Again, direct substitution gives a word $X\overline X$.

For instance, for $p=31$ the first family simply gives
$$
APBBA,
$$
which has nine non-boundary chords.

### 5. Conclusion

Every prime $p>3$ is congruent to
$$
1,5,7,\text{ or }11\pmod{12}.
$$
The four infinite families above start at
$$
61,\quad53,\quad31,\quad47
$$
in these four residue classes, respectively, and $37,41$ are handled separately.

Therefore
$$
\boxed{\text{for every prime }p\ge31
\text{ there is a noncrossing perfect matching with no parallel edges}}
$$
and moreover the matching can always be chosen to have corner-depth at most $2$.

So nesting is necessary for prime $p$, but **one level of nesting already suffices for every prime $p\ge31$**.

Required fields are marked with *

Edit Summary*

Cancel

1

$\begingroup$ Did you use an AI/LLM to write this? $\endgroup$

Sam Hopkins
– Sam Hopkins ♦

2026-08-26 13:26:42 +00:00
Commented 18 hours ago
$\begingroup$ Yes, is that OK? $\endgroup$

Ákos Dúcz
– Ákos Dúcz

2026-08-26 13:37:27 +00:00
Commented 17 hours ago
6

$\begingroup$ Not if it is raw LLM output which you have not taken the time to digest, understand, and present in a coherent way, no. $\endgroup$

Sam Hopkins
– Sam Hopkins ♦

2026-08-26 13:38:46 +00:00
Commented 17 hours ago
4

$\begingroup$ Okay, I've checked the $p = 12 j + 7$ case (note that my $j$ is Akos's $k+2$). It's a little prettier to write it as $A^j P B^j$. The resulting word is $(\bar{v} \bar{u})^j (\bar{v} v) (uv)^j = \bar{v} \bar{u} \bar{v} \cdots \bar{v} \bar{u} \bar{v} v u v \cdots v u v$ with $u=00111$ and $v=1010100$, which is clearly the bit complement of its shift. $\endgroup$

David E Speyer
– David E Speyer

2026-08-26 14:43:52 +00:00
Commented 16 hours ago
6

$\begingroup$ I put up a meta question about this meta.mathoverflow.net/questions/6531/… . $\endgroup$

David E Speyer
– David E Speyer

2026-08-26 15:03:44 +00:00
Commented 16 hours ago

| Show 1 more comment

Correct minor typos or mistakes
Clarify meaning without changing it
Add related resources or links
Always respect the author’s intent
Don’t use edits to reply to the author

create code fences with backticks ` or tildes ~
```
like so
```
add language identifier to highlight code
```python
def function(foo):
print(foo)
```
put returns between paragraphs
for linebreak add 2 spaces at end
_italic_ or **bold**
quote by placing > at start of line
to make links (use https whenever possible)

<https://example.com>

[example](https://example.com)

<a href="https://example.com">example</a>
MathJax equations $\sin^2 \theta$

formatting help »
answering help »

MathJax help »