zbMATH — the first resource for mathematics

Directed graphs and combinatorial properties of semigroups. (English) Zbl 1005.20043
Let $$D$$ be a fixed finite graph. The graph $$G=(V,E)$$ is said to be $$D$$-saturated if for every infinite subset $$W$$ of $$V$$ there exists a subgraph of $$G$$ isomorphic with $$D$$ having all vertices in $$W$$.
Let $$S$$ be a semigroup. The authors associate to $$S$$ the following three graphs: $$\text{Pow}(S)$$, $$\text{Div}(S)$$, $$\text{Ann}(S)$$ for which $$S$$ is the vertex set (in the construction of $$\text{Div}(S)$$ $$S$$ is assumed to be a semigroup with $$0$$). The set of edges is defined as follows. If $$u,v\in S$$ and $$u\neq v$$ then:
$$(u,v)$$ is a edge for $$\text{Pow}(s)\iff v$$ is a power of $$u$$.
$$(u,v)$$ is a edge for $$\text{Div}(S)\iff u$$ divides $$v$$,
$$(u,v)$$ is a edge for $$\text{Ann}(S)\iff uv=0$$.
The purpose of this paper is to characterize the commutative semigroups $$S$$ for which the graphs $$\text{Pow}(S)$$ or $$\text{Div}(S)$$ or $$\text{Ann}(S)$$ are $$D$$-saturated.

MSC:
 20M14 Commutative semigroups 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 05C20 Directed graphs (digraphs), tournaments 20M05 Free semigroups, generators and relations, word problems
Full Text:
References:
  Chartland, G.; Lesniak, L., Graphs and digraphs, (1996), Chapman & Hall London  Clifford, A.H.; Preston, G.B., The algebraic theory of semigroups, (1961), Amer. Math. Soc Providence · Zbl 0111.03403  de Luca, A.; Varricchio, S., Regularity and finiteness conditions, (), 747-810  de Luca, A.; Varricchio, S., Finiteness and regularity in semigroups and formal languages, Monographs in theoretical computer science, (1998), Springer-Verlag Berlin  Graham, R.L., Rudiments of Ramsey theory, (1981), Amer. Math. Soc Providence  Graham, R.L.; Rothschild, B.L.; Spencer, J.H., Ramsey theory, Discrete math. and optimization, (1990), Wiley New York  Grillet, P.A., Semigroups: an introduction to structure theory, (1995), Dekker New York · Zbl 0874.20039  Howie, J.M., Fundamentals of semigroup theory, (1995), Clarendon Press Oxford · Zbl 0835.20077  Justin, J., Characterisation of the repetitive commutative semigroups, J. algebra, 21, 87-90, (1972) · Zbl 0248.05004  Justin, J.; Kelarev, A.V., Factorisations of infinite sequences in semigroups, Ann. mat. pura appl., 174, 87-96, (1998) · Zbl 0963.20034  Kelarev, A.V., Combinatorial properties of sequences in groups and semigroups, Combinatorics, complexity and logic, Discrete mathematics and theoretical computer science, (1996), Springer-Verlag Auckland, p. 289-298 · Zbl 0914.68155  Lothaire, M., Combinatorics on words, (1983), Addison-Wesley London · Zbl 0514.20045  Robinson, D.J.S., A course in the theory of groups, (1982), Springer-Verlag New York/Berlin · Zbl 0496.20038  Shevrin, L.N.; Ovsyannikov, A.J., Semigroups and their subsemigroup lattices, (1996), Kluwer Academic Dordrecht · Zbl 0858.20054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.