Combinatorial reconstruction problems, Hopf algebras and graph posets

Abstract

A conjectura de reconstrução de vértice afirma que todo grafo simples, finito e não direcionado com três ou mais vértices é determinado, via isomorfismo, pela coleção de subgrafos vértice deletados não rotulados. A conjectura de reconstrução de aresta afirma que todo grafo simples, finito e não direcionado com quatro ou mais arestas é determinado, via isomorfismo, por sua coleção de subgrafos aresta deletados não rotulados. Nós consideramos problemas análogos de reconstruir um grafo arbitrário G, via isomorfismo, de seu poset abstrato de subgrafo aresta, o poset abstrato de subgrafo induzido e o reticulado abstrato de ligação. Mostramos que, se um grafo não tem vértices isolados, então o reticulado abstrato de ligação e o poset abstrato de subgrafo induzido podem ser construídos a partir do poset abstrato de subgrafo aresta, exceto para as famílias de grafos que caracterizamos. Nós também estudamos outras estruturas relacionadas obtidas por considerar diferentes tipos de homomorfismos (ou seja, homomorfismos em geral, monomorfismos, epimorfismos, etc.) e questões sobre construções relacionando estas estruturas (por exemplo, quais estruturas podem ser construídas de quais outras estruturas). Estas questões são motivadas pela seguinte conjectura de Thatte. Seja G o conjunto de todos os grafos não rotulados. Seja f:G->G uma bijeção tal que para todo G,H em G, o número de homomorfismos de G para H é igual ao número de homomorfismos de f(G) para f(H). Então, f é o mapa de identidade. Esta conjectura é mais fraca do que a conjectura de reconstrução de aresta.

Em seguida, construímos uma subálgebra da álgebra UGQSym estudada por Borie. Os elementos desta álgebra são séries de potência formal que podem ser avaliadas em grafos, e conta o número de ocorrências de blocos. Nesta formulação, nós obtemos uma prova algébrica de um resultado de Whitney.

Dado o baralho de um grafo G, todos subgrafos vértice próprios de G podem ser contados usando um resultado básico em reconstrução de grafos, conhecido como lemma de Kelly. Consideramos o problema de refinar o lema para contar subgrafos enraizados de modo que o vértice raiz coincida com o vértice deletado. Mostramos que tal contagem não é possível em geral, a menos que a conjectura de reconstrução de vértice é verdadeira, mas um multiconjunto de subgrafos enraizados de altura fixa k pode ser construído de um baralho de G desde que G tem raio maior que k. Nós provamos um resultado análogo para o problema de reconstrução de aresta.