Return to 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$ over $\mathbb{F}_2$?

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) > 1/c$, and $c/(c^2 - c + 1) < 1/(c - 1)$ we would then get that

$$\frac{1}{c} < 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.

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.

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$ over $\mathbb{F}_2$?

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) > 1/c$, and $c/(c^2 - c + 1) < 1/(c - 1)$ we would then get that

$$\frac{1}{c} < 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.

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$ over $\mathbb{F}_2$?

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) > 1/c$, and $c/(c^2 - c + 1) < 1/(c - 1)$ we would then get that

$$\frac{1}{c} < 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.

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$ over $\mathbb{F}_2$?

Intuitively again it seems obvious that one should take the whole plane as $V$ with rate $r_0 = c/(c^2 - c + 1)$. If one takes 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 one removes 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) > 1/c$, and $c/(c^2 - c + 1) < 1/(c - 1)$ we would then get that

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

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

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$ over $\mathbb{F}_2$?

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) > 1/c$, and $c/(c^2 - c + 1) < 1/(c - 1)$ we would then get that

$$\frac{1}{c} < 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.