2
$\begingroup$

Let $\mathcal{A}$ be the family of all subsets of $U = [2n+1] = \{1,2,\ldots,2n,2n+1\}$ with size $n+1$, $n \ge 1$. The size of $\mathcal{A}$ is therefore $\binom{2n+1}{n+1}$.

For any family $\mathcal{F} \subseteq \mathcal{A}$ let $R_j(\mathcal{F}) \subseteq U$ be a set of minimum size such that $j \in R_j(\mathcal{F})$ and any $S \in \mathcal{F}$ has a non-empty intersection with $R_j(\mathcal{F})$.

Let:

$$r(\mathcal{F}) = \max_{1 \le j \le 2n+1} \vert R_j(\mathcal{F}) \vert$$

Due to symmetry of $\mathcal{A}$ and the equality $\binom{2n+1}{n+1}=\sum_{k=0}^n \binom{n+k}{n}$ it is possible to show that $r(\mathcal{A}) = n+1$.

Now choose any family $\mathcal{G} \subset \mathcal{A}$ with size $\vert \mathcal{G} \vert \ge \binom{2n+1}{n+1}-\big\lfloor \frac{n}{2} \big\rfloor$. I would like to prove that still:

$$r(\mathcal{G})=n+1 \tag{1}$$

For example, for $n = 2$, $\mathcal{A} = \{\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{1,4,5\},\{2,3,4\},\{2,3,5\},\{2,4,5\},\{3,4,5\}\}$ and $r(\mathcal{A})=\vert R_1(\mathcal{A})\vert = \vert \{1,2,3\} \vert = 3$. If we take $\mathcal{G}$ of size $9 = \binom{2n+1}{n+1}-\big\lfloor \frac{n}{2} \big\rfloor$, $\mathcal{G} = \{\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{1,4,5\},\{2,3,4\},\{2,3,5\},\{2,4,5\}\}$ we have $\vert R_1(\mathcal{G})\vert = \vert R_2(\mathcal{G})\vert = 2$ but $\vert R_3(\mathcal{G})\vert = \vert R_4(\mathcal{G})\vert = \vert R_5(\mathcal{G})\vert = 3$ and $r(\mathcal{G}) = 3 = n+1$.

Any hint for proving or disproving $(1)$?

$\endgroup$

1 Answer 1

4
$\begingroup$

This is false in general. Let $X=\{1, \dots, n+1\}$, $Y=\{n+1, \dots, 2n+1\}$, and $Z$ be any $(n+1)$-subset of $[2n+1]$ not containing $n+1$. Let $\mathcal{F}=\mathcal{A} \setminus \{X,Y,Z\}$. Then for all $j \in [n]$, we may take $R_j(\mathcal{F})=[n]$, since $Y \notin \mathcal{F}$. Similarly, for all $j \in \{n+2, \dots, 2n+1\}$ we may take $R_j(\mathcal{F})=\{n+2, \dots, 2n+1\}$, since $X \notin \mathcal{F}$. Finally, we may take $R_{n+1}(\mathcal{F})$ to be the complement of $Z$, since $Z \notin \mathcal{F}$. Thus, $r(\mathcal{F}) \leq n$. This is a counterexample to your conjecture, provided $n \geq 6$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .