A Sidon-type condition on set systems

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

l a m b d a

, one obtains a

t

-design with index

l a m b d a

. On the other hand, if all

t

-subsets occur with different frequencies, such a family has been called (by Sarvate and others) a

t

-adesign. An elementary observation shows that such families always exist for

v > k g e t

. Here, we study the smallest possible maximum frequency

m u = m u (t, k, v)

. The exact value of

m u

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

m u

for higher

t

follow from a probabilistic argument. Some connections are made with the famous Sidon problem of additive number theory.

Recommendations

Cited In (1)

This page was built for publication: A Sidon-type condition on set systems