Diferenças
Aqui você vê as diferenças entre duas revisões dessa página.
| Próxima revisão | Revisão anterior | ||
| grafos:brickfactory:menor_contraexemplo [2022/07/14 20:24] – criada modeus | grafos:brickfactory:menor_contraexemplo [2022/07/15 11:10] (atual) – edição externa 127.0.0.1 | ||
|---|---|---|---|
| Linha 1: | Linha 1: | ||
| - | === O menor contraexemplo | + | === O menor contraexemplo para a Conjectura de Zarankiewicz |
| 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, | 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, | ||
| 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. | 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. | ||