Gráfico regular de alta circunferência com uma ordem total "localmente uniforme" nos nós

10

Definições

Seja e sejam d , r e g inteiros positivos (com g > 2 r + 1 ).ϵ>0drgg>2r+1

Seja um gráfico finito simples, d- regular, sem direção e finito, com perímetro pelo menos g .G=(V,E)dg

Deixe ser uma ordem total em V .V

Para cada , deixar V vV consistem dos nós que estão dentro da distância r do v em L (o caminho mais curto de v para qualquer u V v tem no máximo r arestas), e deixá- L v ser o subgráfico de G induzido por V v . Lembre-se de que assumimos que G tem uma circunferência alta; portanto G v é uma árvore. Seja v a restrição de avVVvVrvGvuVvrGvGVvGGvv .Vv

Dizemos que uma aresta é boa se ( G u , u ) e ( G v , v ) são isomórficas. Ou seja, existe uma bijeção f : V uV v que preserva adjacências ( { x , y } E iff { f ( x ) , f ( y ){u,v}E(Gu,u)(Gv,v)f:VuVv{x,y}E ) e ordem ( x y se f ( x ) f ( y ) ). Caso contrário, uma vantagem éruim.{f(x),f(y)}Exyf(x)f(y)

Dizemos que é ε -boa se há pelo menos ( 1 - ε ) | E | boas arestas.(G,)ϵ(1ϵ)|E|

Questão

Seja . Existe um par ϵ-bom ( G , ) para qualquer ϵ > 0 e qualquer r e g (com r g )?d=4ϵ(G,)ϵ>0rgrg

Observações:

  • Gostaria de saber a resposta para um geral , mas d = 4 é o primeiro caso não trivial.dd=4

  • O tamanho de não importa, desde que seja finito. Eu não preciso de uma construção de G ; mera existência ou não existência é suficiente.GG

Exemplos

  • Se , a resposta é "sim". Podemos simplesmente pegar um ciclo suficientemente longo e ordenar os nós ao longo do ciclo. Existem algumas arestas ruins perto da aresta que unem o nó maior e o menor, mas todas as outras arestas são boas: para quase todos os nós v , o par ( G v , v ) é apenas um caminho com 2 nós r + 1 em uma ordem crescente.d=2v(Gv,v)2r+1

  • Se , a resposta é "sim". Basta fazer um gráfico regular de alta circunferência.r=0

  • Se é suficientemente pequeno, a resposta é "sim" para qualquer mesmo d . Basta pegar um gráfico de grade ( d / 2 ) tridimensional (com os limites contornados para torná-lo d- regular) e ordenar os nós lexicograficamente por suas coordenadas. Novamente, temos algumas arestas ruins próximas aos limites da grade, mas podemos reduzir arbitrariamente o número de arestas ruins.gd(d/2)d

  • Se não precisar ser finito, a resposta é "sim" para qualquer d . Uma árvore infinita regular tem uma ordem total, de modo que todas as arestas sejam boas.Gd

  • Se é ímpar er é suficientemente grande, a resposta é "não". Em essência, Naor & Stockmeyer (1995) mostram que todo nó é incidente em pelo menos uma borda não boa.dr

fundo

(Esta seção pode ser pulada com segurança.)

A questão está relacionada aos fundamentos da computação distribuída e, em particular, aos algoritmos locais .

vG(Gv,v)ve={u,v}euvuv

Para muitos problemas clássicos de gráficos, sabe-se que uma ordem total não ajuda (relações muito mais fracas fornecem essencialmente a mesma quantidade de informações de quebra de simetria), mas alguns casos ainda estão abertos - e um resultado geral que cobre o caso de todas as gráficos de circunferência podem ser um avanço.

(G,)

VvV(v)N

Jukka Suomela
fonte

Respostas:

3

(G,)ϵ>0rgd

Para detalhes, consulte arXiv: 1201.6675 .

Jukka Suomela
fonte