3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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}.$$ $\endgroup$ Jan 27, 2021 at 15:28
  • $\begingroup$ Where the term $+\binom{a}{r}$ comes from? $\endgroup$ Jan 27, 2021 at 15:30
  • $\begingroup$ 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\}$. $\endgroup$
    – mgus
    Jan 27, 2021 at 20:04
  • $\begingroup$ 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}$. $\endgroup$ Jan 27, 2021 at 20:56
  • $\begingroup$ 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. $\endgroup$
    – mgus
    Jan 27, 2021 at 21:34

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – mgus
    Jan 28, 2021 at 20:27
  • 1
    $\begingroup$ @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}$. $\endgroup$ Jan 28, 2021 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.