Wyniki wyszukiwania - BazTech

1

Inflation Agorithm for Cox-regular Postive Edge-bipartite Graphs with Loops

Makuracki B., Simson D., Zyglarski B.

Fundamenta Informaticae

|

2017

|

Vol. 153, nr 4

367--398

EN

We continue the study of finite connected edge-bipartite graphs Δ, with m ≥ 2 vertices (a class of signed graphs), started in [SIAM J. Discrete Math. 27(2013), 827-854] and developed in [Fund. Inform. 139(2015), 249-275, 145(2016), 19-48] by means of the non-symmetric Gram matrix ĞΔ ∊ Mn(Z) defining Δ, its symmetric Gram matrix GΔ:=1/2[ĞΔ+ĞtrΔ]∊ Mn(1/2Z), and the Gram quadratic form qΔ : Zn → Z. In the present paper we study connected positive Cox-regular edge-bipartite graphs Δ, with n ≥ 2 vertices, in the sense that the symmetric Gram matrix GΔ∊ Mn(Z) of Δ is positive definite. Our aim is to classify such Cox-regular edge-bipartite graphs with at least one loop by means of an inflation algorithm, up to the weak Gram Z-congruence Δ ~Z Δ', where Δ ~ZΔ' means that GΔ' = Btr.GΔ .B, for some B ∊ Mn(Z) such that det B = ±1. Our main result of the paper asserts that, given a positive connected Cox-regular edge-bipartite graph Δ with n ≥ 2 vertices and with at least one loop there exists a Cox-regular edge-bipartite Dynkin graph Dn ∊ {Bn, Cn, F4, G2} with loops and a suitably chosen sequence t-• of the inflation operators of one of the types Δ'↦t-aΔ' and Δ'↦t-abΔ' such that the composite operator Δ↦t-•Δ reduces Δ to the bigraph Dn such that Δ ~Z Dn and the bigraphs Δ, Dn have the same number of loops. The algorithm does not change loops and the number of vertices, and computes a matrix B ∊ Mn(Z), with det B = ±1, defining the weak Gram Z-congruence Δ ~Z Dn, that is, satisfying the equation GDn= Btr.GΔ.B.

2

Symbolic Algorithms Computing Gram Congruences in the Coxeter Spectral Classification of Edge-bipartite Graphs. [Part 2], Isotropy Mini-groups

Simson D.

Fundamenta Informaticae

|

2016

|

Vol. 145, nr 1

49--80

EN

In this two parts article with the same title we continue the Coxeter spectral study of the category UBigrm of loop-free edge-bipartite (signed) graphs Δ, with m ≥ 2 vertices, we started in [SIAM J. Discr. Math. 27(2013), 827-854] for corank r = 0 and r = 1. Here we study the class of all non-negative edge-bipartite graphs Δ ∈ UBigrn+r of corank r ≥ 0, up to a pair of the Gram Z-congruences ;~z and ≈z, by means of the non-symmetric Gram matrix ĞΔ∈Mn+r(Z) of Δ, the symmetric Gram matrix GΔ:=1/2[ĞΔ+ĞΔ-tr]∈Mn+r(Z), the Coxeter matrix CoxΔ:[formula...], its spectrum speccΔ⊂C, called the Coxeter spectrum of Δ, and the Dynkin type DynΔ∈{An,Dn,E6,E7,E8} associated in Part 1 of this paper. One of the aims in the study of the category UBigrn+r is to classify the equivalence classes of the non-negative edge-bipartite graphs in UBigrn+r with respect to each of the Gram congruences ~Z and ≈Z. In particular, the Coxeter spectral analysis question, when the congruence Δ≈ZΔ′ holds (hence also Δ~ZΔ′ holds), for a pair of connected non-negative graphs Δ,Δ′∈uBigrn+rsuch that speccΔ=speccΔ′ and DynΔ=DynΔ′, is studied in the paper. One of our main aims in this Part 2 of the paper is to get an algorithmic description of a matrix B defining the strong Gram Z-congruence Δ≈ZΔ′, that is, a Z-invertible matrix B∈Mn+r(Z) such that [formula...]. We obtain such a description for a class of non-negative connected edge-bipartite graphs Δ∈uBigrn+r of corank r = 0 and r = 1. In particular, we construct symbolic algorithms for the calculation of the isotropy mini-group ..., for a class of edge-bipartite graphs Δ∈uBigrn+r. Using the algorithms, we calculate the isotropy mini-groupGl(n,Z)D where D is any of the Dynkin bigraphs An, Bn, Cn, Dn, E6, E7, E8, F4, G2 and .D is any of the Euclidean graphs .[formula...].

3

Symbolic Algorithms Computing Gram Congruences in the Coxeter Spectral Classification of Edge-bipartite Graphs. [Part 1], A Gram Classification

Simson D.

Fundamenta Informaticae

|

2016

|

Vol. 145, nr 1

19--48

EN

We continue the Coxeter spectral study of the category UBigrm of loop-free edge-bipartite (signed) graphs Δ, with m ≥ 2 vertices, we started in [SIAM J. Discr. Math. 27(2013), 827-854] for corank r = 0 and r = 1. Here we study the class of all non-negative edge-bipartite graphs Δ ∈ UBigrn+r of corank r ≥ 0, up to a pair of the Gram Z-congruences ~ z and ≈z, by means of the non-symmetric Gram matrix GΔ∈ Mn+r(Z), the symmetric Gram matrix GΔ:=[formula..]..., the Coxeter matrix CoxΔ:=[formula...]... and its spectrum speccΔ ⊂ C, called the Coxeter spectrum of Δ. One of the aims in the study of the category UBigrn+r is to classify the equivalence classes of the non-negative edge-bipartite graphs in UBigrn+r with respect to each of the Gram congruences ~Z and ≈Z. In particular, the Coxeter spectral analysis question, when the strong congruence Δ≈ZΔ′ holds (hence also ΔZΔ′ holds), for a pair of connected non-negative graphs Δ, Δ′ ∈ UBigrn+r such that speccΔ = speccΔ′, is studied in the paper. One of our main aims is an algorithmic description of a matrix B defining the Gram Z-congruences Δ≈ZΔ′ and ΔZΔ′, that is, a Z-invertible matrix B∈Mn+r(Z) such that ..., respectively. We show that, given a connected non-negative edge-bipartite graph Δ in UBigrn+r of corank r ≥ 0 there exists a simply laced Dynkin diagram D, with n vertices, and a connected canonical r-vertex extension ... of D of corank r (constructed in Section 2) such that Δ~ZD. We also show that every matrix B defining the strong Gram Z-congruence Δ≈ZΔ′ in UBigrn+r has the form [formula...], where CΔ,CΔ′∈Mn+r(Z) are fixed Z-invertible matrices defining the weak Gram congruences Δ~Z ... and Δ′~ZD with an r-vertex extended graph ..., respectively, and B ∈Mn+r(Z) is Z-invertible matrix lying in the isotropy group ... Moreover, each of the columns k∈Zn+r of B is a root of Z, i.e., ... Algorithms constructing the set of all such matrices B are presented in case when r = 0. We essentially use our construction of a morsification reduction map ... that reduces (up to ≈Z) the study of the set UBigr... of all connected non-negative edge-bipartite graphs Δ in UBigrD such that ... to the study of G1(n+r,Z)D-orbits in the set MorD⊆G1(n+r,Z) of all matrix morsifications of the graph D.

4

Mesh Algorithms for Coxeter Spectral Classification of Cox-regular Edge-bipartite Graphs with Loops. [Part] 1, Mesh Root Systems

Kasjan S., Simson D.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 2

153--184

EN

This is the first part of our two part paper with the same title. Following our Coxeter spectral study in [Fund. Inform. [123(2013), 447-490] and [SIAM J. Discr. Math. 27(2013), 827- 854] of the category UBigrn of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, we study here the larger category RBigrn of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual Z-congruences ~Z and ≈Z. The positive graphs Δ in RBigrn, with dotted loops, are studied by means of the complex Coxeter spectrum speccΔ C C, the irreducible mesh root systems of Dynkin types Bn, n ≥ 2, Cn, n ≥ 3, F4, G2, the isotropy group Gl(n;Z)Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure A ppl. Algebra 215(2011), 13-24] and [Fund. Inform. [123(2013), 447-490]. One of our aims of the paper is to study the Coxeter spectral analysis question: "Does the congruence Δ ≈Z Δ' hold, for any pair of connected positive graphs Δ;Δ' ∊ RBigrn such that speccΔ = speccΔ' and the numbers of loops in Δ and Δ0 coincide?" We do it by a reduction to the Coxeter spectral study of the Gl(n, Z)D-orbits in the set MorD Mn(Z) of matrix morsifications of a Dynkin diagram D = DΔ ∊ UBigrn associated with Δ. In particular, we construct in the second part of the paper numeric algorithms for computing the connected positive edge-bipartite graphs Δ in RBigrn, for a fixed n ≥ 2, mesh algorithms for computing the set of all Z-invertible matrices B ∊ Gl(n;Z) definining the Z-congruence Δ ≈Z Δ', for positive graphs Δ;Δ' ∊ RBigrn, with n ≥ 2 fixed, and mesh-type algorithms for the mesh root systems Γ(RD Δ(RΔФΔ). In the first part of the paper we present an introduction to the study of Cox-regular edge-bipartite graphs Δ with dotted loops in relation with the irreducible reduced root systems and the Dynkin diagrams Bn, n ≥ 2, Cn, n ≥ 3, F4, G2. Moreover, we construct a unique ФD-mesh root system (RD,ФD) for each of the Cox-regular edge-bipartite graphs Bn, n ≥ 2, Cn, n ≥ 3, F4, calG2 of the type Bn, n ≥ 2, Cn, n ≥ 3, F4, G2, respectively. Our main inspiration for the study comes from the representation theory of posets, groups and algebras, Lie theory, and Diophantine geometry problems.

5

Mesh Algorithms for Coxeter Spectral Classification of Cox-regular Edge-bipartite Graphs with Loops [Part] 2. Application to Coxeter Spectral Analysis

Kasjan S., Simson D.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 2

185--209

EN

This is a second part of our two part paper with the same title. Following our Coxeter spectral study in [Fund. Inform. [123(2013), 447-490] and [SIAM J. Discr. Math. 27(2013), 827- 854] of the category UBigrn of loop-free edge-bipartite (signed) graphs Δ, with n = 2 vertices, we study here the larger category RBigrn of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual Z-congruences ~Z and Z. The positive graphs Δ in RBigrn, with dotted loops, are studied by means of the complex Coxeter spectrum speccΔ C, the irreducible mesh root systems of Dynkin types Bn, n = 2, Cn, n = 3, F4, G2, the isotropy group Gl(n, Z)Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure Appl. Algebra 215(2011), 13-24] and [Fund. Inform. [123(2013), 447-490]. One of our aims of our two part paper is to study the Coxeter spectral analysis question: "Does the congruence Δ Z Δ' hold, for any pair of connected positive graphs Δ,Δ' ∊ RBigrn such that speccΔ = speccΔ' and the numbers of loops in ΔandΔ' coincide?"We do it by a reduction to the Coxeter spectral study of the Gl(n, Z)D-orbits in the set MorD C Mn(Z) of matrix morsifications of a Dynkin diagram D = DΔ ∊ UBigrn associated with Δ. In this second part, we construct numeric algorithms for computing the connected positive edge-bipartite graphs Δ in RBigrn, for a fixed n = 2, mesh algorithms for computing the set of all Z-invertible matrices B ∊ Gl(n, Z) definining the Z-congruenceΔ Z Δ', for positive graphsΔ,Δ' ∊ RBigrn, with n geq2 fixed, and mesh-type algorithms for the mesh root systems Γ(R·Δ,ΦΔ). We also present a classification and a structure type results for positive Cox-regular edge-bipartite graphs Δ with dotted loops.

6

Algorithms for Isotropy Groups of Cox-regular Edge-bipartite Graphs

Kasjan S., Simson D.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 3

249--275

EN

This paper can be viewed as a third part of our paper [Fund. Inform. 2015, in press]. Following our Coxeter spectral study in [Fund. Inform. 123(2013), 447-490] and [SIAM J. Discr. Math. 27(2013), 827-854] of the category UBigrn of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, we study a larger category RBigrn of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual Z-congruences ~Z and ≈Z. The positive graphs Δ in RBigrn, with dotted loops, are studied by means of the complex Coxeter spectrum speccΔ ⊂ C, the irreduciblemesh root systems of Dynkin types Bn, n ≥ 2, Cn, n ≥ 3, F4, G2, the isotropy group G1(n, Z)Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure Appl. Algebra 215(2011), 13-24]. Here we present combinatorial algorithms for constructing the isotropy groups G1(n,Z)Δ. One of the aims of our three paper series is to develop computational tools for the study of the Zcongruence ~Z and the following Coxeter spectral analysis question: "Does the congruence Δ ≈Z Δ' holds, for any pair of connected positive graphsΔ,Δ' ∈ RBigrn such that speccΔ = speccΔ' and the numbers of loops in Δ and Δ' coincide?". For this purpose, we construct in this paper a extended inflation algorithm Δ → DΔ, with DΔ ~Z Δ, that allows a reduction of the question to the Coxeter spectral study of the G1(n,Z)D-orbits in the set MorD ⊂ Mn(Z) of matrix morsifications of the associated edge-bipartite Dynkin graph D = DΔ ∈ RBigrn. We also outline a construction of a numeric algorithm for computing the isotropy group G1(n,Z)Δ of any connected positive edge-bipartite graph Δ in RBigrn. Finally, we compute the finite isotropy group G1(n,Z)D, for each of the Cox-regular edge-bipartite Dynkin graphs D.

7

Stanisław Balcerzyk - życie i twórczość

Simson D.

Wiadomości Matematyczne

|

2014

|

T. 50, Nr 2

261--284

PL

5 marca 2015 roku minie dziesiąta rocznica śmierci Stanisława Balcerzyka (29 VI 1932 - 5 III 2005), wybitnego algebraika toruńskiego o bardzo szerokim zakresie zainteresowań naukowych, autora dwóch monografii naukowych, profesora Uniwersytetu Mikołaja Kopernika w Toruniu, wieloletniego pracownika Instytutu Matematycznego PAN w Warszawie, prezesa Polskiego Towarzystwa Matematycznego w latach 1985-1987. Zmarł w wieku 73 lat w Toruniu, gdzie spoczął na cmentarzu św. Jerzego. Był uczniem i doktorantem profesora Jerzego Marii Łosia.

8

Toroidal Algorithms for Mesh Geometries of Root Orbits of the Dynkin Diagram D4

Simson D.

Fundamenta Informaticae

|

2013

|

Vol. 124, nr 3

339--364

EN

By applying symbolic and numerical computation and the spectral Coxeter analysis technique of matrix morsifications introduced in our previous paper [Fund. Inform. 124(2013)], we present a complete algorithmic classification of the rational morsifications and their mesh geometries of root orbits for the Dynkin diagram 4 The structure of the isotropy group Gl(4, {Z})D4 of D 4 is also studied. As a byproduct of our technique we show that, given a connected loop-free positive edge-bipartite graph Δ, with n ≥ 4 vertices (in the sense of our paper [SIAM J. Discrete Math. 27(2013)]) and the positive definite Gram unit formqΔ ; Zn→Z, any positive integer d ≥ 1 can be presented as d = qΔ(v), with v Є Zn In case n = 3, a positive integer d ≥ 1 can be presented as d = qΔ(v), with v Є Zn , if and only if d is not of the form 4a(16 · b + 14), where a and b are non-negative integers.

9

Algorithms Determining Matrix Morsifications,Weyl orbits, Coxeter Polynomials and Mesh Geometries of Roots for Dynkin Diagrams

Simson D.

Fundamenta Informaticae

|

2013

|

Vol. 123, nr 4

447--490

EN

By computer algebra technique and computer computations, we solve the mesh morsification problems 1.10 and present a classification of irreducible mesh roots systems, for some of the simply-laced Dynkin diagramsΔ ∈ {An,Dn, E6, E7,E8}. The methods we use show an importance of computer algebra tools in solving difficult modern algebra problems of enough high complexity that had no solution by means of standard theoretical tools only. Inspired by results of Sato [Linear Algebra Appl. 406(2005), 99-108] and a mesh quiver description of indecomposable representations of finite-dimensional algebras and their derived categories explained in [London Math. Soc. Lecture Notes Series, Vol. 119, 1988] and [Fund. Inform. 109(2011), 425-462] (see also 5.11), given a Dynkin diagram Δ, with n vertices and the Euler quadratic form qΔ : Zn → Z, we study the set MorΔ ⊆ Mn(Z) of all morsifications of qΔ [37], i.e., the non-singular matrices A ∈ Mn(Z) such that its Coxeter matrix CoxA := −A · A−tr lies in Gl(n, Z) and qΔ(v) = v · A · vtr, for all v ∈ Zn. The matrixWeyl groupWΔ (2.13) acts on MorΔ and the determinant detA ∈ Z, the order cA ≥ 2 of CoxA (i.e. the Coxeter number), and the Coxeter polynomial coxA(t) := det(t ·E−CoxA) ∈ Z[t] are WΔ-invariant. Moreover, the finite set RqΔ = {v ∈ Zn; qΔ(v) = 1} of roots of qΔ is CoxA- invariant. The following problems are studied in the paper: (a) determine the WΔ-orbits Orb(A) of MorΔ and the set CPolΔ = {coxA(t); A ∈ MorΔ}, (b) construct a finite minimal CoxA-mesh quiver in Zn containing all CoxA-orbits of the finite set RqΔ of roots of qΔ. We prove that CPolΔ is a finite set and we construct algorithms allowing us to solve the problems for the morsifications A = [aij ] ∈ MorΔ, with |aij | ≤ 2. In this case, by computer algebra technique and computer computations, we prove that, for n ≤ 8, the number of the WΔ-orbits Orb(A) is at most 6, sΔ := |CPolΔ| ≤ 9 and, given A,A′ ∈ MorΔ and n ≤ 7, the following three conditions are equivalent: (i) A′ = Btr · A · B, for some B ∈ Gl(n, Z), (ii) coxA(t) = coxA′ (t), and (iii) cA · detA = cA′ · detA′. We also show that sΔ equals 6, 5, and 9, if Δ is the diagram E6, E7, and E8, respectively.

10

A Framework for Coxeter Spectral Analysis of Edge-bipartite Graphs, their Rational Morsifications and Mesh Geometries of Root Orbits

Simson D.

Fundamenta Informaticae

|

2013

|

Vol. 124, nr 3

309--338

EN

Following the spectral Coxeter analysis of matrix morsifications for Dynkin diagrams, the spectral graph theory, a graph coloring technique, and algebraic methods in graph theory, we continue our study of the category UBigrn of loop-free edge-bipartite (signed) graphs ∆, with n > 2 vertices, by means of the Coxeter number oa, the Coxeter spectrum specc∆ of ∆, that is, the spectrum of the Coxeter polynomial cox∆(t) ∈ Z[t] and the Z-bilinear Gram form b∆ : Zn x Zn →Z of ∆ [SIAM J. Discrete Math. 27(2013)]. Our main inspiration for the study comes from the representation theory of posets, groups and algebras, Lie theory, and Diophantine geometry problems. We show that the Coxeter spectral classification of connected edge-bipartite graphs A in UBigrn reduces to the Coxeter spectral classification of rational matrix morsifications A ∈ MorD∆ for a simply-laced Dynkin diagram D∆ associated with ∆. Given ∆ in UBigrn, we study the isotropy subgroup Gl(n, Z)∆ of Gl(n, Z) that contains the Weyl group W∆. and acts on the set Mor∆ of rational matrix morsifications A of ∆ in such a way that the map A → (speccA, det A, c∆) is Gl(n, Z)∆-invariant. It is shown that, for n < 6, specc∆ is the spectrum of one of the Coxeter polynomials listed in Tables 3.11-3.11(a) (we determine them by computer search using symbolic and numeric computation). The question, if two connected positive edge-bipartite graphs ∆, ∆' in UBigrn, with specc∆= specc∆,, are Z-bilinear equivalent, is studied in the paper. The problem if any Z-invertible matrix A ∈ Mn(Z) is Z-congruent with its transpose Atr is also discussed.

11

Mesh Algorithms for Solving Principal Diophantine Equations, Sand-glass Tubes and Tori of Roots

Simson D.

Fundamenta Informaticae

|

2011

|

Vol. 109, nr 4

425-462

EN

We study integral solutions of diophantine equations q(x) = d, where x = (x1, . . . , xn), n ≥1, d .∈Z is an integer and q : Z^n →Z is a non-negative homogeneous quadratic form. Contrary to the negative solution of the Hilbert’s tenth problem, for any such a form q(x), we give efficient algorithms describing the set Rq(d) of all integral solutions of the equation q(x) = d in a Φ_A-mesh translation quiver form. We show in Section 5 that usually the set Rq(d) has a shape of a Φ_A-mesh sand-glass tube or of a A-mesh torus, see 5.8, 5.10, and 5.13. If, in addition, the subgroup Ker q = {v ∈Z^n; q(v) = 0} of Zn is infinite cyclic, we study the solutions of the equations q(x) = 1 by applying a defect δ_A : Z^n → Z and a reduced Coxeter number čA ∈ N defined by means of a morsification b_A : Zn × Zn → Z of q, see Section 4. On this way we get a simple graphical algorithm that constructs all integral solutions in the shape of a mesh translation oriented graph consisting of Coxeter A-orbits. It turns out that usually the graph has at most three infinite connected components and each of them has an infinite band shape, or an infinite horizontal tube shape, or has a sand-glass tube shape. The results have important applications in representation theory of groups, algebras, quivers and partially ordered sets, as well as in the study of derived categories (in the sense of Verdier) of module categories and categories of coherent sheaves over algebraic varieties.

12

An Algorithmic Solution of a Birkhoff Type Problem

Simson D., Wojewódzki M.

Fundamenta Informaticae

|

2008

|

Vol. 83, nr 4

389-410

EN

We give an algorithmic solution in a simple combinatorial data of Birkhoff?s type problem studied in [22] and [25], for the category repft(I, K[t]/(tm)) of filtered I-chains of modules over the K-algebra K[t]/(tm) of K-dimension m < ?, where m ^(3) 2, I is a finite poset with a unique maximal element, and K is an algebraically closed field. The problem is to decide when the indecomposable objects of the category repft(I, K[t]/(tm)) admit a classification by means of a suitable parametrisation. A complete solution of this important problem of the modern representation theory is contained in Theorems 2.4 and 2.5. We show that repft(I, K[t]/(tm)) admits such a classification if and only if (I, m) is one of the pairs of the finite list presented in Theorem 2.4, and such a classification does not exist for repft(I, K[t]/(tm)) if and only if the pair (I, m) is bigger than or equal to one of the minimal pairs of the finite list presented in Theorem 2.5. The finite lists are constructed by producing computer accessible algorithms and computational programs written in MAPLE and involving essentially the package CREP (see Section 4). On this way the lists are obtained as an effect of computer computations. In particular, the solution we get shows an importance of the computer algebra technique and computer computations in solving difficult and important problems of modern algebra.

13

Konstrukcja pierścieni Sąsiady

Simson D.

Roczniki Polskiego Towarzystwa Matematycznego. Seria 2: Wiadomości Matematyczne

|

2005

|

[Z] 41

119-124

14

Początki toruńskiej algebry

Simson D.