Given n k-element subsets of n, is there a small subset A of n which intersects them all? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T04:43:53Z http://mathoverflow.net/feeds/question/25067 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/25067/given-n-k-element-subsets-of-n-is-there-a-small-subset-a-of-n-which-intersects-t Given n k-element subsets of n, is there a small subset A of n which intersects them all? David Diamondstone 2010-05-17T22:29:24Z 2010-05-19T16:20:42Z <p>I'm looking for an answer to the following question. (An answer to a slightly different question would be good as well, since it could be useful for the same purpose.)</p> <blockquote> <p>Given a set <em>C</em> consisting of <em>n</em> subsets of {1, 2, ..., <em>n</em>}, each of size <em>k</em>, does there exist some small A $\subset$ {1, 2, ..., <em>n</em>} such that <em>A</em> intersects all (or all except a small number) of the sets in <em>C</em>?</p> </blockquote> <p>Preferably, "small" will be $\epsilon$<i>n</i> where $\epsilon$ can be made arbitrarily small, as long as <em>n</em> and <em>k</em> are sufficiently large.</p> <p>I'm hoping the answer is yes. Here is why some such <em>A</em> might exist: on average, each element of {1, 2, ..., <em>n</em>} intersects <em>k</em> sets in <em>C</em>, so one might hope to make do with <em>A</em> of size on the order of <em>n</em>/<i>k</i>.</p> <p>This smells a bit like some version of Ramsey's theorem to me, or like the Erdős–Ko–Rado theorem, but it doesn't (as far as I can tell) follow directly from either.</p> http://mathoverflow.net/questions/25067/given-n-k-element-subsets-of-n-is-there-a-small-subset-a-of-n-which-intersects-t/25070#25070 Answer by Ben Green for Given n k-element subsets of n, is there a small subset A of n which intersects them all? Ben Green 2010-05-17T23:19:26Z 2010-05-17T23:51:05Z <p>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 $2\log k/k$ times $n$, and this multiplier tends to zero as $k$ tends to infinity. </p> <p>Here's a free copy of the paper.</p> <p><a href="http://www.cs.tau.ac.il/~nogaa/PDFS/Publications/Transversal%20numbers%20of%20uniform%20hypergraphs.pdf" rel="nofollow">http://www.cs.tau.ac.il/~nogaa/PDFS/Publications/Transversal%20numbers%20of%20uniform%20hypergraphs.pdf</a></p> <p>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. </p> <p>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$. </p> <p>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}$.</p> <p>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.</p> http://mathoverflow.net/questions/25067/given-n-k-element-subsets-of-n-is-there-a-small-subset-a-of-n-which-intersects-t/25246#25246 Answer by Karl Waugh for Given n k-element subsets of n, is there a small subset A of n which intersects them all? Karl Waugh 2010-05-19T16:20:42Z 2010-05-19T16:20:42Z <p>Do you want to know the size of A without having to look at what is in C, just looking at n and k? </p> <p>If you do, you can easily find a few bounds on the size of A. </p> <p>Lets call the sets in C, $C_1, C_2$ etc. and if we define $C_1 = {1, 2, ... k }$ and then $C_2 = {k+1, k+2, ... 2k }$ etc obviously upto $C_{\lfloor \frac{n}{k} \rfloor}$ and define the rest of them to be whatever you like (as long as you use the last few elements). Then if A intersects all of the sets in C, then it must contain at least 1 element from the first k, one from the second k etc. so must have at least n/k elements. </p> <p>If you actually have particular sets of C and would like to find the A as small as possible, then you could try some algorithm that tries to home in on the set. Something such as: </p> <p>Relabel 1, 2, ... n such that 1 appears in more (or the same) number of sets in C as 2 does, and so on. So set $A_1 = {1, 2, ... n }$ So given $A_i$, take the highest element x of $A_i$ such that for each set $C_i$ with x in $C_i$ then $A \cap C_i \ge 2$. Then set $A_{i+1} = A_i - x$.</p> <p>I hope those two ideas help.</p>