2
$\begingroup$

Consider a design $(X,\mathcal{B})$, satisfying:

  1. Each block in $\mathcal{B}$ has the same size

  2. The intersection of every two blocks has the same size

Of course, it is easy to find many examples of such design. For instance, each symmetric balanced incomplete block design (BIBD) satisfies the above two conditions.

I am interested in the following question:

Given the number of points and the size of blocks, find the maximum number of blocks and construct the design achieving this maximum number.

I tried my best to check the 'Handbook of Combinatorial Designs' and found nothing. I am not sure if this kind of design has been studied before.

Thank you in advance!

$\endgroup$
4
  • $\begingroup$ Sunflowers are another example. Your optimal example is likely a union of isomorphic sunflowers. I do not know if they have been studied other than in the context of delta systems in infinitary combinatorics. Kunen's book Set Theory has info on the infinite version. Gerhard "Maybe That Is Too Big" Paseman, 2017.05.11. $\endgroup$ May 11, 2017 at 21:45
  • $\begingroup$ Your design does not seem to have any "balance" condition such as each pair of points lies in a constant number of blocks. So this moves you out of design theory in the direction of intersecting set systems and Erdos-Ko-Rado style results. For example if your constant intersection size is 1, then take all k-sets on a fixed point as the blocks. $\endgroup$ May 11, 2017 at 22:43
  • $\begingroup$ He does ask about a maximality, so this may imply some degree of regularity. Projective Plane perhaps? Gerhard "I'm Thinking Of Overlapping Sunflowers" Paseman, 2017.05.11. $\endgroup$ May 11, 2017 at 22:50
  • $\begingroup$ Thank you all. I realized the design I am interested in has been studied in a more general setting named intersecting families in extremal set theory. $\endgroup$
    – smart cat
    May 12, 2017 at 21:46

1 Answer 1

1
$\begingroup$

Under your hypotheses, the Frankl-Wilson theorem says that $|\mathcal{B}| \leq |X|$. More generally, if there are $s$ possible intersection sizes, $|\mathcal{B}| \leq \binom{|X|}{s}$.

I'm not aware of general lower bounds or explicit constructions for this problem but there may be something in the literature. Knowing what to google should help.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.