On the maximum size of $(a,b)$-town (mod $k$) families

Abstract

For integers $n\ge k\ge 2$ and $0\le a,b\le k-1$, let $m_{k,n}(a,b)$ denote the maximum size of an $(a,b)$-town (mod $k$) family of an $n$-element set, a collection of subsets of whose cardinalities are congruent to $a$ modulo $k$ and whose pairwise intersections are congruent to $b$ modulo $k$. This notion generalizes the classical Oddtown and Eventown problems. We prove that $m_{k,n}(a,b)\le n$ whenever $a\not\equiv b(\mathrm{mod}k)$, thereby resolving a conjecture of Veselinov and Marinov. We also disprove another conjecture of theirs by showing that $m_{3,11}(2,2)>m_{3,11}(1,1)$. For the diagonal case $a\equiv b(\mathrm{mod}k)$, we establish the general bound $m_{k,n}(a,a)\le 2^{\lfloor n/2\rfloor }$ and completely determine when equality holds. We further obtain improved bounds and exact values in several special cases. The proofs combine characteristic-zero linear algebra with methods from coding theory and finite geometry.

22 pages