Algorithms computing O(n, Z)-orbits of P-critical edge-bipartite graphs and P-critical unit forms using Maple and C#
We present combinatorial algorithms constructing loop-free P-critical edge-bipartite (signed) graphs Δ′, with n ≥ 3 vertices, from pairs (Δ, w), with Δ a positive edge-bipartite graph having n-1 vertices and w a sincere root of Δ, up to an action ∗ : UBigrn × O(n, Z) → UBigrn of the orthogonal group...
Збережено в:
| Дата: | 2013 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2013
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/152352 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Algorithms computing O(n, 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. — 2013. — Vol. 16, № 2. — С. 242–286. — Бібліогр.: 43 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-152352 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1523522019-06-12T01:25:18Z Algorithms computing O(n, Z)-orbits of P-critical edge-bipartite graphs and P-critical unit forms using Maple and C# Polak, A. Simson, D. We present combinatorial algorithms constructing loop-free P-critical edge-bipartite (signed) graphs Δ′, with n ≥ 3 vertices, from pairs (Δ, w), with Δ a positive edge-bipartite graph having n-1 vertices and w a sincere root of Δ, up to an action ∗ : UBigrn × O(n, Z) → UBigrn of the orthogonal group O(n, Z) on the set UBigrn of loop-free edge-bipartite graphs, with n ≥ 3 vertices. Here Z is the ring of integers. We also present a package of algorithms for a Coxeter spectral analysis of graphs in UBigrn and for computing the O(n, Z)-orbits of P-critical graphs Δ in UBigrn 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 UBigrn and connected positive graphs in UBigrn, together with their Coxeter polynomials, reduced Coxeter numbers, and the O(n, Z)-orbits, for n ≤ 10. The computational results are presented in tables of Section 5. 2013 Article Algorithms computing O(n, 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. — 2013. — Vol. 16, № 2. — С. 242–286. — Бібліогр.: 43 назв. — англ. 1726-3255 2010 MSC:15A63, 11Y16, 68W30, 05E10 16G20, 20B40, 15A21. http://dspace.nbuv.gov.ua/handle/123456789/152352 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We present combinatorial algorithms constructing loop-free P-critical edge-bipartite (signed) graphs Δ′, with n ≥ 3 vertices, from pairs (Δ, w), with Δ a positive edge-bipartite graph having n-1 vertices and w a sincere root of Δ, up to an action ∗ : UBigrn × O(n, Z) → UBigrn of the orthogonal group O(n, Z) on the set UBigrn of loop-free edge-bipartite graphs, with n ≥ 3 vertices. Here Z is the ring of integers. We also present a package of algorithms for a Coxeter spectral analysis of graphs in UBigrn and for computing the O(n, Z)-orbits of P-critical graphs Δ in UBigrn 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 UBigrn and connected positive graphs in UBigrn, together with their Coxeter polynomials, reduced Coxeter numbers, and the O(n, Z)-orbits, for n ≤ 10. The computational results are presented in tables of Section 5. |
| format |
Article |
| author |
Polak, A. Simson, D. |
| spellingShingle |
Polak, A. Simson, D. Algorithms computing O(n, Z)-orbits of P-critical edge-bipartite graphs and P-critical unit forms using Maple and C# Algebra and Discrete Mathematics |
| author_facet |
Polak, A. Simson, D. |
| author_sort |
Polak, A. |
| title |
Algorithms computing O(n, Z)-orbits of P-critical edge-bipartite graphs and P-critical unit forms using Maple and C# |
| title_short |
Algorithms computing O(n, Z)-orbits of P-critical edge-bipartite graphs and P-critical unit forms using Maple and C# |
| title_full |
Algorithms computing O(n, Z)-orbits of P-critical edge-bipartite graphs and P-critical unit forms using Maple and C# |
| title_fullStr |
Algorithms computing O(n, Z)-orbits of P-critical edge-bipartite graphs and P-critical unit forms using Maple and C# |
| title_full_unstemmed |
Algorithms computing O(n, Z)-orbits of P-critical edge-bipartite graphs and P-critical unit forms using Maple and C# |
| title_sort |
algorithms computing o(n, z)-orbits of p-critical edge-bipartite graphs and p-critical unit forms using maple and c# |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2013 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/152352 |
| citation_txt |
Algorithms computing O(n, 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. — 2013. — Vol. 16, № 2. — С. 242–286. — Бібліогр.: 43 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT polaka algorithmscomputingonzorbitsofpcriticaledgebipartitegraphsandpcriticalunitformsusingmapleandc AT simsond algorithmscomputingonzorbitsofpcriticaledgebipartitegraphsandpcriticalunitformsusingmapleandc |
| first_indexed |
2025-07-13T02:53:28Z |
| last_indexed |
2025-07-13T02:53:28Z |
| _version_ |
1837498591922356224 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 16 (2013). Number 2. pp. 242 – 286
c© Journal “Algebra and Discrete Mathematics”
Algorithms computing O(n,Z)-orbits of
P -critical edge-bipartite graphs and P -critical
unit forms using Maple and C#
Agnieszka Polak and Daniel Simson
Abstract. We present combinatorial algorithms constructing
loop-free P -critical edge-bipartite (signed) graphs ∆′, with n ≥ 3
vertices, from pairs (∆, w), with ∆ a positive edge-bipartite graph
having n-1 vertices and w a sincere root of ∆, up to an action
∗ : UBigrn × O(n,Z) → UBigrn of the orthogonal group O(n,Z)
on the set UBigrn of loop-free edge-bipartite graphs, with n ≥ 3
vertices. Here Z is the ring of integers. We also present a package of
algorithms for a Coxeter spectral analysis of graphs in UBigrn and
for computing the O(n,Z)-orbits of P -critical graphs ∆ in UBigrn
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 UBigrn and connected positive graphs
in UBigrn, together with their Coxeter polynomials, reduced Coxeter
numbers, and the O(n,Z)-orbits, for n ≤ 10. The computational
results are presented in tables of Section 5.
1. Introduction
Throughout, we denote by N the set of non-negative integers, by Z
the ring of integers, and by Q ⊂ R ⊂ C the field of the rational, real, and
the complex numbers, respectively. We view Zn, with n ≥ 1, as a free
The research is supported by Polish Research Grant NCN 2011/03/B/ST1/00824
2010 MSC: 15A63, 11Y16, 68W30, 05E10 16G20, 20B40, 15A21.
Key words and phrases: edge-bipartite graph, unit quadratic form, P -critical
edge-bipartite graph, Gram matrix, sincere root, orthogonal group, algorithm, Coxeter
polynomial, Euclidean diagram.
A. Polak, D. Simson 243
abelian group. We denote by e1, . . . , en the standard Z-basis of Zn. Given
n ≥ 1, we denote by Mn(Z) the Z-algebra of all square n by n matrices,
and by E ∈ Mn(Z) the identity matrix.
Following some ideas of the spectral graph theory [7], the graph coloring
techniques [2] and [14], and of the unit quadratic forms investigation given
in [3], [5]-[6], [9], [12], [21]-[22], [28], [29], [36], [40], we study in [38] the
category of loop-free edge-bipartite (signed [42]) graphs ∆ by means of
the Coxeter spectrum of ∆, that is, the finite set specc∆ ⊂ C of all
complex roots of the Coxeter polynomial cox∆(t) ∈ Z[t] of ∆, see Section
2. In particular, we are interested in an orthogonal and Coxeter spectral
classification of positive and non-negative loop-free edge-bipartite graphs
∆ (in the sense of Definition 1.1). In the present paper we study in details
P -critical loop-free edge-bipartite graphs ∆, by applying a technique
developed in [5]-[6], [21], [22], [35]–[38]. In this case, the Coxeter spectrum
specc∆ of ∆ is a subset of the unit circle and consists of roots of unity.
Our main inspiration for the study comes from the representation
theory of posets (see [5], [8], [28], [31]-[32], [40]), groups and algebras (see
[1], [16]-[19], [29], [39]), Lie theory, and Diophantine geometry problems,
see [35]-[37].
Our motivation comes also from the fact that positive (and non-
negative) edge-bipartite graphs, P -critical graphs, positive unit forms,
and P -critical forms (and their positive roots) have important applications
in the study of indecomposable representations of posets, tame algebras,
tame vector space categories and tame bimodule matrix problems, see
[1], [4], [8], [10], [20], [22], [28], [30]–[34], [39]. [43].
Here we use the terminology and notation introduced in [38]. In
particular, by an edge-bipartite graph (bigraph, in short) we mean a
pair ∆ = (∆0, ∆1), where ∆0 is a finite non-empty set of vertices and
∆1 is a finite set of edges equipped with a disjoint union bipartition
∆1 = ∆−
1 ∪ ∆+
1 such that the set
∆1(i, j) = ∆−
1 (i, j) ∪ ∆+
1 (i, j)
of edges connecting the vertices i and j does not contain edges lying
in ∆−
1 (i, j) ∩ ∆+
1 (i, j), for each pair of vertices i, j ∈ ∆0, and either
∆1(i, j) = ∆−
1 (i, j) or ∆1(i, j) = ∆+
1 (i, j). Note that the edge-bipartite
graph ∆ can be viewed as signed multi-graph satisfying a separation
property, see [38] and [42].
We define an edge-bipartite graph ∆ = (∆0, ∆1) to be simply-laced if
(b1) the set ∆1(i, j) contains at most one edge, for each pair of
vertices i, j ∈ ∆0, and
244 P -critical edge-bipartite graphs
(b2) ∆1(j, j) is empty, for any j ∈ ∆0, that is, ∆ is loop-free.
We say that ∆ has no isolated loop if |∆−
1 (j, j)| 6= 1, for j = 1, . . . , n. If
∆ has no loop, we call it loop-free.
We visualize ∆ as a (multi-)graph in a Euclidean space Rm, m ≥ 2,
with the vertices numbered by the integers 1, . . . , n; usually, we simply
write ∆0 = {1, . . . , n}. Any edge in ∆−
1 (i, j) is visualised as a continuous
one •i−−− •j , and any edge in ∆+
1 (i, j) is visualised as a dotted one •i- - -•j .
We view any finite graph ∆ = (∆0, ∆1) as an edge-bipartite one by
setting ∆−
1 (i, j) = ∆1(i, j) and ∆+
1 (i, j) = ∅, for each pair of vertices
i, j ∈ ∆0.
We denote by Bigrn the category of finite edge-bipartite graphs, with
n ≥ 2 vertices, and usual edge-bipartite graph maps as morphisms, see
[38] for details. We denote by UBigrn the full subcategory of Bigrn whose
objects are the loop-free edge-bipartite graphs.
Following the representation theory of finite-dimensional K-algebras
over an algebraically closed field K (see [1], [8],[31], [39]) and the mesh-
geometry study of roots of integral unit quadratic forms described in
[35]–[37], the edge-bipartite graphs ∆ ∈ UBigrn are studied in [38] by
means of the Coxeter(-Gram) transformation Φ∆ : Zn → Zn (and its
spectral properties, compare with [7]) associated with the non-symmetric
adjacency matrix Ď∆ and the non-symmetric Gram matrix Ǧ∆ of
∆ defined as follows.
Definition 1.1 (see [38]). Let ∆ = (∆0, ∆1) be an edge-bipartite graph in
Bigrn, with ∆0 = {a1, . . . , an}, n ≥ 1, and the bipartition ∆1 = ∆−
1 ∪ ∆+
1 .
(a) The non-symmetric adjacency matrix Ď∆ and the
non-symmetric Gram matrix Ǧ∆ of ∆ are defined to be the square
matrices
Ď∆ =
d∆
11 d∆
12 . . . d∆
1n
0 d∆
22 . . . d∆
2n
.
.
.
.
.
.
.
.
.
.
.
.
0 0 . . . d∆
nn
, Ǧ∆ =E+Ď∆ =
1 + d∆
11 d∆
12 . . . d∆
1n
0 1 + d∆
22 . . . d∆
2n
.
.
.
.
.
.
.
.
.
.
.
.
0 0 . . . 1 + d∆
nn
where d∆
ij = −|∆−
1 (ai, aj)|, if there is an edge ai−−− aj and i ≤ j,
d∆
ij = |∆+
1 (ai, aj)|, if there is an edge ai- - -aj and i ≤ j. We set d∆
ij = 0,
if ∆1(ai, aj) is empty or j < i.
(b) The matrix G∆ := 1
2(Ǧ∆ + Ǧtr
∆) is called the symmetric Gram
matrix of ∆. By the symmetric adjacency matrix (or, signed adja-
cency matrix, see [42]) of ∆ ∈ UBigrn we mean the symmetric matrix
Ad∆ := Ď∆ + Ďtr
∆ ∈ Mn(Z).
A. Polak, D. Simson 245
The spectrum of ∆ ∈ UBigrn is defined to be the set spec∆ ⊂ R of n
real eigenvalues of the symmetric matrix Ad∆ ∈ Mn(Z) (see [42]), i.e.,
the set of all n roots of the polynomial
P∆(t) = det(t · E − Ad∆) ∈ Z[t],
called the characteristic polynomial of the edge-bipartite graph ∆.
(c) ∆ = (∆0, ∆1) is defined to be positive (resp. non-negative), if
the symmetric Gram matrix G∆ := 1
2(Ǧ∆ + Ǧtr
∆) of ∆ is positive definite
(resp. positive semi-definite).
(d) We define ∆ to be P -critical, if ∆ has no loop, is not positive,
and any proper full (induced) edge-bipartite subgraph of ∆ is positive.
Any edge-bipartite graph ∆ = (∆0, ∆1) ∈ UBigrn, with ∆1 = ∆−
1 ∪ ∆+
1 ,
is uniquely determined by its non-symmetric adjacency matrix Ď∆ and
its non-symmetric Gram matrix Ǧ∆.
If ∆ is simply-laced, we have d∆
11 = . . . = d∆
nn = 0, d∆
ij = −1, if i < j
and there is an edge ai−−− aj , and d∆
ij = 1, if i < j and there is an edge
ai- - -aj .
Throughout this paper, for simplicity of the presentation, we assume
that ∆0 = {1, . . . , n}, that is, a1 = 1, . . . , an = n.
In Sections 2 and 3, we study in details P -critical edge-bipartite
graphs ∆, by applying unit quadratic form results obtained in [21] and
[22]. In particular, in Theorem 2.8 we give a useful characterization of
P -critical edge-bipartite graphs, and we present an algorithm in the form
(∆, w) 7→ ∆[[w]] that associates to any pair (∆, w), with ∆ ∈ UBigrn
positive, w = (w1, . . . , wn) ∈ Zn its sincere root (i.e., w · G∆ · wtr = 1
and w1 6= 0, . . . , wn 6= 0), a P -critical edge-bipartite graph ∆[[w]] in
UBigrn+1. We show that the map (∆, w) 7→ ∆[[w]] is invariant under
the orthogonal group action O(n,Z) × UBigrn → UBigrn (2.1), and any
P -critical edge-bipartite graph ∆′ in UBigrn+1 has the form ∆′ = ∆[[w]].
We also present a package of algorithms for a Coxeter spectral analysis
of graphs in UBigrn and for computing the O(n,Z)-orbits of P -critical
graphs ∆ in UBigrn, 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 UBigrn, the connected positive ones, their
unit quadratic forms, their Coxeter polynomials, and the O(n,Z)-orbits,
for n ≤ 10. The computing results are presented in tables of Section 5.
Main results of the paper are announced in [24]-[25] and were presented
at the Sixth European Conference on Combinatorics, Graphs Theory and
Applications, EuroComb′11, Budapest, August 2011, and at International
246 P -critical edge-bipartite graphs
Conference Combinatorics 2012, Perugia, September 2012, see also [26].
Some applications of the results presented here are given in [27].
2. Preliminaries
Given n ≥ 1, we denote by
Gl(n,Z) = {A ∈ Mn(Z); det A ∈ {−1, 1}} ⊂ Mn(Z)
the group of Z-invertible matrices with integer coefficients, and by
O(n,Z) = {B ∈ Mn(Z); B · Btr = E}
its subgroup formed by the orthogonal matrices. Recall from [36] that
O(n,Z) is generated by:
• the diagonal matrices ε̂(j) = diag(1, . . . , 1, −1j , 1, . . . , 1) ∈ Mn(Z),
where 1 ≤ j ≤ n, −1j = −1 is the jth coordinate of the vector
ε(j) = diag(1, . . . , 1, −1j , 1, . . . , 1), and
• the permutation matrices σ̂ = Mσ, where σ ∈ Sn is a permutation
of the set {1, . . . , n}.
We define the right action
∗ : Bigrn × O(n,Z) −−−−→ Bigrn (2.1)
of the orthogonal group O(n,Z) on Bigrn as follows. Let ∆ = (∆0, ∆1)
be an edge-bipartite graph in Bigrn, with n ≥ 2.
(i) If ε̂(j) = diag(1, . . . , 1, −1j , 1, . . . , 1), where 1 ≤ j ≤ n, we define
∆∗ε̂(j) to be the graph in Bigrn obtained from ∆ by replacing every dotted
edge •i- - -•j , with i 6= j, by a continuous one, and every continuous edge
•s−−− •j , with s 6= j, by a dotted one. The remaining edges (in particular
the loops at j) remain unchanged.
(ii) If σ̂ = Mσ is a permutation matrix defined by σ ∈ Sn, we define
∆ ∗ σ̂ to be the the graph in Bigrn obtained from ∆ by the permutation
σ−1 of the vertices of ∆ as well as the corresponding edges between them.
It is shown in [38] that (i) and (ii) uniquely define the action (2.1), be-
cause every matrix B ∈ O(n,Z) has a unique decomposition
B = σ̂ · ε̂, where σ̂ ∈ Ŝn := {σ̂ ∈ O(n,Z); σ ∈ Sn} and ε̂ is a finite
product of matrices of the type ε̂(j), see [36, Lemma 2.3].
It is easy to see that the full subcategories SLBigrn and UBigrn of
Bigrn, whose objects are the simply-laced edge-bipartite graphs and the
loop-free edge-bipartite graphs, are O(n,Z)-invariant.
A. Polak, D. Simson 247
Assume that ∆ has no isolated loop. The Coxeter polynomial of
∆ is the characteristic polynomial
cox∆(t) = det(t · E − Cox∆) (2.2)
of the Coxeter matrix
Cox∆ := −Ǧ∆ · Ǧ−tr
∆ ∈ Gl(n,Z)
of ∆. The group automorphism Φ∆ : Zn → Zn defined by the formula
Φ∆(v) = v · Cox∆ is called the Coxeter transformation of ∆, compare
with Drozd [8]. The set specc∆ ⊆ C of n complex eigenvalues of Φ∆ is
called the Coxeter spectrum of ∆. The order c∆ of Cox∆ in Gl(n,Z)
is called the Coxeter number of ∆. In other words, c∆ is a minimal
integer c ≥ 1 such that Coxc
∆ = E. If there is no such integer, we set
c∆ = ∞.
It is shown in [38] that the matrices Ǧ∆, Cox∆, the Coxeter polynomial
cox∆(t), and the Coxeter number c∆ depend on the numbering of the
vertices of the bigraph ∆. Moreover, the Coxeter spectrum specc∆ of ∆
is a subset of the unit circle, if ∆ is non-negative and loop-free.
We associate with ∆ ∈ UBigrn the Gram forms q∆ : Zn → Z and
b∆ : Zn × Zn → Z defined by the formula
q∆(x) = x · Ǧ∆ · xtr = x2
1 + · · · + x2
n +
∑
i<j d∆
ijxixj ,
b∆(x, y) = x · Ǧ∆ · ytr.
(2.3)
The set of roots of ∆ (and of q∆) is defined to be the set
R∆ = {v ∈ Zn; q∆(v) = 1}. The set Ker q∆ = {v ∈ Zn; q∆(v) = 0}
is called the kernel of q∆.
In the study of the subcategory UBigrn of Bigrn consisting of the loop-
free edge-bipartite graphs ∆, we essentially use the results on unit integral
quadratic forms obtained in [3], [9], [12], [21]-[22], [28]-[29], [33]-[36], [39].
For this purpose we recall some definitions.
A unit integral quadratic form is a map q : Zn −−−→ Z, n ≥ 1, defined
by the formula
q(x) = q(x1, . . . , xn) = x2
1 + . . . + x2
n +
∑
i<jqijxixj , (2.4)
where qij ∈ Z, for i < j. Obviously, q is uniquely determined by its
non-symmetric Gram matrix
Ǧq =
1 q12 . . . q1n
0 1 . . . q2n
...
...
. . .
...
0 0 . . . 1
∈ Mn(Z) (2.5)
248 P -critical edge-bipartite graphs
and by the symmetric Gram matrix Gq = 1
2 [Ǧq + Ǧtr
q ] of q, because
q(x) = x · Ǧq · xtr = x · Gq · xtr, where Ǧtr
q means the transpose of
Ǧq and x = (x1, . . . , xn) ∈ Zn. The polar form of q is the symmetric
Z-bilinear form bq : Zn × Zn −−−→ 1
2 · Z defined by the formula
bq(x, y) = x · Gq · ytr =
1
2
[q(x + y) − q(x) − q(y)],
where the vectors x = (x1, . . . , xn), y = (y1, . . . , yn) ∈ Zn are viewed as
one-row matrices, and we set ytr =
[
y1
.
.
.
yn
]
.
We call q positive (resp. non-negative) if q(v) > 0 (resp. q(v) ≥ 0),
for all non-zero vectors v ∈ Zn. A vector v ∈ Zn is said to be a q-root
(of unity), if q(v) = v · Gq · vtr = 1. A vector v = (v1, . . . , vn) ∈ Zn is said
to be sincere, if v1 6= 0, . . . , vn 6= 0. We say that v is positive, if v 6= 0
and v1 ≥ 0, . . . , vn ≥ 0. Given v = (v1, . . . , vn) ∈ Zn and s ∈ {1, . . . , n},
we set
v(s) := (v1, . . . , vs−1, vs+1, . . . , vn) ∈ Zn−1.
Given n ≥ 1, we denote by U(Zn,Z) the set of all unit forms q : Zn → Z.
We recall from [36, Section 2], that the Coxeter(-Gram) polyno-
mial of q : Zn → Z is the characteristic polynomial
coxq(t) := det(t · E − Coxq) ∈ Z[t]
of the Coxeter(-Gram) matrix
Coxq := −Ǧq · Ǧ−tr
q .
The Coxeter number of q is the order cq of the matrix Coxq in the
group Gl(n,Z), i.e., a minimal integer c ≥ 1 such that Coxc
q = E. If there
is no such integer, we set cq = ∞.
To any unit form q : Zn → Z, we associate in [36, Section 2] an
edge-bipartite graph bigr(q) of q with the vertices 1, . . . , n as follows.
Two vertices s 6= j are joined by |qsj | continuous edges •s−−− •j if qsj < 0,
and by qsj dotted edges •s- - -•j if qsj > 0. There is no edge between
s and j, if qsj = 0, or s = j. We say that q is connected if the graph
bigr(q) is connected.
We recall from [36] that a unit form q : Zn → Z, with n ≥ 2, is defined
to be P -critical (critical with respect to the positivity) if q is not positive,
and each of the restrictions
q(1), . . . , q(n) : Zn−1 → Z
A. Polak, D. Simson 249
of q is positive, where q(j) = q|xj=0. The form q : Zn −−→Z is defined to
be principal if q is non-negative and Ker q = {v ∈ Zn; q(v) = 0} is an
infinite cyclic subgroup of Zn.
Positive unit forms, P -critical unit forms and their roots are essentially
applied in the representation theory of finite-dimensional algebras R,
coalgebras C, and their derived categories Db(mod R), see [1], [11], [17],
[31]–[35], [39], [43]. They are mainly used as a computational tool for
determining the representation type (finite, tame, wild) of an algebra
R and in a combinatorial description of the Auslander-Reiten quiver
Γ(mod R) of its module category mod R, see [1], [10], [31], [34]-[35],
[39]-[40], and [43].
Given a ∈ ∆0, we denote by ∆(a) the edge-bipartite graph obtained
from ∆ by removing the vertex a together with all edges •i- - - -•a and
•a−−− •j connected with a.
In the study of the category UBigrn, the following result is of impor-
tance, see also [38].
Proposition 2.6. The correspondence ∆ 7→ q∆ defines a bijection
q• : UBigrn
1−1
−−−−→ U(Zn,Z) (2.7)
with the following properties:
(a) Ǧq∆
= Ǧ∆, Gq∆
= G∆, Rq∆
= R∆, Coxq∆
= Cox∆, cq∆
= c∆,
and coxq∆
(t) = cox∆(t),
(b) an edge bipartite graph ∆ ∈ UBigrn is positive (resp. non-negative,
principal, P -critical) if and only if the unit form q∆ : Zn → Z is positive
(resp. non-negative, principal, P -critical).
Proof. It is easy to see that q
(a)
∆ = q∆(a) , for a = 1, . . . , n. In view of [38,
Lemma 2.1], the unit form q∆ is P -critical if and only if ∆ is not positive
and the edge bipartite graphs ∆(1), . . . , ∆(n) are positive, or equivalently,
every full edge-bipartite subgraph ∆′ of ∆ is positive, apply [38, Lemma
2.1(c)] and its proof. The remaining properties of q• follow by applying
the foregoing definitions.
Throughout the paper, we often use the bijection (2.7) as an identifica-
tion ∆ ≡ q∆. In particular, we often describe the bigraph ∆ by presenting
its unit form q∆, or the matrix Ǧ∆.
Now we are able to present a useful characterization of P -critical
edge-bipartite graphs.
250 P -critical edge-bipartite graphs
Theorem 2.8. Assume that ∆ is a loop-free edge-bipartite graph in
UBigrn, with n ≥ 3. The following four conditions are equivalent.
(a) ∆ is P -critical.
(b) The bigraph ∆ is non-negative and the free abelian group
Ker q∆ = {v ∈ Zn, q(v) = 0} is infinite cyclic generated by a sincere
vector h∆ = (h1, . . . , hn), such that −6 ≤ hj ≤ 6, for all j ∈ {1, . . . , n},
and hs ∈ {−1, 1}, for some s ∈ {1, . . . , n}.
(c) The set R∆ := {v ∈ Zn; q∆(v) = 1} of roots of ∆ is infinite, and
each of the subbigraphs ∆(1), . . . , ∆(n) of ∆ has only finitely many roots.
(d) There exist a Euclidean diagram D∆ ∈ {Ãn−1, D̃n−1, Ẽ6, Ẽ7, Ẽ8},
see (5.1), and a group isomorphism T : Zn → Zn such that q∆ ◦ T is the
quadratic form qD∆ : Zn → Z, n = |D∆0|, of the diagram D∆ and T
carries a sincere vector h′ ∈ Ker qD∆ to a sincere vector in Ker q∆.
Proof. Since we have q
(a)
∆ = q∆(a) , for a = 1, . . . , n, then R
q
(a)
∆
= R∆(a) .
On the other hand, by Proposition 2.6, ∆ is P -critical if and only if the
unit form q∆ is P -critical. Then the equivalence of (a)–(d) follows by
applying [21, Theorem 2.3] and [38].
In the classification of P -critical unit forms q ∈ U(Zn,Z), we use the
right action
∗ : U(Zn,Z) × O(n,Z) −−−−−→ U(Zn,Z) (2.9)
(defined in [36, Section 2]), that associates to q ∈ U(Zn,Z) and B ∈ O(n,Z)
the unit form q ∗ B : Zn → Z by setting (q ∗ B)(x) = q(x · Btr), for x ∈ Zn
(see also [21]). It is easy to see that the action (2.9) coincides with the
action (2.1) under the identification q• : UBigrn
1−1
−→ U(Zn,Z) (2.7).
By [36, Lemma 2.3], the group O(n,Z) is generated by the following
two subgroups:
• the group Ĉn
2 of all matrices ε̂ = ε · E, where E ∈ Mn(Z) is the
identity matrix and ε = (ε1, . . . , εn) ∈ Cn
2 runs through all vectors
with coefficients ε1, . . . , εn ∈ C2 = {−1, 1}, the cyclic group of order
two, and
• the group Ŝn of all matrices σ̂ = Mσ of the group homomorphisms
σ : Zn → Zn given by the permutation σ ∈ Sn and defined by
σ(x) = x · M tr
σ = (xσ(1), . . . , xσ(n)), where Sn is the symmetric
group of order n!.
A. Polak, D. Simson 251
Moreover, every matrix B ∈ O(n,Z) has a unique form B = σ̂ · ε̂, with
σ̂ ∈ Ŝn and ε̂ ∈ Ĉn
2 , the group O(n,Z) is finite of order |O(n,Z)| = n! · 2n,
and O(n,Z) admits the semi-direct product decomposition O(n,Z) =
Ŝn ⋊ Ĉn
2 , with respect to the right group action • : Ĉn
2 × Ŝn → Ĉn
2 of Ŝn
on the group Ĉn
2 defined by the formula ε̂•σ̂ = diag(εσ−1(1), . . . , εσ−1(n)).
Note that ε̂ · σ̂ = σ̂ · (ε̂•σ̂), for all ε̂ ∈ Ĉn
2 and σ̂ ∈ Ŝn.
It follows from the description of O(n,Z) given above that q ∗ B ∈
U(Zn,Z), if q ∈ U(Zn,Z) and B ∈ O(n,Z). It is easy to see that the
set P -crit(Zn,Z) of all P -critical unit forms q : Zn → Z, and the set
posit(Zn,Z) of all positive unit forms q : Zn → Z are O(n,Z)-invariant
subsets of U(Zn,Z).
Following [21] and [38], we investigate recursive algorithmic procedures
that construct all O(n,Z)-orbits of the P -critical bigraphs and O(n,Z)-
orbits in P -crit(Zn,Z), for n ≥ 3. We do it by applying the following
correspondence
inds,εs : Zn−1 −−−−→ P -crit(Zn,Z), (p, w) 7→ q := qp,s,w,εs (2.10)
defined by the formula (3.2), from the set
Zn−1 ={(p, w); p ∈ posit(Zn−1,Z), w∈Zn−1 a sincere root of p},(2.11)
to the set P -crit(Zn,Z) of all P -critical unit forms q : Zn → Z. We show
that inds,εs (2.10) defines a surjective map
ind : O(n-1,Z)-Orb(Zn−1) −−−−−→ O(n,Z)-Orb(P -crit(Zn,Z)),
with n ≥ 3, between the set of O(n-1,Z)-orbits in Zn−1 and the set of
O(n,Z)-orbits in P -crit(Zn,Z). By applying a package of algorithms
presented in Section 4, symbolic computations in Maple, and numerical
computations in C#, we compute in Section 5 all P -critical unit forms
q : Zn → Z, together with their Coxeter-Gram polynomials and the
O(n,Z)-orbits, for n ≤ 10.
Under the identification q• : UBigrn−1
1−1
−→ U(Zn−1,Z) (2.7), we can
identify the set Zn−1 with the set
Z ′
n−1 ={(∆, w); ∆ ∈ UBigrn−1 positive, w∈Zn−1 a sincere root of ∆},
(2.12)
n ≥ 3, and the correspondence inds,εs (2.10) can be viewed as a map
inds,εs : Z ′
n−1 −−−−→ UBigrn, (∆, w) 7→ ∆[[w, s, εs]], (2.13)
see (3.6). It follows from our next result that ∆[[w, s, εs]] is a P -critical
bigraph.
252 P -critical edge-bipartite graphs
A connection between P -critical bigraphs and positive ones, and
between P -critical unit forms and positive ones is given by the following
result proved in [21, Section 3], see also [12].
Proposition 2.14. Assume that q : Zn → Z is a P -critical unit form
(2.4), with n ≥ 3, Ker q = Z · h and s ∈ {1, . . . , n} is such that hs ∈
{−1, 1}.
(a) The vector h(s) := (h1, . . . , hs−1, hs+1, . . . hn) ∈ Zn−1 is a sincere
root of the positive unit form q(s) : Zn−1 → Z.
(b) The form q can be reconstructed from the triple (q(s), s, h(s)) by
the formula q(x) = q(s)(x(s)) + x2
s − 2 · bq(s)(x(s), h(s)) · hs · xs, where
x(s) = (x1, . . . , xs−1, xs+1, . . . , xn) ∈ Zn−1 and bq(s) is the symmetric
bilinear polar form of q(s)(x(s)) = q(s)(x1, . . . , xs−1, xs+1, . . . xn).
3. Main theorem and main algorithm
For n ≥ 3, the correspondence inds,εs : Zn−1 −−−−−→ P -crit(Zn,Z)
(2.10) between positive unit forms p : Zn−1 → Z, with a sincere root,
and P -critical forms q : Zn → Z, and the correspondence (2.13) between
positive loop-free bigraphs ∆, with a sincere root, and P -critical bigraphs
are described in the following theorem (its proof is outlined in [21]).
Theorem 3.1. (a) Given n ≥ 3, s ∈ {0, 1, . . . , n − 1}, εs ∈ {−1, 1}, a
positive connected loop-free bigraph ∆ ∈ UBigrn−1, with the unit form
p := q∆ : Zn−1 → Z and a sincere root w = (w1, . . . , wn−1) ∈ Zn−1 of ∆
and of p := q∆, the bigraph ∆′ corresponding via (2.7) to the unit form
q∆′ := qp,s,w,εs : Zn → Z defined by the formula
q(x) := q∆′(x1, . . . , xn) = p(x(s)) + x2
s − 2 · bp(x(s), w) · εs · xs, (3.2)
is P -critical and Ker q∆′ = Z · ŵεs, where bp : Zn−1 × Zn−1 → Z is the
symmetric polar form of p and ŵεs =(w1, . . . , ws−1, εs, ws, . . . wn−1)∈Zn.
(b)The set Zn−1 (2.11) is an O(n,Z)-invariant subset of
posit(Zn−1,Z) × Zn−1 under the action (p, w) ∗ B := (p ∗ B, w · B),
with B ∈ O(n,Z). The map (p, w) 7→ inds,εs(p, w) := qp,s,w,εs described in
(3.2) defines a surjection
ind : O(n−1,Z)-Orb(Zn−1) −−−−−→ O(n,Z)-Orb(P -crit(Zn,Z)) (3.3)
between the set of O(n−1,Z)-orbits of Zn−1 and the set of O(n,Z)-orbits
in the set P -crit(Zn,Z) of P -critical unit forms.
A. Polak, D. Simson 253
(c) A right inverse of ind is given by q 7→ ress(q) := (q(s), h(s)) defined
in (a), that associates to any P -critical form q = q∆, with
Ker q = Z · h and hs ∈ {−1, 1}, the pair (q(s), h(s)) ∈ Zn−1.
Proof. Assume that n ≥ 3, ∆ is a connected positive loop-free bigraph in
UBigrn−1, p := q∆ : Zn−1 → Z is its unit form and w = (w1, . . . , wn−1) ∈
Zn−1 a sincere root of p. Let ∆′ ∈ UBigrn be the bigraph corresponding
via (2.7) to the unit form q := qp,s,w,εs : Zn → Z defined by the formula
(3.2), that is, q∆′ = qp,s,w,εs . Throughout the proof, we set p := q∆ and
q = q∆′ = qp,s,w,εs .
(a) Assume that p ∈ posit(Zn−1,Z), w ∈Zn−1 is a sincere root of p,
s ∈ {0, 1, . . . , n}, εs ∈ {−1, 1}, and q := qp,s,w,εs : Zn → Z is defined by
the formula (3.2).
We prove that q is P -critical by showing that q is non-negative and
Ker q = Z · h, where h is sincere vector, see Theorem 2.8. For simplicity
of the presentation, we assume that s = n, that is, q is defined by the
formula
q(x1, . . . , xn) = p(x(n)) + x2
n − 2 · bp(x(n), w) · εn · xn.
It follows that q(n) = p, Ǧq(n) = Ǧp, Gq(n) = Gp, and
Ǧq =
[
Ǧp −2Ǧp · wtr · εn
0 1
]
and Gq =
[
Gp −Gp · wtr · εn
−w · Gp · εn 1
]
are the non-symmetric and the symmetric Gram matrix of q, respectively.
We split the proof in three steps.
Step 1.1◦ First, we show that det Gq = 0 and q is not positive. Since
q(n) = p is positive and v ·Gp ·vtr = p(v), for all v ∈ Zn−1, then det Gp > 0,
and, in view of the Cauchy theorem, the obvious equality
[
Gp −Gp · wtr · εn
−w · Gp · εn 1
]
=
=
[
Gp 0
−w · Gp · εn 1
]
·
[
E −G−1
p Gp · wtr · εn
0 1 − (−wGpεn) · G−1
p · (−Gpwtrεn)
]
yields
det Gq = (det Gp) · (1 − w · Gp · wtr) = (det Gp) · (1 − p(w)) = 0,
because p(w) = 1. Hence, by Sylvester′s criterion, the unit form q is not
positive.
Step 1.2◦ We prove that the unit form q is non-negative. Consider
the rational subspace W = Qn−1 × {0} of Qn. Since q(n) = p then
bq(n) = bp and the rational bilinear form bq|W = bp : Qn−1 × Qn−1 → Q
254 P -critical edge-bipartite graphs
is positive. Hence, there is a direct sum decomposition Qn = W ⊕ W ⊥,
where W ⊥ = {v ∈ Qn; bq(v, w) = 0, for all w ∈ W} is the orthogonal
complement of W . It follows that W ⊥ = Q · η, for some non-zero vector
η ∈ W ⊥.
(i) First we show that bq(η, η) = 0. For, let e = {e1, . . . , en} be the
standard basis of Qn. Note that the Gram matrix of q in the Q-basic
e′ = {e1, . . . , en−1, η} of Qn has the diagonal form
Ge
′
q =
bq(e1, η)
Gp
.
.
.
bq(en−1, η)
bq(η, e1) . . . bq(η, en−1) bq(η, η)
=
[
Gp 0
0 bq(η, η)
]
.
If C ∈ Mn(Q) is the translation matrix from e to e′, then det C 6= 0,
Ge
′
b = Ctr · Gb · C and Cauchy’s theorem yields
(det Gp)·bq(η, η) = det Ge
′
b = det(Ctr ·Ge
b ·C) = (det C)2 ·(det Gb) = 0,
because det Gb = 0, by 1.1◦. It follows that bq(η, η) = 0, because p is
positive and det Gp > 0.
(ii) Next, by applying (i), we prove that q : Qn → Q is non-negative,
i.e., q(v) ≥ 0, for each v ∈ Qn. Since Qn = W ⊕ Q · η, the vector v has
the form v = w + λ · η, where w ∈ W , λ ∈ Z, and we get
q(v) = q(w + λ · η) = bq(w + λ · η, w + λ · η)
= bq(w, w) + λ2 · bq(η, η) + 2λ · bq(w, η)
= p(w) ≥ 0,
because bq(η, η) = 0, bq(w, η), bq(w, w) = q(w) = p(w) ≥ 0 and the
positivity of p : Zn−1 → Z implies that the rational form p : Qn−1 → Q
is positive. The proof of Step 1.2◦ is complete.
Step 1.3◦ We show that Ker q = Z · ŵεs , where
ŵεs = (w1, . . . , ws−1, εs, ws, . . . wn−1) ∈ Zn.
Since q : Zn → Z is non-negative, then
Ker q = rad q =
⋂n
i=1 Ker bq(ei, −)
(see [36, Proposition 2.8]) and therefore Ker q coincides with the abelian
subgroup UZ ⊆ Zn of all solutions v ∈ Zn of the system of Z-linear
equations
bq(e1, x) = 0
...
bq(en, x) = 0
(3.4)
Denote by UQ the rational subspace of Qn of all solutions v ∈ Qn of the
system (3.4).
Since det Gq = 0 and det Gq(n) = det Gp > 0 then rank(Gq)=n − 1
and the system (3.4) has a non-zero solution ξ ∈ Qn such that UQ = Q · ξ,
A. Polak, D. Simson 255
because dimQ UQ = n − rank(Gq) = 1. Let ξ = (k1
r1
, . . . , kn
rn
), where
r1 . . . , rn ∈ N\{0} and k1, . . . , kn ∈ Z. If r = lcm(r1, . . . , rn), then ξ′ =
r · ξ ∈ Zn is non-zero and 0 = q(ξ) = q(1
r
· ξ′) = 1
r2 · q(ξ′), that is, ξ′ ∈ UZ.
Then the group UZ ⊆ Zn is non-zero and, hence, it is free of rank ≤ n. It
follows that UZ is of rank one, because UZ ⊆ UQ = Q · ξ.
We show that Ker q = UZ = Z · ŵεs . Since the formula (3.2) yields
q(ŵεs) = p(w) + ε2
s − 2bp(w, w) · εs · εs = 1 + 1 − 2 = 0 then ŵεs ∈ Ker q
and Ker q ⊇ Z · ŵεs . To prove the inverse inclusion, assume that h is a
Z-generator of the rank one group Ker q = UZ, i.e., Ker q = Z · h. Then
there exists λ ∈ Z such that ŵεs = λ · h. Since h ∈ Zn and the sth
coordinate of ŵεs equals εs ∈ {−1, 1} then the equality εs = λ · hs yields
εs, λ, hs ∈ {−1, 1}. It follows that ŵεs generates the group Ker q = Z · v.
Since the vector ŵεs is sincere, q is non-negative, and Ker q = Z · ŵεs
then, by Theorem 2.8, q is P -critical and the proof of (a) is complete.
(b) We recall from [36] that given q : Zn → Z, σ̂ ∈ Ŝn, and ε̂ ∈ Ĉn
2 ,
with ε1, . . . , εn ∈ C2 = {−1, 1}, we have
(A) the form (q ∗ σ̂)(x) = q(x · σ̂tr) = q(xσ(1), . . . , xσ(n)) is obtained
from q(x) by permuting the variables of x under σ ∈ Sn, and
(B) (q ∗ ε̂)(x) = q(x · ε̂) = q(ε1 · x1, . . . , εn · xn).
(C) two integral unit forms q1, q2 : Zn → Z lie in the same O(n,Z)-
orbit if and only if Gq1 = Btr · Gq2 · B, for some matrix B ∈ O(n,Z).
Assume that p : Zn−1 → Z is positive, w ∈ Zn−1 is a sincere root of p,
and
q1 := qp,s1,w,εs1
, q2 := qp,s2,w,εs2
are P -critical forms associated with (p, w) by applying the construction
(3.2), with some s1, s2 ≤ n and εs1 , εs2 ∈ C2 = {−1, 1}. We split the
proof of (b) in several steps.
Step 2.1◦ We show that P -critical forms q1, q2 : Zn → Z lie in the
same O(n,Z)-orbit.
2.1.1◦ First, we assume that s := s1 = s2 and εs1 6= εs2 . It follows
that q1(x) is obtained from q2(x) by xs 7→ −xs, that is, q1 = q2 ∗ ε̂′, where
ε′
s = −1, and ε′
j = 1, for all j 6= s, see (B). Consequently, the forms
q1, q2 : Zn → Z lie in the same O(n,Z)-orbit.
2.1.2◦ Next, we assume that s1 6= s2 and εs1 = εs2 . We find a matrix
B ∈ O(n,Z) such that Gq1 = Btr · Gq2 · B.
In case s1 = 1 and s2 ∈ {2, . . . , n}, we set
256 P -critical edge-bipartite graphs
B =
0 1 0 . . . 0 0 0 . . . 0
0 0 1 . . . 0 0 0 . . . 0
...
...
...
. . .
...
...
...
. . .
...
0 0 0 · · · 1 0 0 . . . 0
1 0 0 . . . 0 0 0 . . . 0
0 0 0 · · · 0 1 0 . . . 0
...
...
...
. . .
...
. . .
...
. . .
...
0 0 0 · · · 0 0 0 . . . 1
=
e2
e3
.
.
.
ei
e1
ei+1
.
.
.
en
, where i = s2.
For simplicity of the presentation, we assume that s2 = n. Then
Gq1 =
[
1 −w · Gp
−Gp · wtr Gp
]
, Gq2 =
[
Gp −Gp · wtr
−w · Gp 1
]
are the sym-
metric Gram matrices of the forms q1, q2, respectively, and simple calcu-
lation yields
Btr · Gq2 · B =
=
0 0 0 · · · 0 1
1 0 0 · · · 0 0
0 1 0 · · · 0 0
.
.
.
.
.
.
. . .
.
.
.
0 0 0 . . . 1 0
·
[
Gp −Gp · wtr
−w · Gp 1
]
·
0 1 0 0 · · · 0
0 0 1 0 · · · 0
.
..
.
..
.
..
. . .
.
..
0 0 0 . . . 1
1 0 0 . . . 0
=
[
−w · Gp 1
Gp −Gp · wtr
]
·
0 1 0 0 · · · 0
0 0 1 0 · · · 0
.
.
.
.
.
.
.
.
.
. . .
.
.
.
0 0 0 . . . 1
1 0 0 . . . 0
= Gq1 .
In case s1 6= s2 and s1, s2 ∈ {2, . . . , n}, we set
B =
1 . . . 0 0 0 . . . 0 0 0 . . . 0
.
.
.
. . .
.
.
.
.
.
.
. . .
.
.
.
.
.
.
.
.
.
. . .
.
.
.
0 . . . 1 0 0 . . . 0 0 0 . . . 0
0 . . . 0 0 0 . . . 0 1 0 . . . 0
0 . . . 0 0 1 . . . 0 0 0 . . . 0
.
.
.
. . .
.
.
.
.
.
.
.
.
.
. . .
.
.
.
.
.
.
.
.
.
. . .
.
.
.
0 . . . 0 0 0 . . . 1 0 0 . . . 0
0 . . . 0 1 0 . . . 0 0 0 . . . 0
0 . . . 0 0 0 . . . 0 0 1 . . . 0
.
.
.
. . .
.
.
.
.
.
.
.
.
.
. . .
.
.
.
.
.
.
.
.
.
. . .
.
.
.
0 . . . 0 0 0 . . . 0 0 0 . . . 1
=
e1
e2
.
.
.
ei−1
ej
ei+1
.
.
.
ej−1
ei
ej+1
.
.
.
en
= τ̂ ,
where i = s1, j = s2, and τ is the transpose permutation (i, j). For
simplicity of the presentation, we assume that s1 = n − 1, s2 = n and,
given a ≤ k ≤ n − 1 and b ≤ s ≤ n − 1, we denote by G
[(a,k)(b,s)]
p the
(k − a + 1) × (s − b + 1) matrix obtained from Gp by removing the rows
enumerated by 1, . . . , a − 1, k + 1, . . . , n − 1 and the columns enumerated
by 1, . . . , b − 1, s + 1, . . . , n − 1.
A. Polak, D. Simson 257
Given w ∈ Zn and 1 ≤ k ≤ s ≤ n, we set w̃ = −Gp · wtr and
w̃(k,s) = (wk, . . . , ws). Then
Gq1 =
G
[(1,n−2)(1,n−2)]
p w̃(1,n−2) G
[(1,n−2)(n−1,n−1)]
p
[w̃(1,n−2)]tr 1 w̃
(n−1,n−1)
n−1
G
[(n−1,n−1)(1,n−2)]
p w̃
(n−1,n−1)
n−1 G
[(n−1,n−1)(n−1,n−1)]
p
, and
Gq2 =
[
Gp w̃
w̃tr 1
]
.
Note that Btr = B = τ̂ and, given a matrix A ∈ Mn(Z), the matrix
A · B = A · τ̂ (resp. B · A = τ̂ · A) is obtained from A by the transpose
of its ith column with the jth column (resp. of its ith row with the jth
row). Then a straightforward computation yields
Btr · Gq2 · B =
=
1 0 0 0 . . . 0 0
0 1 0 0 . . . 0 0
.
.
.
.
.
.
. . .
.
.
.
.
.
.
0 0 0 1 . . . 0 0
0 0 0 0 . . . 0 1
0 0 0 0 . . . 1 0
·
[
Gp w̃
w̃tr 1
]
·
1 0 0 0 . . . 0 0
0 1 0 0 . . . 0 0
.
.
.
.
.
.
. . .
.
.
.
.
.
.
0 0 0 1 . . . 0 0
0 0 0 0 . . . 0 1
0 0 0 0 . . . 1 0
=
G
[(1,n−2)(1,n−1)]
p w̃(1,n−2)
w̃tr 1
G
[(n−1,n−1)(1,n−1)]
p w̃(n−1,n−1)
·
1 0 0 0 . . . 0 0
0 1 0 0 . . . 0 0
.
..
.
..
. . .
.
..
.
..
0 0 0 1 . . . 0 0
0 0 0 0 . . . 0 1
0 0 0 0 . . . 1 0
= Gq1 .
Step 2.2◦ We show that the P -critical forms q1 := qp1,s1,w1,εs1
,
q2 := qp2,s2,w2,εs2
lie in the same O(n,Z)-orbit, if (p1, w1), (p2, w2) ∈ Zn−1
lie in the same O(n−1,Z)-orbit.
In view of Step 2.1◦, without loss of generality, we can assume that
s1 = s2 = 1 and εs1 = εs2 = 1. Then
Gq1 =
[
1 −w1 · Gp1
−(w1 · Gp1 )tr Gp1
]
, Gq2 =
[
1 −w2 · Gp2
−(w2 · Gp2 )tr Gp2
]
is the symmetric Gram matrix of the form q1 and q2, respectively.
Assume that B′ ∈ O(n−1,Z) is a matrix such that
(p1, w1) ∗ B′ = (p1 ∗ B′, w1 · B′) = (p2, w2), and we set B =
[
1 0
0 B′
]
∈
O(n,Z). We show that q2(x) = q1(x · Btr), for all x ∈ Zn, by proving that
the equality Btr · Gq1 · B = Gq2 holds, see (A3).
258 P -critical edge-bipartite graphs
Since (B′)tr = (B′)−1, (B′)tr · Gp1 · B′ = Gp2 and w2 = w1 · B′, we
obtain
Gq2 =
[
1 −w2 · Gp2
−(w2 · Gp2 )tr Gp2
]
=
[
1 −w2 · (B′)tr · Gp1 · B′
−(w2 · (B′)tr · Gp1 · B′)tr (B′)tr · Gp1 · B′
]
=
[
1 −w1 · B′ · (B′)−1 · Gp1 · B′
−(w1B′ · (B′)−1 · Gp1 · B′)tr (B′)tr · Gp1 · B′
]
=
[
1 −w1 · Gp1 · B′
−(w1 · Gp1 · B′)tr (B′)tr · Gp1 · B′
]
= Btr · Gq1 · B
and the proof of Step 2.2◦ is complete. Consequently, we have a well
defined map (3.3)
ind : O(n−1,Z)-Orb(Zn−1) −−−−−→ O(n,Z)-Orb(P -crit(Zn,Z))
induced by the map (p, w) 7→ ind(p, w) := qp,s,w,εs on the orbit represen-
tatives, see (3.2).
To finish the proof of (b), it remains to show that the map ind (3.3)
is surjective. Hence (b) follows, because the surjectivity of ind is a conse-
quence of Proposition 2.14. Since the statement (c) follows from Proposi-
tion 2.14, the proof is complete.
Construction 3.5. Assume that n ≥ 3. It follows from the proof of
Theorem 3.1 that the correspondence inds,εs : Z ′
n−1 −−−→ UBigrn (2.13),
with s = n, associates to any pair (∆, w) ∈ Z ′
n−1 the P -critical bigraph
∆′ := ∆[[w, n, εn]] ∈ UBigrn (3.6)
defined as follows. The set ∆′
0 of vertices of ∆′ is obtained from
∆0 = {1, 2, . . . , n−1} by adding a new vertex n, that is,
∆′
0 = {1, 2, . . . , n−1, n}.
We set w′ := −2Ǧ∆ · w. By Theorem 3.1, each of the coordinates
w′
1, . . . , w′
n−1 of the vector w′ = (w′
1, . . . , w′
n−1) ∈ Zn−1 lies in {−1, 0, 1},
because the bigraph ∆′ corresponds to the unit form q defined by the
formula (3.2). Hence, q1n = w′
1, . . . , qn−1n = w′
n−1, ∆′ is P -critical,
Ǧ∆′ =
[
Ǧ∆ −2Ǧ∆ · wtr · εn
0 1
]
=
[
Ǧ∆ w′tr
0 1
]
(3.7)
A. Polak, D. Simson 259
and q1n, . . . , qn−1n ∈ {−1, 0, 1}, because the restriction q[j,n](xj , xn) :=
x2
j + x2
n + qjnxjxn of q(x) is positive, for j = 1, . . . , n − 1, see also [38,
Theorem 4.1].
It follows that the set of edges of ∆′ := ∆[[w, n, εn]] is the enlargement
of ∆1 by adding a new continuous edge •s−−− •n, for any s such that
w′
s < 0, and a new dotted edge •r- - -•n, for any r such that w′
r > 0.
It follows from [21, Corollary 4.10] and our calculation in Section 5
that the surjective map (3.3) is far from being injective, see also Remark
4.10. However, by applying Theorem 3.1, its proof, and the correspondence
(p, w) 7→ qp,w,s,εs defined by (3.2), we get Algorithm 3.8 constructing the
set P -crit(Zn+1,Z) of all P -critical unit forms q : Zn+1 → Z from the
unit forms p ∈ posit(Zn,Z), with a sincere root w, for n ≥ 3, as well
as the set of P -critical bigraphs ∆′ ∈ UBigrn from the positive ones
∆ ∈ UBigrn−1, with a sincere root w, for n ≥ 2. Its implementation is
presented in the following section as Algorithms 4.8 and 4.9.
By applying Algorithm 3.8 and the package of algorithms presented
in the following section, we compute in Section 5 all P -critical unit forms
q : Zn+1 → Z, for n ≤ 9, up to the action (2.9) of the orthogonal group
O(n+1,Z) on U(Zn+1,Z), and the set of P -critical bigraphs ∆′ ∈ UBigrn,
for n ≥ 2, up to the action (2.1) of the orthogonal group O(n,Z) on
Bigrn.
Algorithm 3.8. Input: An integer n ≥ 3 and the finite sets of matrices
O(n,Z) ⊆ Mn(Z) and O(n+1,Z) ⊆ Mn+1(Z) (see [21, 3.1]).
Output: A finite set P -crit•
n+1 ⊆ P -crit(Zn+1,Z) of pairwise differ-
ent representatives of all O(n + 1,Z)-orbits in P -crit(Zn+1,Z).
Step 1◦ Construct a finite set posit•
n ⊆ posit(Zn,Z) of pairwise
different representatives p : Zn → Z of O(n,Z)-orbits in posit(Zn,Z).
Step 2◦ Given p ∈ posit•
n, construct the finite set
Rp = {w ∈ Zn; p(w) = 1}
of roots of p, and then construct the list SRp of all sincere vectors in Rp.
Step 3◦ Construct a finite set Z−
n of pairwise different representatives
of all O(n,Z)-orbits in the finite set
Z•
n = {(p, w); p ∈ posit•
n, w ∈ SRp},
see [21, Proposition 3.7(c)].
Step 4◦ Given (p, w) ∈ Z−
n , construct the Gram matrices Ǧp and Gp
of p, then construct the matrix Gp,w =
[
1 −w · 2 · Gp
0 Ǧp
]
,
260 P -critical edge-bipartite graphs
Step 5◦ Given (p, w) ∈ Z−
n , construct the unit form qp,w : Zn+1 → Z,
by applying the formula qp,w(x) = x · Gp,w · xtr.
Step 6◦ Take for P -crit•
n+1 the finite set {qp,w}(p,w)∈Z−
n
.
Remark 3.9. (i) We implement the groups O(n,Z) ⊆ Mn(Z)
and O(n+1,Z) ⊆ Mn+1(Z) in the C# programming language, by ap-
plying Algorithm 4.5 of the following section.
(ii) In Step 1◦ we can apply the correspondence
(p, µ) 7→ p̂µ ∈ posit(Zn+1,Z)
that associates to any p ∈ posit(Zn,Z) and any vector µ = (µ1, . . . , µn),
such that µ1, . . . , µn ∈ {−1, 0, 1} and det
[
2Gp µtr
µ 2
]
> 0, the one-point
extension positive form
p̂µ(x) = x ·
[
Ǧp µtr
0 1
]
· xtr,
see [21, Theorem 4.1]. In fact, we should apply an implementation of [21,
Algorithm 4.5]. The positivity of the unit form p̂µ is checked by applying
Algorithm 4.1 based on Sylvester′s citerion. To get the subset posit•
n of
posit(Zn,Z), we apply Algorithm 4.7 of the following section.
(iii) In Step 2◦ we can apply the restrictively counting algorithm [35,
Algorithm 4.2] and [36, Algorithm 3.7, Remark 3.8].
(iv) In Step 3◦, note that two P -critical edge-bipartite graphs con-
structed from pairs (p, w) and (p, −w) lie in the same O(n + 1,Z)-orbit.
4. A package of algorithms
We present a package of algorithms that we apply in our construction
of all O(n,Z)-orbits of a P -critical unit form for n ≥ 3. We use the
standard convention: when a unit quadratic form q is operated upon
in a computer program, it is implemented as a two-dimensional array
in C# representing the corresponding symmetric Gram matrix Gq (or
non-symmetric Gram matrix Ǧq) of q.
The following algorithm verifies in a polynomial time O(n4) wheather
or not a quadratic form p : Zn → Z is positive or a bigraph ∆ ∈ UBigrn
is positive.
Algorithm 4.1 (SylvesterCriterion). Input: An integer n ≥ 2 and
the non-symmetric Gram matrix Ǧp ∈ Mn(Z) of a unit form p : Zn → Z.
Output: True if p is positive definite, false otherwise.
1◦ Ĝp = Ǧp + Ǧtr
p
2◦ k = 0; N = n;
A. Polak, D. Simson 261
3◦ if (det Ĝp > 0) k + +;
4◦ i = n;
5◦ while(i > 1){
6◦ W = the matrix (of size N ≥ 2) obtained from Ĝp by choosing the first N
rows and the first N columns of Ĝp;
7◦ W = the matrix (of size N -1) obtained from W by removing the i-th row
and the i-th column;
8◦ N − −;
10◦ if (det W > 0) k + +;
11◦ i − −;}
12◦ if (n == k) return true;
13◦ return false;
By applying Algorithm 4.1, we check in a polynomial time O(n5)
wheather or not q = q∆ : Zn → Z is P -critical or a bigraph ∆ ∈ UBigrn
is P -critical.
Algorithm 4.2 (IsPcritical). Input: An integer n ≥ 2 and the
non-symmetric Gram matrix Ǧq ∈ Mn(Z) of a unit form q : Zn → Z.
Output: True if q is P -critical, false otherwise.
1◦ Ĝq = Ǧq + Ǧtr
q
2◦ if (SylvesterCriterion(Ĝq,n)==false){
3◦ for(i = 1; i <= n; + + i){
4◦ L = the matrix obtained from Ĝq by removing i-th row and i-th column;
5◦ if(SylvesterCriterion(L, n − 1)==false)
6◦ return false;}
7◦ return true; }
8◦ else return false;
Now, we present three algorithms that we need in our implementation
of the orthogonal group
O(n,Z) = Ŝn ⋊ Ĉn
2 ,
for a given n ≥ 2, see (2.9) and [36, Lemma 2.3]. First (see Algorithm 4.3),
we present an implementation of the symmetric group Sn by applying an
algorithm of Johnson [13] and Trotter [41] based on the idea of adjacent
transpositions; originally it generates the symmetric group Sn. A simple
modification of the algorithm constructs the subgroup Ŝn ⊆ O(n,Z) of
O(n,Z) as follows.
Algorithm 4.3 (GeneretePermutation). Input: An integer
n ≥ 2.
Output: The group Ŝn ⊆ O(n,Z) ⊆ Mn(Z), see (2.9).
1◦ for(i = 1;i <= n;i + +){
2◦ P [i] = i; //P is a vector of integers
262 P -critical edge-bipartite graphs
3◦ C[i] = 1; //C is a vector of integers
4◦ P R[i] = true;} //P R is a vector of booleans
5◦ C[n] = 0;
6◦ for(t = 1; t <= n; + + t)
7◦ M [t, P [t]] = 1; //M is a matrix of integers
8◦ PMatrix.Add(M); //PMatrix is a list of matrices
9◦ i = 1;
10◦ while(i < n){
11◦ i = 1; x = 0;
12◦ while(C[i] == n − i + 1){
13◦ P R[i]=(P R[i]==true)?false:true;
14◦ C[i] = 1;
15◦ if(P R[i]) x + +;
16◦ i + +; }
17◦ if (i < n){
18◦ if (P R[i]) k = C[i] + x;
19◦ else k = n − i + 1 − C[i] + x;
20◦ P [k] ↔ P [k + 1]
21◦ for(t = 1; t <= n; + + t)
22◦ M [t, P [t]] = 1;
23◦ PMatrix.Add(M);
24◦ C[i] = C[i] + 1;}
25◦ }
26◦ return PMatrix;
Now we present an implementation of the finite group Ĉn
2 ⊆ O(n,Z)
defined in Section 2 (see (2.9)), which uses the Gray binary generation (see
[15]). We modify the Gray algorithm by interchanging all zeros with −1.
Obviously, the modified algorithm constructs the group Ĉn
2 ⊆ O(n,Z) ⊆
Mn(Z).
Algorithm 4.4 (GenereteSignMatrices). Input: An integer n ≥ 2.
Output: The group Ĉn
2 ⊆ O(n,Z) ⊆ Mn(Z), see (2.9).
1◦ for(t = 1; t <= n; + + t)
2◦ B[t] = −1;
3◦ i = 0; p = 1;
4◦ do{
5◦ for(t = 1; t <= n; + + t){
6◦ C[t − 1] = B[t]; //C is a vector of integers
7◦ M [t, t] = C[t − 1];} //M is a matrix of integers
8◦ SMatrix.Add(M); //SMatrix is a list of matrices
9◦ i + +;
10◦ j = i;
11◦ p = 1;
12◦ while(j%2 == 0){
13◦ j = j/2;
14◦ p + +;}
A. Polak, D. Simson 263
15◦ if (p ≤ n){
16◦ if (B[p] == −1) B[p] = 1;
17◦ else B[p] = −1;}
18◦ }while(p ≤ n);
19◦ return SMatrix;
Finally, by applying Algorithm 4.3 and Algorithm 4.4, we define an
algorithm constructing the orthogonal group O(n,Z) = Ŝn ⋊ Ĉn
2 , for a
given integer n ≥ 2.
Algorithm 4.5 (OrthogonalGroup). Input: An integer n ≥ 2
and a list of permutation matrices PMatrix.
Output: The matrices B ∈ O(n,Z).
1◦ SMatrix=GenereteSignMatrices(n);
2◦ foreach(int[,] P in PMatrix){
3◦ foreach(int[,] S in SMatrix){
4◦ W = P ∗ S ∈ Mn(Z);
5◦ All.Add(W );} } //All is a list of matrices
6◦ return All;
Hint. We use the fact that every matrix B ∈ O(n,Z) = Ŝn ⋊ Ĉn
2 can be
uniquely represented as the product B = P · S, where P = σ̂ ∈ Ŝn and
S = ε̂ ∈ Ĉn
2 , see [36, Lemma 2.3] and Sections 2-3. A list of permutation
matrices PMatrix is a subset of the set of all permutation matrices Ŝn.
With bigraph ∆ ∈ UBigrn we associate the graph ∆ which is con-
structed from ∆ by replacing all broken edges •- - -• with full edges
•−−− •.
We denote by Ǧ•
∆=NonSymmetricGramMatrixOfGraph(Ǧ∆)
the non-symmetric Gram matrix of the graph ∆ constructed from the
bigraph ∆ with non-symmetric Gram matrix Ǧ∆.
We denote by Ĝ•
∆=SymmetricGramMatrixOfGraph(Ĝ∆)
the duplicate symmetric Gram matrix 2G∆ of the graph ∆ constructed
from the bigraph ∆ with the duplicate symmetric Gram matrix 2G∆.
The following algorithm checks, if two unit forms q1, q2 : Zn → Z
lie in the same O(n,Z)-orbit under the action (2.9), or two bigraphs
∆, ∆′ ∈ UBigrn lie in the same O(n,Z)-orbit under the action (2.1). Here
(Algorithm 4.6 and Algorithm 4.7) we use the fact that if two bigraphs
∆, ∆′ ∈ UBigrn lie in the same O(n,Z)-orbit then the associated graphs
∆ and ∆
′
are isomorphic.
264 P -critical edge-bipartite graphs
Algorithm 4.6 (CompareOrbits). Input: An integer n ≥ 2,
the non-symmetric Gram matrices Ǧq1 , Ǧq2 ∈ Mn(Z) of unit forms
q1, q2 : Zn −−→ Z, and the orthogonal group O(n,Z) ⊆ Mn(Z) (4.5).
Output: True if q1, q2 lie in the same O(n,Z)-orbit, false otherwise.
1◦ Ĝq1 = Ǧq1 + Ǧtr
q1
; Ĝq2 = Ǧq2 + Ǧtr
q2
;
2◦ if(the numbers of zero coefficients in the matrices Ĝq1 and Ĝq1 are not equal)
3◦ return false;
4◦ else{
5◦ Ĝq1 = Ǧq1 + Ǧtr
q1
, Ĝq2 = Ǧq2 + Ǧtr
q2
; let PMatrix be an empty list;
6◦ Ĝ•
q1
=SymmetricGramMatrixOfGraph(Ĝq1 );
Ĝ•
q2
=SymmetricGramMatrixOfGraph(Ĝq2 );
7◦ Find all permutation matrices P ∈ Mn(Z) such that P tr · Ĝ•
q1
· P = Ĝ•
q2
and
add P to PMatrix;
8◦ if (PMatrix is empty) return false;
9◦ Orthogonal=OrthogonalGroup(n, PMatrix);
6◦ foreach([,] B in Orthogonal)
7◦ if(Btr · Ĝq1 · B == Ĝq2 )
8◦ return true;}
9◦ return false;
Algorithm 4.7 (SetOfOrbitRepresentatives). Input: An
integer n ≥ 2, a finite non-empty subset H ⊂ U(Zn,Z) of P -critical (or pos-
itive) quadratic forms, and the orthogonal group O(n,Z) ⊆ Mn(Z) (4.5).
Output: A list AMatrix of non-symmetric Gram matrices Ǧq of
pairwise different representatives q : Zn → Z of all O(n,Z)-orbits O(n,Z)∗
q, with Ǧq ∈ H.
1◦ Let AMatrix, AMatrix•, SMatrix be the empty lists;
2◦ Add first a matrix H[0] from H to AMatrix;
H•[0]=NonSymmetricGramMatrixOfGraph(H[0]);
add H•[0] to AMatrix•;
3◦ SMatrix:=GeneretePermutation(n);
4◦ for(i = 1; i < |H|; i + +){
5◦ Let WMatrix• be the list of matrices such that P tr ·Ĝ•
∆·P , where P ∈SMatrix,
Ĝ•
∆=SymmetricGramMatrixOfGraph(Ĥ[i]) and Ĥ[i] = H[i] + H[i]tr;
6◦ For each matrix A• ∈AMatrix• do steps 7◦ − 11◦;
7◦ For each matrix W • ∈WMatrix• do {
8◦ Let PMatrix be an empty list of matrices;
9◦ if (W • = •, where • = A• + A•tr) add permutation matrix P
(corresponding to W •) to PMatrix; }
10◦ if (PMatrix is not empty){
• Ort=OrthogonalGroup(n, PMatrix);
• Generate a list W1 of matrices such that Btr · Ĥ[i] · B, where B ∈ Ort and
Ĥ[i] = H[i] + H[i]tr;
• Check if there exists a matrix in W1 which is equal to matrix  = A + Atr (we
verify this equality for (duplicate) symmetric Gram matrices coding bigraphs) and if
A. Polak, D. Simson 265
so, go to Step 4◦; if such matrix does not exist go to Step 6◦ (i.e., repeat Steps 7◦ − 11◦
for another matrix from AMatrix•); }
11◦ else (i.e, PMatrix is empty) go to Step 6◦;
12◦ If in Steps 7◦ − 11◦ no orthogonal matrix has been found to witness that
H[i] is in the same orbit as one of the matrices in AMatrix, then add H[i] to AMatrix
and add H•[i] to AMatrix•, where
H•[i]=NonSymmetricGramMatrixOfGraph(H[i]);
13◦ }
13◦ return AMatrix;
Algorithm 4.8 (PcriticalFormsFromPositiveForm). In-
put: An integer n ≥ 2, the non-symmetric Gram matrix Ǧp of a positive
form p : Zn −−→ Z, and the list Wp of all sincere roots of p.
Output: A list of P -critical forms q : Zn+1 −−→ Z constructed from
p by applying (3.3).
1◦ Ĝp = Ǧp + Ǧtr
p ;
2◦ for(i = 1;i <= n + 1;+ + i)
3◦ for(j = 1;j <= n + 1;+ + j){
4◦ if(i > 1 && j > 1)
5◦ Q[i, j] = Ǧp[i − 1, j − 1];
6◦ else {
7◦ if((i > 1 && j == 1)||(i == 1 && j > 1))
8◦ Q[i, j] = 0;
9◦ else Q[i, j] = 1;}
10◦ }
11◦ foreach(int[] w in Wp){
12◦ ŵ = −w · Ĝp;
13◦ for(i = 1;i <= n + 1;+ + i)
14◦ if(i > 1)
15◦ Q[1, i] = ŵ[i − 1]; //Q is a matrix of integers
16◦ if(IsPcritical(Q, n + 1)==1)
17◦ All.Add(Q); } //All is a list of matrices
18◦ return All;
Algorithm 4.9 (AllPcriticalForms). Input: An integer n ≥ 3
and a list GP of non-symmetric Gram matrices Ǧp of pairwise different
representatives p : Zn −−→ Z of all O(n,Z)-orbits in posit(Zn,Z).
Output: A list of non-symmetric Gram matrices Ǧq of pairwise
different representatives q : Zn+1 −−→ Z of all O(n+1,Z)-orbits in the set
P -crit(Zn+1,Z).
1◦ foreach(int[,] P in GP ){
2◦ M=PcriticalFormsFromPositiveForm(P ,n)
3◦ All.Add(M); }//All is a list of matrices
4◦ Âll=list of pairwise different representatives of all O(n+1,Z)-orbits in
P -crit(Zn+1,Z) selected from All by apllying Algorithm 4.6;
5◦ return Âll;
266 P -critical edge-bipartite graphs
Remark 4.10. (a) It follows from Proposition 2.6, (2.13), and Construc-
tion 3.7 that, in view of the identification
q• : UBigrn−1
1−1
−→ U(Zn−1,Z),
see (2.7), Algorithms 4.6-4.9 apply to edge-bipartite graphs in UBigrn
and construct all P -critical bigraphs ∆ ∈ UBigrn.
(b) The complexity of Algorithms 4.8 is dominated by the cardinality
|Wp| of the set Wp of all sincere roots of a given p ∈ posit(Zn,Z); more
precisely, it is bounded by O(|Wp| ∗ n5), where the consecutive values
of |Wp| can be computed by the restrictively counting algorithm [36,
Algorithm 4.2].
(c) The complexity of Algorithm 4.6 is O(|O(n,Z)|).
(d) The complexity of Algorithms 4.7 and 4.9 is also dominated by
|O(n,Z)|.
5. A classification and tables of computing results
In this section we present a classification of P -critical unit forms in
U(Zn,Z) (and hence P -critical bigraphs ∆ ∈ UBigrn), for n ≤ 10. We
get it by applying the package of algortithms of the previous section. By
symbolic computations in Maple and numerical computations in C#, we
compute P -critical unit forms and connected positive unit forms, together
with their Coxeter polynomials and the O(n,Z)-orbits, for n ≤ 10. The
results are presented in tables 5.6-5.9.
We recall from [36, Section 2], that the Coxeter polynomial of
q : Zn → Z, is the characteristic polynomial
coxq(t) = det(t · E − Coxq) ∈ Z[t]
of the Coxeter(-Gram) matrix
Coxq := −Ǧq · Ǧ−tr
q ,
where Ǧq is the Gram matrix (2.5), see also [35]. In general, Coxq depends
on the numbering of the indeterminates in the form q(x1, . . . , xn). In our
classification of P -critical forms we use the Coxeter polynomials of the
Euler quadratic form q∆ : Zn+1 → Z, with n + 1 = |∆0|, of the following
A. Polak, D. Simson 267
simply-laced Euclidean graphs (extended Dynkin diagrams)
n+1
✏
✏
✏
✏
✏
✏
✏
P
P
P
P
P
P
P
•
Ãn :
•−−−−•−−−−•−−−− . . . −−−−•−−−−• (n ≥ 1);
1 2 3 n
D̃n :
2 n+1
• •
| |
•−−−−•−−−−•−−−−· · · −−−−• −−−−•−−−−• (n ≥ 4);
1 3 4 n−2 n−1 n
Ẽ6 :
•5
|
•4
|
•1−−−−•2−−−−•3−−−−•6−−−−•7;
Ẽ7 :
•5
|
•1−−−−•2−−−−•3−−−−•4−−−−•6−−−−•7−−−−•8;
Ẽ8 :
•4
|
•1−−−−•2−−−−•3−−−−•5−−−−•6−−−−•7−−−−•8−−−−•9.
(5.1)
Note that Ã1 is the Kronecker graph • •.
We recall that the Euler quadratic form q∆ : Z∆0 → Z of a graph
∆ = (∆0, ∆1), with the set of vertices ∆0 and the set of edges ∆1, is
defined by the formula
q∆(x) =
∑
i∈∆0
x2
i +
∑
i<j d∆
ijxixj ,
where x = (xj)j∈∆0
∈ Z∆0 ≡ Zn+1, n + 1 = |∆0|, and d∆
ij = −|∆1(•i, •j)|,
and |∆1(•i, •j)| is the number of edges between the vertices •i, •j in ∆.
If ∆ is any of the diagrams D̃n, n ≥ 4, Ẽ6, Ẽ7, and Ẽ8 then the Coxeter
polynomial F∆(t) := coxq∆
(t) of ∆ has the form
F∆(t)=
tn+1 + tn − tn−1 − tn−2 − t3 − t2 + t + 1, for ∆ = D̃n,
t7 + t6 − 2t4 − 2t3 + t + 1, for ∆ = Ẽ6,
t8+t7 − t5 − 2t4 − t3 + t + 1, for ∆ = Ẽ7,
t9 + t8 − t6 − t5 − t4 − t3 + t + 1, for ∆ = Ẽ8.
(5.2)
Note that, if ∆ = D̃4 or ∆ = D̃5, we have
F∆(t) :=
{
t5 + t4 − 2t3 − 2t2 + t + 1, for n = 4,
t6 + t5 − t4 − 2t3 − t2 + t + 1, for n = 5.
(5.3)
If n ≥ 1 and ∆ = Ãn, then the Coxeter polynomial coxq∆
(t) of ∆ is of
one of the forms F
(1)
∆ (t), F
(2)
∆ (t), . . . , F
(mn)
∆ (t), where
mn =
{
n
2 , if n is even,
n+1
2 , if n + 1 is even,
268 P -critical edge-bipartite graphs
F
(j)
∆ (t)= tn+1−tn−j+1−tj +1 = (t−1)2·vj(t)·vn−j+1(t), for j =1, . . . , mn,
and vm(t) = tm−1 + tm−2 + tm−3 + · · · + t2 + t + 1, see [20], [34], and [38].
In particular, if n + 1 is even and j = mn = n+1
2 , then tn−j+1 = tj
and F
(j)
∆ (t) has the form
F
(mn)
∆ (t) = F
( n+1
2
)
∆ (t) = tn+1 − 2t
n+1
2 + 1.
If Ã1 : • • is the Kronecker graph, we have n = 1, mn = 2 and
F∆(t) = F
(2)
∆ (t) = t2 − 2t + 1.
Now we are able to present a complete classification of P -critical unit
forms (and P -critical bigraphs ∆ ∈ UBigrn), their Coxeter polynomials,
and the O(n,Z)-orbits in the set P -critn := P -crit(Zn,Z), for n ≤ 10.
We get it as a result of computer computation.
Theorem 5.4. (a) If n ≤ 9 then, up to the action of the groups O(n,Z)
and O(n+1,Z), the number of elements in the set Zn (Algorithm 3.8, Step
3◦) and the number of O(n+1,Z)-orbits in P -crit(Zn+1,Z) are as shown
in the following table
n 2 3 4 5 6 7 8 9
|Z−
n | 1 2 4 10 72 639 7980 95
|P -crit•
n+1| 1 1 3 5 24 152 1730 17
where P -crit•
n+1 is the finite set of pairwise different representatives of
all O(n + 1,Z)-orbits in P -crit(Zn+1,Z).
(b) If n = 3, 4, 5 then, up to the action of O(n,Z), the number of
P -critical unit forms q : Zn −−→ Z and the number of P -critical bigraphs
∆ ∈ Bigrn equals 1, 1, 3, respectively, and the forms q = q∆ are listed
in [21, Corollary 4.10], together with their Coxeter polynomials and a
generator h of Ker q = Ker q∆.
(c) If n = 6 or n = 7, the list of P -critical unit forms q : Zn −−→ Z
and P -critical bigraphs ∆ ∈ UBigrn, up to the action of O(n,Z), is
presented in Table 5.7 and Table 5.9, respectively, together with their
Coxeter polynomials.
(d) For n = 8, 9, 10, a list of P -critical unit forms q : Zn −−−−→ Z, up
to the action of O(n,Z), is available on request from the authors (see [23]).
Outline of proof. (a) The table is obtained by computer computation
using implementations of Algorithm 4.8 and Algorithm 4.9 in Maple
and C#.
A. Polak, D. Simson 269
(b) The result for n = 3 and n = 4 can be obtained by simple hand
calculation using Proposition 2.14 and Theorem 3.1. For this purpose we
need to compute the sets Z2 and Z3. We do it directly by using Maple
and Sylvester′s criterion (Algorithm 4.1), see also [21, Algorithm 4.5].
The statements (c) and (d) are obtained by computer calculations
using our package of algorithms presented in Section 4. �
The following tables illustrate the algorithmic construction
ind : Zn −−→ P -critn+1 of Theorem 3.1, in cases n = 6 and n = 7.
By applying our package of algorithms of Section 4, we also construct a
complete set of representatives of the O(n+1,Z)-orbits in P -crit(Zn,Z)
and of P -critical bigraphs in UBigrn, for n = 6 and n = 7. In view of the
identification q• : UBigrn
1−1
−→ U(Zn,Z) (2.7), we present the classification
results for the unit forms q : Zn → Z only.
Throughout, we set P -critn := P -crit(Zn,Z) and we denote by
SRp = {w = (w1, . . . , wn) ∈ Zn; p(w) = 1 and w1 6= 0, . . . , wn 6= 0}
the set of sincere roots w of a positive form p : Zn → Z, by h ∈ Zn+1 a
sincere vector such that Ker q = Z ·h, and by coxq(t) = det(t ·E −Coxq) ∈
Z[t] the Coxeter polynomial of q : Zn+1 → Z.
We recall from Sections 3 and 4 the following notations:
• posit•
n ⊆ posit(Zn,Z) is a complete finite set of pairwise different
representatives p : Zn → Z of all O(n,Z)-orbits in posit(Zn,Z), and
• P -crit•
n+1 ⊆ P -crit(Zn+1,Z) is a complete finite set of pairwise
different representatives of all O(n+1,Z)-orbits in P -crit(Zn+1,Z).
• In the last column of each of the tables, we use the notation
introduced in (5.2) for the Coxeter polynomials F∆(t) (5.2), with ∆ ∈
{D̃n, Ẽ6, Ẽ7, Ẽ8}, and F
(1)
∆ (t), . . . , F (mn)∆(t), with ∆ = Ãn, of the Euler
form q∆, where the vertices of the extended Dynkin diagram ∆ are enumer-
ated as in (5.1). The simply-laced Euclidean diagram D∆ associated with
any P -critical bigraph ∆ (see Definition 5.5) and with its unit quadratic
form q∆ can be determined by applying the inflation algorithm ∆ 7→ t−
ab∆
described in [16, Algorithm 5.9] and [38, Theorem 3.7]. Following [38], we
introduce the following definition.
Definition 5.5. The Euclidean type (or the E-type, in short) of a P -
critical bigraph ∆ ∈ UBigrn+1 is a unique simply-laced Euclidean diagram
D∆ ∈ {Ãn, n ≥ 1, D̃m, m ≥ 4, Ẽ6, Ẽ7, Ẽ8}
such that the symmetric Gram matrix G∆ of ∆ is Z-congruent with the
symmetric Gram matrix GD∆ of the diagram D∆.
270 P -critical edge-bipartite graphs
We recall from Theorem 2.8 that any loop-free P -critical bigraph ∆
in UBigrn+1 is principal and connected. Then, by [38, Section 3], the
existence and the uniqueness of a Euclidean diagram D∆ is a consequence
of [16, Section 5] and [38, Section 3].
A complete list of the Coxeter polynomials of P -critical bigraphs ∆ in
UBigrn+1, with at most 10 vertices, is presented in Table 5.12 and 5.13
at the end of this section.
Table 5.6. A list of P -critical unit forms constructed by ind:
Z5 −−→ P -crit6, for n = 6
p ∈ posit•
5 w ∈ SRp ind(p, w) coxq(t) and E-type
p1(x) =
∑5
i=1
x2
i
−
x1x2 − x1x3 − x1x4 +
x1x5 + x2x3 + x2x4 +
x3x4 − x4x5
w = (1, 1, 1, 1̂, 1̂) q1(x) =
∑6
i=1
x2
i
−
x1x3 − x1x4 − x2x3 −
x2x4 − x2x5 + x2x6 +
x3x4 + x3x5 + x4x5 −
x5x6
t6
− t4
− t2 + 1 = F
(2)
Ã5
(t),
E-type =D̃5
p2(x) =
∑5
i=1
x2
i
−
x1x2 − x1x3 − x1x4 +
x1x5 + x2x4 + x3x4
w = (1, 1, 1, 1̂, 1̂) q2(x) =
∑6
i=1
x2
i
+
x1x5 + x1x6 − x2x3 −
x2x4 − x2x5 + x2x6 +
x3x5 + x4x5
t6
− t4
− t2 + 1 = F
(2)
Ã5
(t),
E-type =D̃5
p3(x) =
∑5
i=1
x2
i
−
x1x2 − x1x3 − x1x4 +
x2x4 + x2x5 + x3x4
w1 = (1, 1, 1, 1̂, 1̂) q3(x) =
∑6
i=1
x2
i
−
x1x2 + x1x3 + x1x5 +
x1x6 − x2x3 − x2x4 −
x2x5 + x3x5 + x3x6 +
x4x5
t6
− t5
− t + 1 = F
(1)
Ã5
(t),
E-type =D̃5
w2 = (1, 2, 1, 1̂, 1̂) q4(x) =
∑6
i=1
x2
i
−
x1x3 − x2x3 − x2x4 −
x2x5 + x3x5 + x3x6 +
x4x5
t6 + t5
− t4
− 2t3
− t2 +
t + 1 = F
D̃5
(t), E-
type =D̃5
p4(x) =
∑5
i=1
x2
i
−
x1x2 − x1x3 − x1x4 +
x2x5 + x3x4 − x4x5
w = (1, 1, 1, 1̂, 1̂) q5(x) =
∑6
i=1
x2
i
−
x1x2 + x1x5 − x2x3 −
x2x4 − x2x5 + x3x6 +
x4x5 − x5x6
t6
− t5
− t + 1 = F
(1)
Ã5
(t),
E-type =D̃5
p5(x) =
∑5
i=1
x2
i
−
x1x2 − x1x3 − x2x4 +
x3x5
w = (1, 1, 1, 1, 1̂) q6(x) =
∑6
i=1
x2
i
−
x1x5 + x1x6 − x2x3 −
x2x4 − x3x5 + x4x6
t6
− 2t3 + 1 = F
(3)
Ã5
(t),
E-type =Ã5
p6(x) =
∑5
i=1
x2
i
−
x1x2 − x1x3 − x1x4 +
x1x5 + x3x4
w = (2, 1, 1, 1, 1̂) q7(x) =
∑6
i=1
x2
i
−
x1x4 − x1x5 − x2x3 −
x2x4 − x2x5 + x2x6 +
x4x5
t6 + t5
− t4
− 2t3
− t2 +
t + 1 = F
D̃5
(t), E-
type =D̃5
p7(x) =∑5
i=1
x2
i
− x1x2 −
x1x3 − x1x4 + x2x5
w1 = (1, 1, 1, 1, 1̂) q8(x) =
∑6
i=1
x2
i
+
x1x2 − x1x4 − x1x5 +
x1x6 − x2x3 − x2x4 −
x2x5 + x3x6
t6 + t5
− t4
− 2t3
− t2 + t +
1 = F
D̃5
(t), E-type =D̃5
w2 = (2, 1, 1, 1, 1̂) q9(x) =
∑6
i=1
x2
i
−
x1x2 + x1x3 + x1x6 −
x2x3 − x2x4 − x2x5 +
x3x6
t6
− t4
− t2 + 1 = F
(2)
Ã5
(t),
E-type =D̃5
w3 = (2, 2, 1, 1, 1̂) q10(x) =
∑6
i=1
x2
i
−
x1x3 − x2x3 − x2x4 −
x2x5 + x3x6
t6 + t5
− t4
− 2t3
− t2 + t +
1 = F
D̃5
(t), E-type =D̃5
A. Polak, D. Simson 271
Table 5.7. A set of representatives of O(n,Z)-orbits in P -crit(Zn,Z),
for n = 6
(p, w) ind(p, w) ∈ O(6,Z)-Orb(q) ⊆ P -crit•
6 coxq(t), E-type
(p5, w) q6(x) =
∑6
i=1
x2
i
− x1x5 + x1x6 − x2x3 − x2x4 − x3x5 +
x4x6
t6
− 2t3 + 1 = F
(3)
Ã5
(t),
E-type =Ã5
(p1, w) q1(x) =
∑6
i=1
x2
i
− x1x3 − x1x4 − x2x3 − x2x4
−x2x5 + x2x6 + x3x4 + x3x5 + x4x5 − x5x6
t6
− t4
− t2 + 1 = F
(2)
Ã5
(t),
E-type =D̃5(p3, w1)
(p2, w)
q2(x) =
∑6
i=1
x2
i
+ x1x5 + x1x6 − x2x3 − x2x4
−x2x5 + x2x6 + x3x5 + x4x5
t6
− t4
− t2 + 1 = F
(2)
Ã5
(t),
E-type =D̃5
(p4, w)
(p7, w1)
(p7, w3) q10(x) =
∑6
i=1
x2
i
− x1x3 − x2x3 − x2x4 − x2x5 + x3x6 t6 + t5
− t4
− 2t3
− t2 + t +
1 = F
D̃5
(t), E-type =D̃5
(p3, w2)
q4(x) =
∑6
i=1
x2
i
− x1x3 − x2x3 − x2x4 − x2x5
+x3x5 + x3x6 + x4x5
t6 + t5
− t4
− 2t3
− t2 + t
+1 = F
D̃5
(t),E-type =D̃5
(p6, w)
(p7, w2)
Hint. The unit forms pj and the vectors w and wj used in 5.7 are the
same as presented in 5.6.
It follows that the surjective correspondence
inds,εs : O(5,Z)-Orb(Z5) −−−−−→ O(6,Z)-Orb(P -crit(Z6,Z))
(3.3) induced by the map (p, w) 7→ inds,εs(p, w) := qp,s,w,εs , is not injective,
see also Remark 5.10 at the end of this section.
Table 5.8. P -critical unit forms constructed by ind: Z6 −−→ P -crit7,
for n = 7
p ∈ posit•
6 w ∈ SRp q = ind(p, w) ∈ P -crit7
p1(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 + x1x6 + x2x3 +
x2x4 + x2x5 + x3x4 +
x3x5 +x4x5 −x4x6 −x5x6
w1 = (1, 1, 1, 1̂, 1̂, 2̂) q1(x) =
∑7
i=1
x2
i
+ x1x7 − x2x3 − x2x4 −
x2x5 − x2x6 + x2x7 + x3x4 + x3x5 + x3x6 +
x4x5 + x4x6 + x5x6 − x5x7 − x6x7
w2 = (1, 1, 1, 1̂, 1̂, 1̂) q2(x) =
∑7
i=1
x2
i
− x1x2 + x1x5 + x1x6 −
x1x7 − x2x3 − x2x4 − x2x5 − x2x6 + x2x7 +
x3x4 + x3x5 + x3x6 + x4x5 + x4x6 + x5x6 −
x5x7 − x6x7
272 P -critical edge-bipartite graphs
Table 5.8. P -critical unit forms constructed by ind: Z6 −−→ P -crit7,
for n = 7
p ∈ posit•
6 w ∈ SRp q = ind(p, w) ∈ P -crit7
p3(x) =∑6
i=1
x2
i
−x1x2 −x1x3 −
x1x4 − x1x5 + x1x6 +
x2x5 − x2x6 + x3x4 +
x3x5 + x4x5 − x5x6
w1 = (1, 1, 1, 1, 2̂, 1̂) q4(x) =
∑7
i=1
x2
i
+ x1x6 − x2x3 − x2x4 −
x2x5 − x2x6 + x2x7 + x3x6 − x3x7 + x4x5 +
x4x6 + x5x6 − x6x7
w2 = (1, 1, 1, 1, 1̂, 1̂) q5(x) =
∑7
i=1
x2
i
+ x1x2 − x1x3 − x1x4 −
x1x5 − x1x6 + x1x7 − x2x3 − x2x4 − x2x5 −
x2x6 + x2x7 + x3x6 − x3x7 + x4x5 + x4x6 +
x5x6 − x6x7
w3 = (2, 1, 1, 1, 1̂, 1̂) q6(x) =
∑7
i=1
x2
i
− x1x2 − x2x3 − x2x4 −
x2x5 − x2x6 + x2x7 + x3x6 − x3x7 + x4x5 +
x4x6 + x5x6 − x6x7
p4(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 + x2x5 + x2x6 +
x3x4 + x3x5 − x3x6 +
x4x5 − x4x6
w = (1, 1, 1, 1, 1̂, 1) q7(x) =
∑7
i=1
x2
i
− x1x3 − x1x7 − x2x3 −
x2x4 − x2x5 − x2x6 + x3x6 + x3x7 + x4x5 +
x4x6 − x4x7 + x5x6 − x5x7
p5(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 + x2x4 + x2x5 +
x2x6 +x3x4 +x3x5 +x4x5
w1 = (1, 2, 1, 1̂, 1̂, 1̂) q8(x) =
∑7
i=1
x2
i
− x1x2 + x1x4 + x1x5 +
x1x6 − x2x3 − x2x4 − x2x5 − x2x6 + x3x5 +
x3x6 + x3x7 + x4x5 + x4x6 + x5x6
w2 = (1, 2, 2, 1̂, 1̂, 1̂) q9(x) =
∑7
i=1
x2
i
− x1x4 − x2x3 − x2x4 −
x2x5 − x2x6 + x3x5 + x3x6 + x3x7 + x4x5 +
x4x6 + x5x6
p6(x) =∑6
i=1
x2
i
−x1x2 −x1x3 −
x1x4 − x1x5 + x1x6 +
x2x5 +x3x4 +x3x5 +x4x5
w1 = (1, 1, 1, 1, 1̂, 1̂) q10(x) =
∑7
i=1
x2
i
+ x1x2 − x1x4 − x1x5 +
x1x7 − x2x3 − x2x4 − x2x5 − x2x6 + x2x7 +
x3x6 + x4x5 + x4x6 + x5x6
w2 = (2, 1, 1, 1, 1̂, 1̂) q11(x) =
∑7
i=1
x2
i
− x1x2 + x1x3 + x1x6 −
x2x3 − x2x4 − x2x5 − x2x6 + x2x7 + x3x6 +
x4x5 + x4x6 + x5x6
w3 = (2, 2, 1, 1, 1̂, 1̂) q12(x) =
∑7
i=1
x2
i
− x1x3 − x2x3 − x2x4 −
x2x5 − x2x6 + x2x7 + x3x6 + x4x5 + x4x6 +
x5x6
p7(x) =∑6
i=1
x2
i
−x1x2 −x1x3 −
x1x4 − x1x5 + x2x5 +
x2x6 +x3x4 +x3x5 +x4x5
w1 = (1, 1, 1, 1, 1̂, 1̂) q13(x) =
∑7
i=1
x2
i
+ x1x3 − x1x4 − x1x5 +
x1x7 − x2x3 − x2x4 − x2x5 − x2x6 + x3x6 +
x3x7 + x4x5 + x4x6 + x5x6
w2 = (1, 2, 1, 1, 2̂, 1̂) q14(x) =
∑7
i=1
x2
i
+ x1x6 − x2x3 − x2x4 −
x2x5 − x2x6 + x3x6 + x3x7 + x4x5 + x4x6 +
x5x6
w3 = (1, 2, 1, 1, 1̂, 1̂) q15(x) =
∑7
i=1
x2
i
+ x1x2 − x1x3 − x1x4 −
x1x5 − x1x6 − x2x3 − x2x4 − x2x5 − x2x6 +
x3x6 + x3x7 + x4x5 + x4x6 + x5x6
w4 = (2, 2, 1, 1, 1̂, 1̂) q16(x) =
∑7
i=1
x2
i
− x1x2 − x2x3 − x2x4 −
x2x5 − x2x6 + x3x6 + x3x7 + x4x5 + x4x6 +
x5x6
p8(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 + x2x5 + x3x4 +
x3x5 + x3x6 + x4x5
w = (1, 1, 1, 1, 1̂, 1̂) q17(x) =
∑7
i=1
x2
i
− x1x5 + x1x7 − x2x3 −
x2x4 − x2x5 − x2x6 + x3x6 + x4x5 + x4x6 +
x4x7 + x5x6
A. Polak, D. Simson 273
Table 5.8. P -critical unit forms constructed by ind: Z6 −−→ P -crit7,
for n = 7
p ∈ posit•
6 w ∈ SRp q = ind(p, w) ∈ P -crit7
p9(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 + x2x6 + x3x4 +
x3x5 + x4x5 − x5x6
w = (1, 1, 1, 1, 1̂, 1̂) q18(x) =
∑7
i=1
x2
i
− x1x4 − x1x5 − x2x3 −
x2x4 − x2x5 − x2x6 + x3x7 + x4x5 + x4x6 +
x5x6 − x6x7
p10(x) =∑6
i=1
x2
i
−x1x2 −x1x3 −
x1x4 − x1x5 + x1x6 +
x2x5 +x3x4 −x3x6 +x4x5
w1 = (1, 1, 1̂, 1, 1̂, 1̂) q19(x) =
∑7
i=1
x2
i
− x1x2 + x1x4 + x1x5 +
x1x6 − x2x3 − x2x4 − x2x5 − x2x6 + x2x7 +
x3x6 + x4x5 − x4x7 + x5x6
w2 = (1, 1, 1̂, 2, 1̂, 1̂) q20(x) =
∑7
i=1
x2
i
− x1x5 − x2x3 − x2x4 −
x2x5 − x2x6 + x2x7 + x3x6 + x4x5 − x4x7 +
x5x6
p11(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 + x2x5 + x2x6 +
x3x4 + x4x5 + x5x6
w = (1, 1, 1, 1̂, 1, 1̂) q21(x) =
∑7
i=1
x2
i
− x1x3 + x1x5 − x2x3 −
x2x4 − x2x5 − x2x6 + x3x6 + x3x7 + x4x5 +
x5x6 + x6x7
p12(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 + x2x5 + x2x6 +
x3x4 + x4x5 − x4x6
w = (1, 1, 1, 1̂, 1, 1̂) q22(x) =
∑7
i=1
x2
i
− x1x3 − x1x6 − x2x3 −
x2x4 − x2x5 − x2x6 + x3x6 + x3x7 + x4x5 +
x5x6 − x5x7
p13(x) =∑6
i=1
x2
i
−x1x2 −x1x3 −
x1x4 + x1x6 − x2x5 −
x2x6 +x3x4 +x3x5 +x4x5
w1 = (1, 1̂, 1, 1, 2̂, 1̂) q23(x) =
∑7
i=1
x2
i
+ x1x6 − x2x3 − x2x4 −
x2x5 + x2x7 − x3x6 − x3x7 + x4x5 + x4x6 +
x5x6
w2 = (1, 1̂, 1, 1, 1̂, 1̂) q24(x) =
∑7
i=1
x2
i
+ x1x3 − x1x4 − x1x5 −
x1x6 − x2x3 − x2x4 − x2x5 + x2x7 − x3x6 −
x3x7 + x4x5 + x4x6 + x5x6
p14(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 + x2x5 + x3x4 +
x4x5 + x4x6
w = (1, 1, 1̂, 2, 1̂, 1̂) q25(x) =
∑7
i=1
x2
i
− x1x2 + x1x4 − x2x3 −
x2x4 − x2x5 − x2x6 + x3x6 + x4x5 + x5x6 +
x5x7
p15(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 +
x1x6 − x2x5 + x3x4 +
x3x5 + x4x5
w = (2, 1, 1, 1, 1̂, 1̂) q26(x) =
∑7
i=1
x2
i
− x1x3 + x1x6 − x2x3 −
x2x4 − x2x5 + x2x7 − x3x6 + x4x5 + x4x6 +
x5x6
p17(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 +x3x5 +x3x6 +x4x5
w1 = (1, 1, 1, 1, 1̂, 1̂) q28(x) =
∑7
i=1
x2
i
− x1x3 + x1x4 + x1x6 +
x1x7 − x2x3 − x2x4 − x2x5 − x2x6 + x4x6 +
x4x7 + x5x6
w2 = (1, 1, 2, 1, 1̂, 1̂) q29(x) =
∑7
i=1
x2
i
+ x1x2 − x1x3 − x1x4 −
x2x3 − x2x4 − x2x5 − x2x6 + x4x6 + x4x7 +
x5x6
w3 = (2, 1, 2, 1, 1̂, 1̂) q30(x) =
∑7
i=1
x2
i
− x1x2 + x1x5 + x1x6 −
x2x3 − x2x4 − x2x5 − x2x6 + x4x6 + x4x7 +
x5x6
w4 = (2, 1, 2, 2, 1̂, 1̂) q31(x) =
∑7
i=1
x2
i
− x1x5 − x2x3 − x2x4 −
x2x5 − x2x6 + x4x6 + x4x7 + x5x6
p20(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 +
x1x6 −x2x5 +x3x4 +x4x5
w = (1, 1, 1, 1̂, 1, 1̂) q36(x) =
∑7
i=1
x2
i
+ x1x5 + x1x7 − x2x3 −
x2x4 − x2x5 + x2x7 − x3x6 + x4x5 + x5x6
274 P -critical edge-bipartite graphs
Table 5.8. P -critical unit forms constructed by ind: Z6 −−→ P -crit7,
for n = 7
p ∈ posit•
6 w ∈ SRp q = ind(p, w) ∈ P -crit7
p21(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x2x5 +x2x6 +x3x4 +x4x5
w1 = (1, 1, 1, 1̂, 1, 1̂) q37(x) =
∑7
i=1
x2
i
− x1x2 + x1x3 + x1x5 +
x1x7 − x2x3 − x2x4 − x2x5 − x3x6 + x3x7 +
x4x5 + x5x6
w2 = (1, 2, 1, 1̂, 1, 1̂) q38(x) =
∑7
i=1
x2
i
− x1x3 + x1x5 + x1x6 −
x2x3 − x2x4 − x2x5 − x3x6 + x3x7 + x4x5 +
x5x6
w3 = (1, 2, 1, 1̂, 2, 1̂) q39(x) =
∑7
i=1
x2
i
− x1x6 − x2x3 − x2x4 −
x2x5 − x3x6 + x3x7 + x4x5 + x5x6
p22(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x2x5 +x3x4 +x3x6 +x4x5
w1 = (1, 1, 1, 1̂, 1, 1̂) q40(x) =
∑7
i=1
x2
i
− x1x2 + x1x4 + x1x5 +
x1x7 − x2x3 − x2x4 − x2x5 − x3x6 + x4x5 +
x4x7 + x5x6
w2 = (1, 1, 2, 1̂, 1, 1̂) q41(x) =
∑7
i=1
x2
i
− x1x4 − x2x3 − x2x4 −
x2x5 − x3x6 + x4x5 + x4x7 + x5x6
p23(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 +
x2x6 +x3x4 −x3x5 −x4x5
w1 = (1, 1, 1, 1, 1, 1̂) q42(x) =
∑7
i=1
x2
i
+ x1x2 − x1x4 − x1x5 +
x1x7 − x2x3 − x2x4 − x2x5 + x3x7 + x4x5 −
x4x6 − x5x6
w2 = (2, 1, 1, 1, 1, 1̂) q43(x) =
∑7
i=1
x2
i
− x1x2 + x1x3 + x1x7 −
x2x3 − x2x4 − x2x5 + x3x7 + x4x5 − x4x6 −
x5x6
w3 = (2, 2, 1, 1, 1, 1̂) q44(x) =
∑7
i=1
x2
i
− x1x3 − x2x3 − x2x4 −
x2x5 + x3x7 + x4x5 − x4x6 − x5x6
p24(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 +
x3x4 −x3x5 −x4x5 +x5x6
w1 = (1, 1, 1, 1, 1, 1̂) q45(x) =
∑7
i=1
x2
i
+ x1x2 − x1x3 − x1x4 −
x1x5 + x1x6 + x1x7 − x2x3 − x2x4 − x2x5 +
x4x5 − x4x6 − x5x6 + x6x7
w2 = (1, 1, 1, 1, 2, 1̂) q46(x) =
∑7
i=1
x2
i
+ x1x2 − x1x3 − x1x6 −
x2x3 − x2x4 − x2x5 + x4x5 − x4x6 − x5x6 +
x6x7
w3 = (2, 1, 1, 1, 1, 1̂) q47(x) =
∑7
i=1
x2
i
− x1x2 + x1x6 + x1x7 −
x2x3 − x2x4 − x2x5 + x4x5 − x4x6 − x5x6 +
x6x7
w4 = (2, 1, 1, 1, 2, 1̂) q48(x) =
∑7
i=1
x2
i
− x1x2 + x1x4 + x1x5 −
x1x6 − x2x3 − x2x4 − x2x5 + x4x5 − x4x6 −
x5x6 + x6x7
w5 = (2, 1, 1, 2, 2, 1̂) q49(x) =
∑7
i=1
x2
i
− x1x5 − x2x3 − x2x4 −
x2x5 + x4x5 − x4x6 − x5x6 + x6x7
w6 = (2, 1, 2, 1, 2, 1̂) q50(x) =
∑7
i=1
x2
i
− x1x4 − x2x3 − x2x4 −
x2x5 + x4x5 − x4x6 − x5x6 + x6x7
p25(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x2x5 +x2x6 −x3x6 +x4x5
w = (1, 1̂, 1, 1, 1̂, 1) q51(x) =
∑7
i=1
x2
i
− x1x2 + x1x3 − x2x3 −
x2x4 − x2x5 − x3x6 + x3x7 − x4x7 + x5x6
A. Polak, D. Simson 275
Table 5.8. P -critical unit forms constructed by ind: Z6 −−→ P -crit7,
for n = 7
p ∈ posit•
6 w ∈ SRp q = ind(p, w) ∈ P -crit7
p27(x) =∑6
i=1
x2
i
−x1x2 −x1x3 −
x1x4 −x1x5 +x2x6 +x4x5
w1 = (2, 1, 1, 1, 1, 1̂) q53(x) =
∑7
i=1
x2
i
+ x1x3 − x1x5 − x1x6 +
x1x7 − x2x3 − x2x4 − x2x5 − x2x6 + x3x7 +
x5x6
w2 = (2, 2, 1, 1, 1, 1̂) q54(x) =
∑7
i=1
x2
i
+ x1x2 − x1x3 − x1x5 −
x1x6 − x2x3 − x2x4 − x2x5 − x2x6 + x3x7 +
x5x6
w3 = (3, 2, 1, 1, 1, 1̂) q55(x) =
∑7
i=1
x2
i
− x1x2 + x1x4 − x2x3 −
x2x4 − x2x5 − x2x6 + x3x7 + x5x6
w4 = (3, 2, 2, 1, 1, 1̂) q56(x) =
∑7
i=1
x2
i
− x1x4 − x2x3 − x2x4 −
x2x5 − x2x6 + x3x7 + x5x6
p28(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 + x4x5 + x4x6
w = (2, 1, 1, 1, 1, 1̂) q57(x) =
∑7
i=1
x2
i
− x1x6 + x1x7 − x2x3 −
x2x4 − x2x5 − x2x6 + x5x6 + x5x7
p29(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x2x5 + x2x6 + x4x5
w = (2, 2, 1, 1, 1, 1̂) q58(x) =
∑7
i=1
x2
i
− x1x5 − x1x6 − x2x3 −
x2x4 − x2x5 − x3x6 + x3x7 + x5x6
p31(x) =∑6
i=1
x2
i
−x1x2 −x1x3 −
x1x4 − x2x5 + x3x6
w1 = (1, 1, 1, 1, 1, 1̂) q60(x) =
∑7
i=1
x2
i
+ x1x2 − x1x5 − x1x6 +
x1x7 − x2x3 − x2x4 − x2x5 − x3x6 + x4x7
w2 = (2, 1, 1, 1, 1, 1̂) q61(x) =
∑7
i=1
x2
i
− x1x2 + x1x3 + x1x4 −
x1x6 + x1x7 − x2x3 − x2x4 − x2x5 − x3x6 +
x4x7
w3 = (2, 1, 2, 1, 1, 1̂) q62(x) =
∑7
i=1
x2
i
+ x1x3 − x1x4 − x1x6 −
x2x3 − x2x4 − x2x5 − x3x6 + x4x7
w4 = (2, 2, 1, 1, 1, 1̂) q63(x) =
∑7
i=1
x2
i
− x1x3 + x1x4 + x1x7 −
x2x3 − x2x4 − x2x5 − x3x6 + x4x7
w5 = (2, 2, 2, 1, 1, 1̂) q64(x) =
∑7
i=1
x2
i
+ x1x2 − x1x3 − x1x4 −
x2x3 − x2x4 − x2x5 − x3x6 + x4x7
w6 = (3, 2, 2, 1, 1, 1̂) q65(x) =
∑7
i=1
x2
i
− x1x2 + x1x5 − x2x3 −
x2x4 − x2x5 − x3x6 + x4x7
w7 = (3, 2, 2, 2, 1, 1̂) q66(x) =
∑7
i=1
x2
i
− x1x5 − x2x3 − x2x4 −
x2x5 − x3x6 + x4x7
p32(x) =∑6
i=1
x2
i
−x1x2 −x1x3 −
x1x4 − x2x5 + x5x6
w1 = (1, 1, 1, 1, 1, 1̂) q67(x) =
∑7
i=1
x2
i
+ x1x2 − x1x4 − x1x5 +
x1x7 − x2x3 − x2x4 − x2x5 − x3x6 + x6x7
w2 = (2, 1, 1, 1, 1, 1̂) q68(x) =
∑7
i=1
x2
i
− x1x2 + x1x3 + x1x7 −
x2x3 − x2x4 − x2x5 − x3x6 + x6x7
w3 = (2, 2, 1, 1, 1, 1̂) q69(x) =
∑7
i=1
x2
i
− x1x3 + x1x6 + x1x7 −
x2x3 − x2x4 − x2x5 − x3x6 + x6x7
w4 = (2, 2, 1, 1, 2, 1̂) q70(x) =
∑7
i=1
x2
i
− x1x6 − x2x3 − x2x4 −
x2x5 − x3x6 + x6x7
p33(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x2x4 −
x3x5 + x4x6
w = (1, 1, 1, 1, 1, 1̂) q71(x) =
∑7
i=1
x2
i
− x1x6 + x1x7 − x2x3 −
x2x4 − x3x5 − x4x6 + x5x7
276 P -critical edge-bipartite graphs
Table 5.8. P -critical unit forms constructed by ind: Z6 −−→ P -crit7,
for n = 7
p ∈ posit•
6 w ∈ SRp q = ind(p, w) ∈ P -crit7
p34(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 +x2x6 +x3x5 +x4x5
w = (1, 1, 1, 1, 1̂, 1̂) q72(x) =
∑7
i=1
x2
i
+ x1x6 + x1x7 − x2x3 −
x2x4 − x2x5 − x2x6 + x3x7 + x4x6 + x5x6
p16(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 + x2x5 + x2x6 +
x3x4 + x5x6
w = (2, 1, 1, 1, 1, 1̂) q27(x) =
∑7
i=1
x2
i
− x1x4 − x1x5 − x2x3 −
x2x4 − x2x5 − x2x6 + x3x6 + x3x7 + x4x5 +
x6x7
p18(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 +x3x5 +x4x5 +x5x6
w = (1, 1, 1, 1, 1̂, 1) q32(x) =
∑7
i=1
x2
i
− x1x3 − x1x7 − x2x3 −
x2x4 − x2x5 − x2x6 + x4x6 + x5x6 + x6x7
p30(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x2x5 + x2x6 + x3x4
w = (2, 2, 1, 1, 1, 1̂) q59(x) =
∑7
i=1
x2
i
− x1x4 − x1x5 − x2x3 −
x2x4 − x2x5 − x3x6 + x3x7 + x4x5
p2(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 + x1x6 + x2x4 +
x2x5 + x3x4 + x3x5 −
x3x6 + x4x5
w = (1, 1̂, 1̂, 1, 1, 1̂) q3(x) =
∑7
i=1
x2
i
− x1x2 + x1x3 − x2x3 −
x2x4 − x2x5 − x2x6 + x2x7 + x3x5 + x3x6 +
x4x5 + x4x6 − x4x7 + x5x6
p19(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x1x5 +x1x6 +x2x5 +x3x4
w1 = (2, 1, 1, 1, 1, 1̂) q33(x) =
∑7
i=1
x2
i
+ x1x2 − x1x3 − x1x4 −
x1x5 − x1x6 − x2x3 − x2x4 − x2x5 − x2x6 +
x2x7 + x3x6 + x4x5
w2 = (3, 1, 1, 1, 1, 2̂) q34(x) =
∑7
i=1
x2
i
+ x1x7 − x2x3 − x2x4 −
x2x5 − x2x6 + x2x7 + x3x6 + x4x5
w3 = (3, 1, 1, 1, 1, 1̂) q35(x) =
∑7
i=1
x2
i
− x1x2 − x1x7 − x2x3 −
x2x4 − x2x5 − x2x6 + x2x7 + x3x6 + x4x5
p26(x) =
∑6
i=1
x2
i
−
x1x2 − x1x3 − x1x4 −
x2x5 +x3x4 +x3x6 −x5x6
w = (1, 1, 1̂, 1, 1, 1) q52(x) =
∑7
i=1
x2
i
− x1x2 + x1x4 − x2x3 −
x2x4 − x2x5 − x3x6 + x4x5 + x4x7 − x6x7
In the following Table 5.9, the unit forms pj , pij , and the vectors w
and wj are the same as presented in Table 5.8.
Table 5.9. A set of representatives of O(n,Z)-orbits in P -crit(Zn,Z),
for n = 7
(p, w) ind(p, w) ∈ O(7,Z)-Orb(q) ⊆ P -crit•
7 coxq(t) and E-type
(p33, w) q71(x) =
∑7
i=1
x2
i
−x1x6 +x1x7 −x2x3 −x2x4 −x3x5 −
x4x6 + x5x7
t7
−t4
−t3+1 = F
(3)
Ã6
(t),
E-type =Ã6
(p1, w2) q2(x) =
∑7
i=1
x2
i
− x1x2 + x1x5 + x1x6 − x1x7 −
x2x3 − x2x4 − x2x5 − x2x6 + x2x7 + x3x4 + x3x5 +
x3x6 + x4x5 + x4x6 + x5x6 − x5x7 − x6x7
t7
−t5
−t2+1 = F
(2)
Ã6
(t),
E-type =Ẽ6
(p3, w2)
A. Polak, D. Simson 277
Table 5.9. A set of representatives of O(n,Z)-orbits in P -crit(Zn,Z),
for n = 7
(p, w) ind(p, w) ∈ O(7,Z)-Orb(q) ⊆ P -crit•
7 coxq(t) and E-type
(p1, w1)
q1(x) =
∑7
i=1
x2
i
+ x1x7 − x2x3 − x2x4 −
x2x5 − x2x6 + x2x7 + x3x4 + x3x5 +
x3x6 + x4x5 + x4x6 + x5x6 − x5x7 − x6x7
t7
−t5
−t2+1 = F
(2)
Ã6
(t),
E-type =Ẽ6
(p5, w1)
(p7, w3)
(p4, w)
q7(x) =
∑7
i=1
x2
i
− x1x3 − x1x7 − x2x3 −
x2x4 − x2x5 − x2x6 + x3x6 + x3x7 +
x4x5 + x4x6 − x4x7 + x5x6 − x5x7
t7
−t5
−t2+1 = F
(2)
Ã6
(t),
E-type =Ẽ6(p7, w1)
(p13, w2)
(p20, w)
q36(x) =
∑7
i=1
x2
i
+ x1x5 + x1x7 − x2x3 −
x2x4 − x2x5 + x2x7 − x3x6 + x4x5 + x5x6
t7
− t6
− t + 1 = F
(1)
Ã6
(t),
E-type =Ẽ6(p25, w)
(p31, w1)
(p22, w2)
q41(x) =
∑7
i=1
x2
i
− x1x4 − x2x3 −
x2x4 − x2x5 − x3x6 + x4x5 + x4x7 + x5x6
t7
−t4
−t3+1 = F
(3)
Ã6
(t),
E-type =D̃6
(p28, w)
(p32, w2)
(p3, w1)
q4(x) =
∑7
i=1
x2
i
+ x1x6 − x2x3 − x2x4 −
x2x5 − x2x6 + x2x7 + x3x6 − x3x7 +
x4x5 + x4x6 + x5x6 − x6x7
t7
−t5
−t2+1 = F
(2)
Ã6
(t),
E-type =Ẽ6(p3, w3)
(p6, w2)
(p19, w1)
(p8, w)
q17(x) =
∑7
i=1
x2
i
− x1x5 + x1x7 −
x2x3 − x2x4 − x2x5 − x2x6 + x3x6 +
x4x5 + x4x6 + x4x7 + x5x6
t7
−t4
−t3+1 = F
(3)
Ã6
(t),
E-type =D̃6(p9, w)
(p22, w1)
(p23, w1)
(p10, w2)
q20(x) =∑7
i=1
x2
i
− x1x5 − x2x3 − x2x4 − x2x5 −
x2x6 + x2x7 + x3x6 + x4x5 − x4x7 + x5x6
t7
−t5
−t2+1 = F
(2)
Ã6
(t),
E-type =Ẽ6(p14, w)
(p17, w2)
(p31, w2)
(p11, w)
q21(x) =
∑7
i=1
x2
i
− x1x3 + x1x5 −
x2x3 − x2x4 − x2x5 − x2x6 + x3x6 +
x3x7 + x4x5 + x5x6 + x6x7
t7
− t6
− t + 1 = F
(1)
Ã6
(t),
E-type =Ẽ6(p12, w)
(p17, w1)
(p21, w1)
(p21, w3)
q39(x) =
∑7
i=1
x2
i
− x1x6 − x2x3 −
x2x4 − x2x5 − x3x6 + x3x7 + x4x5 + x5x6
t7
−t5
−t2+1 = F
(2)
Ã6
(t),
E-type =Ẽ6(p29, w)
(p31, w3)
(p31, w4)
278 P -critical edge-bipartite graphs
Table 5.9. A set of representatives of O(n,Z)-orbits in P -crit(Zn,Z),
for n = 7
(p, w) ind(p, w) ∈ O(7,Z)-Orb(q) ⊆ P -crit•
7 coxq(t) and E-type
(p13, w1)
q23(x) =∑7
i=1
x2
i
+x1x6−x2x3−x2x4−x2x5+x2x7
− x3x6 − x3x7 + x4x5 + x4x6 + x5x6
t7
−t5
−t2+1 = F
(2)
Ã6
(t),
E-type =Ẽ6(p15, w)
(p21, w2)
(p24, w2)
(p24, w3)
(p27, w1)
(p32, w4) q70(x) =
∑7
i=1
x2
i
−x1x6 −x2x3 −x2x4 −x2x5 −x3x6 +
x6x7
t7 + t6
− t5
− t4
− t3
−
t2 + t + 1 = F
D̃6
(t),
E-type =D̃6
(p16, w)
q27(x) =
∑7
i=1
x2
i
− x1x4 − x1x5 − x2x3 − x2x4 −
x2x5 − x2x6 + x3x6 + x3x7 + x4x5 + x6x7
t7 + t6
− t5
− t4
− t3
−
t2 + t + 1 = F
D̃6
(t),
E-type =D̃6
(p23, w2)
(p23, w3) q44(x) =∑7
i=1
x2
i
−x1x3−x2x3−x2x4−x2x5+x3x7
+ x4x5 − x4x6 − x5x6
t7 + t6
− t5
− t4
− t3
−
t2 + t + 1 = F
D̃6
(t),
E-type =D̃6
(p30, w)
(p32, w3)
(p18, w)
q32(x) =∑7
i=1
x2
i
−x1x3−x1x7−x2x3−x2x4−x2x5
− x2x6 + x4x6 + x5x6 + x6x7
t7
−2t5+t4+t3
−2t2+1,
E-type =D̃6(p26, w)
(p32, w1)
(p34, w)
(p19, w3) q35(x) =
∑7
i=1
x2
i
− x1x2 −
x1x7 − x2x3 − x2x4 − x2x5 − x2x6
+ x2x7 + x3x6 + x4x5
t7 + t6
− 2t4
− 2t3 + t +
1 = F
Ẽ6
(t), E-type =Ẽ6
(p5, w2) q9(x) =
∑7
i=1
x2
i
− x1x4 − x2x3 − x2x4
−x2x5 − x2x6 + x3x5 + x3x6 + x3x7
+x4x5 + x4x6 + x5x6
t7 + t6
− 2t4
− 2t3 + t +
1 = F
Ẽ6
(t), E-type =Ẽ6
(p24, w4)
(p19, w2)
q34(x) =∑7
i=1
x2
i
+ x1x7 − x2x3 − x2x4 − x2x5
− x2x6 + x2x7 + x3x6 + x4x5
t7 + t6
− 2t4
− 2t3 + t +
1 = F
Ẽ6
(t), E-type =Ẽ6
(p27, w3)
(p27, w4)
q56(x) =∑7
i=1
x2
i
− x1x4 − x2x3 − x2x4 − x2x5
− x2x6 + x3x7 + x5x6
t7 + t6
− 2t4
− 2t3 + t +
1 = F
Ẽ6
(t), E-type =Ẽ6
(p31, w6)
(p2, w)
q3(x) =∑7
i=1
x2
i
−x1x2+x1x3−x2x3−x2x4−x2x5
− x2x6 + x2x7 + x3x5 + x3x6 + x4x5
+ x4x6 − x4x7 + x5x6
t7 + t6
− 2t4
− 2t3 + t +
1 = F
Ẽ6
(t), E-type =Ẽ6
(p6, w1)
(p10, w1)
(p24, w1)
A. Polak, D. Simson 279
Table 5.9. A set of representatives of O(n,Z)-orbits in P -crit(Zn,Z),
for n = 7
(p, w) ind(p, w) ∈ O(7,Z)-Orb(q) ⊆ P -crit•
7 coxq(t) and E-type
(p17, w4)
q31(x) =∑7
i=1
x2
i
−x1x5−x2x3−x2x4−x2x5−x2x6
+ x4x6 + x4x7 + x5x6
t7 + t6
− 2t4
− 2t3 + t +
1 = F
Ẽ6
(t), E-type =Ẽ6
(p24, w5)
(p24, w6)
(p31, w5)
(p6, w3)
q12(x) =∑7
i=1
x2
i
−x1x3−x2x3−x2x4−x2x5−x2x6
+ x2x7 + x3x6 + x4x5 + x4x6 + x5x6
t7 + t6
− 2t4
− 2t3 + t +
1 = F
Ẽ6
(t), E-type =Ẽ6
(p7, w2)
(p7, w4)
(p17, w3)
(p27, w2)
(p31, w7) q66(x) =
∑7
i=1
x2
i
−x1x5 −x2x3 −x2x4 −x2x5 −x3x6 +
x4x7
t7 + t6
− 2t4
− 2t3 + t +
1 = F
Ẽ6
(t), E-type =Ẽ6
Remark 5.10. It follows from Tables 5.6 and 5.7 that the surjective
correspondence
ind : O(5,Z)-Orb(Z5) −−−−−→ O(6,Z)-Orb(P -crit(Z6,Z))
(3.3) induced by the map (p, w) 7→ inds,εs(p, w) := qp,s,w,εs , is far from
being injective. Indeed, the pairs (p2, w), (p4, w), (p7, w1) lie in differ-
ent O(5,Z)-orbits in Z5, but the P -critical unit forms ind(p2, w) = q2,
inds,εs(p4, w) = q5 and inds,εs(p7, w1) = q8 presented in Table 5.7 lie in
the O(6,Z)-orbit of the unit form
q2(x) =
6∑
i=1
x2
i + x1x5 + x1x6 − x2x3 − x2x4 − x2x5 + x2x6 + x3x5 + x4x5,
because we have q5 ∗ B1 = q2, q8 ∗ B2 = q2, and q8 ∗ B3 = q5, where
B1 =
0 0 0 −1 0 0
0 0 0 0 1 0
−1 0 0 0 0 0
0 0 −1 0 0 0
0 1 0 0 0 0
0 0 0 0 0 −1
, B2 =
0 −1 0 0 0 0
0 0 0 0 1 0
−1 0 0 0 0 0
0 0 0 −1 0 0
0 0 −1 0 0 0
0 0 0 0 0 −1
,
B3 =
0 0 0 0 1 0
0 −1 0 0 0 0
0 0 −1 0 0 0
0 0 0 −1 0 0
−1 0 0 0 0 0
0 0 0 0 0 −1
.
280 P -critical edge-bipartite graphs
Now we present a complete list of the Coxeter polynomials
cox∆(t) ∈ Z[t] of P -critical bigraphs ∆, with at most 10 vertices. To-
gether with the following corollary, the list is obtained by a computer
search.
Corollary 5.11. Assume that ∆ is a P -critical bigraph, with at most 10
vertices.
(a) If ∆ is of the Euclidean type D∆ = Ãn, n ≤ 9, then cox∆(t) is
one of the polynomials listed in the following table, see [25].
Table 5.12. Coxeter polynomials cox∆(t) of P -critical bigraphs ∆ of
E-type Ãn, n ≤ 9 and their reduced Coxeter numbers č∆
j F
(j)
∆
(t) č∆
j = 1 tn+1 − tn − t + 1 n
j ∈ {2, . . . , mn} tn+1 − tn+1−j − tj + 1 lcm(n−j+1, j)
where mn =
{
n
2 , if n is even,
n+1
2 , if n + 1 is even.
(b) If ∆ is of the Euclidean type D∆ ∈ {D̃n, Ẽ6, Ẽ7, Ẽ8}, n ≤ 9, then
cox∆(t) is one of the polynomials presented in Table 5.13.
Table 5.13. Coxeter polynomials cox∆(t) of P -critical bigraphs ∆
D∆ CGpolPEucl = {cox∆(t)}D∆=Eucl =
{
F
(j)
D∆
(t)
}
č∆
D̃4 F
(1)
D̃4
(t) = t5 + t4 − 2t3 − 2t2 + t + 1 č∆ = 2
F
(2)
D̃4
(t) = t5 − t4 − t + 1 = F
(1)
Ã4
(t) č∆ = 4
D̃5 F
(1)
D̃5
(t) = t6 + t5 − t4 − 2t3 − t2 + t + 1 č∆ = 6
F
(2)
D̃5
(t) = t6 − t5 − t + 1 = F
(1)
Ã5
(t) č∆ = 5
F
(3)
D̃5
(t) = t6 − t4 − t2 + 1 = F
(2)
Ã5
(t) č∆ = 4
F
(4)
D̃5
(t) = t6 − t5 − t4 + 2t3 − t2 − t + 1 č∆ = 6
F
(5)
D̃5
(t) = t6 − 2t5 + 3t4 − 4t3 + 3t2 − 2t + 1 č∆ = 4
A. Polak, D. Simson 281
Table 5.13. Coxeter polynomials cox∆(t) of P -critical bigraphs ∆
D∆ CGpolPEucl = {cox∆(t)}D∆=Eucl =
{
F
(j)
D∆
(t)
}
č∆
D̃6 F
(1)
D̃6
(t) = t7 + t6 − t5 − t4 − t3 − t2 + t + 1 č∆ = 4
F
(2)
D̃6
(t) = t7 − t6 − t + 1 = F
(1)
Ã6
(t) č∆ = 6
F
(3)
D̃6
(t) = t7 − t4 − t3 + 1 = F
(3)
Ã6
(t) č∆ = 12
F
(4)
D̃6
(t) = t7 − t6 + t5 − t4 − t3 + t2 − t + 1 č∆ = 4
F
(5)
D̃6
(t) = t7 − t6 − t5 + t4 + t3 − t2 + t + 1 č∆ = 8
F
(6)
D̃6
(t) = t7 − 2t6 + 2t5 − t4 − t3 + 2t2 − 2t + 1 č∆ = 12
F
(7)
D̃6
(t) = t7 − 2t5 + t4 + t3 − 2t2 + 1 č∆ = 6
D̃7 F
(1)
D̃7
(t) = t8 + t7 − t6 − t5 − t3 − t2 + t + 1 č∆ = 10
F
(2)
D̃7
(t) = t8 − t7 − t + 1 = F
(1)
Ã7
(t) č∆ = 7
F
(3)
D̃7
(t) = t8 − t6 − t2 + 1 = F
(2)
Ã7
(t) č∆ = 6
F
(4)
D̃7
(t) = t8 − 2t4 + 1 = F
(4)
Ã7
(t) č∆ = 4
F
(5)
D̃7
(t) = t8 − t7 + t5 − 2t4 + t3 − t + 1 č∆ = 12
F
(6)
D̃7
(t) = t8 − 2t6 + 2t4 − 2t2 + 1 č∆ = 8
F
(7)
D̃7
(t) = t8 − 2t7 + 2t6 − 2t5 + 2t4 − 2t3 + 2t2 − 2t + 1 č∆ = 8
F
(8)
D̃7
(t) = t8 − 2t7 + t6 + 2t5 − 4t4 + 2t3 + t2 − 2t + 1 č∆ = 6
F
(9)
D̃7
(t) = t8 − t7 + 2t6 − 3t5 + 2t4 − 3t3 + 2t2 − t + 1 č∆ = 12
F
(10)
D̃7
(t) = t8 − t7 − t6 + t5 + t3 − t2 − t + 1 č∆ = 10
D̃8 F
(1)
D̃8
(t) = t9 + t8 − t7 − t6 − t3 − t2 + t + 1 č∆ = 6
F
(2)
D̃8
(t) = t9 − t8 − t + 1 = F
(1)
Ã8
(t) č∆ = 8
F
(3)
D̃8
(t) = t9 − t5 − t4 + 1 = F
(4)
Ã8
(t) č∆ = 20
F
(4)
D̃8
(t) = t9 − t8 + 2t7 − 2t6 − 2t3 + 2t2 − t + 1 č∆ = 4
F
(5)
D̃8
(t) = t9 − t8 + t7 − t6 − t3 + t2 − t + 1 č∆ = 12
F
(6)
D̃8
(t) = t9 − t8 − t7 + t6 + t3 − t2 − t + 1 č∆ = 12
F
(7)
D̃8
(t) = t9 − t8 − t7 + 3t6 − 2t5 − 2t4 + 3t3 − t2 − t + 1 č∆ = 6
F
(8)
D̃8
(t) = t9 − t7 + t6 − t5 − t4 + t3 − t2 + 1 č∆ = 12
F
(9)
D̃8
(t) = t9 − t7 − t6 + t5 + t4 − t3 − t2 + 1 č∆ = 24
F
(10)
D̃8
(t) = t9 − 2t7 + t5 + t4 − 2t2 + 1 č∆ = 10
F
(11)
D̃8
(t) = t9 − 2t8 + t7 + t6 − t5 − t4 + t3 + t2 − 2t + 1 č∆ = 24
F
(12)
D̃8
(t) = t9 − 2t8 + 2t7 − 2t6 + t5 + t4 − 2t3 + 2t2 − 2t + 1 č∆ = 20
282 P -critical edge-bipartite graphs
Table 5.13. Coxeter polynomials cox∆(t) of P -critical bigraphs ∆
D∆ CGpolPEucl = {cox∆(t)}D∆=Eucl =
{
F
(j)
D∆
(t)
}
č∆
D̃9 F
(1)
D̃9
(t) = t10 + t9 − t8 − t7 − t3 − t2 + t + 1 č∆ = 14
F
(2)
D̃9
(t) = t10 − t9 − t + 1 = F
(1)
Ã9
(t) č∆ = 9
F
(3)
D̃9
(t) = t10 − t8 − t2 + 1 = F
(2)
Ã9
(t) č∆ = 8
F
(4)
D̃9
(t) = t10 − t6 − t4 + 1 = F
(4)
Ã9
(t) č∆ = 12
F
(5)
D̃9
(t) = t10 − t9 + t8 − 2t7 + 2t6 − 2t5 + 2t4 − 2t3 + t2 − t + 1 č∆ = 24
F
(6)
D̃9
(t) = t10 − t9 + 2t8 − 2t7 + t6 − 2t5 + t4 − 2t3 + 2t2 − t + 1 č∆ = 20
F
(7)
D̃9
(t) = t10 − t9 + t8 − 2t6 + 2t5 − 2t4 + t2 − t + 1 č∆ = 12
F
(8)
D̃9
(t) = t10 − t9 − t6 + 2t5 − t4 − t + 1 č∆ = 20
F
(9)
D̃9
(t) = t10 − 2t9 + 2t8 − 2t7 + t6 + t4 − 2t3 + 2t2 − 2t + 1 č∆ = 12
F
(10)
D̃9
(t) = t10 −2t9 + t8 + t7 −2t6 +2t5 −2t4 + t3 + t2 −2t+1 č∆ = 30
F
(11)
D̃9
(t) = t10 − t9 − t8 + 2t7 − 2t5 + 2t3 − t2 − t + 1 č∆ = 24
F
(12)
D̃9
(t) = t10 − t9 + t7 − t6 − t4 + t3 − t + 1 č∆ = 6
F
(13)
D̃9
(t) = t10 − 2t9 + t8 + 2t6 − 4t5 + 2t4 + t2 − 2t + 1 č∆ = 8
F
(14)
D̃9
(t) = t10 − t9 − t8 + t7 + t3 − t2 − t + 1 č∆ = 14
F
(15)
D̃9
(t) = t10 − t8 + t7 − 2t5 + t3 − t2 + 1 č∆ = 30
F
(16)
D̃9
(t) = t10 − t8 − t7 + 2t5 − t3 − t2 + 1 č∆ = 30
F
(17)
D̃9
(t) = t10 − 2t8 + t6 + t4 − 2t2 + 1 č∆ = 12
Ẽ6 F
(1)
Ẽ6
(t) = t7 + t6 − 2t4 − 2t3 + t + 1 č∆ = 6
F
(2)
Ẽ6
(t) = t7 − t6 − t + 1 = F
(1)
Ã6
(t) č∆ = 6
F
(3)
Ẽ6
(t) = t7 − t5 − t2 + 1 = F
(2)
Ã6
(t) č∆ = 10
F
(4)
Ẽ6
(t) = t7 − 2t6 + 2t5 − t4 − t3 + 2t2 − 2t + 1 č∆ = 12
F
(5)
Ẽ6
(t) = t7 − t6 − t5 + t4 + t3 − t2 − t + 1 č∆ = 8
Ẽ7 F
(1)
Ẽ7
(t) = t8 + t7 − t5 − 2t4 − t3 + t + 1 č∆ = 12
F
(2)
Ẽ7
(t) = t8 − t7 − t + 1 = F
(1)
Ã7
(t) č∆ = 7
F
(3)
Ẽ7
(t) = t8 − t6 − t2 + 1 = F
(2)
Ã7
(t) č∆ = 6
F
(4)
Ẽ7
(t) = t8 − t5 − t3 + 1 = F
(3)
Ã7
(t) č∆ = 15
F
(5)
Ẽ7
(t) = t8 − t7 + t5 − 2t4 + t3 − t + 1 č∆ = 12
F
(6)
Ẽ7
(t) = t8 − 2t6 + 2t4 − 2t2 + 1 č∆ = 8
F
(7)
Ẽ7
(t) = t8 − 2t7 + 2t6 − 2t5 + 2t4 − 2t3 + 2t2 − 2t + 1 č∆ = 8
A. Polak, D. Simson 283
Table 5.13. Coxeter polynomials cox∆(t) of P -critical bigraphs ∆
D∆ CGpolPEucl = {cox∆(t)}D∆=Eucl =
{
F
(j)
D∆
(t)
}
č∆
F
(8)
Ẽ7
(t) = t8 − 2t7 + t6 + 2t5 − 4t4 + 2t3 + t2 − 2t + 1 č∆ = 6
F
(9)
Ẽ7
(t) = t8 − 3t7 + 5t6 − 6t5 + 6t4 − 6t3 + 5t2 − 3t + 1 č∆ = 6
F
(10)
Ẽ7
(t) = t8 − 2t7 + t6 + t5 − 2t4 + t3 + t2 − 2t + 1 č∆ = 9
F
(11)
Ẽ7
(t) = t8 − t7 − t6 + t5 + t3 − t2 − t + 1 č∆ = 10
F
(12)
Ẽ7
(t) = t8 − t7 − t6 + 2t4 − t2 − t + 1 č∆ = 12
Ẽ8 F
(1)
Ẽ8
(t) = t9 + t8 − t6 − t5 − t4 − t3 + t + 1 č∆ = 30
F
(2)
Ẽ8
(t) = t9 − t8 − t + 1 = F
(1)
Ã8
(t) č∆ = 8
F
(3)
Ẽ8
(t) = t9 − t7 − t2 + 1 = F
(2)
Ã8
(t) č∆ = 14
F
(4)
Ẽ8
(t) = t9 − t5 − t4 + 1 = F
(4)
Ã8
(t) č∆ = 20
F
(5)
Ẽ8
(t) = t9 − t8 + t7 − t6 − t3 + t2 − t + 1 č∆ = 12
F
(6)
Ẽ8
(t) = t9 − t8 − t7 + 2t6 − t5 − t4 + 2t3 − t2 − t + 1 č∆ = 18
F
(7)
Ẽ8
(t) = t9 − t8 − t7 + t6 + t3 − t2 − t + 1 č∆ = 12
F
(8)
Ẽ8
(t) = t9 − t8 − t7 + t5 + t4 − t2 − t + 1 č∆ = 18
F
(9)
Ẽ8
(t) = t9 − 2t8 + 2t7 − t6 − t3 + 2t2 − 2t + 1 č∆ = 6
F
(10)
Ẽ8
(t) = t9 − 2t8 + 2t7 − 2t6 + t5 + t4 − 2t3 + 2t2 − 2t + 1 č∆ = 20
F
(11)
Ẽ8
(t) = t9 − 2t8 + t7 + t6 − t5 − t4 + t3 + t2 − 2t + 1 č∆ = 24
F
(12)
Ẽ8
(t) = t9 − 2t8 + t7 + t2 − 2t + 1 č∆ = 14
F
(13)
Ẽ8
(t) = t9 − 2t8 + 3t6 − 2t5 − 2t4 + 3t3 − 2t + 1 č∆ = 12
F
(14)
Ẽ8
(t) = t9 − 3t8 + 4t7 − 3t6 + t5 + t4 − 3t3 + 4t2 − 3t + 1 č∆ = 30
F
(15)
Ẽ8
(t) = t9 − 4t8 + 8t7 − 9t6 + 4t5 + 4t4 − 9t3 + 8t2 − 4t + 1 č∆ = 6
F
(16)
Ẽ8
(t) = t9 − t7 − t6 + t5 + t4 − t3 − t2 + 1 č∆ = 24
F
(17)
Ẽ8
(t) = t9 − 2t7 − t6 + 2t5 + 2t4 − t3 − 2t2 + 1 č∆ = 12
References
[1] I. Assem, D. Simson and A. Skowroński, Elements of the Representation Theory of
Associative Algebras, Vol. 1. Techniques of Representation Theory, London Math.
Soc. Student Texts 65, Cambridge Univ. Press, Cambridge-New York, 2006.
[2] K.T. Balińska and S.K Simić, The nonregular, bipartite, integral graphs with
maximum degree four, Discrete Math. 236(2001), 13–24.
[3] M. Barot and J.A. de la Peña, The Dynkin type of a non-negative unit form, Expo.
Math. 17(1999), 339–348.
284 P -critical edge-bipartite graphs
[4] G. Belitskij and V. V. Sergeichuk, Complexity of matrix problems, Linear Algebra
Appl. 361(2003), 203–222.
[5] V. M. Bondarenko and M. V. Stepochkina, (Min, max)-equivalency of posets and
nonnegative of the quadratic Tits forms, Ukrain. Mat. Zh. 60(2008), 1157–1167.
[6] V. M. Bondarenko and M. V. Stepochkina, Description of posets with respect to
the nonnegativity Tits forms, Ukrain. Mat. Zh. 61(2009), 734–746.
[7] R.A. Brualdi and D. M. Cvetković, Combinatorial Approach to Matrix Theory
and its Application, CRS Press (Boca Raton), 2008.
[8] J. A. Drozd, Coxeter transformations and representations of partially ordered sets,
Funkc. Anal. i Priložen. 8(1974), 34–42 (in Russian); English version: Funct. Anal.
Appl. 8(1974), 219–225.
[9] P. Dräxler, J. A. Drozd, N. S. Golovachtchuk, S. A. Ovsienko, M. Zeldych, To-
wards the classification of sincere weakly positive unit forms, Europ. J. Combinat.
16(1995), 1-16.
[10] P. Gabriel and A. V. Roiter, Representations of Finite Dimensional Algebras,
Algebra VIII, Encyclopaedia of Math. Sc., Vol. 73, Springer–Verlag, 1992.
[11] Y. Han and D. Zhao, Superspecies and their representations, J. Algebra 321(2009),
3668–3680.
[12] H. -J. von Höhne, On weakly positive unit forms, Comment Math. Helvetici,
63(1988), 312–336.
[13] S. M. Johnson, Generation of permutations by adjacent transpositions, Math.
Comp. 17(1963), 282–285.
[14] A. Kisielewicz and M. Szykuła, Rainbow induced subgraphs in proper vertex color-
ings, Fund. Inform. 111(2011), 437–451, doi: 10.3233/FI-2011-572.
[15] D. E. Knuth, The Art of Computer Programming, Vol. 4, Fascicle 2: Generating
All Tuples and Permutations, Addison-Wesley Professional, 2005.
[16] J. Kosakowska, Inflation algorithms for positive and principal edge-bipartite graphs
and unit quadratic forms, Fund. Inform. 119(2012), 149-162, doi: 10.3233/FI-2012-
731.
[17] J. Kosakowska and D. Simson, Hereditary coalgebras and representations of species,
J. Algebra 293(2005), 457–505.
[18] S. Ladkani, On the periodicity of Coxeter transformations and the non-negativity
of their Euler forms, Linear Algebra Appl. 428(2008), 742–753.
[19] P. Lakatos, On spectral radius of Coxeter transformation of trees, Publ. Math.
54(1999), 181–87.
[20] H. Lenzing and J.A de la Peña, Spectral analysis of finite dimensional algebras
and singularities, In: Trends in Representation Theory of Algebras and Related
Topics, ICRA XII, (ed. A. Skowroński), Series of Congress Reports, European
Math. Soc. Publishing House, Zürich, 2008, pp. 541–588.
[21] G. Marczak, A. Polak and D. Simson, P -critical integral quadratic forms and
positive forms. An algorithmic approach, Linear Algebra Appl. 433(2010), 1873–
1888, doi: 10.1016/j.laa. 2010.06.052.
A. Polak, D. Simson 285
[22] S. A. Ovsienko, Integral weakly positive forms, in Schur Matrix Problems and
Quadratic Forms, Inst. Mat. Akad. Nauk USSR, Preprint, 78.25 (1978), pp. 3–17.
[23] A. Polak, http://www.mat.umk.pl/~aga13/pkrytyczne.html, Cited 1 May 2013.
[24] A. Polak and 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:
10.1016/j.endm.2011.10.021.
[25] A. Polak and D. Simson, On Coxeter spectral classification of P -critical edge-
bipartite graphs of Euclidean type Ãn, Proc. Combinatorics 2012, Perugia, Septem-
ber 2012, Electronic Notes in Discrete Mathematics 40(2013), 311–316, doi:
10.1016/j.endm.2013.05.055.
[26] A. Polak and D. Simson, Algorithmic experiences in Coxeter spectral study of
P -critical edge-bipartite graphs and posets, SYNASC 2013, IEEE Computer Society,
IEEE CPS, Tokyo, 2013, in press.
[27] A. Polak and D. Simson, Coxeter spectral classification of almost T P -critical
one-peak posets using symbolic and numeric computations, Linear Algebra Appl.
2014, in press, doi: 10.1016/j.laa. 2013.12.018.
[28] C. M. Ringel, Tame Algebras and Integral Quadratic Forms, Lecture Notes in
Math., Vol. 1099, Springer–Verlag, Berlin–Heidelberg–New York-Tokyo, 1984.
[29] M. Sato, Periodic Coxeter matrices and their associated quadratic forms, Linear
Algebra Appl. 406(2005), 99–108; doi: 10.1016/j.laa. 2005.03.036.
[30] V. V. Sergeichuk, Canonical matrices for linear matrix problems, Linear Algebra
Appl. 317(2000), 53–102.
[31] D. Simson, Linear Representations of Partially Ordered Sets and Vector Space
Categories, Algebra, Logic and Applications, Vol. 4, Gordon & Breach Science
Publishers, 1992.
[32] D. Simson, A reduction functor, tameness and Tits form for a class of orders, J.
Algebra 174(1995), 430–452.
[33] D. Simson, Incidence coalgebras of intervally finite posets, their integral quadratic
forms and comodule categories, Colloq. Math. 115(2009), 259–295.
[34] D. Simson, Integral bilinear forms, Coxeter transformations and Coxeter polyno-
mials of finite posets, Linear Algebra Appl. 433(2010), 699–717; doi: 10.1016/j.laa.
2010.03.04.
[35] D. Simson, Mesh geometries of root orbits of integral quadratic forms, J. Pure
Appl. Algebra 215(2011), 13–34, doi: 10.1016/j.jpaa. 2010.02.029.
[36] D. Simson, Mesh algorithms for solving principal Diophantine equations, sand-glass
tubes and tori of roots, Fund. Inform. 109(2011), 425–520, doi: 10.3233/FI-2011-
603.
[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.
[38] D. Simson, A Coxeter-Gram classification of positive simply-laced bipartite graphs
and unit forms, SIAM J. Discr. Math. 27(2013), 827-854.
286 P -critical edge-bipartite graphs
[39] D. Simson and A. Skowroński, Elements of the Representation Theory of Associative
Algebras, Vol. 2, Tubes and Concealed Algebras of Euclidean Type, London Math.
Soc. Student Texts 71, Cambridge Univ. Press, Cambridge-New York, 2007.
[40] D. Simson and M. Wojewódzki, An algorithmic solution of a Birkhoff type problem,
Fund. Inform. 83(2008), 389–410.
[41] H. F. Trotter, Perm (Algorithm 115), Comm. ACM, 5(1962), 434–435.
[42] T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4(1982), 47–74.
[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.
Contact information
A. Polak Faculty of Mathematics and Computer
Sciences, Nicolaus Copernicus University,
ul. Chopina 12/18, 87-100 Toruń, Poland
E-Mail: apolak@mat.umk.pl
D. Simson Faculty of Mathematics and Computer
Sciences,Nicolaus Copernicus University,
ul. Chopina 12/18, 87-100 Toruń, Poland
E-Mail: simson@mat.umk.pl
Received by the editors: 26.07.2013
and in final form 26.07.2013.
|