Graphs whose strong endomorphism monoids are regular

Let X be a graph, S End X be its strong endomorphism monoid. It is proved that S End X is a regular monoid if and only if the canonical strong factor graph U of X contains no proper subgraph which is isomorphic to U. The result generalizes that of U. Knauer about the regularity of strong endomorphism monoids of graphs.     

A method of finding automorphism groups of endomorphism monoids of relational systems

For any set X and any relation ρ on X, let T(X,ρ) be the semigroup of all maps a:X→X that preserve ρ. Let S(X) be the symmetric group on X. If ρ is reflexive, the group of automorphisms of T(X,ρ) is isomorphic to N_S(X)(T(X,ρ)), the normalizer of T(X,ρ) in S(X), that is, the group of permutations on X that preserve T(X,ρ) under conjugation. The elements of N_S(X)(T(X,ρ)) have been described for the class of so-called dense relations ρ. The paper is dedicated to applications of this result.     

On free spectra of finite completely regular semigroups and monoids

We show that a finite completely regular semigroup has a sub-log-exponential free spectrum if and only if it is locally orthodox and has nilpotent subgroups. As a corollary, it follows that the Seif Conjecture holds true for completely regular monoids. In the process, we derive solutions of word problems of free objects in a sequence of varieties of locally orthodox completely regular semigroups from solutions of word problems in relatively free bands.     

Strongly taut finitely generated monoids

A strongly taut monoid is a monoid in which all the powers of any element of the monoid have the same elasticity, that is, the ratio between the maximum and the minimum length of the factorizations of an element remains unchanged under powers. We give a procedure to determine if a finitely generated commutative monoid is strongly taut. The authors are supported by the project MTM2004-01446 and FEDER funds. The authors would like to thank the referee and P. Baginski for their heplful comments and suggestions. Author’s addresses: P. A. García-Sánchez, Departamento de álgebra, Universidad de Granada, E-18071 Granada, Espa?a; D. Llena, Departamento de Geometría, Topología y Química Orgánica, Universidad de Almería, 04120 Almería, Espa?a; J. C. Rosales, Departamento de álgebra, Universidad de Granada, E-18071 Granada, Espa?a     

Finite digraphs with given regular automorphism groups

With five exceptions, every finite regular permutation group occurs as the automorphism group of a digraph.One of the corollaries: given a finite groupG of ordern, there is a commutative semigroupS of order 2n+2 such that AutSG. The problem whether a latticeL of order Cn with AutLG exists (for some constantC), remains open.     

On infinite tournaments with regular automorphism groups

Atournament regular representation (TRR) of an abstract groupG is a tournamentT whose automorphism group is isomorphic toG and is a regular permutation group on the vertices ofT. L. Babai and W. Imrich have shown that every finite group of odd order exceptZ ₃ ×Z ₃ admits a TRR. In the present paper we give several sufficient conditions for an infinite groupG with no element of order 2 to admit a TRR. Among these are the following: (1)G is a cyclic extension byZ of a finitely generated group; (2)G is a cyclic extension byZ _2n+1 of any group admitting a TRR; (3)G is a finitely generated abelian group; (4)G is a countably generated abelian group whose torsion subgroup is finite.     

Some new strongly regular graphs

We show that three pairwise 4-regular graphs constructed by the second author are members of infinite families.     

Presentations for rook partition monoids and algebras and their singular ideals

We obtain several presentations by generators and relations for the rook partition monoids and algebras, as well as their singular ideals. Among other results, we also calculate the minimal sizes of generating sets (some of our presentations use such minimal-size generating sets), and show that the singular part of the rook partition monoid is generated by its idempotents.     

Explicit construction of regular graphs without small cycles

For every integerd>2 we give an explicit construction of infinitely many Cayley graphsX of degreed withn(X) vertices and girth >0.4801...(logn(X))/log (d−1)−2. This improves a result of Margulis. Dedicated to Paul Erdős on his seventieth birthday     

Factorial regular representation of groups in complete graphs

A necessary and sufficient condition for the group of isomorphisms involved in a factorization of a complete graph into isomorphic factors is established.     

Classification of regular embeddings of hypercubes of odd dimension

By a regular embedding of a graph into a closed surface we mean a 2-cell embedding with the automorphism group acting regularly on flags. Recently, Kwon and Nedela [Non-existence of nonorientable regular embeddings of n-dimensional cubes, Discrete Math., to appear] showed that no regular embeddings of the n-dimensional cubes Q_n into nonorientable surfaces exist for any positive integer n>2. In 1997, Nedela and Škoviera [Regular maps from voltage assignments and exponent groups, European J. Combin. 18 (1997) 807-823] presented a construction giving for each solution of the congruence a regular embedding M_e of the hypercube Q_n into an orientable surface. It was conjectured that all regular embeddings of Q_n into orientable surfaces can be constructed in this way. This paper gives a classification of regular embeddings of hypercubes Q_n into orientable surfaces for n odd, proving affirmatively the conjecture of Nedela and Škoviera for every odd n.     

Posets whose monoids of order-preserving maps are regular

The purpose of this paper is to determine all posetsP such that the monoid of all order-preserving maps ofP intoP is regular in the semigroup-theoretic sense. AMS subject classifications (1980). 06A10, 20M20.     

Local Recognition Of Non-Incident Point-Hyperplane Graphs

Let be a projective space. By H() we denote the graph whose vertices are the non-incident point-hyperplane pairs of , two vertices (p,H) and (q,I) being adjacent if and only if p I and q H. In this paper we give a characterization of the graph H() (as well as of some related graphs) by its local structure. We apply this result by two characterizations of groups G with PSL _n ( )GPGL _n ( ), by properties of centralizers of some (generalized) reflections. Here is the (skew) field of coordinates of .     

Polarities of G. Higman's symmetric design and a strongly regular graph on 176 vertices

We investigate the polarities of G. Higman's symmetric 2-(176, 50, 14) design and find that there are two of them (up to conjugacy), one having 80 and the other 176 absolute points. From the latter we can derive a strongly regular graph with parameters (v, k, , )=(176, 49, 12, 14). Its group of automorphisms is Sym(8) with orbits of size 8 and 168 on the vertices. It does not carry a partial geometry or a delta space, and is not the result of mergingd=1 andd=2 in a distance regular graph with diameter 3 and girth 6 on 176 vertices.     

Self-duality of chiral polytopes

We prove that self-dual chiral polytopes of odd rank possess a polarity, that is, an involutory duality, and give an example showing this is not true in even ranks. Properties of the extended groups, that is of the groups of automorphisms and dualities, of self-dual chiral polytopes are discussed in detail.