Journal of Combinatorics
Volume 4 (2013)
A Sidon-type condition on set systems
Pages: 449 – 456
Consider families of $k$-subsets (or blocks) on a ground set of size $v$. Recall that if all t-subsets occur with the same frequency $\lambda$, one obtains a $t$-design with index $\lambda$. On the other hand, if all $t$-subsets occur with different frequencies, such a family has been called (by Sarvate and others) a $t-a$ design. An elementary observation shows that such families always exist for $v \gt k \geq t$. Here, we study the smallest possible maximum frequency $\mu = \mu (t, k, v)$. The exact value of $\mu$ is noted for $t = 1$ and an upper bound (best possible up to a constant multiple) is obtained for $t = 2$ using PBD closure. Weaker, yet still reasonable, asymptotic bounds on $\mu$ for higher $t$ follow from a probabilistic argument. Some connections are made with the famous Sidon problem of additive number theory.
Published 27 December 2013