Definições
Seja e sejam d , r e g inteiros positivos (com g > 2 r + 1 ).
Seja um gráfico finito simples, d- regular, sem direção e finito, com perímetro pelo menos g .
Deixe ser uma ordem total em V .
Para cada , deixar V v ⊆ V 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 ≤ a .
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 u → V v que preserva adjacências ( { x , y } ∈ E iff { f ( x ) , f ( y ) ) e ordem ( x ≤ y se f ( x ) ≤ f ( y ) ). Caso contrário, uma vantagem éruim.
Dizemos que é ε -boa se há pelo menos ( 1 - ε ) | E | boas arestas.
Questão
Seja . Existe um par ϵ-bom ( G , ≤ ) para qualquer ϵ > 0 e qualquer r e g (com r ≪ g )?
Observações:
Gostaria de saber a resposta para um geral , mas d = 4 é o primeiro caso não trivial.
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.
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.
Se , a resposta é "sim". Basta fazer um gráfico regular de alta circunferência.
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.
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.
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.
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 .
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.
fonte