Nós em Grafos - Departamento de Matemáticaggranja/Talentos/... · 2011-11-07 · Menor minimal...

Nós em GrafosNovos Talentos em Matemática

Joel Moreira

5 de Setembro de 2008

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 1 / 16

Definição

DefiniçãoChamamos enlace a um conjunto finito de curvas fechadas suavesem R3.

Dois enlaces dizem-se equivalentes se um pode ser deformadono outro por uma isotopia ambiente.Um enlace de uma única componente chama-se nó.

Figura: Anéis de Hopf Figura: Nó trevo

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 2 / 16

Definição

DefiniçãoChamamos enlace a um conjunto finito de curvas fechadas suavesem R3.

Dois enlaces dizem-se equivalentes se um pode ser deformadono outro por uma isotopia ambiente.Um enlace de uma única componente chama-se nó.

Figura: Anéis de Hopf Figura: Nó trevo

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 2 / 16

Definição

DefiniçãoChamamos enlace a um conjunto finito de curvas fechadas suavesem R3.

Dois enlaces dizem-se equivalentes se um pode ser deformadono outro por uma isotopia ambiente.Um enlace de uma única componente chama-se nó.

Figura: Anéis de Hopf Figura: Nó trevo

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 2 / 16

Enlaces e nós triviais

Um nó trivial é equivalente a uma circunferência.

Exemplos de nós triviais

Um enlace diz-se trivial se cada componente limita um disco nocomplementar do enlace.

Exemplos de enlaces triviais

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 3 / 16

Enlaces e nós triviais

Um nó trivial é equivalente a uma circunferência.

Exemplos de nós triviais

Um enlace diz-se trivial se cada componente limita um disco nocomplementar do enlace.

Exemplos de enlaces triviais

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 3 / 16

Projecções regulares de enlaces

No arco que passa por baixo interrompe-se o traço.

DefiniçãoUma projecção diz-se regular se não houver dois cruzamentossobrepostos no mesmo ponto do plano.

TeoremaTodo o enlace é equivalente a um que tenha uma projecção regular.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 4 / 16

Projecções regulares de enlaces

No arco que passa por baixo interrompe-se o traço.

DefiniçãoUma projecção diz-se regular se não houver dois cruzamentossobrepostos no mesmo ponto do plano.

TeoremaTodo o enlace é equivalente a um que tenha uma projecção regular.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 4 / 16

Invariantes

DefiniçãoNl(L1, L2) ∈ Z2 é o número de vezes que L1 se sobrepõe a L2

O invariante de arf de um nó N, α(N) ∈ Z2 verifica α(◦) = 0.Teorema

α(N+)− α(N−) = Nl(L1, L2).

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 5 / 16

Invariantes

DefiniçãoNl(L1, L2) ∈ Z2 é o número de vezes que L1 se sobrepõe a L2

O invariante de arf de um nó N, α(N) ∈ Z2 verifica α(◦) = 0.

Teoremaα(N+)− α(N−) = Nl(L1, L2).

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 5 / 16

Invariantes

DefiniçãoNl(L1, L2) ∈ Z2 é o número de vezes que L1 se sobrepõe a L2

O invariante de arf de um nó N, α(N) ∈ Z2 verifica α(◦) = 0.Teorema

α(N+)− α(N−) = Nl(L1, L2).

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 5 / 16

Mergulho de Grafos

DefiniçãoUm mergulho de um grafo é uma função dos seus vértices empontos de R3 e das arestas em curvas suaves que unem as imagensdos vértices correspondentes.

ObservaçõesDois mergulhos do mesmo grafo dizem-se equivalentes se umpode ser deformado no outro por uma isotopia ambiente.Todo o conjunto de ciclos disjuntos forma um enlace.Em dois mergulhos equivalentes de um grafo, os dois enlacesformado por um conjunto fixo de ciclos disjuntos são equivalentes.

TeoremaTodo o mergulho de um grafo é equivalente a um que tenha uma

projecção regular no plano.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 6 / 16

Mergulho de Grafos

DefiniçãoUm mergulho de um grafo é uma função dos seus vértices empontos de R3 e das arestas em curvas suaves que unem as imagensdos vértices correspondentes.

ObservaçõesDois mergulhos do mesmo grafo dizem-se equivalentes se umpode ser deformado no outro por uma isotopia ambiente.

Todo o conjunto de ciclos disjuntos forma um enlace.Em dois mergulhos equivalentes de um grafo, os dois enlacesformado por um conjunto fixo de ciclos disjuntos são equivalentes.

TeoremaTodo o mergulho de um grafo é equivalente a um que tenha uma

projecção regular no plano.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 6 / 16

Mergulho de Grafos

DefiniçãoUm mergulho de um grafo é uma função dos seus vértices empontos de R3 e das arestas em curvas suaves que unem as imagensdos vértices correspondentes.

ObservaçõesDois mergulhos do mesmo grafo dizem-se equivalentes se umpode ser deformado no outro por uma isotopia ambiente.Todo o conjunto de ciclos disjuntos forma um enlace.

Em dois mergulhos equivalentes de um grafo, os dois enlacesformado por um conjunto fixo de ciclos disjuntos são equivalentes.

TeoremaTodo o mergulho de um grafo é equivalente a um que tenha uma

projecção regular no plano.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 6 / 16

Mergulho de Grafos

DefiniçãoUm mergulho de um grafo é uma função dos seus vértices empontos de R3 e das arestas em curvas suaves que unem as imagensdos vértices correspondentes.

ObservaçõesDois mergulhos do mesmo grafo dizem-se equivalentes se umpode ser deformado no outro por uma isotopia ambiente.Todo o conjunto de ciclos disjuntos forma um enlace.Em dois mergulhos equivalentes de um grafo, os dois enlacesformado por um conjunto fixo de ciclos disjuntos são equivalentes.

TeoremaTodo o mergulho de um grafo é equivalente a um que tenha uma

projecção regular no plano.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 6 / 16

Mergulho de Grafos

DefiniçãoUm mergulho de um grafo é uma função dos seus vértices empontos de R3 e das arestas em curvas suaves que unem as imagensdos vértices correspondentes.

ObservaçõesDois mergulhos do mesmo grafo dizem-se equivalentes se umpode ser deformado no outro por uma isotopia ambiente.Todo o conjunto de ciclos disjuntos forma um enlace.Em dois mergulhos equivalentes de um grafo, os dois enlacesformado por um conjunto fixo de ciclos disjuntos são equivalentes.

TeoremaTodo o mergulho de um grafo é equivalente a um que tenha uma

projecção regular no plano.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 6 / 16

Menor minimal

DefiniçãoO grafo A diz-se um menor do grafo B se A pode ser obtido de umsubgrafo de B por contracções de arestas.

DefiniçãoO grafo A diz-se um menor minimal relativamente à propriedade P seA verifica P e nenhum menor próprio de A verifica P.

Por exemplo o K5 é não planar menor minimal

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 7 / 16

Menor minimal

DefiniçãoO grafo A diz-se um menor do grafo B se A pode ser obtido de umsubgrafo de B por contracções de arestas.

DefiniçãoO grafo A diz-se um menor minimal relativamente à propriedade P seA verifica P e nenhum menor próprio de A verifica P.

Por exemplo o K5 é não planar menor minimalJoel Moreira ()Nós em Grafos 5 de Setembro de 2008 7 / 16

O Problema

DefiniçãoUm grafo diz-se intrinsecamente atado quando qualquer seumergulho em R3 contém um ciclo que forma um nó não trivial.Um grafo diz-se intrinsecamente enlaçado quando qualquer seumergulho em R3 contém um par de ciclos disjuntos que formamum enlace não trivial.

ProblemaEncontrar todos os grafos intrinsecamente atados menorminimais.Encontrar todos os grafos intrinsecamente enlaçados menorminimais.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 8 / 16

O Problema

DefiniçãoUm grafo diz-se intrinsecamente atado quando qualquer seumergulho em R3 contém um ciclo que forma um nó não trivial.Um grafo diz-se intrinsecamente enlaçado quando qualquer seumergulho em R3 contém um par de ciclos disjuntos que formamum enlace não trivial.

ProblemaEncontrar todos os grafos intrinsecamente atados menorminimais.Encontrar todos os grafos intrinsecamente enlaçados menorminimais.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 8 / 16

Não planar +1

TeoremaSeja G um grafo não planar. Então G + 1 é intrinsecamente enlaçado.

LemaOs grafos K6 = K5 + 1 e K3,3,1 = K3,3 + 1 são intrinsecamente enlaçados.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 9 / 16

Não planar +1

TeoremaSeja G um grafo não planar. Então G + 1 é intrinsecamente enlaçado.

LemaOs grafos K6 = K5 + 1 e K3,3,1 = K3,3 + 1 são intrinsecamente enlaçados.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 9 / 16

Não planar +1

TeoremaSeja G um grafo não planar. Então G + 1 é intrinsecamente enlaçado.

LemaOs grafos K6 = K5 + 1 e K3,3,1 = K3,3 + 1 são intrinsecamente enlaçados.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 9 / 16

Demonstração do lema

Basta estudar as projecções no plano de K5 e K3,3

Projecções com um único cruzamento

O conjunto das arestas não adjacentes a uma aresta dada forma umciclo, em ambos os casos.

A paridade do número total de cruzamentos entre pares de arestasnão adjacentes não é alterada.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 10 / 16

Demonstração do lema

Basta estudar as projecções no plano de K5 e K3,3

Projecções com um único cruzamento

O conjunto das arestas não adjacentes a uma aresta dada forma umciclo, em ambos os casos.

A paridade do número total de cruzamentos entre pares de arestasnão adjacentes não é alterada.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 10 / 16

Demonstração do teorema

Seja V o vértice do topo.Assim há uma aresta a que passa um número ímpar de vezes porbaixo da curva f formada pelas arestas não adjacentes.a + V formam um ciclo triangular que verifica Nl(a + V , f ) = 1.

No caso geral do teorema:

Escolhemos o subgrafo S de G que origina o menor K5 ou K3,3

Conseguimos achar um caminho aberto A e um ciclo fechado Ftais que A passa um número ímpar de vezes por baixo de F .Assim Nl(A + V , F ) = 1 e temos um enlace não trivial.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 11 / 16

Demonstração do teorema

Seja V o vértice do topo.Assim há uma aresta a que passa um número ímpar de vezes porbaixo da curva f formada pelas arestas não adjacentes.a + V formam um ciclo triangular que verifica Nl(a + V , f ) = 1.

No caso geral do teorema:

Escolhemos o subgrafo S de G que origina o menor K5 ou K3,3

Conseguimos achar um caminho aberto A e um ciclo fechado Ftais que A passa um número ímpar de vezes por baixo de F .Assim Nl(A + V , F ) = 1 e temos um enlace não trivial.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 11 / 16

Operações ∆Y e Y∆

DefiniçãoSeja V um vértice de grau 3. Remover V e adicionar três arestas paraformar um triângulo é uma operação Y∆ e a operação inversa ∆Y .

Teorema (Motwani, Raghunathan e Saran, 1988)Se G′ é obtido de G por uma operação ∆Y e G é intrinsecamenteatado (enlaçado) então G′ é intrinsecamente atado (enlaçado).

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 12 / 16

Operações ∆Y e Y∆

DefiniçãoSeja V um vértice de grau 3. Remover V e adicionar três arestas paraformar um triângulo é uma operação Y∆ e a operação inversa ∆Y .

Teorema (Motwani, Raghunathan e Saran, 1988)Se G′ é obtido de G por uma operação ∆Y e G é intrinsecamenteatado (enlaçado) então G′ é intrinsecamente atado (enlaçado).

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 12 / 16

A família de Peterson

DefiniçãoUm grafo diz-se da família de Peterson se pode ser obtido do K6 poroperações ∆Y ou Y∆.

Há 7 desses grafos, incluindo o de Peterson, o K6 e o K3,3,1.

Teorema (Robertson, Seymour e Thomas, 1993)Um grafo é intrinsecamente enlaçado se e só se contém um menor nafamília de Peterson.

Este teorema resolve o problema de achar todos os grafosintrinsecamente enlaçados menor minimais, que são os da família dePeterson.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 13 / 16

A família de Peterson

DefiniçãoUm grafo diz-se da família de Peterson se pode ser obtido do K6 poroperações ∆Y ou Y∆.

Há 7 desses grafos, incluindo o de Peterson, o K6 e o K3,3,1.

Teorema (Robertson, Seymour e Thomas, 1993)Um grafo é intrinsecamente enlaçado se e só se contém um menor nafamília de Peterson.

Este teorema resolve o problema de achar todos os grafosintrinsecamente enlaçados menor minimais, que são os da família dePeterson.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 13 / 16

K7 intrinsecamente atado

Teorema (Conway e Gordon, 1983)K7 é intrinsecamente atado.

Seja S =∑

α(c) onde a soma corre todos os ciclos hamiltonianos deK7 e α(c) é o invariante de arf.

Provamos que, projectando o mergulho, mudar um cruzamento nãoaltera S usando que α(N+)− α(N−) = Nl(L1, L2) =

∑ω(ai , bj), onde

ω(ai , bj) ∈ Z2 é o número de vezes que ai passa por cima de bj .

Na soma total, cada ω(ai , bj) aparece um número par de vezes.

Vendo uma imersão arbitrária de K7 verifica-se que S = 1.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 14 / 16

K7 intrinsecamente atado

Teorema (Conway e Gordon, 1983)K7 é intrinsecamente atado.

Seja S =∑

α(c) onde a soma corre todos os ciclos hamiltonianos deK7 e α(c) é o invariante de arf.

Provamos que, projectando o mergulho, mudar um cruzamento nãoaltera S usando que α(N+)− α(N−) = Nl(L1, L2) =

∑ω(ai , bj), onde

ω(ai , bj) ∈ Z2 é o número de vezes que ai passa por cima de bj .

Na soma total, cada ω(ai , bj) aparece um número par de vezes.

Vendo uma imersão arbitrária de K7 verifica-se que S = 1.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 14 / 16

K7 intrinsecamente atado

Teorema (Conway e Gordon, 1983)K7 é intrinsecamente atado.

Seja S =∑

α(c) onde a soma corre todos os ciclos hamiltonianos deK7 e α(c) é o invariante de arf.

Provamos que, projectando o mergulho, mudar um cruzamento nãoaltera S usando que α(N+)− α(N−) = Nl(L1, L2) =

∑ω(ai , bj), onde

ω(ai , bj) ∈ Z2 é o número de vezes que ai passa por cima de bj .

Na soma total, cada ω(ai , bj) aparece um número par de vezes.

Vendo uma imersão arbitrária de K7 verifica-se que S = 1.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 14 / 16

K7 intrinsecamente atado

Teorema (Conway e Gordon, 1983)K7 é intrinsecamente atado.

Seja S =∑

α(c) onde a soma corre todos os ciclos hamiltonianos deK7 e α(c) é o invariante de arf.

Provamos que, projectando o mergulho, mudar um cruzamento nãoaltera S usando que α(N+)− α(N−) = Nl(L1, L2) =

∑ω(ai , bj), onde

ω(ai , bj) ∈ Z2 é o número de vezes que ai passa por cima de bj .

Na soma total, cada ω(ai , bj) aparece um número par de vezes.

Vendo uma imersão arbitrária de K7 verifica-se que S = 1.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 14 / 16

K7 intrinsecamente atado

Teorema (Conway e Gordon, 1983)K7 é intrinsecamente atado.

Seja S =∑

α(c) onde a soma corre todos os ciclos hamiltonianos deK7 e α(c) é o invariante de arf.

Provamos que, projectando o mergulho, mudar um cruzamento nãoaltera S usando que α(N+)− α(N−) = Nl(L1, L2) =

∑ω(ai , bj), onde

ω(ai , bj) ∈ Z2 é o número de vezes que ai passa por cima de bj .

Na soma total, cada ω(ai , bj) aparece um número par de vezes.

Vendo uma imersão arbitrária de K7 verifica-se que S = 1.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 14 / 16

Teorema de Foisy

Teorema (Joel Foisy, 2002)K3,3,1,1 é intrinsecamente atado.

Lema

O Grafo G apresentado na figura tem S =:∑

α(c) = 1 se e só seNl(L1, L3) = Nl(L2, L4) = 1

Cada Li é o ciclo decomprimento 2 formado pelasarestas A2i−1 e A2i .

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 15 / 16

Teorema de Foisy

Teorema (Joel Foisy, 2002)K3,3,1,1 é intrinsecamente atado.

Lema

O Grafo G apresentado na figura tem S =:∑

α(c) = 1 se e só seNl(L1, L3) = Nl(L2, L4) = 1

Cada Li é o ciclo decomprimento 2 formado pelasarestas A2i−1 e A2i .

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 15 / 16

Bibliografia

J. Conway, e C. Gordon, Knots and links in spatial graphs, J.Graph Theory 7 (1983), 445-453.

N. Robertson P. Seymour e R. Thomas Linkless embeddings ofgraphs in 3-space, Bulletin of the American Math. Soc., Vol 28, N.1(1993) 84-89.

J. Foisy, Intrinsically knotted graphs, J. Graphs Theory 39 (2002),178-187.

L. Kauffman, Formal Knot Theory, Mathematical Notes, 30,Princeton University Press, Princeton, NJ, 1983.

C. Adams, Knot Book, W. H. Freeman and Company, New York,1994.

Joel Moreira ()Nós em Grafos 5 de Setembro de 2008 16 / 16