2
$\begingroup$

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

$\endgroup$
2
  • 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$ Apr 4, 2014 at 19:59
  • $\begingroup$ @PeterDukes Any $c<1$ would do for me... $\endgroup$ Apr 5, 2014 at 7:02

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks, Peter! This is a very helpful and informative answer. (Btw, I am an avid Set player :) $\endgroup$ Apr 6, 2014 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$ Apr 9, 2014 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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