半群K(n,r)中的幂等生成元

设Singn是由一个n元集上的所有奇异变换所构成的奇异变换半群，I是由Singn中一些亏数为1的幂等元组成的集合，Howie利用有向图证明了：I是Singn的一个生成集当且仅当与其相应的有向图D（I）是强连通的完全图，本文利用多重有向图将这一结果推广到Singn的每个理想K（,r)上。     

The minimal number of generators of a finite semigroup

The rank of a finite semigroup is the smallest number of elements required to generate the semigroup. A formula is given for the rank of an arbitrary (not necessarily regular) Rees matrix semigroup over a group. The formula is expressed in terms of the dimensions of the structure matrix, and the relative rank of a certain subset of the structure group obtained from subgroups generated by entries in the structure matrix, which is assumed to be in Graham normal form. This formula is then applied to answer questions about minimal generating sets of certain natural families of transformation semigroups. In particular, the problem of determining the maximum rank of a subsemigroup of the full transformation monoid (and of the symmetric inverse semigroup) is considered.     

若干有向图的SAS-全染色

提出了有向图的SAS-全染色的概念,有向图D的SAS-全染色是D的一个正常全染色,若对D中点染色来说,不存在长为3的2色有向路.对D中弧染色来说,不存在长为4的2色有向路.并定义了有向图D的SAS-全色数,记为(D).用构造染色的方法给出了一些特殊有向图(有向路,有向圈,定向轮,定向扇,有向双星)的SAS-全色数.     

半群O_n(k)的秩

设O_n是有限链[n]上的保序变换半群.对任意1≤k≤n-1,研究半群O_n(k)={α∈O_n:(x∈[n]x≤k→xα≤k}的秩和幂等元秩,证明了半群O_n(k)的秩为2n-3.进一步,得到了半群O_n(k)(2≤k≤n-1)的幂等元秩为n和半群O_n(1)的幂等元秩为n-1.     

A vector space approach to the road coloring problem

Let G be a strongly connected, aperiodic, two-out digraph with adjacency matrix A. Suppose A = R + B are coloring matrices: that is, matrices that represent the functions induced by an edge-coloring of G. We introduce a matrix Δ = 1/2 (R − B) and investigate its properties. A number of useful conditions involving Δ which either are equivalent to or imply a solution to the road coloring problem are derived.     

Acyclic systems of representatives and acyclic colorings of digraphs

A natural digraph analog of the graph theoretic concept of “an independent set” is that of “an acyclic set of vertices,” namely a set not spanning a directed cycle. By this token, an analog of the notion of coloring of a graph is that of decomposition of a digraph into acyclic sets. We extend some known results on independent sets and colorings in graphs to acyclic sets and acyclic colorings of digraphs. In particular, we prove bounds on the topological connectivity of the complex of acyclic sets, and using them we prove sufficient conditions for the existence of acyclic systems of representatives of a system of sets of vertices. These bounds generalize a result of Tardos and Szabó. We prove a fractional version of a strong‐acyclic‐coloring conjecture for digraphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 177–189, 2008     

Rank properties of the semigroup of endomorphisms over Brandt semigroup

We investigate small rank, lower rank, intermediate rank, upper rank, and large rank of the semigroup of endomorphisms over Brandt semigroup.     

The rank of the endomorphism monoid of a uniform partition

The rank of a semigroup is the cardinality of a smallest generating set. In this paper we compute the rank of the endomorphism monoid of a non-trivial uniform partition of a finite set, that is, the semigroup of those transformations of a finite set that leave a non-trivial uniform partition invariant. That involves proving that the rank of a wreath product of two symmetric groups is two and then use the fact that the endomorphism monoid of a partition is isomorphic to a wreath product of two full transformation semigroups. The calculation of the rank of these semigroups solves an open question.     

Positive matrix semigroups with binary diagonals

We show that a semigroup of positive matrices (all entries greater than or equal to zero) with binary diagonals (diagonal entries either 0 or 1) is either decomposable (all matrices in the semigroup have a common zero entry) or is similar, via a positive diagonal matrix, to a binary semigroup (all entries 0 or 1). In the case where the idempotents of minimal rank in S{\mathcal{S}} satisfy a “diagonal disjointness” condition, we obtain additional structural information. In the case where the semigroup is not necessarily positive but has binary diagonals we show that either the semigroup is reducible or the minimal rank ideal is a binary semigroup. We also give generalizations of these results to operators acting on the Hilbert space of square-summable sequences.     

Completely Simple Semigroups,Lie Algebras,and the Road Coloring Problem

Consider a semigroup generated by matrices associated with an edge-coloring of a strongly connected, aperiodic digraph. We call the semigroup Lie-solvable if the Lie algebra generated by its elements is solvable. We show that if the semigroup is Lie-solvable then its kernel is a right group. Next, we study the Lie algebra generated by the kernel. Lie algebras generated by two idempotents are analyzed in detail. We find that these have homomorphic images that are generalized quaternion algebras. We show that if the kernel is not a direct product, then the Lie algebra generated by the kernel is not solvable by describing the structure of these algebras. Finally, we discuss an infinite class of examples that are shown to always produce strongly connected aperiodic digraphs having kernels that are not right groups.     

Game-perfect digraphs

In the A-coloring game, two players, Alice and Bob, color uncolored vertices of a given uncolored digraph D with colors from a given color set C, so that, at any time a vertex is colored, its color has to be different from the colors of its previously colored in-neighbors. Alice begins. The players move alternately, where a move of Bob consists in coloring a vertex, and a move of Alice in coloring a vertex or missing the turn. The game ends when Bob is unable to move. Alice wins if every vertex is colored at the end, otherwise Bob wins. This game is a variant of a graph coloring game proposed by Bodlaender (Int J Found Comput Sci 2:133?C147, 1991). The A-game chromatic number of D is the smallest cardinality of a color set C, so that Alice has a winning strategy for the game played on D with C. A digraph is A-perfect if, for any induced subdigraph H of D, the A-game chromatic number of H equals the size of the largest symmetric clique of H. We characterize some basic classes of A-perfect digraphs, in particular all A-perfect semiorientations of paths and cycles. This gives us, as corollaries, similar results for other games, in particular concerning the digraph version of the usual game chromatic number.     

J rgens结果的一个新证明

文章研究有界线性算子半群的扰动问题 .在一定条件下 ,我们表明 :设算子 B生成最终依范连续半群 S(t) (t τ) ,K是有界线性算子 .如果‖ K R(σ+iτ,B) K‖→ 0 ,τ→∞ ,那么算子 A =B +K生成的半群 T(t) ,t>2τ是依范连续的 .我们将此结果应用于迁移算子 ,给出 J rgens结果的一个新证明 .     

On the Rank of the Semigroup TE(X)

${\cal T}_X $ denotes the full transformation semigroup on a set $ X $. For a nontrivial equivalence $E$ on $X$, let \[ T_E (X) =\{ f\in {\cal T}_X : \forall \, (a,b)\in E,\, (af,bf)\in E \} . \] Then $T_E (X) $ is exactly the semigroup of continuous selfmaps of the topological space $X$ for which the collection of all $E$-classes is a basis. In this paper, we first discuss the rank of the homeomorphism group $G$, and then consider the rank of $T_E (X)$ for a special case that the set $X$ is finite and that each class of the equivalence $E$ has the same cardinality. Finally, the rank of the closed selfmap semigroup $\Gamma(X)$ of the space $X$ is observed. We conclude that the rank of $G$ is no more than 4, the rank of $T_E (X)$ is no more than 6 and the rank of $\Gamma(X)$ is no more than 5.     

Inverse Near Permutation Semigroups

A transformation semigroup over a set X with N elements is said to be a near permutation semigroup if it is generated by a group G of permutations on N elements and by a set H of transformations of rank N - 1. In this paper we give necessary and sufficient conditions for a near permutation semigroup S = ‹G,H›, where H is a group, to be inverse. Moreover, we obtain conditions which guarantee that its semilattice of idempotents is generated by the idempotents of S of rank greater than N - 2 or N - 3.     

Coloring the edges of a directed graph

Finding large cliques in a graph is an important problem in applied discrete mathematics. In directed graph a possible corresponding problem is finding large transitive subtournaments. It is well-known that coloring the graph speeds up the clique search in the undirected case. In this paper we propose coloring schemes to speed up the tournament search in the directed case. We prove two complexity results about the proposed colorings. A consequence of these results is that in practical computations we have to be content with approximate greedy coloring algorithms.     

半群PO_(n,r)的秩

设POn为Xn上的保序部分变换半群.对任意的2≤r≤n一1,考虑半群PO_(n,r)={α∈PO_n:Im(α)■[r]}([r]={1,2,…,r}),证明了PO_(n,r)的秩为Σn-1k=r(nk)((k-1)(r-1))+r-1.     

半群OI_n(k)的秩

设OI_n是[n]上的保序严格部分一一变换半群.对任意1≤k≤n-1,研究半群OI_n(k)={α∈OI_n:(■x∈dom(α))x≤k■xα≤k}的秩,证明了半群OI_n(k)的秩为n+1.     

Prime serial rings with krull dimension

Let Abe an integral domain and Sa torsion-free can-cellative Abelian semigroup. By analogy with known results on polynomial rings and group rings, results are sought for a number of properties of the semigroup ring A[S]; The properties of interest include coequidimensionality, (universal) catenarity, (stably strong) S-domain, and (locally, residually, totally) Jaffard do-main. Positive results, leading to new examples of rings with some of the above properties, are obtained in case (the quotient group of) Shas rank 1 or Sis finitely generated. An example shows that some results do not carry over in case Shas rank 2 but is not finitely generated.     

The semigroup generated by a unitary orbit of a singular matrix

We investigate the structure of the multiplicative semigroup generated by the set of matrices that are unitarily equivalent to a given singular matrix A. In particular, we give necessary and sufficient conditions, in terms of the singular values of A, for such a semigroup to consist of all matrices of rank not exceeding the rank of A.     

Structure of a permutable Munn semigroup of finite rank

A semigroup any two congruences of which commute as binary relations is called a permutable semigroup. We describe the structure of a permutable Munn semigroup of finite rank. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 6, pp. 742–746, June, 2006.