Search

Let $G$ be a finite solvable group and let $\Delta(G)$ be the character degree graph of $G$. In this paper, we obtain the metric dimension of certain character degree graphs. Specifically, we calculate the metric dimension for a regular character degree graph, a character degree graph with a diameter of $2$ that is not a block, a character degree graph with a diameter of $3$ that also has a cut vertex and a character degree graph with Fitting height $2.$ We also consider two related parameters, base size and adjacency dimension, and their relation to metric dimension for character degree graphs of solvable groups.

This paper makes some preliminary observations towards an extension of current work on graphs defined on groups to simplicial complexes. I define a variety of simplicial complexes on a group which are preserved by automorphisms of the group, and in many cases have a relation to familiar graphs on the group. The ones which seem to reach deepest into the graph structure are two forms of independence complex, and some results on the class of groups for which these two complexes coincide are given. Other examples are treated more briefly., Comment: error in comment corrected

Let $G$ be a transitive permutation group on $\Omega$. The $G$-invariant partitions form a sublattice of the lattice of all partitions of $\Omega$, having the further property that all its elements are uniform (that is, have all parts of the same size). If, in addition, all the equivalence relations defining the partitions commute, then the relations form an \emph{orthogonal block structure}, a concept from statistics; in this case the lattice is modular. If it is distributive, then we have a \emph{poset block structure}, whose automorphism group is a \emph{generalised wreath product}. We examine permutation groups with these properties, which we call the \emph{OB property} and \emph{PB property} respectively, and in particular investigate when direct and wreath products of groups with these properties also have these properties. A famous theorem on permutation groups asserts that a transitive imprimitive group $G$ is embeddable in the wreath product of two factors obtained from the group (the group induced on a block by its setwise stabiliser, and the group induced on the set of blocks by~$G$). We extend this theorem to groups with the PB property, embeddng them into generalised wreath products. We show that the map from posets to generalised wreath products preserves intersections and inclusions. We have included background and historical material on these concepts., Comment: Embedding theorem strengthened

These problems were mostly presented at the problem session at the 30th British Combinatorial Conference at Queen Mary University of London on 4 July 2024. Some were contributed later by conference participants. Thank you to all the contributors. The problems are given here in alphabetical order of presenter. If no originator is given, I assume that the presenter is the originator. Please send corrections to me (\texttt{pjc20@st-andrews.ac.uk}). Solutions should be sent to the presenter; I would appreciate a copy too., Comment: 22 problems from the conference, edited by Peter J. Cameron

Let $G$ be a group. Associate a graph $\mathcal{E}_G$ (called the co-Engel graph of $G$) with $G$ whose vertex set is $G$ and two distinct vertices $x$ and $y$ are adjacent if $[x, {}_k y] \neq 1$ and $[y, {}_k x] \neq 1$ for all positive integer $k$. This graph, under the name ``Engel graph'', was introduced by Abdollahi. Let $L(G)$ be the set of all left Engel elements of $G$. In this paper, we realize the induced subgraph of co-Engel graphs of certain finite non-Engel groups $G$ induced by $G \setminus L(G)$. We write $\mathcal{E}^-(G)$ to denote the subgraph of $\mathcal{E}_G$ induced by $G \setminus L(G)$. We also compute genus, various spectra, energies and Zagreb indices of $\mathcal{E}^-(G)$ for those groups. As a consequence, we determine (up to isomorphism) all finite non-Engel group $G$ such that the clique number is at most $4$ and $\mathcal{E}^-$ is toroidal or projective. Further, we show that $\coeng{G}$ is super integral and satisfies the E-LE conjecture and the Hansen--Vuki{\v{c}}evi{\'c} conjecture for the groups considered in this paper.

Let A be a graph type and B an equivalence relation on a group $G$. Let $[g]$ be the equivalence class of $g$ with respect to the equivalence relation B. The B superA graph of $G$ is an undirected graph whose vertex set is $G$ and two distinct vertices $g, h \in G$ are adjacent if $[g] = [h]$ or there exist $x \in [g]$ and $y \in [h]$ such that $x$ and $y$ are adjacent in the A graph of $G$. In this paper, we compute spectrum of equality/conjugacy supercommuting graphs of dihedral/dicyclic groups and show that these graphs are not integral.

Let $k$ and $l$ be integers, both at least 2. A $(k,l)$-bipartite graph is an $l$-regular bipartite multigraph with coloured bipartite sets of size $k$. Define $\chi(k,l)$ and $\mu(k,l)$ to be the minimum and maximum order of automorphism groups of $(k,l)$-bipartite graphs, respectively. We determine $\chi(k,l)$ and $\mu(k,l)$ for $k\geq 8$, and analyse the generic situation when $k$ is fixed and $l$ is large. In particular, we show that almost all such graphs have automorphism groups which fix the vertices pointwise and have order far less than $\mu(k,l)$. These graphs are intimately connected with both integer doubly-stochastic matrices and uniform set partitions; we examine the uniform distribution on the set of $k\times k$ integer doubly-stochastic matrices with all line sums $l$, showing that with high probability all entries stray far from the mean. We also show that the symmetric group acting on uniform set partitions is non-synchronizing., Comment: 18 pages

Let $\mathcal{F}$ be a set of finite groups. A finite group $G$ is called an \emph{$\mathcal{F}$-cover} if every group in $\mathcal{F}$ is isomorphic to a subgroup of $G$. An $\mathcal{F}$-cover is called \emph{minimal} if no proper subgroup of $G$ is an $\mathcal{F}$-cover, and \emph{minimum} if its order is smallest among all $\mathcal{F}$-covers. We prove several results about minimal and minimum $\mathcal{F}$-covers: for example, every minimal cover of a set of $p$-groups (for $p$ prime) is a $p$-group (and there may be finitely or infinitely many, for a given set); every minimal cover of a set of perfect groups is perfect; and a minimum cover of a set of two nonabelian simple groups is either their direct product or simple. Our major theorem determines whether $\{\mathbb{Z}_q,\mathbb{Z}_r\}$ has finitely many minimal covers, where $q$ and $r$ are distinct primes. Motivated by this, we say that $n$ is a \emph{Cauchy number} if there are only finitely many groups which are minimal (under inclusion) with respect to having order divisible by $n$, and we determine all such numbers. This extends Cauchy's theorem. We also define a dual concept where subgroups are replaced by quotients, and we pose a number of problems.

If $G$ is a graph, $A$ and $B$ its induced subgraphs, and $f\colon A\to B$ an isomorphism, we say that $f$ is a \emph{partial automorphism} of $G$. In 1992, Hrushovski proved that graphs have the \emph{extension property for partial automorphisms} (\emph{EPPA}, also called the \emph{Hrushovski property}), that is, for every finite graph $G$ there is a finite graph $H$, an \emph{EPPA-witness} for $G$, such that $G$ is an induced subgraph of $H$ and every partial automorphism of $G$ extends to an automorphism of $H$. The EPPA number of a graph $G$, denoted by $\mathop{\mathrm{eppa}}\nolimits(G)$, is the smallest number of vertices of an EPPA-witness for $G$, and we put $\mathop{\mathrm{eppa}}\nolimits(n) = \max\{\mathop{\mathrm{eppa}}\nolimits(G) : \lvert G\rvert = n\}$. In this note we review the state of the area, prove several lower bounds (in particular, we show that $\mathop{\mathrm{eppa}}\nolimits(n)\geq \frac{2^n}{\sqrt{n}}$, thereby identifying the correct base of the exponential) and pose many open questions. We also briefly discuss EPPA numbers of hypergraphs, directed graphs, and $K_k$-free graphs., Comment: Minor revision

This paper provides a bridge between two active areas of research, the spectrum (set of element orders) and the power graph of a finite group. The order sequence of a finite group $G$ is the list of orders of elements of the group, arranged in non-decreasing order. Order sequences of groups of order $n$ are ordered by elementwise domination, forming a partially ordered set. We prove a number of results about this poset, among them the following. M.~Amiri recently proved that the poset has a unique maximal element, corresponding to the cyclic group. We show that the product of orders in a cyclic group of order $n$ is at least $q^{\phi(n)}$ times as large as the product in any non-cyclic group,where $q$ is the smallest prime divisor of $n$ and $\phi$ is Euler's function, with a similar result for the sum. The poset of order sequences of abelian groups of order $p^n$ is naturally isomorphic to the (well-studied) poset of partitions of $n$ with its natural partial order. If there exists a non-nilpotent group of order $n$, then there exists such a group whose order sequence is dominated by the order sequence of any nilpotent group of order $n$. There is a product operation on finite ordered sequences, defined by forming all products and sorting them into non-decreasing order. The product of order sequences of groups $G$ and $H$ is the order sequence of a group if and only if $|G|$ and $|H|$ are coprime. The paper concludes with a number of open problems., Comment: Replacement incorporating Amiri's theorem

The Near-Infrared Imager and Slitless Spectrograph (NIRISS) is the science module of the Canadian-built Fine Guidance Sensor (FGS) onboard the James Webb Space Telescope (JWST). NIRISS has four observing modes: 1) broadband imaging featuring seven of the eight NIRCam broadband filters, 2) wide-field slitless spectroscopy (WFSS) at a resolving power of $\sim$150 between 0.8 and 2.2 $\mu$m, 3) single-object cross-dispersed slitless spectroscopy (SOSS) enabling simultaneous wavelength coverage between 0.6 and 2.8 $\mu$m at R$\sim$700, a mode optimized for exoplanet spectroscopy of relatively bright ($J<6.3$) stars and 4) aperture masking interferometry (AMI) between 2.8 and 4.8 $\mu$m enabling high-contrast ($\sim10^{-3}-10^{-4}$) imaging at angular separations between 70 and 400 milliarcsec for relatively bright ($M<8$) sources. This paper presents an overview of the NIRISS instrument, its design, its scientific capabilities, and a summary of in-flight performance. NIRISS shows significantly better response shortward of $\sim2.5\,\mu$m resulting in 10-40% sensitivity improvement for broadband and low-resolution spectroscopy compared to pre-flight predictions. Two time-series observations performed during instrument commissioning in the SOSS mode yield very stable spectro-photometry performance within $\sim$10% of the expected noise. The first space-based companion detection of the tight binary star AB Dor AC through AMI was demonstrated.

Given a finite group $G$, the commuting graph of $G$ is the simple graph whose vertex set is $G$, and two distinct vertices are adjacent if they commute. In this paper, we classify all finite groups whose commuting graph is split and threshold. We also investigate the structure of a group whose commuting graph is either a cograph or a chordal graph, and determine all non-abelian finite simple groups whose commuting graph is a cograph. The results partly answer a question by Peter J. Cameron established in 2022 in his survey paper on graphs defined on groups., Comment: 26 pages

There has been a great deal of research on graphs defined on algebraic structures in the last two decades. In this paper we begin an exploration of hypergraphs defined on algebraic structures, especially groups, to investigate whether this can add a new perspective., Comment: 10 pages, 4 figures

A transitive permutation group $G$ on a finite set $\Omega$ is said to be pre-primitive if every $G$-invariant partition of $\Omega$ is the orbit partition of a subgroup of $G$. It follows that pre-primitivity and quasiprimitivity are logically independent (there are groups satisfying one but not the other) and their conjunction is equivalent to primitivity. Indeed, part of the motivation for studying pre-primitivity is to investigate the gap between primitivity and quasiprimitivity. We investigate the pre-primitivity of various classes of transitive groups including groups with regular normal subgroups, direct and wreath products, and diagonal groups. In the course of this investigation, we describe all $G$-invariant partitions for various classes of permutation groups $G$. We also look briefly at conditions similarly related to other pairs of conditions, including transitivity and quasiprimitivity, $k$-homogeneity and $k$-transitivity, and primitivity and synchronization., Comment: To appear in Journal of Algebra

If $G$ is a transitive group of degree $n$ having a string C-group of rank $r\geq (n+3)/2$, then $G$ is necessarily the symmetric group $S_n$. We prove that if $n$ is large enough, up to isomorphism and duality, the number of string C-groups of rank $r$ for $S_n$ (with $r\geq (n+3)/2$) is the same as the number of string C-groups of rank $r+1$ for $S_{n+1}$. This result and the tools used in its proof, in particular the rank and degree extension, imply that if one knows the string C-groups of rank $(n+3)/2$ for $S_n$ with $n$ odd, one can construct from them all string C-groups of rank $(n+3)/2+k$ for $S_{n+k}$ for any positive integer $k$. The classification of the string C-groups of rank $r\geq (n+3)/2$ for $S_n$ is thus reduced to classifying string C-groups of rank $r$ for $S_{2r-3}$. A consequence of this result is the complete classification of all string C-groups of $S_n$ with rank $n-\kappa$ for $\kappa\in\{1,\ldots,6\}$, when $n\geq 2\kappa+3$, which extends previously known results. The number of string C-groups of rank $n-\kappa$, with $n\geq 2\kappa +3$, of this classification gives the following sequence of integers indexed by $\kappa$ and starting at $\kappa = 1$: $$(1,1,7,9,35,48)$$ This sequence of integers is new according to the On-Line Encyclopedia of Integer Sequences. It will be available as sequence number A359367.

We consider all spanning trees of a complete simple graph $\Gamma$ on $n$ vertices that contain a given $m-$forest $F$. We show that the number of such spanning trees, $\tau(F)$, doesn't depend on the structure of $F$ and is completely determined by the number of vertices $q_i \, (i=1, ..., m)$ in each connected component of $F$. Specifically, $\tau(F) = q_1 q_2 \cdots q_m n^{m-2}$., Comment: Version 2, 3 pages

In this paper, nonzero component graphs and nonzero component union graphs of finite dimensional vector space are studied using the zero-divisor graph of specially constructed 0-1-distributive lattice and the zero-divisor graph of rings. Further, we define an equivalence relation on nonzero component graphs and nonzero component union graphs to deduce that these graphs are the graph join of zero-divisor graphs of Boolean algebras and complete graphs. In the last section, we characterize the perfect and chordal nonzero component graphs and nonzero component union graphs., Comment: arXiv admin note: text overlap with arXiv:2205.04916

In January 1969, Peter M. Neumann wrote a paper entitled "Primitive permutation groups of degree 3p". The main theorem placed restrictions on the parameters of a primitive but not 2-transitive permutation group of degree three times a prime. The paper was never published, and the results have been superseded by stronger theorems depending on the classification of the finite simple groups, for example a classification of primitive groups of odd degree. However, there are further reasons for being interested in this paper. First, it was written at a time when combinatorial techniques were being introduced into the theory of finite permutation groups, and the paper gives a very good summary and application of these techniques. Second, like its predecessor by Helmut Wielandt on primitive groups of degree 2p, it can be re-interpreted as a combinatorial result concerning association schemes whose common eigenspaces have dimensions of a rather limited form. This result uses neither the primality of p nor the existence of a permutation group related to the combinatorial structure. We extract these results and give details of the related combinatorics.

Let G be a finite group with identity e and H \neq \{e\} be a subgroup of G. The generalized non-coprime graph GAmma_{G,H} of G with respect to H is the simple undirected graph with G - \{e \}\) as the vertex set and two distinct vertices a and b are adjacent if and only if \gcd(|a|,|b|) \neq 1 and either a \in H or b \in H, where |a| is the order of a\in G. In this paper, we study certain graph theoretical properties of generalized non-coprime graphs of finite groups, concentrating on cyclic groups. More specifically, we obtain necessary and sufficient conditions for the generalized non-coprime graph of a cyclic group to be in the class of stars, paths, cycles, triangle-free, complete bipartite, complete, unicycle, split, claw-free, chordal or perfect graphs. Then we show that widening the class of groups to all finite nilpotent groups gives us no new graphs, but we give as an example of contrasting behaviour the class of EPPO groups (those in which all elements have prime power order). We conclude with a connection to the Gruenberg--Kegel graph.

The zero-divisor graph of a finite commutative ring with unity is the graph whose vertex set is the set of zero-divisors in the ring, with $a$ and $b$ adjacent if $ab=0$. We show that the class of zero-divisor graphs is universal, in the sense that every finite graph is isomorphic to an induced subgraph of a zero-divisor graph. This remains true for various restricted classes of rings, including boolean rings, products of fields, and local rings. But in more restricted classes, the zero-divisor graphs do not form a universal family. For example, the zero-divisor graph of a local ring whose maximal ideal is principal is a threshold graph; and every threshold graph is embeddable in the zero-divisor graph of such a ring. More generally, we give necessary and sufficient conditions on a non-local ring for which its zero-divisor graph to be a threshold graph. In addition, we show that there is a countable local ring whose zero-divisor graph embeds the Rado graph, and hence every finite or countable graph, as induced subgraph. Finally, we consider embeddings in related graphs such as the $2$-dimensional dot product graph.

The next generation of space-based mm-wave telescopes, such as JAXA's LiteBIRD mission, require focal planes with thousands of detectors in order to achieve their science goals. Digital frequency-domain multiplexing (dfmux) techniques allow detector counts to scale without a linear growth in wire harnessing, sub-Kelvin refrigerator loads, and other scaling problems. In this paper, we introduce Technology Readiness Level 5 (TRL5) electronics suitable for biasing and readout of LiteBIRD's Transition Edge Sensor (TES) bolometers using dfmux techniques. These electronics sit between the spacecraft's payload computer and the cryogenic focal plane, and provide detector biasing, tuning, and readout interfaces between these detectors and the spacecraft's on-board storage. We describe the overall architecture of the electronics, including functional decomposition into modules, the numerology and interconnection of these modules, and their internal and external interfaces. We describe performance measurements to date, including power consumption, thermal performance, and mass, volume, and reliability estimates. This paper is a companion piece to a description of the electronics' on-board Field-Programmable Gate Array (FPGA) firmware., Comment: SPIE Astronomical Telescopes + Instrumentation 2022, 10 pages

A graph is weakly perfect if its clique number and chromatic number are equal. We show that the enhanced power graph of a finite group $G$ is weakly perfect: its clique number and chromatic number are equal to the maximum order of an element of $G$. The proof requires a combinatorial lemma. We give some remarks about related graphs.

This paper characterizes the actual science performance of the James Webb Space Telescope (JWST), as determined from the six month commissioning period. We summarize the performance of the spacecraft, telescope, science instruments, and ground system, with an emphasis on differences from pre-launch expectations. Commissioning has made clear that JWST is fully capable of achieving the discoveries for which it was built. Moreover, almost across the board, the science performance of JWST is better than expected; in most cases, JWST will go deeper faster than expected. The telescope and instrument suite have demonstrated the sensitivity, stability, image quality, and spectral range that are necessary to transform our understanding of the cosmos through observations spanning from near-earth asteroids to the most distant galaxies., Comment: 5th version as accepted to PASP; 31 pages, 18 figures; https://iopscience.iop.org/article/10.1088/1538-3873/acb293

The difference graph $D(G)$ of a finite group $G$ is the difference of enhanced power graph of $G$ and power graph of $G$, with all isolated vertices are removed. In this paper we study the connectedness and perfectness of $D(G)$ with respect to various properties of the underlying group $G$. We also find several connection between the difference graph of $G$ and the Gruenberg-Kegel graph of $G$., Comment: 28 pages

In this paper we study the realizability question for commuting graphs of finite groups: Given an undirected graph $X$ is it the commuting graph of a group $G$? And if so, to determine such a group. We seek efficient algorithms for this problem. We make some general observations on this problem, and obtain a polynomial-time algorithm for the case of extraspecial groups.

We show that conformal geodesics on a Riemannian manifold cannot spiral: there does not exist a conformal geodesic which becomes trapped in every neighbourhood of a point., Comment: Final version. To appear in the Journal of Differential Geometry

We give examples of finite string $C$-groups (the automorphism groups of abstract regular polytopes) that have irreducible characters of real Schur index $2$. This answers a problem of Monson concerning these groups., Comment: 6 pages

We show that $(n+1)$-dimensional Myers-Perry metrics, $n\geq4$, have a conformal completion at spacelike infinity of $C^{n-3,1}$ differentiability class, and that the result is optimal in even spacetime dimensions. The associated asymptotic symmetries are presented.

In this paper we introduce the graph $\Gamma_{sc}(G)$ associated with a group $G$, called the solvable conjugacy class graph (abbreviated as SCC-graph), whose vertices are the nontrivial conjugacy classes of $G$ and two distinct conjugacy classes $C, D$ are adjacent if there exist $x \in C$ and $y \in D$ such that $\langle x, y\rangle$ is solvable. We discuss the connectivity, girth, clique number, and several other properties of the SCC-graph. One of our results asserts that there are only finitely many finite groups whose SCC-graph has given clique number~$d$, and we find explicitly the list of such groups with $d=2$.

Let $G$ be a finite group. A number of graphs with the vertex set $G$ have been studied, including the power graph, enhanced power graph, and commuting graph. These graphs form a hierarchy under the inclusion of edge sets, and it is useful to study them together. In addition, several authors have considered modifying the definition of these graphs by choosing a natural equivalence relation on the group such as equality, conjugacy, or equal orders, and joining two elements if there are elements in their equivalence class that are adjacent in the original graph. In this way, we enlarge the hierarchy into a second dimension. Using the three graph types and three equivalence relations mentioned gives nine graphs, of which in general only two coincide; we find conditions on the group for some other pairs to be equal. These often define interesting classes of groups, such as EPPO groups, $2$-Engel groups, and Dedekind groups. We study some properties of graphs in this new hierarchy. In particular, we characterize the groups for which the graphs are complete, and in most cases, we characterize the dominant vertices (those joined to all others). Also, we give some results about universality, perfectness, and clique number. The paper ends with some open problems and suggestions for further work.

Let $G$ be a finite abelian group, written additively, and $H$ a subgroup of~$G$. The \emph{subgroup sum graph} $\Gamma_{G,H}$ is the graph with vertex set $G$, in which two distinct vertices $x$ and $y$ are joined if $x+y\in H\setminus\{0\}$. These graphs form a fairly large class of Cayley sum graphs. Among cases which have been considered previously are the \emph{prime sum graphs}, in the case where $H=pG$ for some prime number $p$. In this paper we present their structure and a detailed analysis of their properties. We also consider the simpler graph $\Gamma^+_{G,H}$, which we refer to as the \emph{extended subgroup sum graph}, in which $x$ and $y$ are joined if $x+y\in H$: the subgroup sum is obtained by removing from this graph the partial matching of edges having the form $\{x,-x\}$ when $2x\ne0$. We study perfectness, clique number and independence number, connectedness, diameter, spectrum, and domination number of these graphs and their complements. We interpret our general results in detail in the prime sum graphs.

For a positive integer $n$, the full transformation semigroup $T_n$ consists of all self maps of the set $\{1,\ldots,n\}$ under composition. Any finite semigroup $S$ embeds in some $T_n$, and the least such $n$ is called the (minimum transformation) degree of $S$ and denoted $\mu(S)$. We find degrees for various classes of finite semigroups, including rectangular bands, rectangular groups and null semigroups. The formulae we give involve natural parameters associated to integer compositions. Our results on rectangular bands answer a question of Easdown from 1992, and our approach utilises some results of independent interest concerning partitions/colourings of hypergraphs. As an application, we prove some results on the degree of a variant $T_n^a$. (The variant $S^a=(S,\star)$ of a semigroup $S$, with respect to a fixed element $a\in S$, has underlying set $S$ and operation $x\star y=xay$.) It has been previously shown that $n\leq \mu(T_n^a)\leq 2n-r$ if the sandwich element $a$ has rank $r$, and the upper bound of $2n-r$ is known to be sharp if $r\geq n-1$. Here we show that $\mu(T_n^a)=2n-r$ for $r\geq n-6$. In stark contrast to this, when $r=1$, and the above inequality says $n\leq\mu(T_n^a)\leq 2n-1$, we show that $\mu(T_n^a)/n\to1$ and $\mu(T_n^a)-n\to\infty$ as $n\to\infty$. Among other results, we also classify the $3$-nilpotent subsemigroups of $T_n$, and calculate the maximum size of such a subsemigroup., Comment: V2 incorporates referee comments. To appear in Combinatorial Theory. 39 pages, 2 figures, 7 tables

The power graph $P(G)$ of a finite group $G$ is the undirected simple graph with vertex set $G$, where two elements are adjacent if one is a power of the other. In this paper, the matching numbers of power graphs of finite groups are investigated. We give upper and lower bounds, and conditions for the power graph of a group to possess a perfect matching. We give a formula for the matching number for any finite nilpotent group. In addition, using some elementary number theory, we show that the matching number of the enhanced power graph $P_e(G)$ of $G$ (in which two elements are adjacent if both are powers of a common element) is equal to that of the power graph of $G$.

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., Comment: 20 Pages

A spacetime satisfies the non-timelike boundary version of the Penrose property if the timelike future of any point on $\mathcal{I}^-$ contains the whole of $\mathcal{I}^+$. This property was first discussed for asymptotically flat spacetimes by Penrose, along with an equivalent definition (the finite version). In this paper we consider the Penrose property in greater generality. In particular we consider spacetimes with a non-zero cosmological constant and we note that the two versions of the property are no longer equivalent. In asymptotically AdS spacetimes it is necessary to re-state the property in a way which is more suited to spacetimes with a timelike boundary. We arrive at a property previously considered by Gao and Wald. Curiously, this property was shown to fail in spacetimes which focus null geodesics. This is in contrast to our findings in asymptotically flat and asymptotically de Sitter spacetimes. We then move on to consider some further example spacetimes (with zero cosmological constant) which highlight features of the Penrose property not previously considered. We discuss spacetimes which are the product of a Lorentzian and a compact Riemannian manifold. Perhaps surprisingly, we find that both versions of the Penrose property are satisfied in this product spacetime if and only if they are satisfied in the Lorentzian spacetime only. We also discuss the Ellis-Bronnikov wormhole (an example of a spacetime with more than one asymptotically flat end) and the Hayward metric (an example of a non-singular black hole spacetime).

These notes concern aspects of various graphs whose vertex set is a group $G$ and whose edges reflect group structure in some way (so that they are invariant under the action of the automorphism group of $G$). The graphs I will discuss are the power graph, enhanced power graph, deep commuting graph, commuting graph, and non-generating graph, though I give a briefer discussion of the nilpotence and solvability graphs, and make some remarks on more general graphs. Aspects to be discussed include induced subgraphs, forbidden subgraphs, connectedness, and automorphism groups. We can also ask about the graphs formed by the edges in one graph but not in an earlier graph in the hierarchy. I have included some results on intersection graphs of subgroups of various types, which are often in a dual relation to one of the other graphs considered. Another actor is the Gruenberg--Kegel graph, or prime graph, of a group: this very small graph influences various graphs defined on the group. I say little about Cayley graphs, since (except in special cases) these are not invariant under the automorphism group of $G$. The graphs all have the property that they contain \emph{twins}, pairs of vertices with the same neighbours (save possibly one another). Being equal or twins is an equivalence relation, and the automorphism group of the graph has a normal subgroup inducing the symmetric group on each twin class. For some purposes, we can merge twin vertices and get a smaller graph. Continuing until no further twins occur, the result is independent of the reduction, and is the $1$-vertex graph if and only if the original graph is a \emph{cograph}. So I devote a section to cographs and twin reduction, and another to consequences for automorphism groups. There are briefer discussions of related matters.

According to the O'Nan--Scott Theorem, a finite primitive permutation group either preserves a structure of one of three types (affine space, Cartesian lattice, or diagonal semilattice), or is almost simple. However, diagonal groups are a much larger class than those occurring in this theorem. For any positive integer $m$ and group $G$ (finite or infinite), there is a diagonal semilattice, a sub-semilattice of the lattice of partitions of a set $\Omega$, whose automorphism group is the corresponding diagonal group. Moreover, there is a graph (the diagonal graph), bearing much the same relation to the diagonal semilattice and group as the Hamming graph does to the Cartesian lattice and the wreath product of symmetric groups. Our purpose here, after a brief introduction to this semilattice and graph, is to establish some properties of this graph. The diagonal graph $\Gamma_D(G,m)$ is a Cayley graph for the group~$G^m$, and so is vertex-transitive. We establish its clique number in general and its chromatic number in most cases, with a conjecture about the chromatic number in the remaining cases. We compute the spectrum of the adjacency matrix of the graph, using a calculation of the M\"obius function of the diagonal semilattice. We also compute some other graph parameters and symmetry properties of the graph. We believe that this family of graphs will play a significant role in algebraic graph theory.

I give an elementary proof that a quasi-symmetric design without repeated blocks on $v$ points has at most $v\choose2$ blocks, with equality if and only if it is a tight $4$-design.

The purpose of this note is to define a graph whose vertex set is a finite group $G$, whose edge set is contained in that of the commuting graph of $G$ and contains the enhanced power graph of $G$. We call this graph the deep commuting graph of $G$. Two elements of $G$ are joined in the deep commuting graph if and only if their inverse images in every central extension of $G$ commute. We give conditions for the graph to be equal to either of the enhanced power graph and the commuting graph, and show that the automorphism group of $G$ acts as automorphisms of the deep commuting graph.

The Gruenberg-Kegel graph $\Gamma(G)$ associated with a finite group $G$ has as vertices the prime divisors of $|G|$, with an edge from $p$ to $q$ if and only if $G$ contains an element of order $pq$. This graph has been the subject of much recent interest; one of our goals here is to give a survey of some of this material, relating to groups with the same Gruenberg-Kegel graph. However, our main aim is to prove several new results. Among them are the following. - There are infinitely many finite groups with the same Gruenberg-Kegel graph as the Gruenberg-Kegel of a finite group $G$ if and only if there is a finite group $H$ with non-trivial solvable radical such that $\Gamma(G)=\Gamma(H)$. - There is a function $F$ on the natural numbers with the property that if a finite $n$-vertex graph whose vertices are labelled by pairwise distinct primes is the Gruenberg-Kegel graph of more than $F(n)$ finite groups, then it is the Gruenberg-Kegel graph of infinitely many finite groups. (The function we give satisfies $F(n)=O(n^7)$, but this is probably not best possible.) - If a finite graph $\Gamma$ whose vertices are labelled by pairwise distinct primes is the Gruenberg-Kegel graph of only finitely many finite groups, then all such groups are almost simple; moreover, $\Gamma$ has at least three pairwise non-adjacent vertices, and $2$ is non-adjacent to at least one odd vertex. - Groups whose power graphs, or commuting graphs, are isomorphic have the same Gruenberg-Kegel graph. - The groups ${^2}G_2(27)$ and $E_8(2)$ are uniquely determined by the isomorphism types of their Gruenberg-Kegel graphs. In addition, we consider groups whose Gruenberg-Kegel graph has no edges. These are the groups in which every element has prime power order, and have been studied under the name \emph{EPPO groups}; completing this line of research, we give a complete list of such groups., Comment: 32 pages

In an earlier paper by three of the present authors and Csaba Schneider, it was shown that, for $m\ge2$, a set of $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$), 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$ partitions with $r\geq 2$, any $m$ of which are minimal elements of a Cartesian lattice. If $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$, things are more restricted. Any $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. Under this hypothesis, such a 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$ in the $(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.

Let $T$ be a tree on $n$ vertices. We can regard the edges of $T$ as transpositions of the vertex set; their product (in any order) is a cyclic permutation. All possible cyclic permutations arise (each exactly once) if and only if the tree is a star. In this paper we find the number of realised cycles, and obtain some results on the number of realisations of each cycle, for other trees. We also solve the inverse problem of the number of trees which give rise to a given cycle. On the way, we meet some familiar number sequences including the Euler and Fuss--Catalan numbers., Comment: 34 pages, 7 figures and 1 table