Please use this identifier to cite or link to this item: http://hdl.handle.net/1843/58291
Full metadata record
DC FieldValueLanguage
dc.contributor.advisor1Bhalchandra Digambar Thattept_BR
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/5544298698489595pt_BR
dc.contributor.referee1Csaba Schneiderpt_BR
dc.contributor.referee2Fábio Happ Botlerpt_BR
dc.contributor.referee3Monique Muller Lopes Rochapt_BR
dc.contributor.referee4Viktor Bekkertpt_BR
dc.creatorDeisiane Lopes Gonçalvespt_BR
dc.creator.Latteshttp://lattes.cnpq.br/7195754300964482pt_BR
dc.date.accessioned2023-08-28T15:26:35Z-
dc.date.available2023-08-28T15:26:35Z-
dc.date.issued2023-02-09-
dc.identifier.urihttp://hdl.handle.net/1843/58291-
dc.description.abstractA 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.pt_BR
dc.description.resumoThe 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.pt_BR
dc.description.sponsorshipCAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superiorpt_BR
dc.languageengpt_BR
dc.publisherUniversidade Federal de Minas Geraispt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.programPrograma de Pós-Graduação em Matemáticapt_BR
dc.publisher.initialsUFMGpt_BR
dc.rightsAcesso Abertopt_BR
dc.rightsAtribuição-NãoComercial-SemDerivados 3.0 Portugal*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/pt/*
dc.subjectGraph reconstructionpt_BR
dc.subjectGraph posetspt_BR
dc.subjectGraph homomorphismspt_BR
dc.subjectHopf algebraspt_BR
dc.subjectKelly's lemmapt_BR
dc.subject.otherMatemáticapt_BR
dc.subject.otherReconstrução de grafospt_BR
dc.subject.otherHomomorfismos (Matemática)pt_BR
dc.subject.otherHopf, lgebra deen
dc.titleCombinatorial reconstruction problems, Hopf algebras and graph posetspt_BR
dc.title.alternativeProblemas de reconstrução combinatória, álgebras de Hopf e posets de grafospt_BR
dc.typeTesept_BR
Appears in Collections:Teses de Doutorado

Files in This Item:
File Description SizeFormat 
THESIS (3) (1).pdf822.21 kBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons