Loading...
3 results
Search Results
Now showing 1 - 3 of 3
- The commuting graph of the symmetric inverse semigroupPublication . Araújo, João; Bentz, Wolfram; Konieczny, JanuszThe commuting graph of a finite non-commutative semigroup S, denoted G(S), is a simple graph whose vertices are the non-central elements of S and two distinct vertices x, y are adjacent if xy = yx. Let I(X) be the symmetric inverse semigroup of partial injective transformations on a finite set X. The semigroup I(X) has the symmetric group Sym(X) of permutations on X as its group of units. In 1989, Burns and Goldsmith determined the clique number of the commuting graph of Sym(X). In 2008, Iranmanesh and Jafarzadeh found an upper bound of the diameter of G(Sym(X)), and in 2011, Dol˘zan and Oblak claimed that this upper bound is in fact the exact value.The goal of this paper is to begin the study of the commuting graph of the symmetric inverse semigroup I(X). We calculate the clique number of G(I(X)), the diameters of the commuting graphs of the proper ideals of I(X), and the diameter of G(I(X)) when |X| is even or a power of an odd prime. We show that when |X| is odd and divisible by at least two primes, then the diameter of G(I(X)) is either 4 or 5. In the process, we obtain several results about semigroups, such as a description of all commutative subsemigroups of I(X) of maximum order, and analogous results for commutative inverse and commutative nilpotent subsemigroups of I(X). The paper closes with a number of problems for experts in combinatorics and in group or semigroup theory.
- Matrix theory for independence algebrasPublication . Araújo, João; Bentz, Wolfram; Cameron, Peter; Kinyon, Michael; Konieczny, JanuszA universal algebra A with underlying set A is said to be a matroid algebra if (A, 〈·〉), where 〈·〉 denotes the operator subalgebra generated by, is a matroid. A matroid algebra is said to be an independence algebra if every mapping α : X → A defined on a minimal generating X of A can be extended to an endomorphism of A. These algebras are particularly well-behaved generalizations of vector spaces, and hence they naturally appear in several branches of mathematics, such as model theory, group theory, and semigroup theory. It is well known that matroid algebras have a well-defined notion of dimension. Let A be any independence algebra of finite dimension n, with at least two elements. Denote by End(A) the monoid of endomorphisms of A. In the 1970s, Glazek proposed the problem of extending the matrix theory for vector spaces to a class of universal algebras which included independence algebras. In this paper, we answer that problem by developing a theory of matrices for (almost all) finite-dimensional independence algebras. In the process of solving this, we explain the relation between the classification of inde- pendence algebras obtained by Urbanik in the 1960s, and the classification of finite indepen- dence algebras up to endomorphism-equivalence obtained by Cameron and Szab ́o in 2000. (This answers another question by experts on independence algebras.) We also extend the classification of Cameron and Szab ́o to all independence algebras. The paper closes with a number of questions for experts on matrix theory, groups, semi- groups, universal algebra, set theory or model theory.
- The largest subsemilattices of the endomorphism monoid of an independence algebraPublication . Araújo, João; Bentz, Wolfram; Konieczny, JanuszAn algebra A is said to be an independence algebra if it is a matroid algebra and every map α:X→A, defined on a basis X of A, can be extended to an endomorphism of A. These algebras are particularly well-behaved generalizations of vector spaces, and hence they naturally appear in several branches of mathematics such as model theory, group theory, and semigroup theory. It is well known that matroid algebras have a well-defined notion of dimension. Let A be any independence algebra of finite dimension n , with at least two elements. Denote by End(A) the monoid of endomorphisms of A. We prove that a largest subsemilattice of End(A) has either 2n−1 elements (if the clone of A does not contain any constant operations) or 2n elements (if the clone of A contains constant operations). As corollaries, we obtain formulas for the size of the largest subsemilattices of: some variants of the monoid of linear operators of a finite-dimensional vector space, the monoid of full transformations on a finite set X, the monoid of partial transformations on X, the monoid of endomorphisms of a free G-set with a finite set of free generators, among others. The paper ends with a relatively large number of problems that might attract attention of experts in linear algebra, ring theory, extremal combinatorics, group theory, semigroup theory, universal algebraic geometry, and universal algebra.