I believe, reading the abstract, that the paper "Transversal numbers of uniform hypergraphs", Graphs and Combinatorics 6, no. 1, 1990 by Noga Alon answers your question in the affirmative, for some definition of ``your question''. Namely, the worst case is that $A$ has to have size about $2log k/k$ times $n$, and this multiplier tends to zero as $k$ tends to infinity.
Here's a free copy of the paper.
I'm certainly no expert on these matters and my advice would be to look at this and related literature on transversals of hypergraphs. Your collection $C$ of sets is the same thing as a $k$-uniform hypergraph, and the property that you want from $A$ is equivalent to it being a transversal.
Reading Alon's paper a little more I see that what you want is the easier direction of his argument (which gives a tight dependence on $k$). The basic idea is to choose your transversal randomly by picking elements of ${1,dots,n}$ with an appropriate probability $p$. That way, with high probability, you'll hit most of the sets from your collection $C$, and then you just add in one extra element of $A$ for each un-hit set from $C$.
Reading a little further still, I see that the upper bound is probabilistic as well: that is, to make a collection $C$ which is ``bad'', the best plan is to choose sets in $C$ at random from amongst all $k$-element subsets of ${1,dots,n}$.
There's probably literature on your ``almost transveral'' question, but I'll leave someone else to find it. My guess is that random does best in both directions there too.
No comments:
Post a Comment