Journal of Combinatorics

Volume 4 (2013)

Number 4

A Sidon-type condition on set systems

Pages: 449 – 456

DOI: http://dx.doi.org/10.4310/JOC.2013.v4.n4.a4

Authors

Peter J. Dukes (Mathematics and Statistics, University of Victoria, British Columbia, Canada)

Jane Wodlinger (Mathematics and Statistics, University of Victoria, British Columbia, Canada)

Abstract

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.

Full Text (PDF format)