Número máximo de bordes que puede tener un gráfico bipartito con vértices$n,m$ cuando no contiene$4$ - ciclo

Question

Permita que$A_{n,m}$ sea el número máximo de bordes que un gráfico bipartito con$n,m$ vértices puede tener cuando no contiene$4$ - ciclo. He calculado algunos valores:

$A_{2,2}=3$,$A_{3,3}=6$,$A_{4,4}=9$,$A_{4,5}=10$,$A_{5,5}=12$.

Estoy tratando de encontrar la fórmula para$A_{n,m}$. ¿Alguien lo sabe o una pista de cómo encontrarlo?

Especialmente necesito el valor de$A_{6,6}$. Solo sé que$A_{6,6}\ge16$.

Answer 1

Voy a dar pruebas simples de las evaluaciones $A_{4,6}=12,\ A_{5,6}=14,\ A_{6,6}=16,\ A_{6,7}=18,\ $$A_{7,7}=21$.

1. Dado que la relación $\dfrac{A_{m,n}}{mn}$ es un nonincreasing función de $m$$n$, tenemos el recurrente límite superior $$A_{m,n+1}\le\lfloor\frac{n+1}nA_{m,n}\rfloor.$$

2. Es fácil ver que $A_{1,n}=n$ $A_{2,n}=n+1$ todos los $n$.

3.$$A_{3,4}\le\lfloor\frac32A_{2,4}\rfloor=\lfloor\frac{15}2\rfloor=7$$ $$A_{3,5}\le\lfloor\frac54A_{3,4}\rfloor\le\frac{35}4\rfloor=8$$ $$A_{4,5}\le\lfloor\frac43A_{3,5}\rfloor\le\lfloor\frac{32}3\rfloor=10$$ $$A_{4,6}\le\lfloor\frac65A_{4,5}\rfloor\le\lfloor\frac{60}5\rfloor=12$$ $$A_{{5,5}}\le\lfloor\frac54A_{4,5}\rfloor\le\lfloor\frac{50}4\rfloor=12$$ $$A_{5,6}\le\lfloor\frac65A_{5,5}\rfloor\le\lfloor\frac{72}5\rfloor=14$$ $$A_{6,6}\le\lfloor\frac65A_{5,6}\rfloor\le\lfloor\frac{84}5\rfloor=16$$ $$A_{6,7}\le\lfloor\frac76A_{6,6}\rfloor\le\lfloor\frac{112}6\rfloor=18$$ $$A_{7,7}\le\lfloor\frac76A_{6,7}\rfloor\le\lfloor\frac{126}6\rfloor=21$$

4. Deje $G$ ser el bipartito grafo con vértices conjuntos de $U,V$ donde $|U|=6,|V|=7$, y:

• Los elementos de $U$ son las seis caras de un cubo;
• $V$ tiene cuatro elementos correspondientes a cuatro pares de vértices no adyacentes de el cubo, cada uno de los cuatro elementos que se unen a las tres caras incidente con el correspondiente vértice del cubo;
• $V$ tiene tres elementos coresponding a los pares de caras opuestas del cubo, y se unió a los dos caras.

El gráfico de $G$ testigos de la desigualdad de $A_{6,7}\ge18$; por otra parte, mediante la eliminación de uno, dos o tres de la licenciatura $2$ vértices de $G$, podemos lograr que los testigos $A_{6,6}\ge16,\ A_{5,6}=A_{6,5}\ge14$, e $A_{4,6}=A_{6,4}\ge12$. Combinado con el obtenido previamente límites superiores, de esta forma se comprueba la exacta evaluaciones $A_{4,6}=12,\ A_{5,6}=14,\ A_{6,6}=16,$$A_{6,7}=18$.

5. El punto de la línea de incidencia gráfica de un número finito de la geometría es un $C_4$libre de bipartito gráfico. De esta manera obtenemos los límites inferiores $$A_{n^2,\ n^2+n}\ge n^3+n^2$$y $$A_{n^2+n+1,\ n^2+n+1}\ge(n^2+n+1)(n+1)$$ cada vez que un plano proyectivo de orden $n$ existe, por ejemplo, cuando $n$ es una fuente primaria de energía.

Establecimiento $n=2$ (el plano de Fano), llegamos a la $A_{4,6}\ge12$ (de nuevo) y $A_{7,7}\ge21$, lo que, combinado con los obtenidos anteriormente en el límite superior, establece que $A_{7,7}=21$.

La actualización. Gracias a @David para señalar que "la gráfica de G en 4 es, de hecho, la incidencia de la gráfica de la Fano plano con una línea (o punto) quitado."

Answer 2

Una ligera simplificación de la respuesta de bof: las secciones 4 y 5 podrían combinarse, ya que el gráfico$G$ en 4 es de hecho el gráfico de incidencia del plano Fano con una línea (o punto) eliminada.

Answer 3

Echa un vistazo a estas notas de Jacob Fox.