HEXAGONbeta

Even-intersecting families of lattice paths and the Catalan numbers

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Deep Bhattacharjee ↗

Version 1 / Oct 22, 2026 / CC BY 4.0

Abstract

Shankar proved that a family of North--East lattice paths from (0,0)(0,0) to (n,n)(n,n) in which any two paths share an even number of edges has at most 2n2^n members, and conjectured that exactly CnC_n families attain this bound, where CnC_n is the nnth Catalan number. We prove the conjecture. The proof determines all equality cases of the inequality behind Shankar's bound: they correspond to noncrossing partial matchings of {1,…,m}\{1,\dots,m\} whose unmatched points lie under no arc, and there are (m⌊m/2⌋)\binom{m}{\lfloor m/2\rfloor} of them.

Provenance statement

Deep Bhattacharjee chose the problem, Conjecture 4.1 of Shankar (arXiv:2607.23117), and directed the work. Claude (Anthropic), working through Claude Code, searched the literature, found and checked the proofs, wrote the verification programs and drafted the paper. The proof is complete by hand. It determines the equality cases of Shankar's inequality (his Lemma 2.3) as the skeleton systems, given by noncrossing partial matchings whose unmatched points lie under no arc; there are C(m, floor(m/2)) of them, and for m = 2n those without free points give exactly the C_n families F_M. Programs in C, C++, Python (SAT), Julia and Bash check the lemmas and theorems on all small cases. These include Shankar's conjecture for n ≤ 5 and all extremal systems of length up to 6. Lean 4 kernel checks cover the key lemmas and the conjecture for n ≤ 3. Code and proofs: release v1.1.0, https://github.com/creelie/eConjecturePrimitiveTrinomial/releases/tag/v1.1.0.
AI provenance filesAI-PROVENANCE-HEXAGON.md · 2 KB

Tools used

Anthropic
Claude CodeVersion Opus 5.5 Ultracode

References

  1. E. R. Berlekamp, On subsets with intersections of even cardinality , Canad. Math. Bull. 12 (1969), 471--474. 10.4153/CMB-1969-059-3DOI
  2. J. E. Graver, Boolean designs and self-dual matroids , Linear Algebra Appl. 10 (1975), 111--128. 10.1016/0024-3795(75)90003-8DOI
  3. U. Shankar, Oddtown and eventown theorems for lattice paths , preprint, 2026. arXiv:2607.23117 (https://arxiv.org/abs/2607.23117)arXiv
  4. R. P. Stanley, Catalan Numbers , Cambridge University Press, Cambridge, 2015. 10.1017/CBO9781139871495DOI

Version history

  1. v1Submitted by Deep BhattacharjeeInitial depositCurrentOct 22, 2026