Reconhecimento polinomial de álgebras cluster de tipo finito

Página do item simplificado
dc.contributor.advisor1Castonguay, Diane
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/4005898623592261por
dc.contributor.referee1Castonguay, Diane
dc.contributor.referee2Schiffler, Ralf
dc.contributor.referee3Dourado, Mitre Costa
dc.contributor.referee4Carvalho, Marcelo Henrique de
dc.contributor.referee5Longo, Humberto José
dc.creatorDias, Elisângela SIlva
dc.creator.Latteshttp://lattes.cnpq.br/0138908377103572por
dc.date.accessioned2015-11-03T14:30:02Z
dc.date.issued2015-09-09
dc.description.abstractCluster algebras form a class of commutative algebra, introduced at the beginning of the millennium by Fomin and Zelevinsky. They are defined constructively from a set of generating variables (cluster variables) grouped into overlapping subsets (clusters) of fixed cardinality. Since its inception, the theory of cluster algebras found applications in many areas of science, specially in mathematics. In this thesis, we study, with computational focus, the recognition of cluster algebras of finite type. In 2006, Barot, Geiss and Zelevinsky showed that a cluster algebra is of finite type whether the associated graph is cyclically oriented, i.e., all chordless cycles of the graph are cyclically oriented, and whether the skew-symmetrizable matrix associated has a positive quasi-Cartan companion. At first, we studied the two topics independently. Related to the first part of the criteria, we developed an algorithm that lists all chordless cycles (polynomial on the length of those cycles) and another that checks whether a graph is cyclically oriented and, if so, list all their chordless cycles (polynomial on the number of vertices). Related to the second part of the criteria, we developed some theoretical results and we also developed a polynomial algorithm that checks whether a quasi-Cartan companion matrix is positive. The latter algorithm is used to prove that the problem of deciding whether a skew-symmetrizable matrix has a positive quasi-Cartan companion for general graphs is in NP class. We conjecture that this problem is in NP-complete class.We show that the same problem belongs to the class of polynomial problems for cyclically oriented graphs and, finally, we show that deciding whether a cluster algebra is of finite type also belongs to this class.eng
dc.description.provenanceSubmitted by Cláudia Bueno (claudiamoura18@gmail.com) on 2015-10-29T19:17:43Z No. of bitstreams: 2 Tese - Elisângela Silva Dias - 2015.pdf: 1107380 bytes, checksum: e288bc934158fa879639c403bb15ba54 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)eng
dc.description.provenanceApproved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-11-03T14:30:02Z (GMT) No. of bitstreams: 2 Tese - Elisângela Silva Dias - 2015.pdf: 1107380 bytes, checksum: e288bc934158fa879639c403bb15ba54 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)eng
dc.description.provenanceMade available in DSpace on 2015-11-03T14:30:02Z (GMT). No. of bitstreams: 2 Tese - Elisângela Silva Dias - 2015.pdf: 1107380 bytes, checksum: e288bc934158fa879639c403bb15ba54 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-09-09eng
dc.description.resumoAs álgebras cluster formam uma classe de álgebras comutativas introduzida no início do milênio por Fomin e Zelevinsky. Elas são definidas de forma construtiva a partir de um conjunto de variáveis geradoras (variáveis cluster) agrupadas em subconjuntos sobrepostos (clusters) de cardinalidade fixa. Desde a sua criação, a teoria das álgebras cluster encontrou aplicações em diversas áreas da matemática e afins. Nesta tese, estudamos, com foco computacional, o reconhecimento das álgebras cluster de tipo finito. Em 2006, Barot, Geiss e Zelevinsky mostraram que uma álgebra cluster é de tipo finito se o grafo associado é ciclicamente orientado, isto é, todos os ciclos sem corda do grafo são ciclicamente orientados, e se a matriz antissimetrizável associada possui uma companheira quase-Cartan positiva. Em um primeiro momento, estudamos os dois tópicos de forma independente. Em relação à primeira parte do critério, elaboramos um algoritmo que lista todos os ciclos sem corda (polinomial no tamanho destes ciclos) e outro que verifica se um grafo é ciclicamente orientado e, em caso positivo, lista todos os seus ciclos sem corda (polinomial na quantidade de vértices). Relacionado à segunda parte do critério, desenvolvemos alguns resultados teóricos e elaboramos um algoritmo polinomial que verifica se uma matriz companheira quase-Cartan é positiva. Este último algoritmo é utilizado para provar que o problema de decidir se uma matriz antissimetrizável tem uma companheira quase-Cartan positiva para grafos gerais está na classe NP. Conjecturamos que este problema pertence à classe NP-completa. Mostramos que o mesmo pertence à classe de problemas polinomiais para grafos ciclicamente orientados e, por fim, mostramos que decidir se uma álgebra cluster é de tipo finito também pertence a esta classe.por
dc.description.sponsorshipFundação de Amparo à Pesquisa do Estado de Goiás - FAPEGpor
dc.formatapplication/pdf*
dc.identifier.citationDIAS, E. S. Reconhecimento polinomial de álgebras cluster de tipo finito. 2015. 123 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2015.por
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/4848
dc.languageporpor
dc.publisherUniversidade Federal de Goiáspor
dc.publisher.countryBrasilpor
dc.publisher.departmentInstituto de Informática - INF (RG)por
dc.publisher.initialsUFGpor
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)por
dc.rightsAcesso Abertopor
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectÁlgebras clusterpor
dc.subjectCiclos sem cordapor
dc.subjectGrafos ciclicamente orientáveispor
dc.subjectMatriz positivapor
dc.subjectCluster algebraseng
dc.subjectChordless cycleseng
dc.subjectCyclically orientable graphseng
dc.subjectPositive matrixeng
dc.subject.cnpqCIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAOpor
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpor
dc.thumbnail.urlhttp://repositorio.bc.ufg.br/tede/retrieve/22398/Tese%20-%20Elis%c3%a2ngela%20Silva%20Dias%20-%202015.pdf.jpg*
dc.titleReconhecimento polinomial de álgebras cluster de tipo finitopor
dc.title.alternativePolynomial recognition of cluster algebras of finite typeeng
dc.typeTesepor

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Tese - Elisângela Silva Dias - 2015.pdf
Tamanho:
1.06 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
2.11 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Doutorado em Ciência da Computação em Rede - UFMS/UFG (INF)