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

Question

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.

Answer 1

The proof of the maximum is rather straight forward.

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