Degree of vertex in left part of a bipartite graph with distance less than 3 in right part.

Question

A friend and I have worked on the following problems and would appreciate your help generalizing the answer for $n\ge5$:

Suppose participants $P$ at a conference speak one of more of the langages in the set $L$ and that each pair can communicate in at least one language. We already proved that if $|L|=3$ and $|P| \ge10$ then one language has to be spoken by at least $2/3$ of participants. That ratio is $3/5$ if $|L|=4$ and $|P|$ is large enough to dodge low participants irregularity.

We generalize easily to the following problem and would appreciate your take : Let $P$ and $L$ be the two sides of a bipartite graph such that for any pair $(x,y)$ of distinct vertices in $P$ then $dist(x,y)=2$. What is the lowest value for $$p(n)=\max_{\ell\in L} \frac{\deg(\ell)}{n}$$ where $|L|=n$.

Answer 1

An other incomplete answer. I assume that the number of participants is large, so we can continuously divide them into groups. With this method I was able to calculate $p(n)$ for $n$ up to 6.

If we have $n$ languages, then we can divide the people into $2^n$ groups. Each group does or doesn't speak certain languages.

We can name the languages $0$ to $n-1$ and name the groups $0$ to $2^n-1$. Group $i$ speaks language $j$ if the bit $2^j$ is set in the binary notation of $i$. For example, if $n=4$, then group $3 = 0011_2$ speaks languages 0 and 1, but not 2 and 3.

Let the variables $a_0$ up to $a_{2^n-1}$ indicate the size of the groups. The following restrictions apply:

• $a_0 = 0$
• $\displaystyle \forall_i \ \ a_i \ge 0$
• $\displaystyle \sum_{i=0}^{2^n-1} a_i = 1$
• For groups $i$ and $j$: $\quad\displaystyle i\ \&\ j = 0\ \ \implies\ \ a_i = 0\ \vee\ a_j = 0$
  Where $\&$ is the bitwise and.

We can simplify the problem a bit. For $n>2$ we can assume that:

• No one speaks only one language, so $a_i=0$ when $i$ is a power of $2$.
• If anyone speaks only two languages, then without loss of generality we can assume that this will be languages $0$ and $1$. So for all groups $i$ that can speak only two languages, and neither of them is $0$ or $1$, we have $a_i = 0$.

We have to calculate:

$$ \min_{\displaystyle a_i}\ \max\ \left\{\sum \{a_i\ |\ i\ \&\ 2^j \neq 0\} \ \ \middle|\ \ j=0,1,\dots n-1\right\} $$ We can enter the formulas in Mathematica and use the Minimize function to find the minimum for each $n$ and get the corresponding values $a_i$. This can be used to look for patterns that may also be applicable to higher $n$. The following code works for $n \ge 2$:

solve[n_] := Module[{vari, or, max},
    vari = Select[Range[0, 2^n - 1], Total[IntegerDigits[#, 2]] > 1 && (Total[IntegerDigits[#, 2]] > 2 || BitAnd[#, 3] != 0)&];
    or = Or @@ (a[#] == 0 & /@ #) & /@ Select[Tuples[vari, 2], Less @@ # && BitAnd @@ # == 0 &];
    max = Table[(Select[vari, BitGet[#, i] == 1 &] // a // Thread // Total) <= x, {i, 0, n - 1}];
    Minimize[{x, a[#] >= 0 & /@ vari, Total[a /@ vari] == 1, or, max}, Join[a /@ vari, {x}]]
];

Below the results. Note that these solutions are probably not unique. $$ \begin{array}{|c|c|c|} \hline n & p(n) & a_i \\ \hline 1 & 1 & \begin{array}{c|c} 0 & a_i \\ \hline 1 & 1 \\ \end{array} \\ \hline 2 & 1 & \begin{array}{cc|c} 0 & 1 & a_i \\ \hline 1 & 1 & 1 \\ \end{array} \\ \hline 3 & 2/3 & \begin{array}{ccc|c} 0 & 1 & 2 & a_i \\ \hline 0 & 1 & 1 & 1/3 \\ 1 & 0 & 1 & 1/3 \\ 1 & 1 & 0 & 1/3 \\ \end{array} \\ \hline 4 & 3/5 & \begin{array}{cccc|c} 0 & 1 & 2 & 3 & a_i \\ \hline 0 & 0 & 1 & 1 & 1/5 \\ 0 & 1 & 1 & 0 & 1/5 \\ 1 & 0 & 1 & 0 & 1/5 \\ 1 & 1 & 0 & 1 & 2/5 \\ \end{array} \\ \hline 5 & 5/9 & \begin{array}{ccccc|c} 0 & 1 & 2 & 3 & 4 & a_i \\ \hline 0 & 0 & 1 & 1 & 1 & 2/9 \\ 0 & 1 & 0 & 1 & 1 & 2/9 \\ 1 & 0 & 0 & 0 & 1 & 1/9 \\ 1 & 0 & 0 & 1 & 0 & 1/9 \\ 1 & 1 & 1 & 0 & 0 & 1/3 \\ \end{array} \\ \hline 6 & 1/2 & \begin{array}{cccccc|c} 0 & 1 & 2 & 3 & 4 & 5 & a_i \\ \hline 0 & 1 & 0 & 1 & 1 & 0 & 1/4 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1/4 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1/4 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1/4 \\ \end{array} \\ \hline \end{array} $$ Unfortunately the time to calculate increases very fast, so it is not feasible to calculate this for $n \ge 7$. Unless we can add more restrictions about some $a_i$ being $0$.

Because of Misha's answer, the output for $n = 7$ would look something like this: $$ \begin{array}{|c|c|c|} \hline n & p(n) & a_i \\ \hline 7 & 3/7 & \begin{array}{ccccccc|c} 0 & 1 & 2 & 3 & 4 & 5 & 6 & a_i \\ \hline 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1/7 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1/7 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1/7 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1/7 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1/7 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1/7 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1/7 \\ \end{array} \\ \hline \end{array} $$

Answer 2

Here's an incomplete answer.

If there are $m$ participants, and at most $pm$ speak each language, then each language allows conversation between $\binom{pm}{2}$ pairs of people; there are $\binom{m}{2}$ pairs of people total, so we must have $$n \cdot \binom{pm}{2} \ge \binom{m}{2}.$$ This can only hold for arbitrarily large $m$ if $n \cdot \frac{p^2}{2} \ge \frac12$, or $p(n) \ge \frac{1}{\sqrt n}$.

To show that this is not a terrible lower bound: we have a nearly-matching upper bound when $n = q^2 + q + 1$ for some prime power $q$. In this case, there is a construction with $n$ languages and $n$ participants in which each participant speaks $q+1$ languages: just let $P$ be the set of points and $L$ be the set of lines of the projective plane of order $q$, and suppose a person speaks a language if the corresponding point lies on the corresponding line.

We can reproduce this exactly for $2n, 3n, 4n, \dots$ participants by having groups of size $2, 3, 4,\dots$ speak exactly the same set of languages, and approximately by dividing people into groups as evenly as possible. In this way, no language is spoken by more than $p(q^2+q+1) = \frac{q+1}{q^2+q+1}$ of the participants, which is a $\frac1{\sqrt n} + O(\frac1n)$ fraction.

I expect the projective plane construction to be the best possible when it applies, but I don't know what the optimal answer is for, e.g., $p(5)$.