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.



Maximum number of subsets in which people co-exist with their friends
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}$.


