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:

*

*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.

*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.
 A: 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}$.
