Catalan classification conjecture for extremal even-intersecting lattice-path families

Let $B_m(x,y)\in\mathbb F_2$ denote the parity of the number of common edges of the two $m$-step paths encoded by $x,y\in\{0,1\}^m$. The basic recurrence is

$$B_m(p\alpha,q\beta) = B_{m-1}(p,q) + \mathbf 1_{\alpha=\beta}\mathbf 1_{\mathrm{wt}(p)=\mathrm{wt}(q)}.$$

The proof proceeds by determining the equality cases in the quadratic inequality underlying Shankar's Lemma 2.3.

For a Dyck prefix $P$, let $\mathcal E(P)$ be its noncrossing partial matching. If $u_1<\cdots<u_r$ are the unmatched positions, define $\mathcal A_\varepsilon(P)$ to be the set of binary words whose bits are opposite on every edge of $\mathcal E(P)$, with the unmatched bits prescribed by $\varepsilon\in\{0,1\}^r$.

Deleting all matched coordinates preserves the parity kernel:

$$B_m(x,y)=B_r(\bar x,\bar y).$$

The main structural result is the following equality classification. Under the hypotheses of Shankar's quadratic lemma,

$$\sum_i |A_i|^2=2^m$$

holds if and only if, up to reordering,

$$\{A_i\} = \{\mathcal A_\varepsilon(P):\varepsilon\in\{0,1\}^r\}$$

for a unique Dyck prefix $P$.

Two rigidity statements enter the proof.

First, if two Dyck-prefix partitions are cross-compatible for $B_m$, then their noncrossing partial matchings coincide, and hence the Dyck prefixes are equal.

Second, the local reconstruction problem reduces to classifying adjacent-weight pairs $u,v$ for which

$$\Delta_{u,v}(z) = B(u,z)+B(v,z)$$

vanishes outside the two adjacent Hamming layers. Apart from the canonical pairs

$$u=t1,\qquad v=t0,$$

there is one alternating exceptional pair in odd dimension. A finite-state induction gives the complete classification. The exceptional pair is incompatible with the global cross-constancy conditions, so the reconstruction has only the two Dyck extensions $PU$ and $PD$.

For the original lattice-path problem, Shankar's left/right decomposition identifies a path $F$ with an equal-weight pair

$$(u(F),v(F)) \in \{0,1\}^n\times\{0,1\}^n.$$

Thus an extremal family of size $2^n$ gives an admissible relation $R$ of size $2^n$. Equality throughout the componentwise Cauchy-Schwarz argument forces both sides of $R$ to be Dyck-prefix equality partitions.

The components therefore induce a bijection

$$\phi:\{0,1\}^r\to\{0,1\}^r$$

that preserves Hamming weight and the parity kernel:

$$B_r(\phi(x),\phi(y))=B_r(x,y).$$

A rigidity argument on the Boolean cube shows that every such bijection is the identity. Consequently,

$$R= \bigcup_{\varepsilon\in\{0,1\}^r} \mathcal A_\varepsilon(P) \times \mathcal A_\varepsilon(Q).$$

Reflect the matching of $Q$ into the second half of the path and join corresponding unmatched positions. This produces a noncrossing perfect matching $M$ of $[2n]$. The original extremal family is exactly

$$\mathcal F_M.$$

The matching is unique. Indeed,

$$\{i,j\}\in M$$

if and only if every word in $\mathcal F_M$ has opposite bits in positions $i$ and $j$. If $i,j$ belong to different matching edges, those edges can be oriented independently so that the two bits agree.

Therefore every extremal even-intersecting family arises from a unique noncrossing perfect matching of $[2n]$. Since such matchings are counted by the Catalan number,

$$C_n=\frac{1}{n+1}\binom{2n}{n},$$

there are exactly $C_n$ extremal families.

The complete proof, including the equality classification, localized-pair finite-state argument, cross-rigidity lemma, reconstruction theorem, and Boolean-cube rigidity argument, is contained in the attached manuscript.

The LaTeX source and finite verification code are available at:

https://github.com/FDmd233/catalan-lattice-path-classification

The finite computations are auxiliary checks and are not used in place of the theoretical proof.

AI assistance disclosure: OpenAI GPT-5.6 Sol was used during the investigation, proof checking, drafting, and preparation of the manuscript.