Wyniki wyszukiwania - BazTech

1

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.

2

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.

3

A mesh algorithm for principal quadratic forms

Polak A.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2011

|

Vol. 11, no. 1

23--31

EN

In 1970 a negative solution to the tenth Hilbert problem, concerning the determination of integral solutions of diophantine equations, was published by Y. W. Matiyasevich. Despite this result, we can present algorithms to compute integral solutions (roots) to a wide class of quadratic diophantine equations of the form q(x) = d, where q : Z is a homogeneous quadratic form. We will focus on the roots of one (i.e., d = 1) of quadratic unit forms (q11 = ... = qnn = 1). In particular, we will describe the set of roots Rq of positive definite quadratic forms and the set of roots of quadratic forms that are principal. The algorithms and results presented here are successfully used in the representation theory of finite groups and algebras. If q is principal (q is positive semi-definite and Ker q={v ∈ Zn; q(v) = 0}= Z · h) then |Rq| = ∞. For a given unit quadratic form q (or its bigraph), which is positive semi-definite or is principal, we present an algorithm which aligns roots Rq in a Φ-mesh. If q is principal (|Rq| is less than ∞), then our algorithm produces consecutive roots in Rq from finite subset of Rq, determined in an initial step of the algorithm.