Return to Answer

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

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.

OK this is not really an answer, but I have a long remark that might lead to an answer.

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 there is a maximal subspace. (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 maximal subspace. 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. I suspect this is only a minor detail, but it requires checking some system (edit: not the one in my avatar!) for $\gamma>11$.

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

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 very 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 there is a maximal subspace. (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 maximal subspace. So I believe there could be systems with domination number 13, in fact.

Disclaimer: I acknowledge it is not completely 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. I strongly suspect this is only a minor detail. A hand check of some random system on 15 points (edit: not the one in my avatar!) should get $\gamma>11$.

OK this is not really an answer, but I have a long remark that might lead to an answer.

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 there is a maximal subspace. (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 maximal subspace. 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. I suspect this is only a minor detail, but it requires checking some system (edit: not the one in my avatar!) for $\gamma>11$.