Minimax sums of posets and the quadratic Tits form
In this paper we study the structure of infinite posets with positive Tits form. In particular, there arise posets of specific form which we call minimax sums of posets.
Збережено в:
| Дата: | 2004 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2004
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/155944 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Minimax sums of posets and the quadratic Tits form / V.M. Bondarenko, A.M. Polishchuk // Algebra and Discrete Mathematics. — 2004. — Vol. 3, № 1. — С. 17–36. — Бібліогр.: 20 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-155944 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1559442019-06-18T01:27:38Z Minimax sums of posets and the quadratic Tits form Bondarenko, V.M. Polishchuk, A.M. In this paper we study the structure of infinite posets with positive Tits form. In particular, there arise posets of specific form which we call minimax sums of posets. 2004 Article Minimax sums of posets and the quadratic Tits form / V.M. Bondarenko, A.M. Polishchuk // Algebra and Discrete Mathematics. — 2004. — Vol. 3, № 1. — С. 17–36. — Бібліогр.: 20 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 15A, 16G. http://dspace.nbuv.gov.ua/handle/123456789/155944 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
In this paper
we study the structure of infinite posets with positive Tits form. In
particular, there arise posets of specific form which we call minimax
sums of posets. |
| format |
Article |
| author |
Bondarenko, V.M. Polishchuk, A.M. |
| spellingShingle |
Bondarenko, V.M. Polishchuk, A.M. Minimax sums of posets and the quadratic Tits form Algebra and Discrete Mathematics |
| author_facet |
Bondarenko, V.M. Polishchuk, A.M. |
| author_sort |
Bondarenko, V.M. |
| title |
Minimax sums of posets and the quadratic Tits form |
| title_short |
Minimax sums of posets and the quadratic Tits form |
| title_full |
Minimax sums of posets and the quadratic Tits form |
| title_fullStr |
Minimax sums of posets and the quadratic Tits form |
| title_full_unstemmed |
Minimax sums of posets and the quadratic Tits form |
| title_sort |
minimax sums of posets and the quadratic tits form |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2004 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/155944 |
| citation_txt |
Minimax sums of posets and the quadratic Tits form / V.M. Bondarenko, A.M. Polishchuk // Algebra and Discrete Mathematics. — 2004. — Vol. 3, № 1. — С. 17–36. — Бібліогр.: 20 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT bondarenkovm minimaxsumsofposetsandthequadratictitsform AT polishchukam minimaxsumsofposetsandthequadratictitsform |
| first_indexed |
2025-07-14T08:08:57Z |
| last_indexed |
2025-07-14T08:08:57Z |
| _version_ |
1837609032037171200 |
| fulltext |
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 1. (2004). pp. 17 – 36
c© Journal “Algebra and Discrete Mathematics”
Minimax sums of posets and the quadratic Tits
form
Vitalij M. Bondarenko, Andrej M. Polishchuk
Communicated by V. V. Kirichenko
Dedicated Michael Ringel on the occasion of his sixtieth birthday
Abstract. Let S be an infinite poset (partially ordered set)
and Z
S∪0
0
the subset of the cartesian product Z
S∪0 consisting of
all vectors z = (zi) with finite number of nonzero coordinates. We
call the quadratic Tits form of S (by analogy with the case of
a finite poset) the form qS : Z
S∪0
0
→ Z defined by the equality
qS(z) = z2
0
+
∑
i∈S z2
i +
∑
i<j,i,j∈S zizj − z0
∑
i∈S zi. In this paper
we study the structure of infinite posets with positive Tits form. In
particular, there arise posets of specific form which we call minimax
sums of posets.
1. Introduction
A (finite or infinite) poset S is called a sum of subposets A1 . . . , Am if
Ai ∩ Aj = ∅ for any distinct i, j and S = A1 ∪ . . . ∪ Am. If any two
elements a ∈ Ai and b ∈ Aj are incomparable whenever i 6= j, this sum
is called direct. We say that the sum S = A1 + . . . + Am is said to be
minimax (resp. semiminimax) if x < y with x and y belonging to different
summands implies that x is minimal and (resp. or) y maximal in S.
Let S be a finite poset. Denote by R0(S) the set of pairs (x, y) ∈ S×S
with “adjacent” x and y (i.e. comparable x and y such that there is no
element z satisfying x < z < y if x < y, and x > z > y if x > y). If
2000 Mathematics Subject Classification: 15A, 16G.
Key words and phrases: poset, minimax sum, the rank of a sum, the Tits
form.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.18 Minimax sums of posets and the quadratic Tits form
S = A1 + . . . + Am, the number
r0(S) =
1
2
(|R0(S)| −
m∑
i=1
|R0(Ai)|)
will be called the rank of the sum.
Recall that a linear ordered set is also called a chain (or a chained
set).
From the well-known results of V. M. Bondarenko, M. M. Kleiner,
L. A. Nazarova and A. G. Zavadskij (see e.g. [1]) it follows that finite
posets of various representation types have a number of properties which
are naturally formulated in our new terms (and, clearly, could not be
observed before).
Theorem 1. Let S be a minimal poset of infinite (resp. wild) representa-
tion type. Then S is a minimax sum of three (resp. three or four) chains,
having rank 0 or 1.
Theorem 2. Let S be a faithful poset of finite representation type. Then
S is a minimax sum of n 6 3 chains.
Theorem 3. Let S be a minimal non-finitely-parameter poset. Then S
is a semiminimax sum of three or four chains.
Theorem 4. Let S be a faithful poset of polynomial growth (up to iso-
morphism and duality, the number of such posets is 110). Then S is a
semiminimax sum of n 6 4 chains.
Notice that in Theorem 2 and 4 the number of the chains is not
necessarily equal to the width of S.
We do not know direct proofs of this theorems. But in studying some
of properties of the Tits form of posets there appear to be new connections
with minimax sums, and we will see one of such connection in this paper.
The quadratic Tits form, introduced by P. Gabriel [2] for quivers and
Yu. A. Drozd for posets and a wide class of classification problems (see
resp. [3] and [4] plays an important role in representation theory. In
particular, there are many results on connections between representation
types of various objects and properties of the Tits forms. The reader in-
terested in this theme is referred to the papers of [5], [6], the monographs
[1], [7], and, e.g., the papers [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
(with the bibliographies therein). Our paper is devoted to study the
structure of infinite posets with positive Tits form.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.V. M. Bondarenko, A. M. Polishchuk 19
2. Formulation of the main result
Let S be an infinite poset and Z denotes the integer numbers. Denote
by (ZS∪0)0 = Z
S∪0
0 the subset of the cartesian product Z
S∪0 consisting
of all vectors z = (zi) with finite number of nonzero coordinates. We call
the quadratic Tits form of S (by analogy with the case of a finite poset)
the form qS : Z
S∪0
0 → Z defined by the equality
qS(z) = z2
0 +
∑
i∈S
z2
i +
∑
i<j,i,j∈S
zizj − z0
∑
i∈S
zi.
This form is called positive if it take positive values for all z ∈ Z
S∪0
0 .
In considering a poset S = (A, 6) the set A will not be written and
therefore we keep to the following conventions: by a subset of S we mean
a subset of A together with the induced order relation (which is denoted
by the same symbol 6), we write x ∈ S instead of x ∈ A, etc.
The definition of rank of a sum of finite posets from Introduction
is incorrect for infinite ones. Now we introduce the notion of the rank
of a sum of posets in the general case (which coincides with those of
Introduction in the case of finite posets).
For a sum S of posets A1, . . . , An let R<(Ai, Aj) denotes the set of
pairs (x, y) ∈ Ai × Aj with x < y. Such a pair (a, b) is said to be short
if there is no other such a pair (a′, b′) satisfying a 6 a′, b′ 6 b. By
R<
0 (Ai, Aj) we denote the subset of all short pairs from R<(Ai, Aj). We
call the order r0 = r0(A1, . . . , An) of the set
R0(A1, . . . , An) =
n⋃
i,j=1
(i6=j)
R<
0 (Ai, Aj)
the rank of the sum S. Obviously, a direct sum of posets has the rank 0.
Note that the notion of a sum have been introduced by the internal
way (see Introduction). The external way is possible but not natural,
however it is natural in some special cases, and in particular when one
has a minimax sum of rank 1 of two chains.
A poset with the only pair of incomparable elements will be called an
almost chain or an almost chained set.
Our aim in this paper is to classifying the infinite posets with positive
Tits form.
Main theorem. Let S be an infinite poset. Then the Tits form of S is
positive if and only if one of the following condition holds:
1) S is a minimax sum of rank r < 2 of two chains;
2) S is a direct sum of a chain and an almost chain.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.20 Minimax sums of posets and the quadratic Tits form
Note that a sum of rank 0 of two chains from condition 1) is the direct
sum of these chains; chains in 1) and 2) may be empty.
3. Subsidiary lemmas
When we determine some poset T , the corresponding order relation is
given up to transitivity. In the case when the elements of a poset T
are denoted by natural numbers, the order relation is denoted by ≺ (to
distinguish between the given relation and the natural ordering of the
integer numbers); and then the coordinates zi of a vector z ∈ Z
T∪0 will
be arranged in the natural way (in increasing order of the integer index
i ∈ T ∪ 0). If, in addition, we indicate the figure corresponding to the
poset T , its points are not indexed, but the reader can easily establish
a one-to-one correspondence between elements of T and points of the
figure.
Lemma 1. Let T = {1, 2, 3, 4} (without comparable i and j for i 6= j) :
e e e e ;
then qT (2, 1, 1, 1, 1) = 0, and consequently the form qT (z) is not positive.
Lemma 2. Let T = {1, 2, 3, 4 | 1 ≺ 4, 2 ≺ 4, 3 ≺ 4} :
e e e
e
¡
¡
¡
@
@
@
;
then qT (1, 1, 1, 1,−1) = 0, and consequently the form qT (z) is not positive.
Lemma 3. Let T = {1, 2, 3, 4, 5, 6, 7, 8 | 2 ≺ 3, 4 ≺ 5 ≺ 6 ≺ 7 ≺ 8} :
e e
e
e
e
e
ee
e
;
then qT (6, 3, 2, 2, 1, 1, 1, 1, 1) = 0, and consequently the form qT (z) is not
positive.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.V. M. Bondarenko, A. M. Polishchuk 21
Lemma 4. Let T = {1, 2, 3, 4, 5, 6, 7, 8 | 2 ≺ 8, 3 ≺ 4 ≺ 5 ≺ 6 ≺ 7 ≺ 8} :
e e e
e
e
ee
e
e
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥¥
;
then qT (4, 2, 3, 1, 1, 1, 1, 1,−2) = 0, and consequently the form qT (z) is
not positive.
Lemma 5. Let T = {1, 2, 3, 4, 5, 6, 7, 8 | 1 ≺ 3, 2 ≺ 3, 2 ≺ 5, 4 ≺ 5 ≺ 6 ≺
7 ≺ 8} :
e e e
e e
e
e
e
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
;
then qT (0, 1, 3,−2, 2,−1,−1,−1,−1) = 0, and consequently the form
qT (z) is not positive.
Lemma 6. Let T = {1, 2, 3, 4 | 1 ≺ 3, 1 ≺ 4, 2 ≺ 3, 2 ≺ 4} :
e e
e e
¡
¡
¡
@
@
@
;
then qT (0, 1, 1,−1,−1) = 0, and consequently the form qT (z) is not posi-
tive.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.22 Minimax sums of posets and the quadratic Tits form
Lemma 7. Let T = {1, 2, 3, 4, 5, 6, 7 | 1 ≺ 2, 3 ≺ 4 ≺ 5 ≺ 6 ≺ 7, 1 ≺ 5} :
e
e
e
e
e
e
e
¢
¢
¢
¢
¢
¢
;
then qT (0,−2, 1,−1,−1, 1, 1, 1) = 0, and consequently the form qT (z) is
not positive.
Lemma 8. Let T = {1, 2, 3, 4, 5, 6, 7 | 1 ≺ 5, 2 ≺ 3 ≺ 4 ≺ 5 ≺ 6 ≺ 7} :
e e
e
e
e
e
e
£
£
£
£
£
£
£
££
;
then qT (1, 2, 1, 1, 1,−1,−1,−1) = 0, and consequently the form qT (z) is
not positive.
Lemma 9. Let T = {1, 2, 3, 4, 5, 6, 7 | 1 ≺ 3 ≺ 4 ≺ 5 ≺ 6 ≺ 7, 1 ≺ 2 ≺
6} :
e
e
e
e
e
e
e
£
£
£
£
£
£
£
££
@
@
@
;
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.V. M. Bondarenko, A. M. Polishchuk 23
then qT (1,−1, 2, 1, 1, 1,−1,−1) = 0, and consequently the form qT (z) is
not positive.
Lemma 10. Let T = {1, 2, 3, 4, 5, 6, 7, 8 | 1 ≺ 2 ≺ 8, 3 ≺ 4 ≺ 5 ≺ 6 ≺ 7 ≺
8} :
e
e
e
e
e
e
e
e
¤
¤
¤
¤
¤
¤
¤
¤
¤
¤
¤¤
;
then qT (3, 2, 2, 1, 1, 1, 1, 1,−3) = 0, and consequently the form qT (z) is
not positive.
Lemma 11. Let T = {1, 2, 3, 4, 5, 6, 7, 8 | 1 ≺ 2, 3 ≺ 4 ≺ 5 ≺ 6 ≺ 7 ≺
8, 1 ≺ 4} :
e
e
e
e
e
e
e
e
¡
¡
¡
;
then qT (1,−3, 2,−2, 1, 1, 1, 1, 1) = 0, and consequently the form qT (z) is
not positive.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.24 Minimax sums of posets and the quadratic Tits form
Lemma 12. Let T = {1, 2, 3, 4, 5, 6, 7, 8 | 1 ≺ 7, 2 ≺ 3 ≺ 4 ≺ 5 ≺ 6 ≺ 7 ≺
8} :
e e
e
e
ee
e
e
e
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥¥
;
then qT (2, 3, 1, 1, 1, 1, 1,−2,−2) = 0, and consequently the form qT (z) is
not positive.
Lemma 13. Let T = {1, 2, 3, 4, 5, 6, 7, 8 | 1 ≺ 4, 2 ≺ 3 ≺ 4 ≺ 5 ≺ 6 ≺ 7 ≺
8} :
e e
e
e
e
e
e
e
¢
¢
¢
¢
¢
¢
;
then qT (1, 3, 2, 2,−1,−1,−1,−1,−1) = 0, and consequently the form
qT (z) is not positive.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.V. M. Bondarenko, A. M. Polishchuk 25
Lemma 14. Let T = {1, 2, 3, 4, 5, 6, 7, 8 | 1 ≺ 2 ≺ 8, 3 ≺ 4 ≺ 5 ≺ 6 ≺ 7 ≺
8, 1 ≺ 7} :
e
e
e
e
e
e
e
e
¤
¤
¤
¤
¤
¤
¤
¤
¤
¤
¤¤
¤
¤
¤
¤
¤
¤
¤
¤
¤
¤
¤¤
;
then qT (2, 2, 1, 1, 1, 1, 1,−1,−2) = 0, and consequently the form qT (z) is
not positive.
Lemma 15. Let T = {1, 2, 3, 4, 5, 6, 7, 8 | 1 ≺ 2 ≺ 8, 3 ≺ 4 ≺ 5 ≺ 6 ≺ 7 ≺
8, 1 ≺ 4} :
e
e
e
e
e
e
e
e
¤
¤
¤
¤
¤
¤
¤
¤
¤
¤
¤¤
¡
¡
¡
;
then qT (1,−2, 2,−1, 1, 1, 1, 1,−1) = 0, and consequently the form qT (z)
is not positive.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.26 Minimax sums of posets and the quadratic Tits form
Lemma 16. Let T = {1, 2, 3, 4, 5, 6, 7, 8 | 1 ≺ 2 ≺ 5, 3 ≺ 4 ≺ 5 ≺ 6 ≺ 7 ≺
8, 1 ≺ 4} :
e
e
e
e
e
e
e
e
¡
¡
¡
¡
¡
¡
;
then qT (1, 1, 2, 2, 1,−1,−1,−1,−1) = 0, and consequently the form qT (z)
is not positive.
Lemma 17. Let T = {1, 2, 3, 4, 5, 6, 7, 8 | 1 ≺ 3 ≺ 4 ≺ 5 ≺ 6 ≺ 7 ≺ 8, 1 ≺
2 ≺ 8} :
e
e
e
e
e
e
e
e
@
@
@
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥¥
;
then qT (2,−2, 3, 1, 1, 1, 1, 1,−2) = 0, and consequently the form qT (z) is
not positive.
For a poset T , we denote by T ∗ the poset dual to T ; we will always
assume that T ∗ = T as usual sets (then x < y in T ∗ = S iff x > y in T ).
Since the Tits forms of a poset T and the dual poset T ∗ are the same, the
dual lemmas (Lemmas 1∗ – 17∗), i.e. those with the dual posets T ∗
1 –T ∗
17
instead of T1–T17 (and the same vectors), are hold.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.V. M. Bondarenko, A. M. Polishchuk 27
4. Proof of Main theorem: necessity
We first introduce some definitions and notation.
Given nonempty subsets X, Y ∈ S, we write X ⊳ Y if x < y for some
x ∈ X, y ∈ Y . and X 6⊳Y if otherwise. The sum S = A1 + . . . + Am
is said to be one-sided if the transitive relation on the set of summands
{A1, . . . , Am} generated by the relation ⊳ is an order relation. When the
sum S is one-sided and Ai ⊳ Aj is not satisfied whenever i > j (resp.
i < j), we say that the sum is right (resp. left).
Let A and B be subsets of a poset S. If there are no comparable
elements x ∈ A and y ∈ B, then A and B will be called incomparable
(in this case their sum is direct). It is natural to assume that subsets
A 6= ∅ and B = ∅ are incomparable; and when we say that A and B
are not incomparable (or write x < y for some x ∈ A and y ∈ B), it, in
particular, means that A 6= ∅ and B 6= ∅).
A subset A of a poset S is said to be upper (respectively lower) if
x ∈ A whenever x > y (respectively x < y) and y ∈ A. The subset
of S consisting of all elements x which are comparable to each element
y ∈ S is denoted by S0; obviously, it is chained. Note that we identify
singletons with the elements themselves.
Let S be a poset. By NS(x), where x is an element of S, we denote
the set of all elements of S not comparable to x, and, for a subset X of S,
set NS(X) =
⋂
x∈X NS(x). An element x ∈ S is said to be isolated if x ∈
NS(S \x), or in other words the subsets {x} and S \x are incomparable;
analogously, a subset A of S is said to be isolated if A and S \ A are
incomparable. Recall that the width of the poset S is the maximum
number of pairwise incomparable elements of S; it is denoted by w(S).
We will need a special case of the following proposition.
Proposition 18. An infinite poset S of finite width m is a sum of chains
S1, . . . , Sm with S1 being infinite and each Si a maximal chained subset
in Si + · · · + Sm.
Proof. It follows from Theorem 15 [20, p.133] that the poset S is a sum
of chained subsets X1, · · · , Xm. One of these chains, say X1, is infinite.
Let m > 1 (the case m = 1 is obvious). Set
X
(1)
1 = X1,
X
(2)
1 = X
(1)
1 ∪ {x ∈ X2 |X
(1)
1 ∪ x is chained},
X
(3)
1 = X
(2)
1 ∪ {x ∈ X3 |X
(2)
1 ∪ x is chained},
.....................................................................
X
(m)
1 = X
(m−1)
1 ∪ {x ∈ Xm |X
(m−1)
1 ∪ x is chained}.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.28 Minimax sums of posets and the quadratic Tits form
Obviously, X
(1)
1 ⊆ X
(2)
1 · · · ⊆ X
(m)
1 with all the subsets to be chained.
Moreover, it is easy to see that X
(m)
1 is a maximal chained subset (of S).
Indeed, suppose the contrary and let a 6∈ X
(m)
1 be an element with the
subset X
(m)
1 ∪ a to be chained; and if a ∈ Xj , then a ∈ X
(j)
1 (by the
definition of X
(j)
1 ), and consequently a ∈ X
(m)
1 ; a contradiction.
Thus we can take X
(m)
1 as S1. Note that in fact we do not make use
of infiniteness in the last arguments; considering the poset (X2 \ S1) +
· · · + (Xm \ S1) of width m − 1 and applying induction (on the width),
we complete the proof of our statement.
We proceed now immediately to the proof of the necessity of the
theorem; up to the end of the section we assume that S is an infinite poset
with positive Tits form. We prove that one of the following condition
holds:
I) S is a direct sum of two chained subsets;
II) S is a direct sum of a chained and an almost chained subsets;
III) S is a minimax sum of rank r = 1 of two chained subsets.
By Lemma 1 w(S) < 4. If w(S) = 1, then condition I (with a direct
summand to be empty) holds.
We now consider the case w(S) = 2. Then by Lemma 6 S0 = S−
0 ∪S+
0 ,
where the subset S−
0 is lower and the subset S+
0 upper.
We say that a poset S contains (no) subsets of the form T , where T
is a fixed poset, if there are (no) subsets of S isomorphic to T .
We need the following simple statement.
Proposition 19. A (finite or infinite) poset with positive Tits form is
chained or almost chained if and only if it contains no subset isomorphic
to one of the following posets:
a) {1, 2, 3} (without comparable i 6= j);
b) {1, 2, 3 | 1 ≺ 2}.
Proof. It is easy to see that a poset P is chained or almost chained if and
only if it contains no subset isomorphic to the poset a) or the poset b) or
the following one:
c) {1, 2, 3, 4 | 1 ≺ 3, 1 ≺ 4, 2 ≺ 3, 2 ≺ 4}.
But when P has positive Tits form, it does not contain subsets of the
form c).
Using this proposition, we prove the following lemma.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.V. M. Bondarenko, A. M. Polishchuk 29
Lemma 20. If w(S) = 2 and S0 is infinite, then S is almost chained.
Proof. Since w(S) = 2, the poset S contains no subsets of the form a). It
remains to show that S contains no subsets of the form b). Suppose the
contrary and fix elements a, b, c such that b < c and a is incomparable
with {b, c}. Since S0 is infinite, so is S−
0 or S+
0 . We may assume, without
loss of generality, that S+
0 is infinite (otherwise we replace S by S∗). Then
the subset of S, consisting of the elements a, b, c and arbitrary elements
d1 < d2 < d3 < d4 < d5 of S+
0 , is isomorphic to the poset T from Lemma
13, a contradiction.
Thus, if S is of width 2 and S0 is infinite, then condition II) (with the
empty chain) holds.
We now consider the case when S0 is empty. Then obviously NS(x) 6=
∅ for any x ∈ S.
Lemma 21. If w(S) = 2 and S0 = ∅, then S is a one-sided minimax
sum (of rank r > 0) of two chained subset.
Proof. We set up S in the form of a sum of two chained subset P and
Q with P being infinite (see Proposition 18). We can obviously suppose
that S = P + Q is of rank at least 1. Let a ∈ P and b ∈ Q be some
comparable elements; without loss of generality one may assume that
a < b (when a > b, we replace S by S∗).
Set
P1 = {x ∈ S |x > b} ∩ P = {a}> ∩ {x ∈ P |x > b},
P2 = {x ∈ S |x < b} ∩ P = ({a}> ∩ {x ∈ P |x < b}) ∪ ({a}< ∩ P ) ∪ {a},
P3 = {a}> ∩ NS(b).
Since P is infinite and P = P1 ∪P2 ∪P3, one of the subsets Pi is infinite.
We first show that the poset P1 is finite. Suppose the contrary and
consider the subset Q1, consisting of the element b, arbitrary elements
c ∈ NS(a), d ∈ NS(b) and arbitrary elements e1 < e2 < e3 < e4 < e5 from
P1. When c is comparable to d (then c < d), the subset of Q1, consisting
of the elements a, b, c, d, is isomorphic to the poset T from Lemma 6; and
when c and d are incomparable, Q1 is isomorphic to the poset T from
Lemma 13. In both cases we get a contradiction. So P1 is finite.
Show, further, that the subset P2 is finite too. Suppose the contrary
and let ai, 1 6 i 6 5 be elements of P2 such that a1 < a2 < a3 <
a4 < a5 (note that the inequality a5 6 a does not necessarily hold). Fix
elements c ∈ NS(a5), d ∈ NS(b) and consider the subset R1, consisting
of the elements b, c, d, a1, a2, a3, a4, a5; we may assume that c and d are
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.30 Minimax sums of posets and the quadratic Tits form
incomparable (otherwise a5, b, c and d form a subset isomorphic to T from
Lemma 6). If c and ai are incomparable for each i = 1, 2, 3, 4 then R1 is
isomorphic to the poset T ∗ from Lemma 11∗, a contradiction. Otherwise
we denote by s the largest i ∈ {1, 2, 3, 4} for which ai < b. Then if
s = 1, the subset R1 is isomorphic to the poset T ∗ from Lemma 15∗,
and if s = 4, R1 is isomorphic to the poset T ∗ from Lemma 16∗; when
s = 2, the subset R1 \ {d} is isomorphic to the poset T ∗ from Lemma 9∗,
and when s = 3, the subset R1 \ {b} is isomorphic to the poset T ∗ from
Lemma 8∗. Again we have a contradiction. Thus, the subsets P1 and P2
are finite, and consequently P3 is infinite.
We now show that the element b is a maximal element of Q (then,
since S0 = ∅, b is a maximal element of S).
Suppose the contrary and fix an element c of {b}> ∩ Q. Consider
the subset R2, consisting of the elements a, b, c and arbitrary elements
a1 < a2 < a3 < a4 < a5 of the subset NS(b). If c and ai are incom-
parable for each i = 1, 2, 3, 4, 5 then R2 is isomorphic to the poset T ∗
from Lemma 10∗, a contradiction. Otherwise we denote by s the largest
i ∈ {1, 2, 3, 4, 5} for which ai is comparable to c; then obviously as < c.
When s = 1, the subset R2 is isomorphic to the poset T ∗ from Lemma
14∗; when s = 4, the subset R2 is isomorphic to the poset T ∗ from Lemma
15∗; when s = 5, the subset R2 is isomorphic to the poset T ∗ from Lemma
17∗; when s = 2 the subset R2 \ {b} is isomorphic to the poset T ∗ from
Lemma 8∗; when s = 3 the subset R2 \ {a} is isomorphic to the poset T ∗
from Lemma 7∗. Again we have a contradiction. Thus, b is a maximal
element of Q (and of S).
Further, the element a is a minimal one of P (then, since S0 = ∅, a is a
minimal element of S). Indeed, if a were not minimal then {a}<∩P would
not be empty and the subset, consisting of the elements a, b, an arbitrary
element c ∈ {a}< ∩ P and arbitrary elements a1 < a2 < a3 < a4 < a5 of
the subset NS(b), would be isomorphic to the poset T ∗ from Lemma 12∗,
a contradiction.
Thus, we have proved that b is a maximal element of Q (and of S) and
a is a minimal element of P (and of S). Because the elements a ∈ P and
b ∈ Q such that a < b were chosen to be arbitrary, in fact we have also
proved that a and Q \ {b} (b and P \ {a}) are incomparable; moreover,
by Lemma 6 there are no elements x ∈ P and y ∈ Q satisfying x > y. So
S is a one-sided minimax sum of the (chained) subsets P and Q.
Thus, from Lemma 21 we have that if w(S) = 2 and S0 = ∅, then
condition I) or II) holds.
Finally, we consider the case when S is of width 2 and S0 is finite,
but not empty.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.V. M. Bondarenko, A. M. Polishchuk 31
Lemma 22. If w(S) = 2 and S0 is finite, but not empty, then the poset
S is a one-sided minimax sum of an infinite chained and a one-element
subsets.
Proof. Recall that S0 = S−
0 ∪S+
0 (S−
0 and S+
0 are, respectively, the lower
and the upper parts of S0). Since S1 = S \ S0 is an infinite subset of
width 2, we have, by Lemma 21, that S1 is a one-sided minimax sum of
an infinite chained subset P and an (infinite or finite, but not empty)
chained subset Q.
Without loss of generality we may assume that S+
0 6= ∅ (otherwise
we replace S by S∗). Moreover, the subset S+
0 is one-element, otherwise
the subset, consisting of elements d1 < d2 < d3 < d4 < d5 of P , where
d1 is not minimal and d5 is not maximal in P , and any elements a ∈ Q,
b, c ∈ S+
0 (b 6= c), is isomorphic to the poset T from Lemma 12.
We first show that the rank of S1 (as the one-sided minimax sum of
P and Q) is equal to 0. Suppose the contrary and distinguish two cases:
P ⊳ Q and Q ⊳ P . In the first case the subset, consisting of a minimal
element a ∈ P , a maximal element b ∈ Q, an element c ∈ S+
0 and
arbitrary elements d1 < d2 < d3 < d4 < d5 from P \{a}, is isomorphic to
the poset T from Lemma 17. In the second case the subset, consisting of
a minimal element a ∈ Q, a maximal element b ∈ P , an element c ∈ S+
0
and arbitrary elements d1 < d2 < d3 < d4 < d5 from P \{b}, is isomorphic
to the poset T from Lemma 12. In both cases we obtain a contradiction.
So, S1 is the direct sum of the posets P and Q. Then Q is one-element,
otherwise the subset, consisting of elements a ∈ S+
0 , b1, b2 ∈ Q(a 6= b)
and c1, c2, c3, c4, c5 ∈ P (ci 6= cj for i 6= j), is isomorphic to the poset
T from Lemma 10, a contradiction. Further, the subset S−
0 is empty,
otherwise the subset, consisting of elements a ∈ S+
0 , b ∈ Q, c ∈ S−
0 and
d1, d2, d3, d4, d5 ∈ P (di 6= dj for i 6= j), is isomorphic to the poset T from
Lemma 17, a contradiction.
From what we have said above, it follows that S is a one-sided mini-
max sum of an infinite chained and a one-element subsets (having rank 1).
So, from Lemma 22 we have that if w(S) = 2 and S0 is finite, but not
empty, then condition III) holds.
Thus, the proof of the necessity part of the theorem in the case, when
the width of S is equal to 2, is completed. More precisely, we have proved
that, for an infinite poset S of width 2 with the Tits form being positive,
one of the following conditions holds:
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.32 Minimax sums of posets and the quadratic Tits form
I′)=I) S is a direct sum of two chained subsets;
II′) S is an almost chained subset;
III′)=III) S is a minimax sum of rank r = 1 of two
chained subsets.
It remains for us to consider the case when the width of the poset S
is equal to 3. Note that in this case S0 = ∅ (by Lemma 2).
We begin with three lemmas.
Lemma 23. If w(S) = 3 and R is an isolated chained subset of S,
containing more than one elements, then S \ R is an almost chained
poset.
Proof. If the subset R is infinite, then the subset S′ = S \R (of width 2)
contains no subsets of the form b) (see Proposition 19), otherwise S con-
tains a subset isomorphic to the poset T from Lemma 3, a contradiction;
consequently, by Proposition 19, the subset S′ is almost chained.
If R is finite and S′
0 infinite, then S′ is almost chained by Lemma 20.
The case, when R and S′
0 are finite, is impossible, since by Lemmas 21 and
22 the set S′ contains a subset isomorphic to the poset {1, 2, 3, 4, 5, 6 | 2 <
3 < 4 < 5 < 6}, and hence S contains a subset isomorphic to the poset
T from Lemma 3.
Lemma 24. If w(S) = 3, then S cannot be a one-sided minimax sum of
chained and almost chained subsets, having nonzero rank.
Proof. Suppose the contrary, and let P, Q be corresponding chained and
almost chained subsets, respectively. Without loss of generality we may
assume that P ⊳ Q (otherwise we replace S by S∗); denote by a the only
minimal element of P . Then Q has two maximal elements, because oth-
erwise the subset, consisting of the minimal element a, the only maximal
element of Q and two incomparable elements of Q, is isomorphic to the
poset T from Lemma 2, a contradiction. Denote these maximal elements
by b and c. Since P ⊳ Q, we have a < b or a < c; let a < b. When the
elements a and c are comparable, S contains a subset isomorphic to the
poset T ∗ from Lemma 2∗, if P is infinite, and a subset isomorphic to the
poset T from Lemma 6, if Q is infinite; when a and c are incomparable,
S contains a subset isomorphic to the poset T ∗ from Lemma 4∗, if P
is infinite, and a subset isomorphic to the poset T ∗ from Lemma 11∗,
if Q is infinite. In all cases we obtain a contradiction, thus proving the
lemma.
Lemma 25. Let R be an infinite maximal chained subset of S. Then any
subset T of S, which does not intersect R and such that R + T is almost
chained, consist of a one element.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.V. M. Bondarenko, A. M. Polishchuk 33
Indeed, if T consisted of more than one elements then, by definition
the almost chained poset, all but one of them would be comparable to
each element of R, a contradiction with maximality of R.
Continuing the proof (of the necessity of the theorem), we repre-
sent S as a sum of chained subsets S1, S2 and S3 with S1 being infinite
and maximal chained (see Proposition 18). Denote by Sij , where i < j
(i, j = 1, 2, 3), the subset Si +Sj . From what we proved above, it follows
that each of the infinite posets (of width 2) S12 and S13 satisfies one of
conditions I′),II′), III′).
We first show that in fact each of the poset S12 and S13 satisfies
condition I′) or II′).
Suppose contrary and, for instance, let condition III′) holds for S12.
Then S12 is a one-sided minimax sum of S1 and S2; we may assume that
S1 ⊳ S2 (if S2 ⊳ S1, we replace S by S∗); denote by a the only minimal
element of S1. If S13 satisfies condition I′) or condition III′) with S1 ⊳S3,
then S1 \ {a} is an isolated subset of S \ {a}, and hence by Lemma
23 the subset S23 = S23 ∩ (S \ {a}) is almost chained; but then S is
a one-sided minimax sum of the chained subset S1 and almost chained
subset S23, a contradiction with Lemma 24. In the case when S13 satisfies
condition III′) with S3 ⊳ S1, the subset S1 has also the only maximal
element which we denote by b. Then S1 \ {a, b} is an isolated subset of
S \ {a, b}, and hence by Lemma 23 the subset S23 = S23 ∩ (S \ {a, b})
is almost chained; denote by c the only minimal element of S3 and by
d the only maximal element of S2. It is easy to see that S contains a
subset isomorphic to the poset T from Lemma 6, if c < d, and a subset
isomorphic to the poset T from Lemma 4, if c and d are incomparable.
Again we have a contradiction. Finally, we consider the case when S13
satisfies condition II′). By Lemma 25 the poset S3 consist of one element,
say c; let d denotes the only element of S1 which is incomparable with
c. By Lemma 24 the element c is comparable to some element of S2;
then S′
2 = {x ∈ S2 | c < x} 6= ∅ or S′′
2 = {x ∈ S2 | c > x} 6= ∅. First,
let S′
2 = {x ∈ S2 | c < x} 6= ∅; fix some element b in it. Obviously, c
is minimal either in S13 or in S13 \ {a} (otherwise S12 is not a minimax
sum of S1 and S2). In the first case the subset of S, consisting of the
elements a = d, c, the maximal element of S2 and an arbitrary element
of S1 \ {a}, is isomorphic to the poset T from Lemma 6, a contradiction.
And in the second case, the element b is maximal in S2 (because S12 is a
one-sided minimax sum of S1 and S2) and the element c is incomparable
with the subset S2 \ {b}; but then the (infinite) poset S \ {a} is a one-
sided minimax sum of the almost chained subset S13\{a} and the chained
subset S2, a contradiction with Lemma 24. Suppose now that S′
2 = ∅,
and S′′
2 6= ∅; then S′′
2 does not contain the maximal element e of S2
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.34 Minimax sums of posets and the quadratic Tits form
(otherwise w(S) = 2), and the subset, consisting of the elements a, c, e
and an arbitrary element of S′′
2 , is isomorphic to the poset T from Lemma
6, a contradiction.
So each of the posets S12 and S13 satisfies I′) or II′).
When both S12 and S13 satisfy condition I′), S1 is incomparable with
S23, and by Lemma 23 the poset S23 is almost chained; hence S satisfies
condition II) of the theorem.
Show, further, that the case, when both S12 and S13 satisfy condition
II′), is impossible. Assume the contrary. Then by Lemma 25 each of the
posets S2 and S3 consist of a one element, say a and c, respectively; the
only incomparable with a (respectively, c) element of S1 is denoted by b
(respectively, d); because w(S) = 2, the element c is incomparable with
the elements a and b (hence d = b). And it is easy to see from this that
S contains a subset isomorphic to the poset T from Lemma 2, or to the
dual poset T ∗. We obtain a contradiction.
Thus, it remains to consider the case when one of the subset S12, S13,
say S12, satisfies condition I′), and the other one, i.e. S13, satisfies con-
dition II′). Then, as in the previous case, S3 consist of a one element —
c; the only incomparable with c element of S1 is denote again by d.
Show that c is incomparable with S2. Assume the contrary. Without
loss of generality we may assume that c < a for some a ∈ S2 (otherwise
we replace S by S∗). Then the subset {c, d}> is infinite, because other-
wise so is the subset {c, d}< (since S1 is infinite) and then the subset of
S, consisting of the elements a, c, d and any five elements of {c, d}<, is
isomorphic to the poset T ∗ from Lemma 13∗. Further, since w(S) = 3,
the subset NS(c) ∩ S2 is nonempty; fix some element b in it. And the
subset of S, consisting of the elements a, b, c, d and any four elements of
{c, d}>, is isomorphic to the poset T from Lemma 5, a contradiction. So
c is incomparable with S2, and then S satisfies condition II).
The proof of the necessity part of the theorem is completed.
5. Proof of Main theorem: sufficiency
Suppose first that an infinite poset S is the direct sum of two chains
or of a chain and an almost chain, and show that the Tits form qS(z) is
positive. Obviously, it suffices to do it for the finite posets P = Pm,n−m =
{−m,−m+1, . . . ,−1,−0, +0, 1, 2, . . . , m, m+1, . . . , n | −m ≺ −m+1 ≺
. . . ≺ −1 ≺ −0 ≺ 1 ≺ 2 ≺ . . . ≺ m,−1 ≺ +0 ≺ 1, m + 1 ≺ . . . ≺ n},
where n and m < n are an arbitrary natural number. Moreover, since
for each z ∈ Z
P∪0, one has the (easily verifiable) equality qP (z) = qQ(z′),
where Q = Pm,0, z′0 = z0 −
∑n
s=m+1 zs, z′s = zs for s = −m,−m +
1, . . . ,−1,−0, +0, 1, 2, . . . , m and z′s = −zs for s = m+1, . . . , n, it suffices
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.V. M. Bondarenko, A. M. Polishchuk 35
to consider the (almost chained) posets Q = Pm,0. The fact that the Tits
form of a poset Q = Pm,0 is positive follows from the following (easily
verifiable) equality: 2qQ(z) = z2
0 +
∑−1
i=−m z2
i +
∑m
i=1 z2
i + (z−0 − z+0)
2 +
(z0 −
∑
j∈Q zj)
2.
It remains to prove that the Tits form qS(z) is positive for S to be a
minimax sum of two chained posets, having rank 1. Obviously, it suffices
to do it for the finite posets R = Rn = {1, 2 . . . , 2n | 1 ≺ 2 · · · ≺ n, n+1 ≺
· · · ≺ 2n, 1 ≺ 2n}, J¤Ґ n > 1. Denote by R′ = R′
n the poset (R\{2n})∪
{−1}, where −1 < i for i = 2, . . . , n; it is the direct sum of a chained and
an almost chained subsets. The fact that the Tits form qR(z) is positive
follows from the following (easily verifiable) equality: qR(z) = qR′(z′),
where z′0 = z0−z2n, z′i = zi for i = 1, . . . , n, n+1, . . . , 2n−1, z′−1 = −z2n.
The proof of the sufficiency of the theorem is completed.
References
[1] D. Simson, Linear Representations of Partially Ordered Sets and Vector Space
Category. Gordon and Breach Science Publishers. 1992. 499p.
[2] P. Gabriel, Unzerlegbare Darstellungen, Manuscripts Math., 6 (1972), 71–103,309.
[3] Y. A. Drozd, Coxeter transformations and representations of partially ordered
sets, Funkc. Anal. i Priložen, 8 (1974), 34–42 (in Russian).
[4] Y. A. Drozd, On tame and wild matrix problems, Matrix problems, Kiev: Inst.
Math. Acad. Sci. Ukrain. SSR, 1977, 104–114 (in Russian).
[5] Matrix problems. A collection of scientific works. Kiev: Inst. Math. Acad. Sci.
Ukrain. SSR, 1977. 166p. (in Russian).
[6] Representations and quadratic forms. A collection of scientific works. Kiev: Inst.
Math. Acad. Sci. Ukrain. SSR, 1979. 152p. (in Russian).
[7] C. M. Ringel, Tame algebras and integral quadratic forms, Lecture notes in math.,
1099, 1984, 376p.
[8] V. M. Bondarenko, A. G. Zavadskij, L. A. Nazarova, On representations of tame
partially ordered sets, Representations and Quadratic Forms: Kiev: Inst. Math.
Acad. Sci. Ukrain. SSR, 1979, 75–106 (Russian).
[9] A. G. Zavadskij, Series of representations and the Tits form, Kiev: Inst. Math.
Acad. Sci. Ukrain. SSR., Preprint N 27 (1981), 3–20 (in Russian).
[10] K. Bongartz, Algebras and quadratic forms, J. London Math. Soc. (2), 28, N3
(1983), 461–469.
[11] H. Kraft, Ch. Reidtmann, Geometry of representations of quivers, London Math.
Soc. Lecture Note Ser., 116 (1986), 109–145.
[12] N. Marmaridis, One point extensions of trees and quadratics forms, Fund. Math.,
134, N1 (1990), 15–35.
[13] D. Simson, A reduction functor, tameness, and Tits form for a class of orders, J.
Algebra, 174 (1995), 430–452.
[14] S. Kasjan, D. Simson, Tame prinjective type and Tits form of two-peak posets. I,
J. Pure Appl. Algebra, 106, N3 (1996), 307–330.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.36 Minimax sums of posets and the quadratic Tits form
[15] S. Kasjan, D. Simson, Tame prinjective type and Tits form of two-peak posets. II,
J. Algebra, 187, N1 (1997), 71–96.
[16] Y. A. Drozd, Representations of bisected posets and reflection functors, Algebras
and modules, II (Geiranger, 1996), CMS Conf. Proc., 24 (1998), 153–165.
[17] J. A. de la Peňa, A. Skowroński, The Tits and Euler forms of a tame algebra,
Math. Ann., 315, N1 (1999), 37–59.
[18] P. Dräxler, J. A. de la Peňa, Tree algebras with non-negative Tits form, Comm.
Algebra, 8 (2000), 3993–4012.
[19] B. Deng Quasi-hereditary algebras and quadratic forms, J. Algebra, 239, N2
(2001), 438–459.
[20] G. Birkhoff, Theory of Lattices. Moscow, 1984. 564 p. (in Russian).
Contact information
V. M. Bondarenko,
A. M. Polishchuk
Institute of Mathematics,
Tereshchenkivska 3, 01601 Kyiv, Ukraine
E-Mail: vit-bond@imath.kiev.ua
Received by the editors: 18.11.2003
and final form in 09.02.2004.
|