Algorithms computing ${\rm O}(n, \mathbb{Z})$-orbits of $P$-critical edge-bipartite graphs and $P$-critical unit forms using Maple and C\#

A. Polak ; D. Simson

Algebra and discrete mathematics, Tome 16 (2013) no. 2, pp. 242-286.

Résumé

We present combinatorial algorithms constructing loop-free $P$-critical edge-bipartite (signed) graphs $\Delta'$, with $n\geq 3$ vertices, from pairs $(\Delta , w)$, with $\Delta $ a positive edge-bipartite graph having $n-1$ vertices and $w$ a sincere root of $\Delta $, up to an action $*:\mathcal{U} \mathcal{B} igr_n \times {\rm O}(n,\mathbb{Z}) \to \mathcal{U}\mathcal{B} igr_n$ of the orthogonal group ${\rm O}(n,\mathbb{Z})$ on the set $\mathcal{U} \mathcal{B} igr_n$ of loop-free edge-bipartite graphs, with $n\geq 3$ vertices. Here $\mathbb{Z}$ is the ring of integers. We also present a package of algorithms for a Coxeter spectral analysis of graphs in $\mathcal{U} \mathcal{B} igr_n$ and for computing the ${\rm O}(n, \mathbb{Z})$-orbits of $P$-critical graphs $\Delta$ in $\mathcal{U} \mathcal{B} igr_n$ as well as the positive ones. By applying the package, symbolic computations in Maple and numerical computations in C#, we compute $P$-critical graphs in $\mathcal{U} \mathcal{B} igr_n$ and connected positive graphs in $\mathcal{U} \mathcal{B} igr_n$, together with their Coxeter polynomials, reduced Coxeter numbers, and the ${\rm O}(n, \mathbb{Z})$-orbits, for $n\leq 10$. The computational results are presented in tables of Section 5.

Détail

Keywords: unit quadratic form, $P$-critical edge-bipartite graph, sincere root, algorithm, Euclidean diagram.
Mots-clés : edge-bipartite graph, Gram matrix, orthogonal group, Coxeter polynomial

Bibliographie

[1] I. Assem, D. Simson, A. Skowroński, Elements of the Representation Theory of Associative Algebras, v. 1, London Math. Soc. Student Texts, 65, Techniques of Representation Theory, Cambridge Univ. Press, Cambridge–New York, 2006 | MR | Zbl

[2] K. T. Balińska, S. K. Simić, “The nonregular, bipartite, integral graphs with maximum degree four”, Discrete Math., 236 (2001), 13–24 | DOI | MR | Zbl

[3] M. Barot, J. A. de la Peña, “The Dynkin type of a non-negative unit form”, Expo. Math., 17 (1999), 339–348 | MR | Zbl

[4] G. Belitskij, V. V. Sergeichuk, “Complexity of matrix problems”, Linear Algebra Appl., 361 (2003), 203–222 | DOI | MR

[5] V. M. Bondarenko, M. V. Stepochkina, “(Min, max)-equivalency of posets and nonnegative of the quadratic Tits forms”, Ukrain. Mat. Zh., 60 (2008), 1157–1167 | MR | Zbl

[6] V. M. Bondarenko, M. V. Stepochkina, “Description of posets with respect to the nonnegativity Tits forms”, Ukrain. Mat. Zh., 61 (2009), 734–746 | DOI | MR | Zbl

[7] R. A. Brualdi, D. M. Cvetković, Combinatorial Approach to Matrix Theory and its Application, CRS Press, Boca Raton, 2008

[8] Funct. Anal. Appl., 8 (1974), 219–225 | DOI | MR | Zbl

[9] P. Dräxler, J. A. Drozd, N. S. Golovachtchuk, S. A. Ovsienko, M. Zeldych, “Towards the classification of sincere weakly positive unit forms”, Europ. J. Combinat., 16 (1995), 1–16 | DOI | MR | Zbl

[10] P. Gabriel, A. V. Roiter, Algebra, v. VIII, Encyclopaedia of Math. Sc., 73, Representations of Finite Dimensional Algebras, Springer-Verlag, 1992 | MR | Zbl

[11] Y. Han, D. Zhao, “Superspecies and their representations”, J. Algebra, 321 (2009), 3668–3680 | DOI | MR | Zbl

[12] H. -J. von Höhne, “On weakly positive unit forms”, Comment Math. Helvetici, 63 (1988), 312–336 | DOI | MR | Zbl

[13] S. M. Johnson, “Generation of permutations by adjacent transpositions”, Math. Comp., 17 (1963), 282–285 | DOI | MR | Zbl

[14] A. Kisielewicz, M. Szykuł{a}, “Rainbow induced subgraphs in proper vertex colorings”, Fund. Inform., 111 (2011), 437–451 | DOI | MR | Zbl

[15] D. E. Knuth, The Art of Computer Programming, Fascicle 2, v. 4, Generating All Tuples and Permutations, Addison-Wesley Professional, 2005 | MR

[16] J. Kosakowska, “Inflation algorithms for positive and principal edge-bipartite graphs and unit quadratic forms”, Fund. Inform., 119 (2012), 149–162 | DOI | MR | Zbl

[17] J. Kosakowska, D. Simson, “Hereditary coalgebras and representations of species”, J. Algebra, 293 (2005), 457–505 | DOI | MR | Zbl

[18] S. Ladkani, “On the periodicity of Coxeter transformations and the non-negativity of their Euler forms”, Linear Algebra Appl., 428 (2008), 742–753 | DOI | MR | Zbl

[19] P. Lakatos, “On spectral radius of Coxeter transformation of trees”, Publ. Math., 54 (1999), 181–187 | MR | Zbl

[20] H. Lenzing, J. A. de la Peña, “Spectral analysis of finite dimensional algebras and singularities”, Trends in Representation Theory of Algebras and Related Topics, ICRA XII, Series of Congress Reports, ed. A. Skowroński, European Math. Soc. Publishing House, Zürich, 2008, 541–588 | MR | Zbl

[21] G. Marczak, A. Polak, D. Simson, “$P$-critical integral quadratic forms and positive forms. An algorithmic approach”, Linear Algebra Appl., 433 (2010), 1873–1888 | DOI | MR | Zbl

[22] S. A. Ovsienko, Integral weakly positive forms, Schur Matrix Problems and Quadratic Forms, Preprint, 78.25, Inst. Mat. Akad. Nauk USSR, 1978, 3–17 | Zbl

[23] A. Polak (Cited 1 May 2013) http://www.mat.umk.pl/ãga13/pkrytyczne.html

[24] A. Polak, D. Simson, “Symbolic and numerical computation in determining $P$-critical unit forms and Tits $P$-critical posets”, Proc. Sixth European Conference on Combinatorics, Graph Theory and Applications EuroComb2011 (Budapest, August 2011), Electronic Notes in Discrete Mathematics, 38, 2011, 723–730 | DOI | Zbl

[25] A. Polak, D. Simson, “On Coxeter spectral classification of $P$-critical edge-bipartite graphs of Euclidean type $\widetilde{\mathbb{A}}_n$”, Proc. Combinatorics 2012 (Perugia, September 2012), Electronic Notes in Discrete Mathematics, 40, 2013, 311–316 | DOI

[26] A. Polak, D. Simson, “Algorithmic experiences in Coxeter spectral study of $P$-critical edge-bipartite graphs and posets”, SYNASC 2013, IEEE CPS, Tokyo, 2013 (to appear)

[27] A. Polak, D. Simson, “Coxeter spectral classification of almost $TP$-critical one-peak posets using symbolic and numeric computations”, Linear Algebra Appl., 2014 (to appear) | DOI | MR

[28] C. M. Ringel, Tame Algebras and Integral Quadratic Forms, Lecture Notes in Math., 1099, Springer-Verlag, Berlin–Heidelberg–New York-Tokyo, 1984 | MR | Zbl

[29] M. Sato, “Periodic Coxeter matrices and their associated quadratic forms”, Linear Algebra Appl., 406 (2005), 99–108 | DOI | MR | Zbl

[30] V. V. Sergeichuk, “Canonical matrices for linear matrix problems”, Linear Algebra Appl., 317 (2000), 53–102 | DOI | MR | Zbl

[31] D. Simson, Linear Representations of Partially Ordered Sets and Vector Space Categories, Algebra, Logic and Applications, 4, Gordon Breach Science Publishers, 1992 | MR | Zbl

[32] D. Simson, “A reduction functor, tameness and Tits form for a class of orders”, J. Algebra, 174 (1995), 430–452 | DOI | MR | Zbl

[33] D. Simson, “Incidence coalgebras of intervally finite posets, their integral quadratic forms and comodule categories”, Colloq. Math., 115 (2009), 259–295 | DOI | MR | Zbl

[34] D. Simson, “Integral bilinear forms, Coxeter transformations and Coxeter polynomials of finite posets”, Linear Algebra Appl., 433 (2010), 699–717 | DOI | MR | Zbl

[35] D. Simson, “Mesh geometries of root orbits of integral quadratic forms”, J. Pure Appl. Algebra, 215 (2011), 13–34 | DOI | MR | Zbl

[36] D. Simson, “Mesh algorithms for solving principal Diophantine equations, sand-glass tubes and tori of roots”, Fund. Inform., 109 (2011), 425–520 | DOI | MR

[37] D. Simson, “Algorithms determining matrix morsifications, Weyl orbits, Coxeter polynomials and mesh geometries of roots for Dynkin diagrams”, Fund. Inform., 123 (2013), 447–490 | MR | Zbl

[38] D. Simson, “A Coxeter-Gram classification of positive simply-laced bipartite graphs and unit forms”, SIAM J. Discr. Math., 27 (2013), 827–854 | DOI | MR | Zbl

[39] D. Simson, A. Skowroński, Elements of the Representation Theory of Associative Algebras, v. 2, London Math. Soc. Student Texts, 71, Tubes and Concealed Algebras of Euclidean Type, Cambridge Univ. Press, Cambridge–New York, 2007 | MR | Zbl

[40] D. Simson, M. Wojewódzki, “An algorithmic solution of a Birkhoff type problem”, Fund. Inform., 83 (2008), 389–410 | MR | Zbl

[41] H. F. Trotter, “Perm (Algorithm 115)”, Comm. ACM, 5 (1962), 434–435 | DOI

[42] T. Zaslavsky, “Signed graphs”, Discrete Appl. Math., 4 (1982), 47–74 | DOI | MR | Zbl

[43] Y. Zhang, “Eigenvalues of Coxeter transformations and the structure of the regular components of the Auslander–Reiten quiver”, Comm. Algebra, 17 (1989), 2347–2362 | DOI | MR | Zbl