Submitted 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) / Approved 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) / Made 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-09 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / Cluster 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. / As á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.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/4848 |
| Date | 09 September 2015 |
| Creators | Dias, Elisângela SIlva |
| Contributors | Castonguay, Diane, Castonguay, Diane, Schiffler, Ralf, Dourado, Mitre Costa, Carvalho, Marcelo Henrique de, Longo, Humberto José |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, 600, -7712266734633644768, 8930092515683771531, 3671711205811204509, -961409807440757778 |
Page generated in 0.0024 seconds