# Maximum number of subsets in which people co-exist with their friends

Let $$P = \{1,\dots,p\}$$ be a set of people. Consider partitioning $$P$$ into two disjoint sets, $$A$$ (of cardinality $$a$$) and $$A^c = P-A$$. Let us index $$A$$ as $$A = \{A_1,\dots,A_a\}$$. Each person in $$A$$ can choose at most $$a$$ people from $$A^c$$ to be friends with. Formally, $$A_i$$ can be friends with at most $$a$$ people denoted with $$F_i \subset A^c$$. We form all $$p \choose r$$ subsets $$S_1, \dots, S_{p \choose r}$$ of $$P$$, each of size $$r$$.

People in $$A$$ are a bit "strange" and have the following requirements:

1. They want to only co-exist with their friends in any subsets they belong to; they don't want other people from $$A^c$$ in their subsets.
2. They want to be in majority in the subsets $$S_i$$ they participate into, i.e., for those subsets: $$S_i \cap A \geq \frac{r+1}{2}$$.

Let $$r' = \frac{r+1}{2}$$.

Assuming:

• $$r$$ is odd, $$r \geq 3$$
• $$r \leq a < p/2$$

the question I am interested in is

"What is the maximum number of subsets $$S$$ of $$P$$ which either consist of people exclusively from $$A$$ or all people in $$S \cap A^c$$ are friends of the people in $$S \cap A$$ and $$|S \cap A^c| \geq r'$$ ?"

More formally, I want to find the best choice of the sets $$F_1, \dots, F_a$$ s.t. the following quantity is maximized $$\left|\left\{S: |A\cap S| \geq r' \text{ and } \forall j\in A^c\cap S, j \in F_i \text{ for all } i\in A\cap S\right\}\right|.$$

I think that the above quantity is equal to $$\left|\left\{S: |A\cap S| \geq r' \text{ and } (A^c\cap S)\subseteq \bigcap\limits_{i\in A\cap S}F_i\right\}\right|$$

and that the maximum value is achieved if all people in $$A$$ choose to be friends with the same subset of $$A^c$$, i.e., when $$F_1 = \dots = F_a = F$$

for some fixed $$F\subset A^c$$. My intuition is that this maximizes the overlap among the friendship sets. Then, the number of subsets with the above property is $$\sum_{i=r'}^{\max\{a,r-1\}}{{a}\choose{i}}{{a}\choose{r-i}} + {a \choose r}.$$

But I am not sure how to prove this since my argument for $$F_1 = \dots = F_a = F$$ is not well-established.

• Just a couple of cents: (i) "$\forall j\in A^c\cap S, j \in F_i \text{ for all } i\in A\cap S$" simply means that $$(A^c\cap S) \subseteq \bigcap\limits_{i\in A\cap S}F_i$$ (ii) we have $$\sum_{i=r'}^a{{a}\choose{i}}{{a}\choose{r-i}} = \frac{1}{2}\binom{2a}{r}.$$ Jan 27, 2021 at 15:28
• Where the term $+\binom{a}{r}$ comes from? Jan 27, 2021 at 15:30
• Hello, I have incorporated your first comment to the expression. Now, the term $\binom{a}{r}$ refers to the number of subsets that consist exclusively from people in $A$ since I have assumed that $a\geq r$. This quantity is not included in the summation. But, I have corrected the summation bounds so that $i = r', r'+1,\dots, \max\{a, r-1\}$.
– mgus
Jan 27, 2021 at 20:04
• It was included in summation -- as the term with $i=r$. It was ok to keep the upper limit as $a$ as the product of binomial coefficients is simply zeros when $i>r$. If you like to have $\max$ in the limit, then $\max\{a,r\}$ would be better to incorporate this extra term $\binom{a}{r}$. In either case, the sum still simplifies to just $\frac{1}{2}\binom{2a}{r}$. Jan 27, 2021 at 20:56
• Thanks for your comments. Can you help me prove (or disprove) the argument that setting $F_i$'s to be all equal to each other maximizes the desired quantity? Based on your first observation, rewriting $\forall j\in A^c\cap S, j \in F_i \text{ for all } i\in A\cap S$ as $(A^c\cap S) \subseteq \bigcap\limits_{i\in A\cap S}F_i$ seems to make this argument more intuitive. But, I am still not sure whether this is rigorous to serve as a proof.
– mgus
Jan 27, 2021 at 21:34

The cardinality $$\begin{split} &\left|\left\{S\in\binom{P}{r}: |A\cap S| \geq r' \text{ and } (A^c\cap S)\subseteq \bigcap\limits_{i\in A\cap S}F_i\right\}\right| \\ =& \sum_{i=r'}^a \left|\left\{S\in\binom{P}{r}: |A\cap S| = i \text{ and } (A^c\cap S)\subseteq \bigcap\limits_{i\in A\cap S}F_i\right\}\right|. \end{split}$$ If all $$F_i$$ are the same and have size $$a$$, then we obtain the number of suitable sets $$S=(A\cap S) \sqcup (A^c\cap S)$$ equals $$\sum_{i=r'}^a \binom{a}{i}\binom{a}{r-i}=\frac12\binom{2a}{r},$$ where $$\binom{a}{i}$$ enumerates the suitable subsets $$A\cap S\subseteq S$$ and $$\binom{a}{r-i}$$ enumerates the suitable subsets $$A^c\cap S\subseteq S$$. It also follows that in this case the number of suitable sets $$S$$ containing any two fixed elements $$x,y\in A$$ equals $$N:=\sum_{i=r'}^a \binom{a-2}{i-2}\binom{a}{r-i}.$$
However, if $$F_i$$ are not all the same, then there exist two elements $$x,y\in A$$ such that $$F_x\ne F_y$$, implying that $$b:=|F_x\cap F_y|. It can be easily seen that in this case the number of suitable sets $$S$$ containing $$x,y$$ does not exceed $$\sum_{i=r'}^a \binom{a-2}{i-2}\binom{b}{r-i} < N.$$ It follows that the number of suitable sets $$S$$ in this case is smaller than $$\frac12\binom{2a}{r}$$.
• Hi, I understand your proof and thanks. But, can you explain why $\sum_{i=r'}^a \binom{a}{i}\binom{a}{r-i}=\frac12\binom{2a}{r}$ perhaps writing a couple of steps? I have tried to show this using the identity $\sum_{k=0}^{n}{{r}\choose{k}}{{s}\choose{n-k}} = {{r+s}\choose{n}}$ but I cannot figure it out.
• @mgus: That's because by symmetry $\sum_{i\geq r'} \binom{a}{i}\binom{a}{r-i} = \sum_{i<r'} \binom{a}{i}\binom{a}{r-i}$, and therefore they both are equal to the half of $\sum_{i=0}^a \binom{a}{i}\binom{a}{r-i} = \binom{2a}{r}$. Jan 28, 2021 at 23:46