CONTRIBUIÇÃO DOS GRAFOS (Zilderlânio)

1 INTRODUÇÃO

A principal contribuição deste trabalho está relacionada à apresentação de uma forma sistemática de obtenção de emparelhamentos de arestas de polígonos hiperbólicos regulares via grafos conduzindo a superfícies de Riemann orientadas e compactas. Em outras palavras, obtemos via grafos trivalentes, emparelhamentos para polígonos hiperbólicos regulares com 12g - 6 arestas e ângulos iguais a 2π/3, no caso em que o quociente do plano hiperbólico por um grupo Fuchsiano Γ (gerado pelo emparelhamento do polígono), , é uma superfície compacta, orientável, de gênero g, g > 2. Assim, esses polígonos estão associados a tesselação {12g - 6, 3}.

Uma das motivações para o estudo de emparelhamento de arestas de polígonos hiperbólicos que estão associados à tesselação {12g - 6, 3} é que tais tesselações fornecem empacotamentos de esferas com densidade máxima ([3] e [1]) e, portanto, estão relacionadas com a construção de códigos ótimos cuja probabilidade de erro é mínima, [2]. Um apanhado bibliográfico relacionado a tesselações e códigos pode ser encontrado na introdução do trabalho [12].

Em [6], Jorgensen-Naatanen fizeram o estudo para o caso de g = 2, mostraram que, a menos de reflexão, existem 8 formas diferentes de emparelhamento de arestas de um polígono fundamental com 18 arestas, 18, tal que a superfície correspondente S é orientável de gênero 2 e o grafo induzido formado pela fronteira de 18é um grafo trivalente com 9 arestas e 6 vértices.

Em [4] e [5], Faria e Palazzo construíram as generalizações para os 8 casos possíveis de emparelhamentos para polígonos com 18 arestas correspondentes a g = 2 na tesselação {12g - 6, 3}.

Lee Mosher, em [8], mostrou que existem 1726 tipos diferentes de emparelhamentos de polígonos fundamentais12g-6 que conduzem a superfícies de gênero 3. Se desconsiderarmos as imagens espelho desses padrões, então são essencialmente 927 padrões de emparelhamentos. Utilizando métodos semelhantes aos de [6] e considerando g = 3, Gou Nakamura em [9], através de grafos trivalentes obteve, e exibiu em seu trabalho, os 927 padrões de emparelhamentos.

Os artigos acima citados, [6] e [9], serviram como inspiração para este estudo onde através de grafos trivalentes obtemos mais emparelhamentos de arestas para polígonos hiperbólicos com 12g - 6 arestas, tais que todos os ciclos de vértices tem comprimento 3. Desse modo, o grupo Γ gerado pelo emparelhamento das arestas desses polígonos fornece, através do quociente pelo plano hiperbólico, , uma superfície de RiemannS compacta orientável de gênero g, g > 2.

Neste trabalho, nós generalizamos para g > 3 a construção de grafos trivalentes baseados nos casos B-14, B-10 e A-3, considerados por Nakamura, em [9], para g = 3. E a partir destes, obtemos os emparelhamentos de arestas para polígonos hiperbólicos regulares com 12g - 6 arestas, tal que a superfície correspondente S é fechada, orientável e compacta de gênero g, conforme veremos nas subseções 3.1, 3.2 e 3.3, respectivamente.

O presente artigo está organizado da seguinte forma. Na seção 2, apresentamos algumas definições preliminares ao desenvolvimento do trabalho. Já na seção 3, tratamos das três generalizações obtidas a partir das idéias apresentadas em [6] e [9]. Finalizamos com a conclusão na seção 4.

2 EMPARELHAMENTO DE ARESTAS E GRAFOS

Utilizaremos o modelo do disco unitário 2 para a geometria hiperbólica plana. Seja um polígono fechado convexo em 2 e seja o conjunto de todas as arestas de .

Definição 2.1. Um emparelhamento de arestas é o conjunto Φ = {γτ|τ ∈ } de isometrias que, para toda aresta τ ∈ temos,

1) existe aresta τ' ∈ com γτ(τ') = τ;

2) as isometrias γτ e γτ' satisfazem a relação γτ' = γτ-1;

3) se τ for aresta de então τ' = ∩γτ-1( ).

A definição de um grafo é apresentada a seguir.

Definição 2.2. [13, p. 5], [7, p. 3] Um grafo G consiste de um par de conjuntos (V(G),A(G)) onde V(G) é um conjunto não vazio de elementos chamados vértices de G, e A(G) é um conjunto de pares não ordenados de vértices distintos de V(G), chamados arestas de G.

Neste texto, vamos nos restringir a grafos em que o conjunto de vértices V(G) é finito. Utilizaremos caminhos em grafos conexos trivalentes, para gerar um emparelhamento de arestas de polígonos, assim seguem as definições.

Definição 2.3.

1) O grau (ou valência) de um vértice v é o número de arestas (cada laço conta duas vezes) incidentes a ele.

2) Um grafo G onde cada vértice tem o mesmo grau k é um grafo k-regular.

3) Um grafo 3-regular é chamado cúbico ou trivalente.

Definição 2.4. [6, p. 453] Dado um grafo G, uma rotação de um vértice v de G é uma permutação cíclica de todas as arestas incidentes com v.

Como os vértices tem grau 3, existem apenas duas rotações não triviais: a rotação no sentido horário e a rotação no sentido anti-horário, indicadas por um círculo preenchido (•) e por um círculo vazio (º), respectivamente, conforme [6]. O círculo preenchido (•) corresponde caminhar para a aresta da esquerda e o círculo vazio (º) corresponde caminhar para a aresta da direita([6], [9]).

A seguir, tratamos dos grafos a partir dos quais obtemos os emparelhamentos de arestas generalizados.

3 EMPARELHAMENTOS GENERALIZADOS A PARTIR DE GRAFOS

Nesta seção, apresentamos os resultados obtidos de um procedimento que deduzimos, em [10], para encontrar os emparelhamentos relacionados aos gêneros g = 2 e g = 3, apresentados em [6] e [9], respectivamente. Além disso, analisamos situações para g > 3 e obtivemos expressões generalizadas para estas situações.

Seja G um grafo trivalente conexo, imerso em uma superfície fechada S de gênero g de forma que S\G seja uma única componente conexa correspondente a um polígono fundamental . Sejam na e nv o número de arestas e de vértices de G, respectivamente. E seja f o número de faces (2-células) de S. Então, pela Fórmula da característica de Euler, temos:

Logo, se o número de arestas de G é igual a na = (12g - 6)/2 então o número de vértices de G é igual a nv = (12g - 6)/3. Assim, cortando S ao longo de G obtemos um polígono fundamental 12g-6 com 12g - 6 arestas e um emparelhamento de arestas associado.

Seja G um grafo trivalente com (12g - 6)/3 vértices e (12g - 6)/2 arestas. Para examinar se G é imerso em S, com complemento conexo, deve-se analisar se existem caminhos fechados em G. Logo, é necessário e suficiente que [6, pág. 405]:

a) caminhamos em cada aresta de G exatamente uma vez em cada sentido e;

b) não retornemos imediatamente na mesma aresta da qual viemos.

Assim, consideremos os grafos B-14, B-10 e A-3 das Figuras 1, 7 e 8, respectivamente, onde os casos g = 3 foram apresentado por Nakamura em [9] e nos serviram de inspiração para gerar os grafos de outros gêneros. Apresentaremos primeiro o caso B-14, [11].

Fonte: http://www.scielo.br/scielo.php?pid=S2179-84512014000200003&script=sci_arttextB