3
$\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!

Improve this question
$\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$
    – Gerhard Paseman
    Commented 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$
    – Gordon Royle
    Commented 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$
    – Gerhard Paseman
    Commented 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
    Commented May 12, 2017 at 21:46

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .