On Algorithmic Study of Non-negative Posets of Corank at Most Two and their Coxeter-Dynkin Types

• Autorzy: Gąsiorek M. , Zając K.

Identyfikatory

DOI

10.3233/FI-2015-1238

• Języki publikacji: EN

Abstrakty

EN

Here we study the connected posets I that are non-negative of corank one or two, in the sense that the symmetric Gram matrix 1/2 (C_I + C_i^tr) ∊ M_n(Q) is positive semi-definite of corank one or two, where C_II ∊ M_n(Z) is the incidence matrix of I. We study such posets I by means of the Dynkin type Dyn_I and the Coxeter polynomial coxI (t) := det(t.E - Cox_I) ∊ Z[t], where Cox_I := C_I + C_I^tr ∊ M_n(Z) is the Coxeter matrix of I. Among other results, we develop an algorithmic technique that allows us to compute a complete list of such posets I, with |I| ≤ 16, their Dynkin types Dyn_I, and the Coxeter polynomials cox_I(t) ∊Z[t]. We prove that, given a pair of such connected posets I and J, the incidence matrices C_I and C_J are Z-congruent if and only if coxI (t) = coxJ (t) and Dyn_I = Dyn_J

Słowa kluczowe

EN

poset; Coxeter spectrum; Dynkin diagram; Coxeter-Dynkin type

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 139, nr 4
• Strony: 347--367
• Opis fizyczny: Bibliogr. 38 poz., rys., tab.

Twórcy

autor

Gąsiorek M.

• Faculty of Mathematics and Computer Science Nicolaus Copernicus University ul. Chopina 12/18, 87-100 Toruń, Poland

autor

Zając K.

• Faculty of Mathematics and Computer Science Nicolaus Copernicus University ul. Chopina 12/18, 87-100 Toruń, Poland

Bibliografia

• [1] Assem, I., Simson, D., Skowroński, A.: Elements of the representation theory of associative algebras. Volume 1. Techniques of representation theory, vol. 65 of London Math. Soc. Student Texts, Cambridge Univ. Press, Cambridge-New York, 2006, doi: 10.1017/CBO9780511614309.
• [2] Barot, M., de la Peña, J. A.: Derived Tubularity: a Computational Approach, in: Computational Methods for Representations of Groups and Algebras (P. Dräxler, C. Ringel, G. Michler, Eds.), vol. 173 of Progress in Mathematics, Birkhäuser Basel, 1999, 87–106, doi: 10.1007/978-3-0348-8716-8_4.
• [3] Barot, M., de la Peña, J. A.: The Dynkin type of a non-negative unit form, Exposition. Math., 17(4), 1999, 339–348.
• [4] Bocian, R., Felisiak, M., Simson, D.: Numeric and mesh algorithms for the Coxeter spectral study of positive edge-bipartite graphs and their isotropy groups, J. Comput. Appl. Math., 259 (part B), 2014, 815–827, doi:10.1016/j.cam.2013.07.013.
• [5] Brualdi, R. A.: Spectra of digraphs, Linear Algebra Appl., 432(9), 2010, 2181–2213, doi: 10.1016/j.laa.2009.02.033.
• [6] Cvetković, D., Rowlinson, P., Simić, S.: An Introduction to the Theory of Graph Spectra, vol. 75 of London Mathematical Society Student Texts, Cambridge University Press, Cambridge, 2010, doi: 110.1017/CBO9780511801518.
• [7] van Dam, E. R., Haemers, W. H.: Which graphs are determined by their spectrum?, Linear Algebra Appl., 373, 2003, 241–272, doi: 10.1016/S0024-3795(03)00483-X.
• [8] Felisiak, M., Simson, D.: On computing mesh root systems and the isotropy group for simply-laced Dynkin diagrams, Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2012, IEEE CPS, Los Alamitos, Calif. [etc.], 2012, 91–97, doi: 10.1109/SYNASC.2012.16.
• [9] Felisiak, M., Simson, D.: On combinatorial algorithms computing mesh root systems and matrix morsifications for the Dynkin diagram An, Discrete Math., 313(12), 2013, 1358–1367, doi: 10.1016/j.disc.2013.02.003.
• [10] Felisiak, M., Simson, D.: Applications of matrix morsifications to Coxeter spectral study of loop-free edgebipartite graphs, Discrete Applied Mathematics, 192, 2015, 49–64, doi: 10.1016/j.dam.2014.05.002.
• [11] Gąsiorek, M.: Efficient computation of the isotropy group of a finite graph: a combinatorial approach, Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2013, IEEE CPS, Los Alamitos, Calif. [etc.], 2014, 104–111, doi: 10.1109/SYNASC.2013.21.
• [12] Gąsiorek, M., Simson, D.: One-peak posets with positive Tits quadratic form and their mesh translation quivers of roots, and programming in Maple and Python, Linear Algebra Appl. 436, 2012, 2240–2272, doi: 10.1016/j.laa. 2011.10.045.
• [13] Gąsiorek, M., Zając, K.: List of all connected non-negative posets I of corank at most 2 with jIj < 17, 2014, http://mg.mat.umk.pl/pdf/NonNegPosetsCorankMaxTwo.zip.
• [14] Gąsiorek, M., Simson, D., Zając, K.: On Coxeter type study of non-negative posets using matrix morsifications and isotropy groups of Dynkin and Euclidean diagrams, Eur. J. Comb., 48, 2015, 127–142, doi:10.1016/j.ejc.2015.02.015.
• [15] Gąsiorek, M., Simson, D., Zając, K.: Structure and a Coxeter-Dynkin type classification of corank two nonnegative posets, Linear Algebra Appl., 469, 2015, 76–113, doi: 10.1016/j.laa.2014.11.003.
• [16] Gąsiorek, M., Simson, D., Zając, K.: On corank two edge-bipartite graphs and simply extended Euclidean diagrams, Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2014, IEEE CPS, Los Alamitos, Calif. [etc.], 2015, 66–73, doi: 10.1109/SYNASC.2014.17.
• [17] Grześkowiak, M.: Algorithms for relatively cyclotomic primes, Fund. Inform., 125(2), 2013, 161–181, doi:10.3233/FI-2013-858.
• [18] Kasjan, S., Simson, D.: Mesh algorithms for Coxeter spectral classification of Cox-regular edge-bipartite graphs with loops, I. Mesh root systems, II. Application to Coxeter spectral analysis, Fund. Inform., 139, 2015, 153–184, doi: 10.3233/FI-2015-1230.
• [19] Kosakowska, J.: Inflation algorithms for positive and principal edge-bipartite Graphs and Unit Quadratic Forms, Fund. Inform., 119(2), 2012, 149–162, doi: 10.3233/FI-2012-731.
• [20] Kaniecki, M., Kosakowska, J., Malicki, P., Marczak, G.: A horizontal mesh algorithm for a class of edgebipartite graphs and their matrix morsifications, Fund. Inform., 2015, in press.
• [21] Marczak, G., Simson, D., Zając, K.: On computing non-negative loop-free edge-bipartite graphs, Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2013, IEEE CPS, Los Alamitos, Calif. [etc.], 2014, 68–75, doi: 10.1109/SYNASC.2013.16.
• [22] Polak, A., Simson, D.: Algorithms computing O(n;Z)-orbits of P-critical edge-bipartite graphs and P-critical unit forms using Maple and C#, Algebra Discrete Math., 16(2), 2013, 1–40.
• [23] Polak, A., Simson, D.: Algorithmic experiences in Coxeter spectral study of P-critical edge-bipartite graphs and posets, Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2013, IEEE CPS, Los Alamitos, Calif. [etc.], 2014, doi: 10.1109/SYNASC.2013.56.
• [24] Polak, A., Simson, D.: Coxeter spectral classification of almost TP-critical one-peak posets using symbolic and numeric computations, Linear Algebra Appl., 445, 2014, 223–255, doi: 10.1016/j.laa.2013.12.018.
• [25] Simson, D.: Linear representations of partially ordered sets and vector space categories, vol. 4 of Algebra, Logic and Applications, Gordon and Breach Science Publishers, Montreux, 1992.
• [26] Simson, D.: Posets of finite prinjective type and a class of orders, J. Pure Appl. Algebra, 90(1), 1993, 77–103, doi: 10.1016/0022-4049(93)90138-J.
• [27] Simson, D.: Integral bilinear forms, Coxeter transformations and Coxeter polynomials of finite posets, Linear Algebra Appl., 433(4), 2010, 699–717, doi: 10.1016/j.laa.2010.03.041.
• [28] Simson, D.: Mesh algorithms for solving principal Diophantine equations, sand-glass tubes and tori of roots, Fund. Inform., 109(4), 2011, 425–462, doi: 10.3233/FI-2011-520.
• [29] Simson, D.: Mesh geometries of root orbits of integral quadratic forms, J. Pure Appl. Algebra, 215(1), 2011, 13–34, doi: 10.1016/j.jpaa.2010.02.029.
• [30] Simson, D.: Algorithms determining matrix morsifications, Weyl orbits, Coxeter polynomials and mesh geometries of roots for Dynkin diagrams, Fund. Inform., 123(4), 2013, 447–490, doi: 10.3233/FI-2013-820.
• [31] Simson, D.: A Coxeter-Gram classification of simply laced edge-bipartite graphs, SIAM J. Discrete Math., 27, 2013, 827–854, doi: 10.1137/110843721.
• [32] Simson, D.: A framework for Coxeter spectral analysis of edge-bipartite graphs, their rational morsifications and mesh geometries of root orbits, Fund. Inform., 124(3), 2013, 309–338, doi: 10.3233/FI-2013-836.
• [33] Simson, D., Zając, K.: A framework for Coxeter spectral classification of finite posets and their mesh geometries of roots, Intern. J. Math. Mathematical Sciences, Volume 2013, Article ID 743734, 22 pages, doi:10.1155/2013/743734.
• [34] Wojda, A. P.: A condition for a graph to contain k-matching, Discrete Math., 276(1-3), 2004, 375–378, doi:10.1016/S0012-365X(03)00299-1.
• [35] Zając, K.: Numeric algorithms for corank two bigraphs and their mesh geometries of roots, 2015, Fund. Inform., submitted.
• [36] Zaslavsky, T.: Signed graphs, Discrete Appl. Math., 4(1), 1982, 47–74, doi: 10.1016/0166-218X(82)90033-6.
• [37] Zhang, Y. B.: Eigenvalues of Coxeter transformations and the structure of regular components of an Auslander-Reiten quiver, Comm. Algebra, 17(10), 1989, 2347–2362, doi: 10.1080/00927878908823853.
• [38] The Polish Grid Infrastructure, http://www.plgrid.pl.