Al contar de 2 maneras, muestre que existe un ciclo de cuatro conocidos

La dificultad inmediata puede explicarse como un error en el planteamiento del problema. El autor me escribió (a través de Facebook Messenger), "es mi error, exactamente es$111$parejas", en lugar de$110$parejas anotadas en la Pregunta.

El problema general:

Para$n$participantes de la conferencia, cuántas parejas$f(n)$podrían conocerse entre sí sin incluir un "ciclo" de cuatro que podrían estar sentados cada uno entre dos de sus conocidos?

se estudia activamente en la literatura de investigación combinatoria, por ejemplo, Extremal Graphs Without 4-Cycles . Los lectores no deben dejarse intimidar por el vocabulario de la teoría de grafos para discutir estos problemas. Los participantes forman los vértices de un gráfico cuyas aristas son las parejas de personas que se conocen.

Supongamos para un gráfico con$n = 35$vértices que no hay$4$-ciclos. Entonces dos vértices cualesquiera$A,B$tendrá como máximo un vértice adyacente en común; si comparten dos "vecinos" distintos$C,D$, en conjunto formarían un$4$-subgrafo de ciclo (que suponemos que no existe):

$\require{AMScd}$

Entonces el conteo$S$de todos los caminos no dirigidos de longitud dos, como$A\frac{\phantom{XXX }}{\phantom{XXX}}C\frac{\phantom{XXX}}{\phantom{XXX}}B$, está acotado arriba por el recuento de pares no ordenados$\{A,B\}$de vértices,$\binom{35}{2}$. De este modo$S\le 595$.

Tenemos la segunda forma de contar.$S$. Considere para cada vértice$C$cuantos pares distintos de vecinos$A,B$tiene que formar un camino de longitud dos,$A \frac{\phantom{XXX }}{\phantom{XXX}} C \frac{\phantom{XXX}}{\phantom{XXX}} B$. Por lo tanto, usando la notación de la pregunta$a_i$para el número de vecinos en cada vértice:

No sabemos exactamente cuáles son todos los grados de vértice $a_i$son, por lo que no podemos evaluar directamente$S$de lo anterior. Pero sabemos por el lema del apretón de manos que la suma de todos los$a_i$'s es el doble del número de aristas.

Si hay$111$bordes,$S$debe ser al menos el mínimo de la expresión anterior donde$\sum a_i = 222$. El mínimo se alcanzaría repartiendo los grados lo más equitativamente posible entre los$35$vértices, a saber, doce vértices de grado$\lceil 222/35 \rceil = 7$y el otro$23$vértices de grado$\lfloor 222/35 \rfloor = 6$. Entonces$S \ge 12\binom{7}{2} + 23\binom{6}{2} = 597$.

Dado que eso contradice el límite superior anterior en$S$, lo sabemos$111$bordes en$35$vértices garantiza una$4$-cycle subgraph, que es lo que requiere el problema (corregido). Sin embargo, deja el problema interesante como se planteó originalmente (con$110$bordes) sin resolver; puede un$4$-ciclo ser evitado con sólo$110$bordes? No encontré una respuesta definitiva al investigar esta pregunta.