Skip to main content
4 of 5
added 20 characters in body
Peter Dukes
  • 1.1k
  • 1
  • 8
  • 17

The answer might be negative for $(15,3,1)$-designs (tedious work required). In any case, an easy argument works for higher $\lambda$; see my own comment below.

Following up on Gordon's comment, consider the projective Steiner triple system $PG_3(2)$ on 15 points. Concretely, the points can be presented as the nonzero binary 4-tuples; blocks are the triples of vectors with zero sum.

Now, the points are dominated by a parallel class of 5 blocks: $$ \begin{array}{ccc} 0001 &0010 &0011\\ 0100 &1000 &1100\\ 0101 &1010 &1111\\ 0110 &1101 &1011\\ 0111 &1001 &1110\\ \end{array} $$ The blocks are dominated by a maximal subspace of 7 points (e.g. those quadruples with a leading zero).

What's more, one block of the above parallel class can be taken inside the subspace. So I think we get domination number $11=(5-1)+7$. It is going to be hard (see below) to do this well in general.

It is easy to see that, in a Steiner triple system of order $v$, covering all points with $v/3$ blocks is best possible and can occur if and only if there is a parallel class. Likewise, touching all blocks with $(v-1)/2$ points is best possible and occurs if and only if they form a flat. (A quick counting argument is needed.)

Now, there are 10 out of 80 Steiner triple systems of order 15 with no parallel class, and nearly all of the 80 (I forget exactly how many) have no nontrivial flats. So I believe there could be systems with domination number 12, in fact.

Disclaimer: I acknowledge it is not correct for me to separately consider points and blocks in your bipartite graph. That is, I have not checked carefully whether not having to dominate the chosen points by blocks, and vice-versa, fails to help enough for one of these "bad" systems. It requires checking some system (edit: not the one in my avatar!) for $\gamma>11$.

Peter Dukes
  • 1.1k
  • 1
  • 8
  • 17