grafos:brickfactory:menor_contraexemplo [WikiMat]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.

=== O menor contraexemplo para a Conjectura de Zarankiewicz (se existir) deve ter $m, n$ ímpares ===

Seja $n = 2k-1$ e suponha $cr(K_{m, n}) = \bigg\lfloor\dfrac{m}{2}\bigg\rfloor \bigg\lfloor\dfrac{m-1}{2}\bigg\rfloor\bigg\lfloor\dfrac{n}{2}\bigg\rfloor \bigg\lfloor\dfrac{n-1}{2}\bigg\rfloor =\bigg\lfloor\dfrac{m}{2}\bigg\rfloor \bigg\lfloor\dfrac{m-1}{2}\bigg\rfloor(k-1)^2$. Note que $K_{m, n+1}$ possui $n+1$ subgrafos isomorfos a $K_{m, n}$, cada um com $cr(K_{m,n})$ cruzamentos. Mas cada cruzamento pertence a $n-1$ subgrafos.
Logo, $K_{m, n+1}$ possui pelo menos $\bigg\lfloor\dfrac{m}{2}\bigg\rfloor \bigg\lfloor\dfrac{m-1}{2}\bigg\rfloor(k-1)^2\dfrac{n+1}{n-1} = \bigg\lfloor\dfrac{m}{2}\bigg\rfloor\bigg\lfloor\dfrac{m-1}{2}\bigg\rfloor\bigg\lfloor\dfrac{n+1}{2}\bigg\rfloor\bigg\lfloor\dfrac{n}{2}\bigg\rfloor$ cruzamentos.