Algorytmy numeryczne w spektralnej analizie Coxetera bigrafów.

Abstract

Celem rozprawy jest rozwiązanie klasy problemów algorytmiczno-obliczeniowych (sformułowanych w pracach [48]–[50], [69]–[76]) występujących w spektralnej klasyfikacji Coxetera-Grama spójnych dodatnich prostych grafów oznakowanych, a także spójnych dodatnich krawędziowo-dwudzielnych grafów ∆ bez pętli (w skrócie bigrafów) zdefiniowanych w [70].

Rozdziały 1 oraz 2 poświęcone są krótkiemu wprowadzeniu do spektralnej analizy Coxetera grafów oznakowanych oraz klasy nieujemnych grafów krawędziowo-dwudzielnych ∆ bez pętli a także podaniu motywacji do badań nad problemami spektralnej klasyfikacji Coxetera skończonych bigrafów.

Przypomnijmy, że z dowolnym bigrafem ∆ bez pętli o skończonym zbiorze ponumerowanych n >= 1 wierzchołków, stowarzysza się jego zespolone spektrum Coxetera specc_∆ ⊆ C, tj. spektrum Z-odwracalnej macierzy Coxetera Cox_∆ := −Ǧ_∆ · Ǧ_∆^{−tr} ∈ Mn(Z), gdzie Ǧ_∆ ∈ Mn(Z) jest niesymetryczną macierzą Grama bigrafu ∆.

Jednym z celów rozprawy jest podanie klasyfikacji dodatnich grafów krawędziowo-dwudzielnych z dokładnością do silnej Z-kongruencji Grama, zdefiniowanej w pracy [70] następująco:

“∆ ≈Z ∆' ⇐⇒ Ǧ_∆' = B^tr · Ǧ_∆ · B, dla pewnej macierzy B ∈ Gl(n, Z)”.

Innym z celów rozprawy jest zbudowanie algorytmów symbolicznych i numerycznych obliczających macierz B ∈ Gl(n, Z) definiującą Z-kongruencję Grama ∆ ≈Z ∆', dla dowolnej pary bigrafów spełniających relację ∆ ≈Z ∆' (lub takich, dla których zachodzi równość specc_∆ = specc_∆' ich spektrów Coxetera).

W rozdziale 3 przedstawiamy narzędzia techniczne i algorytmiczne pozwalające zredukować rozważane problemy spektralnej klasyfikacji Coxetera-Grama do badania analogicznych problemów dla pewnego skończonego zbioru Mor_D ⊆ Mn(Z) wszystkich morsyfikacji macierzowych A (zdefiniowanego w pracach [69]–[71]) dla ustalonego jednorodnego diagramu Dynkina D ∈ {An, n >= 1, Dn, n ­>= 4, E6, E7, E8}. Zbiór Mor_D jest niezmienniczym podzbiorem zbioru macierzy Mn(Z) względem działania ∗ : Mn(Z) × Gl(n, Z)_D → Mn(Z), (A, B) |→ A ∗ B := B^tr · A · B ograniczonego do skończonej podgrupy Gl(n, Z)_D grupy liniowej Gl(n, Z), zwanej grupą izotropii diagramu D (zobacz [70]). Jednym z ważniejszych wyników tego rozdziału są autorskie algorytmy obliczające zbiór Mor_D, grupę izotropii Gl(n, Z)_D oraz zbiór Gl(n, Z)_D -orbit w Mor_D, dla dowolnego jednorodnego diagramu Dynkina D, a także wyniki tych obliczeń.

Jednym z głównych osiągnięć tej rozprawy jest przedstawiona w rozdziale 4 pełna klasyfikacja spójnych dodatnich grafów krawędziowo-dwudzielnych ∆ o co najwyżej 9-ciu wierzchołkach, z dokładnością do silnej Z-kongruencji Grama ∆ ≈Z ∆'. Udowodnione twierdzenie klasyfikacyjne orzeka, że każdy taki bigraf jest Z-kongruentny z jednym z 26 bigrafów klasyfikujących.

Rozdział 5 zawiera konstrukcje nieskończonych serii morsyfikacji A ∈ Mor_An diagramu Dynkina An, o parami różnych spektrach Coxetera, dla n >= 1.

W rozdziałach 6 oraz 7 przedstawiamy ideę redukcji badanych problemów klasyfikacyjnych do konstrukcji klasy symbolicznych algorytmów toroidalno-oczkowych konstruujących macierze B definiujące silną Z-kongruencję Grama ∆ ≈Z ∆'. W szczególności, dla klasy nieskończonych serii morsyfikacji diagramu Dynkina D = An budujemy algorytmy symboliczne konstruujące, dla dowolnej pary morsyfikacji A, A' ∈ Mor_D leżących w tej samej Gl(n, Z)_D-orbicie, pewną macierz B ∈ Gl(n, Z) taką, że A' = A ∗ B^tr.

W drugiej uzupełnionej wersji rozprawy dodaliśmy rozdział 8, w którym szacujemy złożoność obliczeniową stosowanych algorytmów.

Główne wyniki rozprawy zostały opublikowane w artykułach [8], [9], [24], [27]–[31].

The aim of this thesis is to solve class of the algorithmic and computing problems (formulated in [48]–[50], [69]–[76]) for Coxeter-Gram spectral classification of the connected positive simple signed graphs and connected positive loop-free edge-bipartite graphs ∆ (bigraphs, in short) defined in [70].

The first and the second chapter are devoted to short introduction to the Coxeter spectral analysis of the signed graphs and the class of the loop-free non-negative edge-bipartite graphs ∆. Moreover, we present a motivation for the study of Coxeter spectral analysis problems of the finite edge-bipartite graphs.

Recall that, with any loop-free bigraph ∆ with n >= 1 vertices numbered by the integers, we associate the (complex) Coxetera spectrum specc_∆ ⊆ C, i.e., the spectrum of the Z-invertible Coxeter matrix Cox_∆ := −Ǧ_∆ · Ǧ_∆^{−tr} ∈ Mn(Z), where Ǧ_∆ ∈ Mn (Z) is the non-symmetric Gram matrix of ∆.

One of the aims of this thesis is to classify positive edge-bipartite graphs, up to the Gram Z-bilinear congruence defined in [70] as follows

“∆ ≈Z ∆' ⇐⇒ Ǧ_∆' = B^tr · Ǧ_∆ · B, for some B ∈ Gl(n, Z)”.

Another issue of this thesis is to construct symbolic and numeric algorithms for computing matrix B ∈ Gl(n, Z) defining the Gram Z-bilinear congruence ∆ ≈Z ∆', for any pair of edge-bipartite graphs such that ∆ ≈Z ∆' (or their Coxeter spectra equality holds specc_∆ = specc_∆').

In the third chapter we present technical and algorithmic tools that allows a reduction of the Coxeter-Gram spectral classification problems to the analogue problems for some finite set Mor_D ⊆ Mn(Z) of matrix morsifications A (defined in [69]–[71]) of the fixed simply laced Dynkin diagram D ∈ {An, n >= 1, Dn, n >= 4, E6, E7, E8}. Set Mor_D is invariant subset of Mn(Z) under the action ∗ : Mn(Z)×Gl(n, Z)_D → Mn(Z), (A, B) |→ A∗B := B^tr ·A·B limited to isotropy group Gl(n, Z)_D of the diagram D, that is a finite subgroup of the general linear group Gl(n, Z) (see [70]). Main results of this chapter are our algorithms computing the set MorD, isotropy group Gl(n, Z)_D and the set of Gl(n, Z)_D-orbits in Mor_D, for any simply laced Dynkin diagram D. We also present results of these computer calculations.

One of the main results of this thesis is a complete classification of positive connected edge-bipartite graphs with at most nine vertices, up to the Gram Z-bilinear congruence ∆ ≈Z ∆', presented in the fourth chapter. It follows from our classification theorem that any of those bigraphs are Z-congruent with one of the 26 classifying bigraphs presented in chapter four.

The fifth chapter contains constructions of several infinite series of matrix morsification A ∈ Mor_An for the diagram An, with pairwise different Coxeter spectra, for n >= 1.

In the six and the seventh chapter we present an idea of a reduction from studied classification problems to the build class of symbolic toroidal mesh algorithms for computing matrix B ∈ Gl(n, Z) defining the Gram Z-bilinear congruence ∆ ≈Z ∆'. In particular, for a class of the infinite series of matrix morsification for Dynkin diagram D = An we build symbolic algorithms constructing some matrix B ∈ Gl(n, Z) such that A' = A ∗ B^tr , for any pair of morsifications A, A' ∈ Mor_D, that lie in the same Gl(n, Z)D -orbit.

In the second supplemented version of this thesis we added the eighth chapter in which we estimate the complexity of used algorithms.

The main results of this thesis have been published in the articles [8], [9], [24], [27]–[31].