O Problema da Fábrica de Tijolos
Durante a Segunda Guerra Mundial, o matemático húngaro Pál Turán foi forçado a trabalhar em uma fábrica de tijolos, empurrando vagões sobre trilhos que ligavam os fornos aos armazéns da fábrica. Turán observou que os vagões eram mais difíceis de empurrar em pontos onde os trilhos se cruzavam e, inspirado por essa situação, começou a se perguntar como a fábrica poderia ser rearranjada a fim de minimizar o número de tais cruzamentos.
É fácil ver que o esquema geral da fábrica pode ser representado por um grafo bipartido completo em que os vértices estão particionados em fornos e armazéns. No entanto, para traduzir os cruzamentos de trilhos para a linguagem de Teoria dos Grafos, precisamos de mais alguns conceitos.
Imersão
Uma imersão do grafo no plano é uma representação dele no plano em que pontos representam vértices e arcos ligando pares de pontos que se relacionam representam arestas.
Em geral, pode-se entender a imersão de um grafo no plano como uma forma (note que podem haver várias) de desenhá-lo em uma folha de papel.
Nem sempre é possível evitar que os arcos de uma imersão se cruzem, o que pode causar confusão na interpretação do grafo que ela representa. Em geral, quanto menos cruzamentos ocorrerem, mais claro é o desenho. Essa questão motiva a seguinte definição:
Número de cruzamentos
O número de cruzamentos de um grafo $G$, denotado por $cr(G)$, é o menor número possível de interseções entre os arcos de uma imersão de $G$ no plano.
Problema da Fábrica de Tijolos
Dados $m, n$ inteiros positivos, qual o valor de $cr($$K_{m,n}$$)$?
Como $K_{m,n}\simeq K_{n,m}$, podemos supor, sem perda de generalidade, $m\ge n$.
Se, por exemplo, $n\le 2$, então $cr(K_{m, n})=0$, como sugere a imagem a seguir.
Após o fim da guerra, em 1952, Turán apresentou o problema em algumas palestras na Polônia e alcançou, em ocasiões diferentes, os matemáticos Kazimierz Urbanik e Kazimierz Zarankiewicz. Três anos mais tarde, os dois publicaram, de forma independente, artigos sugerindo soluções equivalentes para o problema. Infelizmente, ambas as soluções estavam incorretas. No entanto, nenhum contraexemplo para a fórmula apresentada, conhecida como Conjectura de Zarankiewicz, foi encontrado até o presente momento.
Conjectura de Zarankiewicz
$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$.
A imersão que atinge esse número de cruzamentos é obtida da seguinte forma:
Sejam $A = \{a_1, \dots, a_m\}$ e $B = \{b_1, \dots, b_n\}$ os conjuntos da bipartição de $G\simeq K_{m, n}$; posicione os vértices de $A$ com índice ímpar sobre o eixo-$x$ positivo e os com índice par sobre o eixo-$x$ negativo, e faça o mesmo com os vértices de $B$ substituindo o eixo-$x$ pelo eixo-$y$. A imagem a seguir mostra uma tal imersão para $m = 6, n = 5$.
O fato de existir uma imersão com esse número de cruzamentos mostra que $cr(K_{m, n}) \le \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$. Assim, para demonstrar a conjectura, basta mostrar que $cr(K_{m, n}) \ge \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$.
A solução de Zarankiewicz, apesar de conter um erro, foi capaz de demonstrar corretamente o caso $n=3$.
Curiosidades
- A Conjectura de Zarankiewicz é verdadeira para $n\le 6$ e $n=7, m\le 9$, ou seja, o menor caso em aberto é o $K_{9,9}$.
- Já se mostrou que, para grafos suficientemente grandes, a solução do problema deve ser pelo menos $83\%$ do número de Zarankiewicz.
- Restringindo os arcos da imersão à segmentos de reta, o Problema da Fábrica de Tijolos ainda é um problema em aberto.
- Determinar o número de cruzamentos de um grafo completo também é um problema em aberto.
Referências
- Lowell Beineke e Robin Wilson. “The Early History of the Brick Factory Problem”. Em: The Mathematical Intelligencer 32 (2010), pp. 41–48.
- S. W. Bowen. Turán’s Brick Factory Problem. 2022.
- Richard K. Guy. “The decline and fall of Zarankiewicz’s theorem”. Em: Proof Techniques in Graph Theory (1968), pp. 63–69.
- Kazimierz Zarankiewicz. “On a problem of P. Turan concerning graphs”. Em: Fundamenta Mathematicae 41 (1955), pp. 137–145.