A teoría de grafos é un bo exemplo de teoría matemática pegada á realidade desde a súa orixe. O problema das pontes de Könisberg [1] resolto por Leonhard Euler en 1736, o estudo das redes eléctricas [2] por Gustav Kirchhoff en 1847 ou a enumeración dos isómeros dos hidrocarburos saturados acíclicos [3] por Arthur Cayley en 1874 ilustran ben esta idea. Pero agora vou interesarme noutra observación da vida ordinaria: en calquera grupo de seis persoas, hai sempre polo menos tres persoas que se coñecen, ou ben tres persoas que non se coñecen. Representemos cada unha destas persoas por un punto e depois unamos dous puntos cun segmento rectilíneo de color vermella se as dúas persoas se coñecen ou azul se non se coñecen.
A observación convértese agora nun teorema, chamado teorema de Ramsey, que se pode reformular da seguinte maneira: o grafo bicolor G que se obtén así [4] contén un triángulo vermello ou azul. Ou aínda mellor, ou ben o grafo vermello dos amigos A, ou ben o grafo azul dos estraños E (chamado complementario de A) contén un triángulo.
En realidade, Frank P. Ramsey demostrou un teorema máis xeral : para cada par de enteiros positivos m e n, existe un número enteiro R(m,n), chamado número de Ramsey [5], tal que calquera grafo completo bicolor G que teña polo menos este número de vértices contén un subgrafo completo con m vértices ou n vértices e coas arestas da mesma color. Como antes, o grafo vermello A contén un subgrafo completo con m vértices, ou ben o seu complementario azul E contén un subgrafo completo con n vértices.
A proba da nosa observación é moi simple. Fixemos un vértice calquera P. Está unido aos outros cinco vértices por arestas de color vermella ou azul. Hai polo menos tres arestas da mesma color, poñamos vermella. Os extremos A, B e C están unidos por aristas das dúas colores. Se unha das arestas (poñamos AB) é vermella, temos daquela un triángulo vermello PAB. Pola contra, se ningunha é vermella, temos un triángulo azul ABC. Observemos ademáis que esta demostración non é certa se consideramos un grupo de cinco persoas. Velaí un grafo bicolor que non contén ningún triángulo da mesma color:
Temos comprobado que R(3,3) = 6. Pero voltemos á nosa cuestión orixinal [6]: de onde provén a beleza da árbore de Kenyon?
Poderiamos pensar nas simetrías, pero non son moi numerosas: catro xiros, catro reflexións e as súas composicións. Cambiemos logo de idea e tentemos construir unha árbore da seguinte maneira. Partamos dun punto
e despois fixemos un dos catro puntos cardinais Norte, Sur, Este e Oeste, N, S, E e O en abreviatura, poñamos O. Esta elección determina unha aresta (coloreada en vermello) que podemos repetir nas tres outras direccións N, E e S :
A elección dun segundo punto cardinal (poñamos S) permite trazar un camiño (formado por dúas arestas vermellas) e repetir a figura nas outras direccións:
Cada sucesión de puntos cardinais determina unha árbore enraizada. Por exemplo, a da figura, que crece cara ao oeste, corresponde á sucesión OSNE…
Velaquí a súa construcción:
Non é a árbore de Kenyon pois non hai máis ca unha maneira de partir cara ao infinito sen idas e voltas, namentres que hai catro maneiras diferentes de facelo na árbore de Kenyon. Tamén é menos simétrica [7]. Pero é igualmente fermosa cá árbore de Kenyon.
Semellantes a elas mesmas arredor de calquera punto, as dúas árbores son indistinguibles a pequena escala. Aventuremos unha resposta: fainas fermosas a súa natureza repetitiva.
Tradución do billete «Graphes»
no sitio Images des Mathématiques
[1] L. Euler, Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum imperialis Petropolitanae, 8 (1736), 128-140.
[2] G. Kirchhoff, Über die Auflösung der Gleichungen, auf welche man bei der Unter-suchung der linearen Verteilung galvanischer Ströme geführt wird. Ann. Phys. Chem., 72 (1847), 497-508.
[3] A. Cayley, On the mathematical theory of isomers. Philos. Mag., 67 (1874), 444-467.
[4] Trátase dun grafo completo onde cada par de vértices está unido por unha aresta.
[5] Véxase tamén este sitio.
[6] Proposta no primeiro billete Comezo da serie.
[7] Pois non posúe ningunha simetría como árbore enraizada e só unha reflexión horizontal se esquecemos a orixe.
