Grado de vértice en la parte izquierda de un gráfico bipartito con una distancia inferior a 3 en la parte derecha.

Question

Un amigo y yo hemos trabajado en los siguientes problemas y agradeceríamos su ayuda para generalizar la respuesta para $n \ge5 $ :

Supongamos que los participantes $P$ en una conferencia hablar de más de los lenguajes en el conjunto $L$ y que cada pareja puede comunicarse en al menos un idioma. Ya hemos demostrado que si $|L|=3$ y $|P| \ge10 $ entonces un idioma tiene que ser hablado por al menos $2/3$ de los participantes. Esa proporción es $3/5$ si $|L|=4$ y $|P|$ es lo suficientemente grande como para esquivar la irregularidad de los participantes bajos.

Generalizamos fácilmente al siguiente problema y agradeceríamos su toma: Que $P$ y $L$ sean los dos lados de un gráfico bipartito de tal manera que para cualquier par $(x,y)$ de distintos vértices en $P$ entonces $dist(x,y)=2$ . ¿Cuál es el valor más bajo de $$p(n)= \max_ { \ell\in L} \frac { \deg ( \ell )}{n}$$ donde $|L|=n$ .

Answer 1

He aquí una respuesta incompleta.

Si hay $m$ participantes, y como máximo $pm$ hablan cada lengua, entonces cada lengua permite la conversación entre $\binom{pm}{2}$ parejas de personas; hay $\binom{m}{2}$ pares de personas en total, por lo que debemos tener $$n \cdot \binom{pm}{2} \ge \binom{m}{2}.$$ Esto sólo puede ser válido para $m$ si $n \cdot \frac{p^2}{2} \ge \frac12$ o $p(n) \ge \frac{1}{\sqrt n}$ .

Para demostrar que no se trata de un límite inferior terrible: tenemos un límite superior casi igual cuando $n = q^2 + q + 1$ para alguna potencia prima $q$ . En este caso, existe una construcción con $n$ idiomas y $n$ participantes en el que cada participante habla $q+1$ idiomas: deja que $P$ sea el conjunto de puntos y $L$ sea el conjunto de rectas del plano proyectivo de orden $q$ y supongamos que una persona habla un idioma si el punto correspondiente se encuentra en la línea correspondiente.

Podemos reproducirlo exactamente para $2n, 3n, 4n, \dots$ participantes mediante grupos de tamaño $2, 3, 4,\dots$ hablar exactamente el mismo conjunto de lenguas, y aproximadamente dividiendo a las personas en grupos lo más equitativos posible. De este modo, ninguna lengua es hablada por más de $p(q^2+q+1) = \frac{q+1}{q^2+q+1}$ de los participantes, que es un $\frac1{\sqrt n} + O(\frac1n)$ fracción.

Espero que la construcción del plano proyectivo sea la mejor posible cuando se aplique, pero no sé cuál es la respuesta óptima para, por ejemplo, $p(5)$ .

Answer 2

Otra respuesta incompleta. Supongo que el número de participantes es grande, por lo que podemos dividirlos continuamente en grupos. Con este método he podido calcular $p(n)$ para $n$ hasta 6.

Si tenemos $n$ idiomas, entonces podemos dividir a la gente en $2^n$ grupos. Cada grupo habla o no habla determinadas lenguas.

Podemos nombrar las lenguas $0$ a $n-1$ y nombrar los grupos $0$ a $2^n-1$ . Grupo $i$ habla el idioma $j$ si el bit $2^j$ se establece en la notación binaria de $i$ . Por ejemplo, si $n=4$ grupo $3 = 0011_2$ habla las lenguas 0 y 1, pero no las 2 y 3.

Que las variables $a_0$ hasta $a_{2^n-1}$ indican el tamaño de los grupos. Se aplican las siguientes restricciones:

• $a_0 = 0$
• $\displaystyle \forall_i \ \ a_i \ge 0$
• $\displaystyle \sum_{i=0}^{2^n-1} a_i = 1$
• Para grupos $i$ y $j$ : $\quad\displaystyle i\ \&\ j = 0\ \ \implies\ \ a_i = 0\ \vee\ a_j = 0$
  Dónde $\&$ es el bit a bit y .

Podemos simplificar un poco el problema. Para $n>2$ podemos suponer que:

• Nadie habla una sola lengua, así que $a_i=0$ cuando $i$ es una potencia de $2$ .
• Si alguien habla sólo dos lenguas, sin pérdida de generalidad podemos suponer que se tratará de lenguas $0$ y $1$ . Así pues, para todos los grupos $i$ que sólo puede hablar dos idiomas, y ninguno de ellos es $0$ ou $1$ tenemos $a_i = 0$ .

Tenemos que calcular:

$$ \min_{\displaystyle a_i}\ \max\ \left\{\sum \{a_i\ |\ i\ \&\ 2^j \neq 0\} \ \ \middle|\ \ j=0,1,\dots n-1\right\} $$ Podemos introducir las fórmulas en Mathematica y utilizar la función Minimizar para encontrar el mínimo de cada una. $n$ y obtener los valores correspondientes $a_i$ . Esto puede utilizarse para buscar patrones que también puedan aplicarse a las categorías superiores. $n$ . El siguiente código funciona para $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}]]
];

Abajo los resultados. Tenga en cuenta que estas soluciones probablemente no son únicas. $$ \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} $$ Desgraciadamente, el tiempo de cálculo aumenta muy rápidamente, por lo que no es factible calcularlo para $n \ge 7$ . A menos que podamos añadir más restricciones sobre algunos $a_i$ en $0$ .

Debido a la respuesta de Misha, la salida para $n = 7$ sería algo así: $$ \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} $$