Noncrossing matchings with no parallel edges

We will see that, in a way, the two examples drawn in the original post and in the answer by David E Speyer (a variation, more exactly) already generate solutions for every $p ≥ 31$.

Disclaimer: GPT-Sol 5.6 (high effort with 40 minutes of thinking) found a construction and I took the time to understand it in a "human" and more visual way to give the explanation below (see the Lemma). It is different from the other solution posted by Ákos Dúcz, even though it uses the same few basic pieces and is also of nesting depth at most $2$ (by chance). Primality of $p$ plays no role.

A Dyck word is a well-parenthesized expression consisting only of parentheses. Dyck words of length $2n$ correspond to ways of pairing up $2n$ equally spaced points on a circle without intersection of the connecting lines. Let's say that a Dyck word is parallel-free if the corresponding pairing contains no parallel segments.

The main lemma tells us how to compose parallel-free Dyck words:

Lemma. Let $A$ be a parallel-free Dyck word. If $XAY$ and $X'AY'$ are parallel-free Dyck words such that $|X|=|Y|$ and $|X'|=|Y'|$, then $(XX')A(YY')$ is also a parallel-free Dyck wod.

Proof. Let $W$ be a Dyck word of length $2n$, for instance the one represented below (we think of it as a set of chords on an arc of a circle).

Every chord is parallel to exactly one "unit" chord joining a point and the next point. Let's displace each chord to its representative "unit" chord:

We say that $W$ is quasi-parallel-free if this process does not collapse two chords. When it is the case, we obtain a binary word $S(W)$ with $n$ ones (the spaces in red in the drawing above) and $n$ zeros (in grey, including the space after the last point). Let $\overline{S(W)}$ be the complementary word and let $t(S(W))$ be the cyclic translation of $S(W)$ by $n$ steps ($t$ is defined on binary words of even length in general). Then $W$ is parallel-free if and only if it is quasi-parallel-free and $t(S(W)) = \overline{S(W)}$. This is seen as follows: if $W$ is represented on a circle instead of an arc of a circle, we may collapse every chord onto two diammetrally opposite unitary chords, without changing its direction. We collapse each chord to one of these two chords, arbitrarily, and we suppose there is no collision. The extra condition for $W$ to be parallel-free is that there must be no collision either when rotating the figure by half a turn.

Note also that every factor of a parallel-free Dyck word is quasi-parallel-free.

Let $A$, $X$, $Y$, $X'$, $Y'$ be as in the statement of the Lemma. We set $a = S(A)$, $x = S(X)$, etc. We have $t(a) = \overline{a}$, $t(xay) = \overline{xay}$ and $t(x'ay') = \overline{x'ay'}$. We must show that $t(xx'ayy') = \overline{xx'ayy'}$. The first condition means that $a$ is of the form $b\overline{b}$. The second condition means that $xb = b \overline{y}$ and the third means that $x'b = b \overline{y'}$. Thus we have $xx'b = xb\overline{y'} = b\overline{yy'}$, i.e., $t(xx'ayy') = \overline{xx'ayy'}$. (One can try to visualize on a drawing what it does, but it is quite clean in algebraic form.) $\Box$

The second step is to find by computational search enough nontrivial parallel-free Dyck words of the form of the lemma and sharing the same middle $A$. Here are four such words with $|A| = 2×7$ and $|X| = |Y| = 2×6,\ 2×7,\ 2×8,\ 2×17$. They can be used to generate parallel-free Dyck words of every length $≥ 2×31$. In fact already since $6$ and $7$ are coprime, the first two can be used to generate every parallel-free Dyck word of length $≥2×67$.

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$.