0
$\begingroup$

This is similar to a previous question, but simpler, I suppose.

Let $\mathcal{B}$ be the family of all subsets of $[n]=\{1,2,\ldots,n\} $ of size $2$. Let $\mathcal{F} = \{\mathcal{A}_1,\ldots,\mathcal{A}_n\}$ be a grouping of sets in $\mathcal{B}$ in such a way that every set belongs to exactly one of the families $\mathcal{A}_i, 1 \le i \le n$. It is not a partition because one or more of the $\mathcal{A}_i$ can be empty. It is explicitly required that $n$ is also the size of $\mathcal{F}$, it is not an error.

Let $\mathcal{F}_a = \{\mathcal{A} \in \mathcal{F} : \exists B \in \mathcal{A} : a \in B\}$, i.e. the number of families that have $a$ as element of at least one of their sets.

We know that for a given $m \le n$, $\vert \mathcal{F}_x \vert \le m, 1 \le x \le n$.

Let $G = \{\{B,C\} : \exists \mathcal{A} \in \mathcal{F} : (B \in \mathcal{A}) \land (C \in \mathcal{A}) \land (B \cap C = \emptyset)\}$, i.e. the unordered couples of sets in $\mathcal{B}$ belonging to the same family and disjoint.

I would like to find a lower bound for $\vert G \vert$ over all possible groupings $\mathcal{F}$ as a function of $m$:

$$\vert G \vert \ge f(m)$$

I have a conjectured possible lower bound:

$$f(m) = \frac{\binom{n-m+1}{2}\binom{n-m-1}{2}}{2} \tag{1}$$

That value can be achieved with $\mathcal{A_1} = \{A \in Q: 1 \in A \}, \mathcal{A_2} = \{A \in Q, A \not\in \mathcal{A_1}: 2 \in A \}, \mathcal{A_3} = \{A \in Q, A \not\in \mathcal{A_1},\mathcal{A_2}: 3 \in A \},\ldots,\mathcal{A_{m-1}} = \{A \in Q, A \not\in \mathcal{A_1},\ldots,\mathcal{A_{m-2}}: m-1 \in A \}, \mathcal{A_m}$ containing the remaining sets, $\mathcal{A_{m+1}}=\cdots=\mathcal{A}_n =\emptyset$. For example, for $n=5$, $m=2$, we have $\mathcal{A_1} =\{\{1,2\},\{1,3\},\{1,4\},\{1,5\}\}$, $\mathcal{A_2} =\{\{2,3\},\{2,4\},\{2,5\},\{3,4\},\{3,5\},\{4,5\}\}$, $\mathcal{A_3} = \mathcal{A_4} = \mathcal{A_5} = \emptyset$, and $f(m)=f(2)=3$.

Is it possible to prove that $(1)$ is actually a lower bound or find another one?

See also this related question.

EDIT 2023-10-06: now crossposted at MathStackExchange.

Improve this question
$\endgroup$
2
  • $\begingroup$ If $m$ is much smaller than $n$, your example is surely not the best, as you can move one set from $\mathcal A_m$ to $\mathcal A_{m-1}$ losing $n-m-2\choose 2$ pairs but gaining only $n-m-2$ ones. $\endgroup$
    – Ilya Bogdanov
    Commented Oct 19, 2023 at 7:05
  • 1
    $\begingroup$ Some example: if $n=q^2+q+1$ and $m=q+1$, you may consider a projective plane over $\mathbb F_q$ and set $\mathcal A_i$ to be the set of pairs of points on the $i$th line. This way you get only $n{q+1\choose 2}{q-1\choose 2}/2<n^3/8$ pairs. $\endgroup$
    – Ilya Bogdanov
    Commented Oct 19, 2023 at 7:09

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .