Low rate c-uniform pairwise intersecting set systems

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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