NDLI: A Coxeter--Gram Classification of Positive Simply Laced Edge-Bipartite Graphs

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Simson, Daniel
Copyright Year	2013
Abstract	Following the spectral graph theory, a graph coloring technique, and algebraic methods in graph theory, we study the category ${\cal U}{\cal B} igr_n$ of loop-free edge-bipartite (signed) graphs $\Delta$, with $n\geq 2$ vertices, up to $\mathbb{Z}$-congruences $\sim_\mathbb{Z}$ and $\approx_\mathbb{Z}$ (defined in the paper), by means of the Gram matrix $ \check G_\Delta \in \mathbb{M}_n(\mathbb{Z})$, the Coxeter--Gram matrix ${\rm Cox}_\Delta= - \check G_\Delta\cdot \check G_\Delta^{-tr} \in \mathbb{M}_n(\mathbb{Z})$, the spectrum $ {\bf specc}_\Delta$ of $\mbox{\rm Cox}_\Delta$, the Coxeter polynomial $\mbox{\rm cox}_\Delta(t)\in \mathbb{Z}[t]$, the Coxeter number ${\bf c}_\Delta \geq 2$, and the $\mathbb{Z}$-bilinear Gram form $b_\Delta: \mathbb{Z}^n\times \mathbb{Z}^n \to \mathbb{Z}$ of $\Delta$. Our main inspiration for the study comes from the representation theory of posets, groups and algebras, Lie theory, and Diophantine geometry problems. One of our aims is to compute the set ${\cal C}{\cal G} pol^+_n$ of all polynomials $\mbox{\rm cox}_\Delta(t)$, with positive connected graphs $\Delta$ in ${\cal U}{\cal B} igr_n$, for all $n\geq 2$, and to present a framework for a classification of graphs $\Delta$ in ${\cal U}{\cal B} igr_n$, up to the congruence $\approx_\mathbb{Z}$, by means of their Coxeter polynomials $\mbox{\rm cox}_\Delta(t)\in \mathbb{Z}[t]$ and Coxeter spectra. In particular, the Coxeter spectral analysis question, whether the congruence $\Delta\approx_\mathbb{Z}\Delta{'}$ holds, for any pair of connected positive graphs $\Delta, \Delta{'}\in {\cal U}{\cal B} igr_n$ such that ${\bf specc}_\Delta={\bf specc}_{\Delta '}$, is studied in the paper. One of our main results contains an affirmative answer to the question and a description of the finite set ${\cal C} {\cal G} pol^+_n$ for $n \leq 8$. One of the tools we apply is an inflation algorithm $ \Delta \mapsto D\Delta $ that associates with any connected positive graph $\Delta\in {\cal U}{\cal B} igr_n$ a simply laced Dynkin diagram $D\Delta$ such that $\Delta\sim_\mathbb{Z} D\Delta$, and $\mbox{\rm cox}_\Delta(t)$ and ${\bf c}_\Delta$ coincide with the Coxeter polynomial $\mbox{\rm cox}_A(t)$ and the Coxeter number ${\bf c}_A$ of a matrix morsification $A\in \mbox{\bf Mor}_{D\Delta }\subseteq\mathbb{M}_n(\mathbb{Z})$ for the diagram $D\Delta$ and, in case $n\leq 8$, all pairs ($\mbox{\rm cox}_\Delta(t),{\bf c}_\Delta$) are listed.
Starting Page	827
Ending Page	854
Page Count	28
File Format	PDF
ISSN	08954801
DOI	10.1137/110843721
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	2
Volume Number	27
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2013-05-02
Access Restriction	Subscribed
Subject Keyword	Coxeter--Gram polynomial Signed and weighted graphs Reflection and Coxeter groups matrix morsification Combinatorial aspects of representation theory Representations of quivers and partially ordered sets inflation algorithm Euclidean diagram Coxeter spectral classification Symbolic computation and algebraic computation Algorithms; complexity Quadratic and bilinear forms, inner products signed graphs Graphs and linear algebra Dynkin diagram edge-bipartite graph mesh root system
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On Coxeter Type Classification of Loop-Free Edge-Bipartite Graphs and Matrix Morsifications

A combinatorial construction for simply-laced Lie algebras

Algorithmic Experiences in Coxeter Spectral Study of P-critical Edge-Bipartite Graphs and Posets

Coxeter invariants for non-negative unit forms of Dynkin type A

A strong Gram classification of non-negative unit forms of Dynkin type A

On Computing Mesh Root Systems and the Isotropy Group for Simply-laced Dynkin Diagrams

Minuscule heaps over simply-laced, star-shaped dynkin diagrams (2002).

Semi-affine coxeter-dynkin graphs and g ⊆ su2(c) (1999).

Semi-affine Coxeter-Dynkin graphs and G ⊆ SU2(C). Dedicated to (1999)

A Coxeter--Gram Classification of Positive Simply Laced Edge-Bipartite Graphs

Similar Documents

On Coxeter Type Classification of Loop-Free Edge-Bipartite Graphs and Matrix Morsifications

A combinatorial construction for simply-laced Lie algebras

Algorithmic Experiences in Coxeter Spectral Study of P-critical Edge-Bipartite Graphs and Posets

Coxeter invariants for non-negative unit forms of Dynkin type A

A strong Gram classification of non-negative unit forms of Dynkin type A

On Computing Mesh Root Systems and the Isotropy Group for Simply-laced Dynkin Diagrams

Minuscule heaps over simply-laced, star-shaped dynkin diagrams (2002).

Semi-affine coxeter-dynkin graphs and g ⊆ su2(c) (1999).

Semi-affine Coxeter-Dynkin graphs and G ⊆ SU2(C). Dedicated to (1999)

A Coxeter--Gram Classification of Positive Simply Laced Edge-Bipartite Graphs