Oddtown and eventown theorems for lattice paths

Abstract

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 $2^n$, and that this bound is attained. If $M_{\mathrm{odd}}(n)$ denotes the maximum size of a family in which every two distinct paths have an odd number of common edges, then we prove \[ M_{\mathrm{odd}}(n)\le n(n-1)+1 \] and construct families showing that $M_{\mathrm{odd}}(n)=\hat{I}˜(n^2)$. Finally, we construct at least $C_n$ distinct extremal even-intersecting families, where $C_n$ is the $n$th Catalan number, and conjecture that these are all the extremal families.

Comments are welcome