Reconhecimento polinomial de álgebras cluster de tipo finito
Carregando...
Data
2015-09-09
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
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.
Descrição
Citação
DIAS, 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.