Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Given a set C consisting of n subsets of {1, 2, ..., n}, each of size k, does there exist some small A $\subset$ {1, 2, ..., n} such that A intersects all (or all except a small number) of the sets in C?

Preferably, "small" will be $\epsilon$n where $\epsilon$ can be made arbitrarily small, as long as n and k are sufficiently large.

I'm hoping the answer is yes. Here is why some such A might exist: on average, each element of {1, 2, ..., n} intersects k sets in C, so one might hope to make do with A of size on the order of n/k.

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.

share|improve this question

2 Answers 2

up vote 11 down vote accepted

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.

Here's a free copy of the paper.

http://www.cs.tau.ac.il/~nogaa/PDFS/Publications/Transversal%20numbers%20of%20uniform%20hypergraphs.pdf

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.

share|improve this answer
    
Thank you very much. –  David Diamondstone May 18 '10 at 7:34

Do you want to know the size of A without having to look at what is in C, just looking at n and k?

If you do, you can easily find a few bounds on the size of A.

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.

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:

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

I hope those two ideas help.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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