Search

Part of the work was done while the authors were visiting the South China University of Science and Technology (SUSTech), Shenzhen, in 2018, and we are grateful (in particular to Professor Cai Heng Li) for the hospitality that we received.The authors would like to thank the Isaac Newton Institute for Mathematical Sciences, Cambridge, for support and hospitality during the programme Groups, representations and applications: new perspectives (supported by EPSRC grant no.EP/R014604/1), where further work on this paper was undertaken. In particular we acknowledge a Simons Fellowship (Cameron) and a Kirk Distinguished Visiting Fellowship (Praeger) during this programme. Schneider thanks the Centre for the Mathematics of Symmetry and Computation of The University of Western Australia and Australian Research Council Discovery Grant DP160102323 for hosting his visit in 2017 and acknowledges the support of the CNPq projects Produtividade em Pesquisa (project no.: 308212/2019-3) and Universal (project no.:421624/2018-3). Diagonal groups are one of the classes of finite primitive permutation groups occurring in the conclusion of the O'Nan-Scott theorem. Several of the other classes have been described as the automorphism groups of geometric or combinatorial structures such as affine spaces or Cartesian decompositions, but such structures for diagonal groups have not been studied in general. The main purpose of this paper is to describe and characterise such structures, which we call diagonal semilattices. Unlike the diagonal groups in the O'Nan-Scott theorem, which are defined over finite characteristically simple groups, our construction works over arbitrary groups, finite or infinite. A diagonal semilattice depends on a dimension m and a group T. For m=2, it is a Latin square, the Cayley table of T, though in fact any Latin square satisfies our combinatorial axioms. However, for m≥3, the group T emerges naturally and uniquely from the axioms. (The situation somewhat resembles projective geometry, where projective planes exist in great profusion but higher-dimensional structures are coordinatised by an algebraic object, a division ring.) A diagonal semilattice is contained in the partition lattice on a set Ω, and we provide an introduction to the calculus of partitions. Many of the concepts and constructions come from experimental design in statistics. We also determine when a diagonal group can be primitive, or quasiprimitive (these conditions turn out to be equivalent for diagonal groups). Associated with the diagonal semilattice is a graph, the diagonal graph, which has the same automorphism group as the diagonal semilattice except in four small cases with m

In an earlier paper by three of the present authors and Csaba Schneider, it was shown that, for $$m\ge 2$$ m ≥ 2 , a set of $$m+1$$ m + 1 partitions of a set $$\Omega $$ Ω , any m of which are the minimal non-trivial elements of a Cartesian lattice, either form a Latin square (if $$m=2$$ m = 2 ), or generate a join-semilattice of dimension m associated with a diagonal group over a base group G. In this paper we investigate what happens if we have $$m+r$$ m + r partitions with $$r\ge 2$$ r ≥ 2 , any m of which are minimal elements of a Cartesian lattice. If $$m=2$$ m = 2 , this is just a set of mutually orthogonal Latin squares. We consider the case where all these squares are isotopic to Cayley tables of groups, and give an example to show the groups need not be all isomorphic. For $$m>2$$ m > 2 , things are more restricted. Any $$m+1$$ m + 1 of the partitions generate a join-semilattice admitting a diagonal group over a group G. It may be that the groups are all isomorphic, though we cannot prove this. Under an extra hypothesis, we show that G must be abelian and must have three fixed-point-free automorphisms whose product is the identity. (We describe explicitly all abelian groups having such automorphisms.) Under this hypothesis, the structure gives an orthogonal array, and conversely in some cases. If the group is cyclic of prime order p, then the structure corresponds exactly to an arc of cardinality $$m+r$$ m + r in the $$(m-1)$$ ( m - 1 ) -dimensional projective space over the field with p elements, so all known results about arcs are applicable. More generally, arcs over a finite field of order q give examples where G is the elementary abelian group of order q. These examples can be lifted to non-elementary abelian groups using p-adic techniques.

Funding: Ajay Kumar is supported by CSIR-UGC JRF, New Delhi, India, through Ref No.: 19/06/2016(i)EU-V/Roll No: 417267. Lavanya Selvaganesh is financially supported by SERB, India, through Grant No.: MTR/2018/000254 under the scheme MATRICS. T. Tamizh Chelvam is supported by CSIR Emeritus Scientist Scheme of Council of Scientific and Industrial Research (No.21 (1123)/20/EMR-II), Government of India. Algebraic graph theory is the study of the interplay between algebraic structures (both abstract as well as linear structures) and graph theory. Many concepts of abstract algebra have facilitated through the construction of graphs which are used as tools in computer science. Conversely, graph theory has also helped to characterize certain algebraic properties of abstract algebraic structures. In this survey, we highlight the rich interplay between the two topics viz groups and power graphs from groups. In the last decade, extensive contribution has been made towards the investigation of power graphs. Our main motive is to provide a complete survey on the connectedness of power graphs and proper power graphs, the Laplacian and adjacency spectrum of power graph, isomorphism, and automorphism of power graphs, characterization of power graphs in terms of groups. Apart from the survey of results, this paper also contains some new material such as the contents of Section 2 (which describes the interesting case of the power graph of the Mathieu group M_{11}) and subsection 6.1 (where conditions are discussed for the reduced power graph to be not connected). We conclude this paper by presenting a set of open problems and conjectures on power graphs. Publisher PDF

Preprint de J. Araújo, J.P. Araújo, W. Bentz, P.J. Cameron, and P. Spiga, “A Transversal Property for Permutation Groups Motivated by Partial Transformations”, Journal of Algebra 573 (2021), 741-759. In this paper we introduce the definition of the (k, l)-universal transversal property for permutation groups, which is a refinement of the definition of k-universal transversal property, which in turn is a refine- ment of the classical definition of k-homogeneity for permutation groups. In particular, a group possesses the (2, n)-universal transversal property if and only if it is primitive; it possesses the (2, 2)-universal transversal property if and only if it is 2-homogeneous. Up to a few undecided cases, we give a classification of groups satisfying the (k, l)-universal transversal property, for k ≥ 3. Then we apply this result for studying regular semigroups of partial transformations. The first and third authors were partially supported by the Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology) through projects UIDB/00297/2020 (Center for Mathematics and Applications) and CEMAT-CIÊNCIAS UID/Multi/04621/2013, and also by the Fundacão para a Ciência e a Tecnologia through project PTDC/MAT-PUR/31174/2017. The second author was partially supported by Fundação Calouste Gulbenkian, Programa Talentos Inteligência Artificial. The fourth author was partially supported by Fundação para a Ciência e a Tecnologia (Portuguese Founda- tion for Science and Technology) through project CEMAT-CIÊNCIAS UID/Multi/04621/2013. info:eu-repo/semantics/publishedVersion

Preprint de J. Araújo, W. Bentz, and P.J. Cameron, “Primitive Permutation Groups and Strongly Factorizable Transformation Semigroups”, Journal of Algebra 565 (2021), 513-530. Let Ω be a finite set and T (Ω) be the full transformation monoid on Ω. The rank of a transformation t ∈ T (Ω) is the natural number |Ωt|. Given A ⊆ T (Ω), denote by 〈A〉 the semigroup generated by A. Let k be a fixed natural number such that 2 ≤ k ≤ |Ω|. In the first part of this paper we (almost) classify the permutation groups G on Ω such that for all rank k transformations t ∈ T (Ω), every element in St := 〈G, t〉 can be written as a product eg, where e2 = e ∈ St and g ∈ G. In the second part we prove, among other results, that if S ≤ T (Ω) and G is the normalizer of S in the symmetric group on Ω, then the semigroup SG is regular if and only if S is regular. (Recall that a semigroup S is regular if for all s ∈ S there exists s′ ∈ S such that s = ss′s.) The paper ends with a list of problems. The first author was partially supported by the Funda ̧c ̃ao para a Ciˆencia e a Tecnologia (Portuguese Foundation for Science and Technology) through the projects UIDB/00297/2020 (Centro de Matemtica e Aplicaes), PTDC/MAT-PUR/31174/2017, UIDB/04621/2020 and UIDP/04621/2020. info:eu-repo/semantics/publishedVersion

A $P_4$-free graph is called a cograph. In this paper we partially characterize finite groups whose power graph is a cograph. As we will see, this problem is a generalization of the determination of groups in which every element has prime power order, first raised by Graham Higman in 1957 and fully solved very recently. First we determine all groups $G$ and $H$ for which the power graph of $G\times H$ is a cograph. We show that groups whose power graph is a cograph can be characterised by a condition only involving elements whose orders are prime or the product of two (possibly equal) primes. Some important graph classes are also taken under consideration. For finite simple groups we show that in most of the cases their power graphs are not cographs: the only ones for which the power graphs are cographs are certain groups PSL$(2,q)$ and Sz$(q)$ and the group PSL$(3,4)$. However, a complete determination of these groups involves some hard number-theoretic problems., 20 Pages

For a prime power q and a positive integer n , we say a subspace U of F q n is cyclically covering if the union of the cyclic shifts of U is equal to F q n . We investigate the problem of determining the minimum possible dimension of a cyclically covering subspace of F q n . (This is a natural generalisation of a problem posed in 1991 by the first author.) We prove several upper and lower bounds, and for each fixed q , we answer the question completely for infinitely many values of n (which take the form of certain geometric series). Our results imply lower bounds for a well-known conjecture of Isbell, and a generalisation thereof, supplementing lower bounds due to Spiga. We also consider the analogous problem for general representations of groups. We use arguments from combinatorics, representation theory and finite field theory.

The undirected power graph (or simply power graph) of a group $G$, denoted by $P(G)$, is a graph whose vertices are the elements of the group $G$, in which two vertices $u$ and $v$ are connected by an edge between if and only if either $u=v^i$ or $v=u^j$ for some $i$, $j$. A number of important graph classes, including perfect graphs, cographs, chordal graphs, split graphs, and threshold graphs, can be defined either structurally or in terms of forbidden induced subgraphs. We examine each of these five classes and attempt to determine for which groups $G$ the power graph $P(G)$ lies in the class under consideration. We give complete results in the case of nilpotent groups, and partial results in greater generality. In particular, the power graph is always perfect; and we determine completely the groups whose power graph is a threshold or split graph (the answer is the same for both classes). We give a number of open problems., Comment: 18 pages, 1 figure

Funding: the research of the last two authors is supported by the Australian Research Council Discovery Project DP200101951. This work was supported by EPSRC grant no EP/R014604/1. In addition, the second author was supported by a Simons Fellowship. We examine the subgroup D(G) of a transitive permutation group G which is generated by the derangements in G. Our main results bound the index of this subgroup: we conjecture that, if G has degree n and is not a Frobenius group, then |G:D(G)|≤ √n-1; we prove this except when G is a primitive affine group. For affine groups, we translate our conjecture into an equivalent form regarding |H:R(H)|, where H is a linear group on a finite vector space and R(H) is the subgroup of H generated by elements having eigenvalue 1. If G is a Frobenius group, then D(G) is the Frobenius kernel, and so G/D(G) is isomorphic to a Frobenius complement. We give some examples where D(G) ≠ G, and examine the group-theoretic structure of G/D(G); in particular, we construct groups G in which G/D(G) is not a Frobenius complement. Postprint

For a nilpotent group $G$, let $\Xi(G)$ be the difference between the complement of the generating graph of $G$ and the commuting graph of $G$, with vertices corresponding to central elements of $G$ removed. That is, $\Xi(G)$ has vertex set $G \setminus Z(G)$, with two vertices adjacent if and only if they do not commute and do not generate $G$. Additionally, let $\Xi^+(G)$ be the subgraph of $\Xi(G)$ induced by its non-isolated vertices. We show that if $\Xi(G)$ has an edge, then $\Xi^+(G)$ is connected with diameter $2$ or $3$, with $\Xi(G) = \Xi^+(G)$ in the diameter $3$ case. In the infinite case, our results apply more generally, to any group with every maximal subgroup normal. When $G$ is finite, we explore the relationship between the structures of $G$ and $\Xi(G)$ in more detail., Comment: 13 pages

Let $G$ be a permutation group of degree $n$, and $k$ a positive integer with $k\le n$. We say that $G$ has the $k$-existential property, or $k$-et for short, if there exists a $k$-subset $A$ of the domain $\Omega$ such that, for any $k$-partition $\mathcal{P}$ of $\Omega$, there exists $g\in G$ mapping $A$ to a transversal (a section) for $\mathcal{P}$. This property is a substantial weakening of the $k$-universal transversal property, or $k$-ut, investigated by the first and third author, which required this condition to hold for all $k$-subsets $A$ of the domain. Our first task in this paper is to investigate the $k$-et property and to decide which groups satisfy it. For example, we show that, for $8\le k\le n/2$, the only groups with $k$-et are the symmetric and alternating groups; this is best possible since the Mathieu group $M_{24}$ has $7$-et. We determine all groups with $k$-et for $4\le k\le n/2$, up to some unresolved cases for $k=4,5$, and describe the property for $k=2,3$ in permutation group language. In the previous work, the results were applied to semigroups, in particular, to the question of when the semigroup $\langle G,t\rangle$ is regular, where $t$ is a map of rank $k$ (with $k, Comment: Added one additional resolved case and pictures for understanding

It is known that, if we take a countable model of Zermelo–Fraenkel set theory ZFC and “undirect” the membership relation (that is, make a graph by joining x to y if either $$x\in y$$ x ∈ y or $$y\in x$$ y ∈ x ), we obtain the Erdős–Rényi random graph. The crucial axiom in the proof of this is the Axiom of Foundation; so it is natural to wonder what happens if we delete this axiom, or replace it by an alternative (such as Aczel’s Anti-Foundation Axiom). The resulting graph may fail to be simple; it may have loops (if $$x\in x$$ x ∈ x for some x) or multiple edges (if $$x\in y$$ x ∈ y and $$y\in x$$ y ∈ x for some distinct x, y). We show that, in ZFA, if we keep the loops and ignore the multiple edges, we obtain the “random loopy graph” (which is $$\aleph _0$$ ℵ 0 -categorical and homogeneous), but if we keep multiple edges, the resulting graph is not $$\aleph _0$$ ℵ 0 -categorical, but has infinitely many 1-types. Moreover, if we keep only loops and double edges and discard single edges, the resulting graph contains countably many connected components isomorphic to any given finite connected graph with loops.

Let G be a group. The power graph of G is a graph with vertex set G in which two distinct elements x, y are adjacent if one of them is a power of the other. We characterize all groups whose power graphs have finite independence number, show that they have clique cover number equal to their independence number, and calculate this number. The proper power graph is the induced subgraph of the power graph on the set $$G-\{1\}$$G-{1}. A group whose proper power graph is connected must be either a torsion group or a torsion-free group; we give characterizations of some groups whose proper power graphs are connected.

Square lattice designs are often used in trials of new varieties of various agricultural crops. However, there are no square lattice designs for 36 varieties in blocks of size six for four or more replicates. Here we use three different approaches to construct designs for up to eight replicates. All the designs perform well in terms of giving a low average variance of variety contrasts. Supplementary materials are available online., Comment: Paper submitted to JABES special issue

The Hall--Paige conjecture asserts that a finite group has a complete mapping if and only if its Sylow subgroups are not cyclic. The conjecture is now proved, and one aim of this paper is to document the final step in the proof (for the sporadic simple group $\mathrm{J}_4$). We apply this result to prove that primitive permutation groups of simple diagonal type with three or more simple factors in the socle are non-synchronizing. We also give the simpler proof that, for groups of affine type, or simple diagonal type with two socle factors, synchronization and separation are equivalent. Synchronization and separation are conditions on permutation groups which are stronger than primitivity but weaker than $2$-homogeneity, the second of these being stronger than the first. Empirically it has been found that groups which are synchronizing but not separating are rather rare. It follows from our results that such groups must be primitive of almost simple type., Comment: Accepted by Journal of Algebra (Charles Sims memorial issue)

Funding: R.A. Bailey and Peter J. Cameron are grateful to Shanghai Jiao Tong University for funding, from the National Science Foundation of China (11671258) and STCSM (17690740800), a research visit where part of this study was done. Alexander L. Gavrilyuk was supported by BK21plus Center for Math Research and Education at Pusan National University, Republic of Korea. Sergey V. Goryainov was supported by the National Science Foundation of China, STCSM (17690740800) and RFBR (17‐51‐560008).

This work was developed within FCT project CEMAT-CIÊNCIAS (UID/Multi/04621/2013). The purpose of this paper is to advance our knowledge of two of the most classic and popular topics in transformation semigroups: automorphisms and the size of minimal generating sets. In order to do this, we examine the k-homogeneous permutation groups (those which act transitively on the subsets of size k of their domain X) where |X|=n and k

Recently Peter Keevash solved asymptotically the existence question for Steiner systems by showing that $S(t,k,n)$ exists whenever the necessary divisibility conditions on the parameters are satisfied and $n$ is sufficiently large in terms of $k$ and $t$. The purpose of this paper is to make a conjecture which if true would be a significant extension of Keevash's theorem, and to give some theoretical and computational evidence for the conjecture. We phrase the conjecture in terms of the notions (which we define here) of synchronization and separation for association schemes. These definitions are based on those for permutation groups which grow out of the theory of synchronization in finite automata. In this theory, two classes of permutation groups (called \emph{synchronizing} and \emph{separating}) lying between primitive and $2$-homogeneous are defined. A big open question is how the permutation group induced by $S_n$ on $k$-subsets of $\{1,\ldots,n\}$ fits in this hierarchy; our conjecture would give a solution to this problem for $n$ large in terms of $k$. We prove the conjecture in the case $k=4$: our result asserts that $S_n$ acting on $4$-sets is separating for $n\ge10$ (it fails to be synchronizing for $n=9$)., Comment: Error in previous version corrected

The goal of this paper is to study primitive groups that are contained in the union of maximal (in the symmetric group) imprimitive groups. The study of types of permutations that appear inside primitive groups goes back to the origins of the theory of permutation groups. However, this is another instance of a situation common in mathematics in which a very natural problem turns out to be extremely difficult. Fortunately, the enormous progresses of the last few decades seem to allow a new momentum on the attack to this problem. In this paper we prove that there are infinite families of primitive groups contained in the union of imprimitive groups and propose a new hierarchy for primitive groups based on that fact. In addition to the previous results and hierarchy, we introduce some algorithms to handle permutations, provide the corresponding GAP implementation, solve some open problems, and propose a large list of open problems.

This paper addresses the question of whether triple arrays can be constructed from Youden squares developed from difference sets. We prove that if the difference set is abelian, then having −1 as multiplier is both a necessary and sufficient condition for the construction to work. Using this, we are able to give a new infinite family of triple arrays. We use an alternative version of the construction to analyze the case of non-abelian difference sets, for which we prove a sufficient condition for giving triple arrays. We do a computer search for such non-abelian difference sets, but have not found any examples satisfying the given condition.

This research was supported by a Marsden grant (UOA1218) of the Royal Society of New Zealand, and by the Portuguese Foundation for Science and Technology (FCT-Fundacao para a Ciencia e a Tecnologia), through CIDMA - Center for Research and Development in Mathematics and Applications, within project UID/MAT/04106/2013.

A classic result of Delsarte connects the strength (as orthogonal array) of a linear code with the minimum weight of its dual: the former is one less than the latter. Since the paper of Hammons et al., there is a lot of interest in codes over rings, especially in codes over $$\mathbb {Z}_{4}$$Z4 and their (usually non-linear) binary Gray map images. We show that Delsarte's observation extends to codes over arbitrary finite commutative rings with identity. Also, we show that the strength of the Gray map image of a $$\mathbb {Z}_{4}$$Z4 code is one less than the minimum Lee weight of its Gray map image.

An $integral$ of a group $G$ is a group $H$ whose derived group (commutator subgroup) is isomorphic to $G$. This paper discusses integrals of groups, and in particular questions about which groups have integrals and how big or small those integrals can be. Our main results are: (1) If a finite group has an integral, then it has a finite integral. (2) A precise characterization of the set of natural numbers $n$ for which every group of order $n$ is integrable: these are the cubefree numbers $n$ which do not have prime divisors $p$ and $q$ with $q\mid p-1$. (3) An abelian group of order $n$ has an integral of order at most $n^{1+o(1)}$, but may fail to have an integral of order bounded by $cn$ for constant $c$. (4) A finite group can be integrated $n$ times (in the class of finite groups) if and only if it is the central product of an abelian group and a perfect group. There are many other results on such topics as centreless groups, groups with composition length $2$, and infinite groups. We also include a number of open problems., 31 pages, no figures; new co-author and new title; the previous posting has been split in half, with the second part to be expanded and resubmitted separately

Let $X$ be a finite set such that $|X|=n$ and let $i\leq j \leq n$. A group $G\leq \sym$ is said to be $(i,j)$-homogeneous if for every $I,J\subseteq X$, such that $|I|=i$ and $|J|=j$, there exists $g\in G$ such that $Ig\subseteq J$. (Clearly $(i,i)$-homogeneity is $i$-homogeneity in the usual sense.) A group $G\leq \sym$ is said to have the $k$-universal transversal property if given any set $I\subseteq X$ (with $|I|=k$) and any partition $P$ of $X$ into $k$ blocks, there exists $g\in G$ such that $Ig$ is a section for $P$. (That is, the orbit of each $k$-subset of $X$ contains a section for each $k$-partition of $X$.) In this paper we classify the groups with the $k$-universal transversal property (with the exception of two classes of 2-homogeneous groups) and the $(k-1,k)$-homogeneous groups (for $2, Comment: Includes changes suggested by the referee of the Transactions of the AMS. We gratefully thank the referee for an outstanding report that was very helpful. We also thank Peter M. Neumann for the enlightening conversations at the early stages of this investigation

The cycle polynomial of a finite permutation group $G$ is the generating function for the number of elements of $G$ with a given number of cycles: \[F_G(x) = \sum_{g\in G}x^{c(g)},\] where $c(g)$ is the number of cycles of $g$ on $\Omega$. In the first part of the paper, we develop basic properties of this polynomial, and give a number of examples. In the 1970s, Richard Stanley introduced the notion of reciprocity for pairs of combinatorial polynomials. We show that, in a considerable number of cases, there is a polynomial in the reciprocal relation to the cycle polynomial of $G$; this is the orbital chromatic polynomial of $\Gamma$ and $G$, where $\Gamma$ is a $G$-invariant graph, introduced by the first author, Jackson and Rudd. We pose the general problem of finding all such reciprocal pairs, and give a number of examples and characterisations: the latter include the cases where $\Gamma$ is a complete or null graph or a tree. The paper concludes with some comments on other polynomials associated with a permutation group., Comment: 16 pages

Let $G$ be a group‎. ‎The power graph of $G$ is a graph with the vertex‎ ‎set $G$‎, ‎having an edge between two elements whenever one is a power of the other‎. ‎We characterize nilpotent groups whose power graphs have finite independence number‎. ‎For a bounded exponent group‎, ‎we prove its power graph is a perfect graph and we determine‎ ‎its clique/chromatic number‎. ‎Furthermore‎, ‎it is proved that for every group $G$‎, ‎the clique number of the power graph of $G$ is at most countably infinite‎. ‎We also measure how close the power graph is to the commuting graph by introducing a new graph which lies in between‎. ‎We call this new graph as the enhanced power graph‎. ‎For an arbitrary pair of these three graphs we characterize finite groups for which this pair of graphs are equal‎.

Let @z(n,m) be the largest number of order m subsquares achieved by any Latin square of order n. We show that @z(n,m)=@Q(n^3) if m@?{2,3,5} and @z(n,m)=@Q(n^4) if m@?{4,6,9,10}. In particular, 18n^3+O(n^2)@?@z(n,2)@?14n^3+O(n^2) and 127n^3+O(n^5^/^2)@?@z(n,3)@?118n^3+O(n^2) for all n. We find an explicit bound on @z(n,2^d) of the form @Q(n^d^+^2) and which is achieved only by the elementary abelian 2-groups. For a fixed Latin square L let @z^@?(n,L) be the largest number of subsquares isotopic to L achieved by any Latin square of order n. When L is a cyclic Latin square we show that @z^@?(n,L)=@Q(n^3). For a large class of Latin squares L we show that @z^@?(n,L)=O(n^3). For any Latin square L we give an @e in the interval (0,1) such that @z^@?(n,L)>=@W(n^2^+^@e). We believe that this bound is achieved for certain squares L.

Let Ω be a set of cardinality n , G a permutation group on Ω , and f : Ω → Ω a map which is not a permutation. We say that G synchronizes f if the semigroup 〈 G , f 〉 contains a constant map. The first author has conjectured that a primitive group synchronizes any map whose kernel is non-uniform. Rystsov proved one instance of this conjecture, namely, degree n primitive groups synchronize maps of rank n − 1 (thus, maps with kernel type ( 2 , 1 , … , 1 ) ). We prove some extensions of Rystsov's result, including this: a primitive group synchronizes every map whose kernel type is ( k , 1 , … , 1 ) . Incidentally this result provides a new characterization of imprimitive groups. We also prove that the conjecture above holds for maps of extreme ranks, that is, ranks 3, 4 and n − 2 . These proofs use a graph-theoretic technique due to the second author: a transformation semigroup fails to contain a constant map if and only if it is contained in the endomorphism semigroup of a non-null (simple undirected) graph. The paper finishes with a number of open problems, whose solutions will certainly require very delicate graph theoretical considerations.

A transformation monoid on a set Ω is called synchronizing if it contains an element of rank 1 (that is, mapping the whole of Ω to a single point). In this paper, I tackle the question: given n and k , what is the probability that the submonoid of the full transformation monoid T n generated by k random transformations is synchronizing? Synchronization is motivated by automata theory, where a deterministic automaton is synchronizing if some sequence of transitions leads to the same point from any starting point. This is equivalent to requiring that the monoid generated by the transitions is synchronizing in the above sense. The question has some similarities with a similar question about the probability that the subgroup of S n generated by k random permutations is transitive. For k = 1 , the answer is 1 / n ; for k = 2 , Dixon’s Theorem asserts that it is 1 − o ( 1 ) as n → ∞ (and good estimates are now known). For our synchronization question, for k = 1 the answer is also 1 / n ; I conjecture that for k = 2 it is also 1 − o ( 1 ) . Following the technique of Dixon’s theorem, we need to analyse the maximal non-synchronizing submonoids of T n . I develop a very close connection between transformation monoids and graphs, from which we obtain a description of non-synchronizing monoids as endomorphism monoids of graphs satisfying some very strong conditions. However, counting such graphs, and dealing with the intersections of their endomorphism monoids, seems difficult.

The power graphP(G) of a group G is the graph whose vertex set is G, with x and y joined if one is a power of the other; the directed power graph $$\overrightarrow{P}(G)$$ has the same vertex set, with an arc from x to y if y is a power of x. It is known that, for finite groups, the power graph determines the directed power graph up to isomorphism. However, it is not true that any isomorphism between power graphs induces an isomorphism between directed power graphs. Moreover, for infinite groups the power graph may fail to determine the directed power graph. In this paper, we consider power graphs of torsion-free groups. Our main results are that, for torsion-free nilpotent groups of class at most 2, and for groups in which every non-identity element lies in a unique maximal cyclic subgroup, the power graph determines the directed power graph up to isomorphism. For specific groups such as $$\mathbb {Z}$$ and $$\mathbb {Q}$$ , we obtain more precise results. Any isomorphism $$P(\mathbb {Z})\rightarrow P(G)$$ preserves orientation, so induces an isomorphism between directed power graphs; in the case of $$\mathbb {Q}$$ , the orientations are either all preserved or all reversed. We also obtain results about groups in which every element is contained in a unique maximal cyclic subgroup (this class includes the free and free abelian groups), and about subgroups of the additive group of $$\mathbb {Q}$$ and about $$\mathbb {Q}^n$$ .

Let $X$ be a finite set such that $|X|=n$. Let $\trans$ and $\sym$ denote respectively the transformation monoid and the symmetric group on $n$ points. Given $a\in \trans\setminus \sym$, we say that a group $G\leq \sym$ is $a$-normalizing if $$ \setminus G=.$$ If $G$ is $a$-normalizing for all $a\in \trans\setminus \sym$, then we say that $G$ is normalizing. The goal of this paper is to classify normalizing groups and hence answer a question posed elsewhere. The paper ends with a number of problems for experts in groups, semigroups and matrix theory., Comment: Three lemmas replaced with a shorter argument and other changes suggested by the referee of the Journal of Algebra

Funding: National Research, Development and Innovation Fund of Hungary, financed under the FK 124814 funding scheme (second author). This work is dedicated to Tamás E. Schmidt. It is shown that the countably infinite dimensional pointed vector space (the vector space equipped with a constant) over a finite field has infinitely many first order definable reducts. This implies that the countable homogeneous Boolean-algebra has infinitely many reducts. Postprint

We give a construction of a family of designs with a specified point-partition and determine the subgroup of automorphisms leaving invariant the point-partition. We give necessary and sufficient conditions for a design in the family to possess a flag-transitive group of automorphisms preserving the specified point-partition. We give examples of flag-transitive designs in the family, including a new symmetric 2-(1408,336,80) design with automorphism group $$2^{12}:((3\cdot \mathrm {M}_{22}):2)$$212:((3·M22):2) and a construction of one of the families of the symplectic designs (the designs $$S^-(n)$$S-(n)) exhibiting a flag-transitive, point-imprimitive automorphism group.

In this paper, we introduce a new parameter of a code, referred to as the remoteness, which can be viewed as a dual to the covering radius. Indeed, the remoteness is the minimum radius needed for a single ball to cover all codewords. After giving some general results about the remoteness, we then focus on the remoteness of permutation codes. We first derive upper and lower bounds on the minimum cardinality of a code with a given remoteness. We then study the remoteness of permutation groups. We show that the remoteness of transitive groups can only take two values, and we determine the remoteness of transitive groups of odd order. We finally show that the problem of determining the remoteness of a given transitive group is equivalent to determining the stability number of a related graph.

Set-theoretic solutions of the Yang–Baxter equation form a meeting-ground of mathematical physics, algebra and combinatorics. Such a solution consists of a set X and a function r : X × X → X × X which satisfies the braid relation.

The multivariate Tutte polynomial $\hat Z_M$ of a matroid $M$ is a generalization of the standard two-variable version, obtained by assigning a separate variable $v_e$ to each element $e$ of the ground set $E$. It encodes the full structure of $M$. Let $\bv = \{v_e\}_{e\in E}$, let $K$ be an arbitrary field, and suppose $M$ is connected. We show that $\hat Z_M$ is irreducible over $K(\bv)$, and give three self-contained proofs that the Galois group of $\hat Z_M$ over $K(\bv)$ is the symmetric group of degree $n$, where $n$ is the rank of $M$. An immediate consequence of this result is that the Galois group of the multivariate Tutte polynomial of any matroid is a direct product of symmetric groups. Finally, we conjecture a similar result for the standard Tutte polynomial of a connected matroid., Comment: 8 pages, final version, to appear in J. Alg. Comb. Substantial revisions, including the addition of two alternative proofs of the main result

The base size of a permutation group, and the metric dimension of a graph, are two of a number of related parameters of groups, graphs, coherent configurations and association schemes. They have been repeatedly re-defined with different terminology in various different areas, including computational group theory and the graph isomorphism problem. We survey results on these parameters in their many incarnations, and propose a consistent terminology for them. We also present some new results, including on the base sizes of wreath products in the product action, and on the metric dimension of Johnson and Kneser graphs.

Jarik Nesetril suggested to the first author the investigation of notions of homogeneity for relational structures, where ''isomorphism'' is replaced by ''homomorphism'' in the definition. Here we look in detail at what happens for posets. For the strict order, all five generalisations of homogeneity coincide, and we give a characterisation of the countable structures that arise. For the non-strict order, there is an additional class. The ''generic poset'' plays an important role in the investigation.

Most of these problems were presented at the conference on Combinatorics, Geometry and Computer Science, held at CIRM, Luminy, 2–4 May 2007. I added one problem on a similar theme after the meeting.The problems have been arranged so that those with similar themes occur together as far as possible.

A collection of open problems, mostly presented at the problem session of the 21st British Combinatorial Conference.

In this paper we investigate guessing number, a relatively new concept linked to network coding and certain long standing open questions in circuit complexity. Here we study the bounds and a variety of properties concerning this parameter. As an application, we obtain the lower and upper bounds for shift graphs, a subclass of directed circulant graphs.

We investigate the computational complexity of finding an element of a permutation group [email protected]?S"n with minimal distance to a given @[email protected]?S"n, for different metrics on S"n. We assume that H is given by a set of generators. In particular, the size of H might be exponential in the input size, so that in general the problem cannot be solved in polynomial time by exhaustive enumeration. For the case of the Cayley Distance, this problem has been shown to be NP-hard, even if H is abelian of exponent two [R.G.E. Pinch, The distance of a permutation from a subgroup of S"n, in: G. Brightwell, I. Leader, A. Scott, A. Thomason (Eds.), Combinatorics and Probability, Cambridge University Press, 2007, pp. 473-479]. We present a much simpler proof for this result, which also works for the Hamming Distance, the l"p distance, Lee's Distance, Kendall's tau, and Ulam's Distance. Moreover, we give an NP-hardness proof for the l"~ distance using a different reduction idea. Finally, we discuss the complexity of the corresponding fixed-parameter and maximization problems.

A transitive (infinite) permutation group which has m orbits on ordered pairs of distinct points has at least m n−1 orbits on ordered n-tuples. This is best possible, and groups attaining the bound can be characterised.

The core of a graph Γ is the smallest graph Δ that is homomorphically equivalent to Γ (that is, there exist homomorphisms in both directions). The core of Γ is unique up to isomorphism and is an induced subgraph of Γ. We give a construction in some sense dual to the core. Thehullof a graph Γ is a graph containing Γ as a spanning subgraph, admitting all the endomorphisms of Γ, and having as core a complete graph of the same order as the core of Γ. This construction is related to the notion of a synchronizing permutation group, which arises in semigroup theory; we provide some more insight by characterizing these permutation groups in terms of graphs. It is known that the core of a vertex-transitive graph is vertex-transitive. In some cases we can make stronger statements: for example, if Γ is a non-edge-transitive graph, we show that either the core of Γ is complete, or Γ is its own core. Rank-three graphs are non-edge-transitive. We examine some families of these to decide which of the two alternatives for the core actually holds. We will see that this question is very difficult, being equivalent in some cases to unsolved questions in finite geometry (for example, about spreads, ovoids and partitions into ovoids in polar spaces).