2026/07/25 by Umesh Shankar
Mathematics · #math.CO
For North-East lattice paths (which we simply call lattice paths), we define intersection in terms of common edges. We prove that a family of paths from (0,0) to (n,n) in which every two distinct paths have an even number of common edges has size at most 2n, and that this bound is attained. If Modd(n) denotes the maximum size of a family in which every two distinct paths have an odd number of common edges, then we prove Modd(n)≤ n(n-1)+1 and construct families showing that Modd(n)=Θ(n2). Finally, we construct at least Cn distinct extremal even-intersecting families, where Cn is the nth Catalan number, and conjecture that these are all the extremal families.