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

Let $U$ be some (unbounded) universe of elements, and let $\mathcal{S}$ be a collection of subsets of size $c$ each, such that any two elements from $\mathcal{S}$ have a non-empty intersection. Let $C \in \mathcal{S}$ be a special and unknown element of this collection. Now for any non-empty subset $V \subseteq U$ we define the rate of $V$ by $R(V) = |V \cap C|/|V|$. The problem is to find a subset $V \subseteq U$ that maximizes $R(V)$. However, we do not know anything about the intersecting set system, so $U,\mathcal{S},C$ could be anything. So what I am really interested in, is the value of:

$$f(c) := \min_{\mathcal{S}} (\max_{V \subseteq U} (\min_{C \in \mathcal{S}} \ R(V))).$$

Equivalently, one could assign a rate to a $c$-uniform pairwise intersecting set system $\mathcal{S}$ by $r(\mathcal{S}) = \max_{V \subseteq U} (\min_{C \in \mathcal{S}} \ R(V))$. The question then comes down to finding a low rate $c$-uniform intersecting set system, i.e.

$$f(c) = \min_{\mathcal{S}} \ r(\mathcal{S}).$$

Below two examples of these rates and a motivation for why I guess that $f(c = 3) = 3/7$.

  • Example: Let $c = 3$, let $U = \{1,\ldots,7\}$ and let $\mathcal{S}$ be constructed from the Fano plane, i.e. $$\mathcal{S} = \{(1,2,3),(1,4,5),(1,6,7),(2,4,7),(3,4,6),(3,5,7),(2,5,6)\}.$$ Then every set has size $c$ and every two sets have intersection exactly $1$. The optimal choice of $V$ is $V = U$ with $R(V) = 3/7$. So $r(\mathcal{S}) = 3/7$ and $f(3) \leq 3/7$.

  • Example: Let $c = 3$, let $U = \mathbb{N}_{+}$ and let $\mathcal{S}$ be defined as $$\mathcal{S} = (1,2,3),(1,4,5),(1,6,7),(1,8,9),\ldots.$$ Taking $V = \{1\}$ gives $R(V) = 1$, so $r(\mathcal{S}) = 1$ and $f(3) \leq 1$. This does not improve the upper bound on $f(3)$, as the Fano plane above already gave a sharper bound.

Intuitively, it seems clear to me that the lowest rates are obtained by taking $\mathcal{S}$ as the projective plane of order $(c - 1)$, so that the rate is maximized by taking $V$ as the set of all points in this projective plane, giving

$$f(c) \stackrel{?}{=} \frac{c}{c^2 - c + 1}$$

For large $c$ this would then give $f(c) \approx 1/c$, i.e. a rate only slightly higher than simply taking $V \in \mathcal{S}$ with $R(V) \geq 1/c$. But I can't find a proof for this in literature, and without resorting to a lot of handwaving and intimidation (statements like "it is obviously true") it seems hard to prove the formula for $f(c)$ rigorously. I hope I am not missing something trivial like a simple one-line proof, although that would of course solve my problem.

Any help is greatly appreciated!


Edit: A simpler question to start with, is: What is the rate of the projective plane of order $c - 1$?

Intuitively again it seems obvious that one should take the whole plane as $V$ with rate $r_0 = c/(c^2 - c + 1)$. If we take one point less, then picking $C$ as a line containing that point gives a rate of $(c - 1)/(c^2 - c) < r_0$. Similarly, if we remove two points, then picking $C$ as the unique line containing those two points gives rate $(c - 2)/(c^2 - c - 1) < r_0$. But even this argument seems to get ugly when trying to generalize it for removing more points.

Note that if we can indeed answer the bold-face question with $r(\mathcal{S}) = c/(c^2 - c + 1)$, then we can conclude that $f(c) \leq c/(c^2 - c + 1)$. And since obviously $f(c) \geq 1/c$, and $c/(c^2 - c + 1) < 1/(c - 1)$ we would then get that

$$\frac{1}{c} \leq f(c) < \frac{1}{c - 1}.$$

So for large $c$, answering the bold-face question may almost be as good as calculating $f(c)$ exactly.

share|improve this question
    
I imagine matroids may be useful here. Perhaps searching the web for your favorite terms with "matroid" is worth a few minutes of your time. Gerhard "Ask Me About System Design" Paseman, 2011.05.05 –  Gerhard Paseman May 5 '11 at 21:56
    
Could you be a bit more specific? I am not that familiar with matroid theory, but I don't see how formulating this as a matroid problem makes the problem easier. Actually at first I was hoping that this "maximality" of projective planes was some obvious property I did not know about, but apparently it is not... –  TMM May 6 '11 at 18:23
    
Regarding matroids, no I cannot. I was initially thinking of picking a set $D$ in $S$ and using it to classify sets in S, using the fact that for any partition $E \cup F$ of $D$, any set in $S$ which intersects $D$ in $G \subseteq E$ must intersect any other set in $S$ which intersects $D$ in $H \subseteq F$, and using that to classify the isomorphism types of set systems $S$, but I know of no clean way to proceed after that. While finite combinatorial designs may ultimately be what you want, I can't guarantee finite. Thus matroids. Gerhard "Ask Me About System Design" Paseman, 2011.05.06 –  Gerhard Paseman May 6 '11 at 19:55
    
I don't know if this is at all useful (and it's possibly well known?), but you can in some sense uniformly finitize the problem. If $\mathcal{S}$ is a $c$-uniform pairwise intersecting set system and some $u \in U$ is in more than $c^{c-1}$ elements of $\mathcal{S}$, then $r(\mathcal{S}) \geq 1/(c-1)$ which (if my arithmetic is correct) is already above the bound given by the projective plane of order $(c-1)$. This gives explicit finite bounds on $|U|$ and $|\mathcal{S}|$ (in terms of $c$) for potential counterexamples. –  Clinton Conley May 9 '11 at 12:25
1  
I'm not quite sure what "over $\mathbb{F}_2$ should mean, but the rate of a projective plane of order c-1 is indeed $c/(c^2-c+1)$. To see this let $V$ be any subset of the point set. We just have to show that there is a line $L$ such that $|V\cap L|/|V|\leqslant c/(c^2-c+1)$. Now suppose that's not the case, i.e. $|V\cap L|> c|V|/(c^2-c+1)$ for every line $L$. Summing over the lines we obtain $$\sum_{L}|V\cap L|>c|V|.$$ But on the left hand side every element of $V$ is counted $c$ times, so the LHS is equal to $c|V|$, contradiction. By th way, what's your plan for $c$'s without proj. planes? –  Thomas Kalinowski May 17 '11 at 1:20
show 2 more comments

4 Answers 4

up vote 2 down vote accepted

The projective plane example can be tweaked to give $f(c)\leqslant (2c)/(c^2-2c+4)\approx 2/c\ $ for general $c$. Let $p$ be the largest prime less than $c$ and take the projective plane of order $p$. Now let $A_1,\ldots,A_{p^2+p+1}$ be pairwise disjoint sets of size $c-p-1$ that are also disjoint to the points of the projective plane. Then our set system is obtained by extending the lines by the sets $A_i$. Clearly the best $V$ is the point set of the projective plane we started with, and using $p+1>c/2$ this gives $$f(c)\leqslant \frac{p+1}{p^2+p+1}\leqslant\frac{c/2}{(c/2)^2-(c/2)+1}=\frac{2c}{c^2-2c+4}.$$

share|improve this answer
1  
This is so much more reasonable than the approach in my answer! But I think it makes more sense just to have a huge number of pairwise disjoint sets of size $c-p-1$ and take as the sets in your family all unions of a line with one of these new sets (there's no reason for the new sets to correspond with the lines). This makes the "clearly the best $V$" part of your argument a little bit more clear (for me, anyway). –  Clinton Conley May 17 '11 at 20:19
2  
If you use q a prime or a power of a prime, then you can replace p+1 > c/2 with something like q+1 > 9c/10, or maybe 8c/9. Small cases plus estimates by Dusart should make something like 8c/9 apply in full generality. Gerhard "Ask Me About System Design" Paseman, 2011.05.17 –  Gerhard Paseman May 17 '11 at 20:21
add comment

I can't tell from your comment whether this is useful, but is $f(c)$ is bounded by about $4/c$ for all $c$. To build a $c$-uniform set system realizing this, fix nonzero naturals $m$ and $n$ such that $m+n = c+1$. The universe $U$ will be the rectangle $m \times n$, and the sets $C\in \mathcal{S}$ will be precisely those of the form

$C_{i,f} = (\{i\}\times n) \cup \{(j,k): f(j)=k\}$,`

for some $i \in m$ and $f: m \backslash \{i\} \to n$. Pictorially, each such $C$ is built from one full column of the rectangle $m \times n$ together with one element from each other column. Certainly any two such sets intersect (in at least two points) and each has $c$ elements.

Moreover, $r(\mathcal{S}) \leq (c+1)/mn$, so choosing $m$ and $n$ to each be about half of $c+1$ will give the desired bound on $f(c)$. To see this, fix $V \subseteq U$. Certainly some column of $U$ contains at most $|V|/m$ points of $V$. Choosing our $C \in \mathcal{S}$ to be the union of this column with the graph of some function missing all the incomplete columns of $V$ will minimize $|V\cap C|$. Since there are at most $|V|/n$ full columns of $U$ contained in $V$, we see $|V\cap C| \leq |V|/m + |V|/n$, from which the above bound follows.

(Of course, counting a bit more carefully gives $r(\mathcal{S}) = c/mn$, but I doubt that such a tiny improvement is worth the extra nuisance.)

share|improve this answer
add comment

I think, at least the case $c=3$ can be settled by a case discussion. Let $\mathcal S$ be an optimal family, and let $\mathcal U$ be the union of all elements of $\mathcal S$. Clearly $|\mathcal U|\geqslant 7$, because otherwise we can take the whole $\mathcal U$ giving $r(\mathcal S)\geqslant 1/2$. First we want to establish $|\mathcal U|=7$. We start with the following simple observations.

  • For any distinct elements $i,j\in\mathcal U$ there is an $A\in\mathcal S$ with $A\cap\{i,j\}=\varnothing$.
  • For any distinct elements $i,j,k,l\in\mathcal U$ there is an $A\in\mathcal S$ with $|A\cap\{i,j,k,l\}|\leqslant 1$.
  • There are elements $A,B\in\mathcal S$ with $|A\cap B|=1$, and we assume from now on wlog $123,145\in\mathcal S$ (omitting brackets and commas in the sets, i.e. writing $123$ for $\{1,2,3\}$).

Now assume $|\mathcal U|\geqslant 8$.

Case 1. $167\in\mathcal S$. Any block containing an element $>7$ must also contain $1$ (to hit each of the blocks $123$, $145$ and $167$). By the above observation there must be a block not containing 1, say $246$. So a block containing $8$ has the form $18i$ with $i\in 246$. But now any block containing neither 1 nor $i$ doesn't intersect $18i$, contradiction.

Case 2. There is no block $1ij$ with $i,j>5$. Then for all $i,j>5$ and all $A\in\mathcal S$, we have $|A\cap\{i,j\}|\leqslant 1$. As there has to be a block with at most one element in $\{2,3,4,5\}$, we may assume wlog that $126\in\mathcal S$ and then also $346\in\mathcal S$ (a block avoiding 1 and 2). Now a block containing $7$ cannot contain 5, because otherwise we get blocks $312$, $346$, $357$ and are in Case 1. Similarly 2 and 7 cannot be in a common block, since otherwise we are in Case 1 with the blocks 415, 436 and 427. So the only remaining possibilities for a block with 7 are 137, 147 and 347. But all of these lead to contradictions: If 137 is a block, any block avoiding 1 and 3 contains 2 and 7, if 147 is a block, any block avoiding 1 and 4 contains 5 and 7, and if 347 is a block, any block avoiding 3 and 4 contains 6 and 7.

So we may now assume that $|\mathcal U|=7$ and still $123\in\mathcal S$ and $145\in\mathcal S$. By the same argument as in Case 2 above, we may assume $167\in\mathcal S$. A block avoiding 1 and 3 is wlog $246$. Now we need a block hitting $1246$ at most once, and this is wlog $257$. We still need a block avoiding 1 and 2. The options are 347 and 356. If we take 347 we must add 356 as well to get a block hitting $1247$ at most once, and if we take 356 first, 347 is forced to get a block that hits 1256 at most once.

share|improve this answer
    
Thanks kali. I considered doing a general case analysis, but for large $c$ this just seems to get ugly. For $c = 3$ your analysis seems to work, but I don't see how or if it can be generalized to higher $c$. –  TMM May 9 '11 at 9:51
    
I definitely agree that for the general case some insight is needed. –  Thomas Kalinowski May 9 '11 at 10:42
add comment

Like algebraic structures, intersecting set systems lend themselves to nice constructions, such as (isomorphic image of a) Cartesian product, proper subsystem, and homomorphic image. Unfortunately, I do not know that these are enough to generate all Intersecting set systems, even given a somewhat rich collection of building blocks.

For c-uniform systems, the product construction seems to be multiplicative on the measure f(c); for subsystems it does not decrease the measure. The situation is not so clear for homomorphic image; it may be possible to decrease the measure, but it is tricky to come up with a map that makes the homomorphic image d-uniform for some d. I suspect that such maps will turn out not to decrease f(c)

EDIT For intersecting set systems with smallest size of set c being finite, the rank function mentioned in the post clearly has minimum $1/c$, so the product construction is not as useful for establishing a lower bound as it is for providing (say for those composite $c$ not corresponding to an order of a projective plane) more examples of low rate c-uniform intersecting set systems. Note also that if there is a c-uniform set system with f(c) < (1- epsilon)/c, the epsilon can be magnified by taking a cartesian power. This is a reason (but not a proof) for me to suspect that the lower bound across all c-uniform set systems for f(c) is 1/c.

Other natural constructions I have looked at seem not to affect a rank function similar to f(c). If one can turn the intersecting set system into an algebraic structure, then I think f(c) will be shown to have 1/c as a lower bound. END EDIT

One idea that I will let others play with. For an intersecting set system on a universe U, pick a in U and then gather all sets which have a as a member. From the remaining sets which do not contain a, pick an element b, and gather all remaining sets which have b as a member. Continue picking such elements to weed out the sets in the system. The set chosen {a,b,c,...} is either a set in the intersecting set system, or can be added as one. If the set system is c-uniform and nontrivial (so that there is no element a beloning to all the sets, I think it a nice conjecture that this set is of size at most c, and can be helpful in showing f(c) <= 1/c.

Gerhard "Missed It By That Much" Paseman, 2011.05.20

share|improve this answer
    
"Note also that if there is a c-uniform set system with f(c) < (1- epsilon)/c, the epsilon can be magnified by taking a cartesian power. This is a reason (but not a proof) for me to suspect that the lower bound across all c-uniform set systems for f(c) is 1/c." -- Are you saying that you suspect that $f(c) \geq 1/c$ for all $c$? Because that is trivial, as I showed in the main text (take $U \in \mathcal{S}\ldots$). –  TMM May 20 '11 at 21:38
    
You're right, that needs fixing. (I was thinking of more general ISS which did not have uniform sizes, but had sets no smaller than c in size. However, even for these, it is similarly clear that the rank function is bounded below by $1/c$.) I'll edit it when I get to a real keyboard. Gerhard "Smart Phones Don't Feel Smart" Paseman, 2011.05.20 –  Gerhard Paseman May 20 '11 at 23:24
add comment

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.