Almost all derivative quivers of artinian biserial rings contain chains
A lower estimate for the number Mn of all labelled
 quivers with n–vertex parts of Artinian biserial rings is given and
 the asymptotic of the relation Mn/Bn, where Bn denotes the number of those quivers all connected components of which are cycles,
 is studied.
Saved in:
| Published in: | Algebra and Discrete Mathematics |
|---|---|
| Date: | 2003 |
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2003
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/155281 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Almost all derivative quivers of artinian biserial rings contain chains / T. Avdeeva, O. Ganyushkin // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 1. — С. 1–5. — Бібліогр.: 9 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860207406706851840 |
|---|---|
| author | Avdeeva, T. Ganyushkin, O. |
| author_facet | Avdeeva, T. Ganyushkin, O. |
| citation_txt | Almost all derivative quivers of artinian biserial rings contain chains / T. Avdeeva, O. Ganyushkin // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 1. — С. 1–5. — Бібліогр.: 9 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | A lower estimate for the number Mn of all labelled
quivers with n–vertex parts of Artinian biserial rings is given and
the asymptotic of the relation Mn/Bn, where Bn denotes the number of those quivers all connected components of which are cycles,
is studied.
|
| first_indexed | 2025-12-07T18:13:13Z |
| format | Article |
| fulltext |
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 2. (2003). pp. 1–5
c© Journal “Algebra and Discrete Mathematics”
Almost all derivative quivers of artinian biserial
rings contain chains
Tetjana Avdeeva and Olexandr Ganyushkin
Communicated by V. V. Kirichenko
Abstract. A lower estimate for the number Mn of all labelled
quivers with n–vertex parts of Artinian biserial rings is given and
the asymptotic of the relation Mn/Bn, where Bn denotes the num-
ber of those quivers all connected components of which are cycles,
is studied.
In the beginning of 70-s P.Gabriel [1] introduced a notion of a quiver
of a finite dimensional algebra over an algebraically closed field — an
directed graph of special type which in concise form preserves some very
important information about the algebra. Using these graphs in [1] (see
also Krugliak [2]) all finite dimensional algebras of finite type over an
algebraically closed field with square zero radical are described. Later
V.Kirichenko has expanded the construction of such an directed graph to
right Noetherian semiperfect rings [3], and then to several other classes of
rings (see, for example, [4], [5] and bibliography there). For some classes
of rings it is convenient to consider a so called derivative quiver RQ(A)
(see [6]), which for the rings under consideration always turns out to be
a simple bipartite graph with equicardinal part, instead of a quiver Q(A)
of a ring A.
In this connection there arises a natural problem of investigation of
graphs which can be quivers of rings of some class. We will deal with
Artinian biserial rings, first introduced by .Fuller [7]. A starting point for
this paper is the following statement( [4], Corollary 5.15): An Artinian
ring A, with square zero Jacobson radical is biserial if and only if its
derivative quiver RQ(A) is a disconnected union of chains and cycles.
2000 Mathematics Subject Classification: 05C30, 05C38, 16P20.
Key words and phrases: artinian rings, quivers, bipartite graphs.
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.2 Almost all derivative quivers..
Therefore, a derivative quiver of an Artinian biserial ring is a simple
bipartite graph with parts of the same cardinality, in which the degree
of each vertex does not exceed 2. In [8] such graphs have been called
Artinian–biserial, or just AB–graphs. An AB–graph with n–vertex parts
is called labelled, if the vertices of each part are numbered from 1 to n
and it is indicated, which of the parts is lower, and which is upper. In
what follows we consider only labelled AB–graphs.
In [8] the number Bn of those AB–graphs with n–vertex parts, all
connected components of which are cycles, is counted:
Bn =
∑
(l1,l2,...,ln)
1l1+2l2+···+nln=n
(n!)2
(l1!)2
n
∏
k=2
(2lk · klk · lk!)
, (1)
and an upper bound for the number Mn of all labelled AB–graphs with
n–vertex parts is obtained:
Mn <
n
∑
k=0
(−1)k
(
n
k
)
n!
(n − k)!
∣
∣ISn−k
∣
∣
2
,
where
∣
∣ISn
∣
∣ — is the order of the inverse symmetric semigroup ISn of
degree n. This estimate, however, is rather rough. Beside this, to give
an estimate for the order in the right-hand side of the latter inequality
for large values of n is itself a difficult problem.
A more effective lower estimate for Mn is given in the following
Lemma. The number Mn of all labelled AB–graphs with n–vertex parts
satisfies the inequality Mn > (n!)2 ·
n
2
.
Proof. Since M1 = 2 and M2 = 16 then the statement is obvious for
n = 1 and for n = 2. Let now n ≥ 3 and suppose that for all k <
n the statement of Lemma is true. Consider those AB–graphs, which
contain a sufficiently long chain of an odd length. Then exactly one of
the endpoints of such a chain will belong to the lower part. To determine
a chain of length 2n− 2k− 1, one has to choose its endpoint in the lower
part, then a vertex in the upper part incident to this endpoint, then the
next vertex of a chain in the lower part, and so on, each time switching
the part of the next vertex choice, till one reaches the 2n − 2k–s vertex
of the chain which is its endpoint from the upper part. Since in this way
one will get every chain of length 2n − 2k − 1 exactly one time then the
number of different chains of length 2n − 2k − 1 equals
n · n · (n − 1) · (n − 1) · (n − 2) · (n − 2) · · · (k + 1) · (k + 1) =
(n!)2
(k!)2
.
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.T. Avdeeva, O. Ganyushkin 3
Since for k ≤
n − 1
2
an AB–graph with n–vertex parts can not contain
more than one chain of length 2n − 2k − 1 then for such values of k the
number of AB–graphs, containing a chain of length 2n − 2k − 1, equals
(n!)2
(k!)2
·Mk. By the inductive assumption Mk > (k!)2 ·
k
2
. Using the
equality M1 = 2, we can assume Mk > (k!)2. It is easily seen, that an
AB–graph with n–vertex parts can contain only one chain of length ≥ n.
Therefore,
Mn >
[(n−1)/2]
∑
k=0
(
n!
k!
)2
(k!)2 = (n!)2 ·
[(n−1)/2]
∑
k=0
1 = (n!)2 ·
[
n − 1
2
]
> (n!)2 ·
n
2
.
Theorem. Let Mn be the number of all labelled AB–graphs with n–
vertex parts, and Bn — the number of those of such graphs, all connected
components of which are cycles. Then lim
n→∞
Bn
Mn
= 0.
Proof. Let us calculate an upper bound for Bn. It is known, that the
number of permutations of a cycle type (l1, l2, . . . , ln) equals
n! ·
(
∏n
k=1(k
lk · lk!)
)
−1
. Since the number of all permutations is n!,
then
∑
(l1,l2,...,ln)
1l1+2l2+···+nln=n
n!
n
∏
k=1
(klk · lk!)
= n!.
After cancellation of both sides by n! we obtain:
∑
(l1,l2,...,ln)
1l1+2l2+···+nln=n
1
n
∏
k=1
(klk · lk!)
= 1.
This equality and an obvious inequality l1! ·
∏n
k=2 2lk ≥ 1, imply:
∑
(l1,l2,...,ln)
1l1+2l2+···+nln=n
1
(l1!)2
n
∏
k=2
(2lk · klk · lk!)
=
=
∑
(l1,l2,...,ln)
1l1+2l2+···+nln=n
1
n
∏
k=1
(klk · lk!)
·
1
l1!
n
∏
k=2
2lk
<
<
∑
(l1,l2,...,ln)
1l1+2l2+···+nln=n
1
n
∏
k=1
(klk · lk!)
= 1.
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.4 Almost all derivative quivers..
This inequality and inequality 1 now imply, that Bn < (n!)2. Therefore,
using Lemma, we obtain:
0 ≤
Bn
Mn
≤
(n!)2
(n!)2 · n
2
=
2
n
.
Thus, lim
n→∞
Bn
Mn
= 0.
Following the tradition for usage of the expression ‘almost all’ (see,
for example, [9]), we obtain the following
Corollary. Almost all AB–graphs with n–vertex parts contain chains.
We conclude by stating the values of Bn and Mn and of the relation
Bn/Mn for small values of n:
n 2 3 4 5
Bn 2 16 151 4991
Mn 16 265 7343 304186
Bn/Mn 0.125 0.0603773 0.0205638 0.0164077
References
[1] Gabriel P. Unzerlegbare Darstellungen 1. Manuscript Math. 6 (1972), 71–103. [5]
[2] Krugliak.S.A. Representations of algebras with zero sguare radical. Zapiski nauchn.
seminarov LOMI Ac.Sci. USSR 28 (1972), 80–89. (in Russian)
[3] Kirichenko, V.V. Generalized uniserial rings, Math. Sb. (N.S.), 99 (141), N 4,
(1976), pp. 559-581. English translation, Math USSR Sb., v. 28, N 4, 1976, pp.
501-520.
[4] Danlyev Kh.M., Kirichenko V.V., Haletskaja Z.P., Jaremenko Ju.V. Weakly prime
semiperfect 2–rings and modules over them. Algebraicheskie issledovania (collec-
tion of papers), Institut mathematiki NAN Ukrainy, Kiev, 1995, 5–32.
[5] Gubareni N.M., Kirichenko V.V. Rings and Modules. - Czestochowa, 2001.
[6] Kirichenko V.V., Bernik O.Ja. Semiperfect rings of distributive module type.
Dopovidi Ac.Sci. URSR. 1988, no. 3, 15–17.
[7] Fuller K.R. Weakly symmetric rings of distributive module type. Comm. in Alge-
bra. 5 (1977), 997–1008.
[8] Avdeeva T.V., Ganyushkin O.G. The number of quivers of Artinian biserial rings.
Visnyk Kyivs’kogo Univ., ser. phiz.–math. sci., 1999, no. 3, 18–27. (in Ukrainian)
[9] Korshunov A.D. Main properties of random graphs with large number of vertices
and edges. Uspehi mathem.nauk 40 (1985), 1(241), 107–173.(in Russian)
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.T. Avdeeva, O. Ganyushkin 5
Contact information
T. Avdeeva Department of Physics and Mathematics,
National of Technical University of Ukraine
”Kyiv of Polytechnical Institute”,37,
Peremohy pr., Kyiv,UKRAINE
O. Ganyushkin Department of Mechanics and Mathematics,
Kyiv Taras Shevchenko University, 64,
Volodymyrska st., 01033, Kyiv, UKRAINE
E-Mail: ganiyshk@mechmat.univ.kiev.ua
Received by the editors: 06.12.2002.
|
| id | nasplib_isofts_kiev_ua-123456789-155281 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-12-07T18:13:13Z |
| publishDate | 2003 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Avdeeva, T. Ganyushkin, O. 2019-06-16T15:30:56Z 2019-06-16T15:30:56Z 2003 Almost all derivative quivers of artinian biserial rings contain chains / T. Avdeeva, O. Ganyushkin // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 1. — С. 1–5. — Бібліогр.: 9 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 05C30, 05C38, 16P20. https://nasplib.isofts.kiev.ua/handle/123456789/155281 A lower estimate for the number Mn of all labelled
 quivers with n–vertex parts of Artinian biserial rings is given and
 the asymptotic of the relation Mn/Bn, where Bn denotes the number of those quivers all connected components of which are cycles,
 is studied. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Almost all derivative quivers of artinian biserial rings contain chains Article published earlier |
| spellingShingle | Almost all derivative quivers of artinian biserial rings contain chains Avdeeva, T. Ganyushkin, O. |
| title | Almost all derivative quivers of artinian biserial rings contain chains |
| title_full | Almost all derivative quivers of artinian biserial rings contain chains |
| title_fullStr | Almost all derivative quivers of artinian biserial rings contain chains |
| title_full_unstemmed | Almost all derivative quivers of artinian biserial rings contain chains |
| title_short | Almost all derivative quivers of artinian biserial rings contain chains |
| title_sort | almost all derivative quivers of artinian biserial rings contain chains |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/155281 |
| work_keys_str_mv | AT avdeevat almostallderivativequiversofartinianbiserialringscontainchains AT ganyushkino almostallderivativequiversofartinianbiserialringscontainchains |