Skip to main content
5 of 5
deleted 125 characters in body
Peter Dukes
  • 1.1k
  • 1
  • 8
  • 17

Gordon has done a proper search of $(15,3,1)$-designs. I guess my incorrect reasoning does lead to a computer-free proof for (15,3,13)-designs. This is kind of cheating though, because there are repeated blocks if one takes 13 copies of a STS. The idea may work for smaller $\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 $\le 11=(5-1)+7$. It is going to be hard (see below) to do this well in general. (Here I was very wrong!)

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.)

This is the key issue it turns out: 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.

Peter Dukes
  • 1.1k
  • 1
  • 8
  • 17