Does there exist a constant $c$ so that the lines of every Steiner triple system on $v$ points can be covered by $cv$ points?

That is if $D \in STS(v)$ with point set $T=\{1,2,\ldots,v\}$ then there exists a subset $P \subseteq T$, $|P|=cv$ and every line of $D$ contains a point from $P$.

  • 1
    $\begingroup$ I may not understand properly, but doesn't $c=1$ work? The goal is to get $c$ as small as possible. Two observations: (1) From simple counting, it's clear that we need $c > 1/3$. (2) If you specify your set $P \subset [v]$ ahead of time and then quantify over all STS on $[v]$, you run into counterexamples for $c$ below $1/2$. $\endgroup$ – Peter Dukes Apr 4 '14 at 19:59
  • $\begingroup$ @PeterDukes Any $c<1$ would do for me... $\endgroup$ – Felix Goldberg Apr 5 '14 at 7:02

I think your question equivalently asks if there is a universal constant $c>0$ such that every Steiner triple system of order $v$ has a 'cap' (line-free set) of size at least $c v$. The complement of a cap is a hitting set, and vice-versa.

The answer to the latter question, and hence (provided I am not goofing up the duality!) to your question is no: not for every Steiner triple system.

Consider this paper by Michael Bateman and Nets Hawk Katz: http://arxiv.org/abs/1101.5851

It obtains an upper bound on maximum caps in the (infinite family of) affine triple systems AG$_d(3)$. These systems are defined by lines (shifts of one-dimensional subspaces) in $\mathbb{F}_3^d$. One cool example for $d=4$ is the 'Set' card game: http://www.setgame.com/set

Anyway, the above paper shows the maximum cap size in AG$_d(3)$ is at most $C \cdot 3^d/d^{1+\epsilon}$, where $C$ and $\epsilon$ are universal positive constants. This translates into $C' v/(\log v)^{1+\epsilon}$, which tends to zero as a proportion of $v$. Correspondingly, the hitting set sizes for these systems is asymptotically $v$.

I should clarify that the above paper was not the first to get a sub-linear bound on the cap size in affine space, but it is the current state of the art to the best of my knowledge.

In the 'other direction', consider systems which contain largest possible flats/subsystems (i.e. order $(v-1)/2$). The projective space PG$_d(2)$ offers one infinite family of examples. Since such flats are hit by every block, you can get away $c \rightarrow 1/2$ in these cases. I believe that is best possible. (It should be straightforward to do better than the counting argument in my comment, which shows $c > 1/3$.)

  • $\begingroup$ Thanks, Peter! This is a very helpful and informative answer. (Btw, I am an avid Set player :) $\endgroup$ – Felix Goldberg Apr 6 '14 at 6:42
  • $\begingroup$ I will have to make sure to lose a game of Set to you next time I visit your area! $\endgroup$ – Peter Dukes Apr 9 '14 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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