An Eventown Result for Multisets

Source abstract

We study an extension of the Eventown problem of sets to multisets on $[n] = \{1,2,...,n\}$. A multiset is called $m$-bounded if each element has multiplicity at most $m$. The intersection of two multisets is defined as the multiset in which each element has multiplicity equal to the minimum of its multiplicities in the two original multisets. A family of $m$-bounded multisets is called an Eventown family if every member and the intersection of every pair of distinct members has even cardinality, with cardinalities counted with multiplicities. We determine the maximum size $E_m(n)$ of such a family for every $m$ and $n$. We show that $E_{2q}(n)=(q+1)^n,$ and $E_{2q+1}(n)=(q+1)^{n-2k}\bigl((q+1)^2+1\bigr)^k,$ where $k=\lfloor n/2\rfloor$. In particular, the case $m=1$ recovers the classical Eventown theorem for sets. We also characterize all extremal families for $m\ge2$. For even $m$, the unique extremal family consists of all multisets in which every element has even multiplicity. For odd $m\ge3$, every extremal family has a product structure arising from two explicit families on pairs of coordinates, together with an additional coordinate restricted to even multiplicities when $n$ is odd. Consequently, there are exactly $k+1$ extremal types up to permutations of the ground set.