Grafos e divisores.2

Nunha entrada anterior chegamos á idea de grafo de divisores de forma natural, como ferramenta para abordaxe do estudo da lonxitude dos camiños nun xogo de múltiplos e divisores que recolliamos da páxina Nrich. Así, dado o conxunto S dos n primeiros números naturais construiamos un grafo de tal xeito que se $$i,j\in S\quad \quad \quad ij\quad é\quad unha\quad aresta\quad \Longleftrightarrow \quad i|j\quad ou\quad j|i$$
O concepto de grafo de divisores pódese ampliar tomando S como calquer subconxunto finito de números enteiros. Con esta nova definición resulta que temos moitos grafos que son grafos de divisores. Por exemplo todos os posibles grafos con 5 vértices ou menos, agás un, son grafos de divisores. Non é nada complicado debuxalos todos asignándolle os números correspondentes aos vértices para comprobar que realmente son grafos de divisores. Velaquí uns poucos de exemplos (a comprobación da totalidade deles pode ser un exercicio divertido)

Unha actividade entretida para os que teñan algo de gosto pola astronomía podía ser o de indagar se as constelacións son grafos de divisores. Velaquí, por exemplo que o Setestrelo sí que o é:Se temos n vértices, o maior número de arestas que podemos establecer entre eles é un deses problemas que se resolven nas primeiras clases de combinatoria:

 son $$\left( \begin{matrix} n \\ 2 \end{matrix} \right) $$.
Tendo isto presente, verifícase o seguinte teorema:
$$Dados\quad dous\quad números\quad naturais,\quad n\quad e\quad m,\quad con\quad 0\le m\le \left( \begin{matrix} n \\ 2 \end{matrix} \right) ,\quad \\ hai\quad polo\quad menos\quad un\quad grafo\quad divisor\quad con\quad n\quad vértices\quad e\quad m\quad arestas$$

Este resultado asegura certa abundancia de grafos divisores. Tamén se sabe que todos os grafos completos K_n , K_m,n ,  as árbores e todos os grafos bipartitos son grafos de divisores. Pero tamén hai moitos outros grafos que non son divisores. O grafo cíclico C₅ non é un grafo divisor, incluso máis, ningún grafo divisor pode conter a C₅. A razón de que isto sexa así vén da transitividade da relación "ser divisor de". Así, todo grafo divisor ten asociado un grafo dirixido no que se u|v podemos establecer un arco (u,v). Se C₅ fose un grafo divisor, tería que haber tres vértices x, y, z, tales que x|y e y|z. Polo tanto x|z e debería haber unha aresta máis que as que ten C₅. De feito, ningún grafo cíclico impar de 5 ou máis vértices, pode ser un grafo divisor.

Pola contra é moi doado establecer un algoritmo que asigne valores numéricos aos vértices co fin de converter en grafos divisores todos os cíclicos pares.  Para comprobarmos que por exemplo C₆ é un grafo de divisores basta ir etiquetando, poñamos por caso, no sentido das agullas dun reloxo, un vértice si e outro non, cos primeiros primos: 2, 3, 5,.... Os vértices intermedios serán o produto dos dous adxacentes. Está claro que a paridade é o que determina que poidamos realizar esta etiquetaxe nun grafo cíclico.
Xa sabemos que C₅ non é grafo de divisores. Podemos dar referencia de moitos máis. Velaquí un par de exemplos:

Entón xurde a cuestión de caracterizar os grafos divisores. Xa sabemos que a todo grafo de divisores vaille asociado un grafo dirixido. Basta escoller os arcos a partir da relación "u divide a v". Daquela temos o seguinte resultado:

Que un grafo sexa un grafo de divisores é equivalente a que exista unha orientación que verifique a propiedade transitva [isto é, se (u,v) e (v,w) son arcos, entón (u,w) tamén o será]

Xeneralizando
Pódese ampliar novamente o concepto de grafo divisor. No canto de considerar o conxunto dos números enteiros podemos tomar un anel conmutativo calquera.
Neste contexto vai unha cuestión. Sexa K₅ o grafo completo de 5 vértices. Será un grafo de divisores? Para abordar a pregunta pensei que se podería resolver se tiñamos un anel con 5 unidades.
Sexa
$$\xi ={ e }^{ \frac { 2\pi i }{ 5 }  }=cos\frac { 2\pi  }{ 5 } +i\cdot sen\frac { 2\pi  }{ 5 }  $$ a raíz quinta da unidade. Resulta que o anel ciclotómico $$Z\left[ \xi  \right] $$ ten como unidades $$1,\xi ,{ \xi  }^{ 2 },{ \xi  }^{ 3 },{ \xi  }^{ 4 }$$ polo que o grafo divisor asociado ao conxunto destes cinco elementos é o grafo completo K₅.
Despois de pegar este chimpo vin que se podía chegar ao mesmo resultado cun grafo en Z, tomando o conxunto de vértices $$S=\left\{ 2,{ 2 }^{ 2 },{ 2 }^{ 3 },{ 2 }^{ 4 },{ 2 }^{ 5 } \right\} $$
Está claro que todos os grafos completos son divisores. A cuestión que me asaltou é se hai algún anel que dea acubillo a algún grafo divisor que non poidamos atopar en Z.

Máis?
Un concepto asociado ao dos grafos divisores é o dos grafos coprimos. Considerando o conxunto de vértices entre os enteiros, as arestas (u,v) estableceranse entre aqueles números que sexan coprimos.
Dada un grafo G calquera, seguindo o seguinte procedemento, obteremos un grafo coprimo isomorfo a G:

• Consideremos o grafo complementario G cos mesmos vértices e cuxas arestas son xusto as que non aparecen en G
• En G etiquetamos todos os vértices aillados con números primos (distintos)
• Se temos unha aresta aillada en G escolleremos outro primo p e etiquetaremos os dous vértices como p e p²
• Se temos unha compoñente de orde 3 ou más en G, asociaremos primos distintos a cada unha das súas arestas. Entón cada vértice etiquétase co produto das arestas que inciden nel.

Deste xeito podemos construir un grafo coprimo isomorfo a calquera outro dado: todos os grafos son grafos coprimos. Velaquí, como exemplo, temos o proceso de etiquetaxe de C₅.

Algunhas lecturas
Whic graphs are divisor graphs?
Bipartite divisor graphs
Divisor graph have arbitrary order and size
On the logest simple paht in a divisor graph
Further new properties of divisor graphs

Grafos e divisores.1

Do portal NRICH

Remexendo pola arañeira batín con este entretido xogo do web NRICH (enriching mathematics).   Participan dous xogadores alternativamente escollendo da grella de números da esquerda que, como se ve, contén os 100 primeiros naturais. As regras son moi sinxelas:
Regra 1.O primeiro xogador pode escoller calquera número menor que 50 (no exemplo puxen o 45).
Regra 2. O seguinte número debe ser sempre un múltiplo ou un divisor do anterior.
Finalización. Perde aquel que non poida coller ningún número máis.
O xogo pode propoñérse en calquera aula dos primeiros cursos da ESO xa que permite desenvolver o cálculo e a familiarización cos conceptos de múltiplo, divisor, número primo, número composto, coprimos,...
NRICH suxire dar novos enfoques ao xogo, como o de presentalo sen a restricción dada pola primeira regra para logo poñer en evidencia a súa necesidade se non queremos ter un xogo trivial. Tamén podemos investigar se hai algunha estratexia gañadora, ou se hai números que nos convén evitar. Claro que as posibilidades non rematan aquí. De ser moi complicada a abordaxe deste xogo, podería restrinxirse a outras versións que tiveran unha menor cantidade de números: 15, 20, 30, 50,... ou, se cadra, somos quen de aventurar que é o que sucede cando partimos de 101 números, ou 200, ..., 1000,...n,...
Tamén está a cuestión de cal é a maior cadea de números que podemos formar na grella da dereita. Por exemplo, na imaxe anterior tiñamos unha cadea de 11 números susceptible de ser ampliada. Para estudar o problema podemos ver que é o que pasa cos primeiros casos.
O problema parece que pode abordarse botando man dos grafos. Partimos dun conxunto de vértices numerados polos n primeiros números
$$S=\left\{ { v }_{ 1 },{ v }_{ 2 },{ v }_{ 3 },...{ v }_{ n } \right\}$$
Para establecermos as arestas usaremos a seguinte definición
$${ \forall i\neq j\quad v }_{ i }\quad e\quad { v }_{ j\quad  }\quad forman\quad unha\quad aresta\quad \Longleftrightarrow \quad i|j\quad ou\quad _{ \quad  }j|i$$
A un grafo así determinado podémoslle chamar grafo de divisores. No grafo de divisores dado polos cinco primeiros números está claro que a cadea máis longa que podemos formar ten unha lonxitude de 4 vértices: 3, 1, 2, 4.
Pero a pouco que pasemos dos primeiros casos, como era de esperar, o grafo vaise complicando. Para o grafo de divisores dos 13 primeiros números naturais teremos polo menos unha cadea de lonxitude 10 a seguinte: 9, 3, 6, 12, 4, 8, 1, 5, 10, 2 (ou 11, 1, 5, 10, 2, 8, 4, 12, 3, 9) que parece difícil de superar

Se lle chamamos f(n) ao valor da lonxitude da máxima cadea que podemos formar nun destes grafos de n números, acabamos de ver que f(4)=f(5)=4 e que f(13)=10. Podemos intentar obter unha táboa que nos ofreza pistas para intentar aventurar o resto dos valores de f(n). Pero a cuestión non é nada simple.
Parece ser que P. Erdös, R. Freud e N. Hegyvári estableceron que para valores de n o suficientemente grandes (nas fórmulas log indica o logaritmo neperiano):
$$f(n)\le (1-log2)n$$
Se quixeramos unha limitación inferior teriamos esta de A. D. Pollington:
$$\forall c>0\quad \exists N/n\ge N\Longrightarrow f(n)\ge n\cdot { e }^{ -(2+c)\sqrt { logn\cdot log(logn) }  }$$
O artigo de Erdös e cia. non falaba de grafos senón de permutacións a₁, a₂ ,a₃, ..., a_{n ,} dos primeiros enteiros 1,2,3,....,n. Ou máis suxerententemente, trataba das permutacións a₁, a₂,a₃, ..., a_i ,....de todos os números naturais. Concretamente dábanse resultados sobre o mínimo común múltiplo  e o máximo común divisor de dous elementos consecutivos nesas permutacións. Un dos teoremas cualificábano os propios autores de pobre resultado. Di o seguinte:
Dada unha permutación de todos os naturais a₁, a₂,a₃, ..., a_i ,....:
$$\bar { \underset { i }{ lim }  } \frac { \left[ { a }_{ i },{ a }_{ i+1 } \right]  }{ i } \ge \frac { 1 }{ 1-log2 } \simeq 3,26$$
Certamente é difícil imaxinar unha permutación  na que este límite fique dentro do ámbito da finitude.

As matemáticas son aburridas e non serven para nada

TEDxGalicia@USC - Elena Vázquez from denha on Vimeo.

A que profesor de matemáticas non lle preguntaron algunha vez sobre a utilidade do que se trataba nas clases?
Nos primeiros anos de docencia respondía falando dun clásico: o estudo das cónicas por Apolonio de Perga (III a.C.). un traballo que parecía completamente inútil ata que despois de case dous milenios Johannes Kepler (1571-1630) aplicara o coñecemento das cónicas ao estudo das traxectorias dos planetas. Efectivamente, os astros errantes movíanse en traxectorias elípticas arredor do Sol, situándose éste nun dos seus focos. A cara do alumnado nese momento era un poema. Non lle vían a utilidade ao coñecemento da primeira lei de Kepler, e confimánranse aínda máis na súa primeira opinión.
Máis recentemente faláballes da seguridade na internet. A garantía de poder facer compras seguras está fundamentada nas propiedades aritméticas. Por exemplo, a encriptación RSA parte da enorme dificultade de descompoñer números grandes (centos de cifras) en factores primos. Pode que sexa cousa miña, pero finalmente quedábame coa impresión de que cando o alumnado asentía sobre a complexidade da factorización estaban entendendo que iso de andar remexendo nos números primos era a un tempo unha lata e improdutivo. E logo non era certo que os ordenadores traballaban con programas e aplicacións? Que pinta aí o mínimo común denominador? De certo que vían o meu relato demasiado forzado.
Agora tendo a facer o mesmo que Elena Vázquez nesta conferencia. Adopto a postura de G. H. Hardy (1877-1947) no seu celebérrimo (?) libro Apoloxía dun matemático e con toda a amargura respondo que, efectivamente, as matemáticas, agás quizais para min e outros coma min que vivimos de contar catro cousas sobre elas, non serven para nada. Así que a alternativa estalles moi clara. Se o alumnado é coherente, debe abandonar calquera esforzo e asumir sen paliativos o suspenso final. No caso de seren inconsecuentes, mellor selo ata o final estudando a materia esfordamente. Con algo de fortuna estes últimos matricularanse finalmente nun sitio coma éste co fin de formar un elo máis nesta cadea dos que, non sen certo sadismo, torturamos as mentes da rapazada con problemas, fórmulas e números absolutamente inútiles e que ademais son realmente insufribles.