Use este identificador para citar o ir al link de este elemento: http://hdl.handle.net/1843/58291
Tipo: Tese
Título: Combinatorial reconstruction problems, Hopf algebras and graph posets
Título(s) alternativo(s): Problemas de reconstrução combinatória, álgebras de Hopf e posets de grafos
Autor(es): Deisiane Lopes Gonçalves
primer Tutor: Bhalchandra Digambar Thatte
primer miembro del tribunal : Csaba Schneider
Segundo miembro del tribunal: Fábio Happ Botler
Tercer miembro del tribunal: Monique Muller Lopes Rocha
Cuarto miembro del tribunal: Viktor Bekkert
Resumen: The vertex reconstruction conjecture asserts that every finite simple undirected graph on three or more vertices is determined, up to isomorphism, by its collection of unlabelled vertex-deleted subgraphs. The edge reconstruction conjecture asserts that every finite simple undirected graph with four or more edges is determined, up to isomorphism, by its collection of unlabelled edge-deleted subgraphs. We consider analogous problems of reconstructing an arbitrary graph G up to isomorphism from its abstract edge‐subgraph poset, its abstract induced subgraph poset and its abstract bond lattice. We show that if a graph has no isolated vertices, then its abstract bond lattice and the abstract induced subgraph poset can be constructed from the abstract edge-subgraph poset except for the families of graphs that we characterise. We also study other relational structures obtained by considering different types of homomorphisms (e.g., general homomorphisms, monomorphisms, epimorphisms, etc.) and questions about constructions relating these structures, (for example, which structures can be constructed from which other structures). These questions are motivated by the following conjecture of Thatte. Let G be the set of all unlabelled graphs. Let f:G -> G be a bijection such that for all G,H in G, the number of homomorphisms from G to H is equal to the number of homomorphisms from f(G) to f(H). Then, f is the identity map. The conjecture is weaker than the edge reconstruction conjecture. Next we construct a subalgebra of the algebra UGQSym studied by Borie. The elements of this algebra are formal power series which can be evaluated on graphs, and count occurrences of blocks. In this formulation, we obtain an algebraic proof of a result of Whitney. Given the vertex-deck of a graph G, all vertex-proper subgraphs of G can be counted using a basic result on graph reconstruction, known as Kelly's lemma. We consider the problem of refining the lemma to count rooted subgraphs such that the root vertex coincides the deleted vertex. We show that such counting is not possible in general unless the vertex reconstruction conjecture is true, but a multiset of rooted subgraphs of a fixed height k can be constructed from the vertex-deck of G provided G has radius more than k. We prove analogous result for the edge reconstruction problem.
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.
Asunto: Matemática
Reconstrução de grafos
Homomorfismos (Matemática)
Hopf, lgebra de
Idioma: eng
País: Brasil
Editor: Universidade Federal de Minas Gerais
Sigla da Institución: UFMG
Curso: Programa de Pós-Graduação em Matemática
Tipo de acceso: Acesso Aberto
Atribuição-NãoComercial-SemDerivados 3.0 Portugal
metadata.dc.rights.uri: http://creativecommons.org/licenses/by-nc-nd/3.0/pt/
URI: http://hdl.handle.net/1843/58291
Fecha del documento: 9-feb-2023
Aparece en las colecciones:Teses de Doutorado

archivos asociados a este elemento:
archivo Descripción TamañoFormato 
THESIS (3) (1).pdf822.21 kBAdobe PDFVisualizar/Abrir


Este elemento está licenciado bajo una Licencia Creative Commons Creative Commons