Propriedades fechadas menores que são explicitamente expressáveis ​​pelo MSO

19

Abaixo, o MSO denota a lógica monádica de segunda ordem de gráficos com quantificações de conjuntos de vértices e de arestas.

Seja uma pequena família fechada de gráficos. Segue-se da teoria menor do gráfico de Robertson e Seymour que é caracterizada por uma lista finita de menores proibidos. Em outras palavras, para cada gráfico , temos que G pertence a \ mathcal {F} se e somente se G exclui todos os gráficos H_i como menores.FFH1 1,H2,...,HkGGFGHEu

Como conseqüência desse fato, temos uma fórmula do MSO φF que é verdadeira no gráfico G se e somente se GF . Por exemplo, gráficos planares são caracterizados pela ausência dos gráficos K3,3 e K5 como menores e, portanto, é fácil escrever explicitamente uma fórmula MSO caracterizando gráficos planares.

O problema é que, para muitas propriedades menores e agradáveis ​​de gráficos fechados, a lista de menores proibidos é desconhecida. Portanto, embora saibamos que existe uma fórmula MSO caracterizando essa família de gráficos, talvez não saibamos o que é essa fórmula.

Por outro lado, pode ser que se consiga inventar uma fórmula explícita para uma dada propriedade sem usar o teorema menor do gráfico. Minha pergunta está relacionada a essa possibilidade.

Pergunta 1: Existe uma família menor fechada de graphs F , de forma que o conjunto de menores proibidos não seja conhecido, mas algumas fórmulas \ varphi do MSO φque caracterizam esse conjunto de gráficos são conhecidas?

Pergunta 2: Sabe-se que alguma fórmula explícita do MSO φ caracteriza algumas das seguintes propriedades?

  1. Gênero 1 (o gráfico é incorporado em um toro) (veja EDITAR abaixo)
  2. Gênero k para alguns k> 1 fixos k>1 1 (veja EDIT abaixo)
  3. k-outerplanarity para alguns k> 1 fixosk>1 1

Gostaria de receber qualquer referência ou opinião sobre este assunto. Por favor, sinta-se livre para considerar outras propriedades fechadas menores, a lista fornecida acima é apenas ilustrativa.

Obs: Por explícito, não quero dizer necessariamente pequeno. É suficiente fornecer um argumento explícito ou algoritmo mostrando como construir a fórmula que caracteriza a propriedade fornecida. Da mesma forma, no contexto desta pergunta, considero que uma família de menores proibidos é conhecida se alguém forneceu um algoritmo explícito para construir essa família.

EDIT: Encontrei um artigo de Adler, Kreutzer, Grohe, que constrói uma fórmula que caracteriza gráficos do gênero com base na fórmula que caracteriza gráficos do gênero k-1. Portanto, este artigo responde aos dois primeiros itens da questão 2. Por outro lado, isso não responde à questão 1 porque, de fato, existe um algoritmo que constrói para cada k, a família de menores proibidos que caracterizam gráficos do gênero k (consulte a seção 4.2). Portanto, essa família é "conhecida" no sentido da pergunta.k

Mateus de Oliveira Oliveira
fonte
Qualquer classe menor proibida pode ser expressa proibindo um número infinito de subgráficos para cada um dos muitos finitos menores proibidos. Você está, portanto, perguntando: existe uma classe de gráfico menos fechada, de modo que a definição infinita de MSO (implicitamente existente) que um por um proíba cada um desses infinitos subgrafos possa ser substituída por uma fórmula finita de MSO (que sabemos explicitamente)? A conjectura de Hadwiger tem essa forma, para cada , uma vez que a colorabilidade é expressável por uma fórmula finita de MSO. Se a conjectura for verdadeira, esses são os gráficos livres de K_k, mas estão abertos. ( k - 1 ) K kk(k-1 1)Kk
András Salamon
11
Eu pensaria que a incorporabilidade no toro pode ser expressa explicitamente como "o gráfico pode ser dividido em duas partes planares" ou algo desse tipo, e da mesma forma para gêneros mais altos.
Emil Jeřábek apoia Monica
Obrigado pela sugestão Emil. Encontrei um artigo que constrói a fórmula que caracteriza gráficos do gênero k com base na fórmula que caracteriza gráficos do gênero k-1. Por outro lado, isso não responde à minha pergunta. Veja a edição.
Mateus de Oliveira Oliveira
@ AndrásSalamon - é fácil expressar um menor proibido em uma expressão MSO explícita e finita. A questão é que não sabemos necessariamente quais menores proibir.
David Eppstein
@ DavidEppstein: ah, perdi isso: obrigado, então a primeira parte do meu comentário pode ser simplificada. No entanto, -Hadwiger ainda parece responder Q1? Temos um conjunto hipotético de menores para cada , mas "apenas" não possui uma prova de que menores de idade é da mesma classe que a definida pela fórmula do MSO " -colourable ". { K k } k { K k } ϕ k = ( k - 1 )k{Kk}k{Kk}ϕk=(k-1 1)
András Salamon

Respostas:

4

Eu tive uma resposta aqui envolvendo gráficos de vértice, mas falha na definição de não ter um conjunto de obstruções explícito nesta pergunta: existe um algoritmo publicado para encontrar o conjunto de obstruções, embora seja muito lento para ser executado, para que não saibamos realmente qual é o conjunto de obstruções.

Então, aqui está outra família de respostas parametrizáveis ​​sem essa falha (pelo menos, tanto quanto eu saiba). Dada uma família fechada menor , e um número inteiro , o gráfico dado tem um gráfico de cobertura -ply em ? Muito desse tipo de pergunta permanece desconhecido: em particular, a conjectura de Negami, que caracterizaria os gráficos que possuem um gráfico de cobertura planar, permanece não comprovada. E é fechado pouco, porque todas as etapas que você toma para tornar menor um de podem ser copiadas na capa.k 1 G k F GFk1 1GkFG

Para testar a existência de uma cobertura -ply de em , no MSO , execute as seguintes etapas:G F 2kGF2

  • G
  • (Eu,j)0 0Eu,j<kGEuj
  • G
  • F
David Eppstein
fonte
David, se não estou perdendo alguma coisa, Adler-Kreutzer-Grohe-2008 deu um algoritmo que calcula uma caracterização secundária excluída para appex-C, desde que você dê como entrada a caracterização secundária da classe C. Mas esse algoritmo pode ser ineficiente . Eu acho que Addler espera que a lista de menores excluídos para appex-PLANAR seja pequena e, portanto, ela esteja solicitando uma lista explícita, porque seria muito complicado construí-la usando seu algoritmo. Estou interessado em uma propriedade pela qual a fórmula MSO é conhecida, mas nenhum algoritmo para a construção de menores é conhecido.
Mateus de Oliveira Oliveira
É verdade para qualquer classe C fechada a menor que a classe de gráficos com cobertura em C é fechada a menor?
Denis
Sim. Veja a frase já na minha resposta sobre "E é fechada pouco porque ...".
David Eppstein
obrigado pela nova resposta. Não vi que a resposta tivesse sido editada até agora.
Mateus de Oliveira Oliveira