Characterization of reducible hexagons and fast decomposition of elementary benzenoid graphs

A benzenoid graph is a finite connected plane graph with no cut vertices in which every interior region is bounded by a regular hexagon of a side length one. A benzenoid graph G is elementary if every edge belongs to a 1-factor of G. A hexagon h of an elementary benzenoid graph is reducible, if the removal of boundary edges and vertices of h results in an elementary benzenoid graph. We characterize the reducible hexagons of an elementary benzenoid graph. The characterization is the basis for an algorithm which finds the sequence of reducible hexagons that decompose a graph of this class in O(n²) time. Moreover, we present an algorithm which decomposes an elementary benzenoid graph with at most one pericondensed component in linear time.     

Path factors and parallel knock-out schemes of almost claw-free graphs

An H₁,{H₂}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H₁ and all other components (if there are any) isomorphic to the graph H₂. We completely characterise the class of connected almost claw-free graphs that have a P₇,{P₂}-factor, where P₇ and P₂ denote the paths on seven and two vertices, respectively. We apply this result to parallel knock-out schemes for almost claw-free graphs. These schemes proceed in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is reducible if such a scheme eliminates every vertex in the graph. Using our characterisation, we are able to classify all reducible almost claw-free graphs, and we can show that every reducible almost claw-free graph is reducible in at most two rounds. This leads to a quadratic time algorithm for determining if an almost claw-free graph is reducible (which is a generalisation and improvement upon the previous strongest result that showed that there was a O(n^5.376) time algorithm for claw-free graphs on n vertices).     

The transvection free groups with polynomial rings of invariants

Let G be a finite linear group containing no transvections. This paper proves that the ring of invariants of G is polynomial if and only if the pointwise stabilizer in G of any subspace is generated by pseudoreflections. Kemper and Malle used the classification of finite irreducible groups generated by pseudoreflections to prove the irreducible case in arbitrary characteristic. We extend their result to the reducible case.     

A geometric approach to complete reducibility

Let G be a connected reductive linear algebraic group. We use geometric methods to investigate G-completely reducible subgroups of G, giving new criteria for G-complete reducibility. We show that a subgroup of G is G-completely reducible if and only if it is strongly reductive in G; this allows us to use ideas of R.W. Richardson and Hilbert–Mumford–Kempf from geometric invariant theory. We deduce that a normal subgroup of a G-completely reducible subgroup of G is again G-completely reducible, thereby providing an affirmative answer to a question posed by J.-P. Serre, and conversely we prove that the normalizer of a G-completely reducible subgroup of G is again G-completely reducible. Some rationality questions and applications to the spherical building of G are considered. Many of our results extend to the case of non-connected G. Mathematics Subject Classification (2000) 20G15, 14L24, 20E42     

The number of spanning trees of plane graphs with reflective symmetry

A plane graph is called symmetric if it is invariant under the reflection across some straight line (called symmetry axis). Let G be a symmetric plane graph. We prove that if there is no edge in G intersected by its symmetry axis then the number of spanning trees of G can be expressed in terms of the product of the number of spanning trees of two smaller graphs, each of which has about half the number of vertices of G.     

The Complete Reducibility of Locally Completely Reducible Finitary Linear Groups

Let V be a vector space over some division ring D, and G a finitarysubgroup of GL(V). If G is locally completely reducible, thenthe D-G modules V, [V, G] and V/C_V(G) need not be completelyreducible, even if dim_DV is finite. Moreover, if F is a field,then V and V/C_V(G) need not be completely reducible. We provehere that if D is a finite-dimensional division algebra andG is locally completely reducible, then [V, G] is always a completelyreducible D-G module. 1991 Mathematics Subject Classification20H25.     

Abelian quotients and orbit sizes of solvable linear groups

Let G be a finite group, and let V be a completely reducible faithful Gmodule. It has been known for a long time that if G is abelian, then G has a regular orbit on V. In this paper we generalize this result as follows. Assuming G to be solvable, we show that G has an orbit of size at least |G/G′| on V. This also strengthens a result of Aschbacher and Guralnick in that situation. Additionally, we prove a similar generalization of the well-known result that if G is nilpotent, then G has an orbit of size at least \(\sqrt {\left| G \right|} \) on V.     

Isomorphisms,automorphisms, and generalized involution models of projective reflection groups

We investigate the generalized involution models of the projective reflection groups G(r, p, q, n). This family of groups parametrizes all quotients of the complex reflection groups G(r, p, n) by scalar subgroups. Our classification is ultimately incomplete, but we provide several necessary and sufficient conditions for generalized involution models to exist in various cases. In the process we solve several intermediate problems concerning the structure of projective reflection groups. We derive a simple criterion for determining whether two groups G(r, p, q, n) and G(r, p′, q′, n) are isomorphic. We also describe explicitly the form of all automorphisms of G(r, p, q, n), outside a finite list of exceptional cases. Building on prior work, this allows us to prove that G(r, p, 1, n) has a generalized involution model if and only if G(r, p, 1, n) ≌ G(r, 1, p, n). We also classify which groups G(r, p, q, n) have generalized involution models when n = 2, or q is odd, or n is odd.     

Reducible subgroups of exceptional algebraic groups

Let G be a simple algebraic group over an algebraically closed field. A closed subgroup H of G is called G-completely reducible (G-cr) if, whenever H is contained in a parabolic subgroup P of G, it is contained in a Levi factor of P. In this paper we complete the classification of connected G-cr subgroups when G has exceptional type, by determining the $L_0$-irreducible connected reductive subgroups for each simple classical factor $L_0$ of a Levi subgroup of G. As an illustration, we determine all reducible, G-cr semisimple subgroups when G has type $F_4$ and various properties thereof. This work complements results of Lawther, Liebeck, Seitz and Testerman, and is vital in classifying non-G-cr reductive subgroups, a project being undertaken by the authors elsewhere.     

Complete reducibility of subgroups of reductive algebraic groups over nonperfect fields II

Let k be a separably closed field. Let G be a reductive algebraic k-group. We study Serre’s notion of complete reducibility of subgroups of G over k. In particular, using the recently proved center conjecture of Tits, we show that the centralizer of a k-subgroup H of G is G-completely reducible over k if it is reductive and H is G-completely reducible over k. We show that a regular reductive k-subgroup of G is G-completely reducible over k. We present examples where the number of overgroups of irreducible subgroups and the number of G(k)-conjugacy classes of k-anisotropic unipotent elements are infinite.     

Super-connected edge transitive graphs

A graph G is said to be super-connected if any minimum cut of G isolates a vertex. In a previous work due to the second author of this note, super-connected graphs which are both vertex transitive and edge transitive are characterized. In this note, we generalize the characterization to edge transitive graphs which are not necessarily vertex transitive, showing that the only irreducible edge transitive graphs which are not super-connected are the cycles C_n(n?6) and the line graph of the 3-cube, where irreducible means the graph has no vertices with the same neighbor set. Furthermore, we give some sufficient conditions for reducible edge transitive graphs to be super-connected.     

Countable sequenceable groups

A finite group G having n elements is said to be sequenceable if there exists an arrangement b₁, b₂…,b_n of its elements such that b₁, b₁b₂,…, b₁b₂? b₁ is also an arrangement of the elements of G. This definition can be extended to the case when G is countably infinite by requiring the existence of a sequence b₁, b₂,…, containing each element of G exactly once, such that the sequence b₁,b₁b₂,… also contains each element of G exactly once. With this definition every countably-infinite group is sequenceable.     

Reducibility number

Let P be a poset in a class of posets P. A smallest positive integer r is called reducibility number of P with respect to P if there exists a non-empty subset S of P with |S|=r and P-S∈P. The reducibility numbers for the power set 2ⁿ of an n-set (n?2) with respect to the classes of distributive lattices, modular lattices and Boolean lattices are calculated. Also, it is shown that the reducibility number r of the lattice of all subgroups of a finite group G with respect to the class of all distributive lattices is 1 if and only if the order of G has at most two distinct prime divisors; further if r is a prime number then order of G is divisible by exactly three distinct primes. The class of pseudo-complemented u-posets is shown to be reducible. Deletable elements in semidistributive posets are characterized.     

A user friendly proof of Nagata's characterization of linearly reductive groups in positive characteristics

Let K be an algebraically closed field of positive characteristic p, and G be a linear algebraic group over K. We give a user friendly proof of Nagata's theorem that every finite-dimensional rational representation of G is completely reducible if and only if the connected component G ⁰ is a torus and p does not divide the index (G?:?G ⁰).     

On reduction of p-groups

We define the notion of irreducibility of a pgroup and show how any pgroup G can be reduced to an irreducible group H. We show that G is realizable as the Galois group of a regular extension of Q(T) if H is. Finally, we give some sufficient conditions on the

number of generators of a pgroup and the structure of its Frattini subgroup for it to be reducible to the trivial group.     

Equicontinuity and balanced topological groups

It was proved by V.G. Pestov in 1988 that a locally compact group G is balanced if and only if any countable subset of G is thin in G. This unexpected result was obtained by using a non-elementary transfinite induction involving properties of infinite ordinals. In the present work, this result is reconsidered in a more general context by using an approach which is comparable, in spirit, to Pestov's, but uses a notably simplified technique. Let X be a topological space, Y a uniform space and $\text{H}$ a set of continuous mappings of X into Y. First, new conditions concerning X are given under which $\text{H}$ is equicontinuous provided its countable subsets are. Next, X and Y are supposed equal to a topological group equipped with its right uniform structure, and the set $\text{H}$ taken into account is the group of all its inner automorphisms. We then obtain theorems such as the following which includes, as a special case, Pestov's result: Let G be a topological group; let us suppose that the space G is strongly functionally generated by the set of all its subspaces of countable o-tightness; then G is balanced if and only if any right uniformly discrete countable subset of G is thin in G. As an application, it is proved that if G satisfies the above hypothesis and is non-Archimedean, then G is balanced if and only if G is strongly functionally balanced.     

Coprime subdegrees for primitive permutation groups and completely reducible linear groups

In this paper we answer a question of Gabriel Navarro about orbit sizes of a finite linear group H ? GL(V) acting completely reducibly on a vector space V: if the H-orbits containing the vectors a and b have coprime lengths m and n, we prove that the H-orbit containing a + b has length mn. Such groups H are always reducible if n,m > 1. In fact, if H is an irreducible linear group, we show that, for every pair of non-zero vectors, their orbit lengths have a non-trivial common factor. In the more general context of finite primitive permutation groups G, we show that coprime non-identity subdegrees are possible if and only if G is of O’Nan-Scott type AS, PA or TW. In a forthcoming paper we will show that, for a finite primitive permutation group, a set of pairwise coprime subdegrees has size at most 2. Finally, as an application of our results, we prove that a field has at most 2 finite extensions of pairwise coprime indices with the same normal closure.     

Upper Bound on the Diameter of a Domination Dot-Critical Graph

A vertex of a graph is called critical if its deletion decreases the domination number, and an edge is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. In this paper, we show that if G is a connected dot-critical graph with domination number k??? 3 and diameter d and if G has no critical vertices, then d??? 2k?3.     

Invariant theory and eigenspaces for unitary reflection groups

We prove some variations of formulas of Orlik and Solomon in the invariant theory of finite unitary reflection groups, and use them to give elementary and case-free proofs of some results of Lehrer and Springer, in particular that an integer is regular for a reflection group G if and only if it divides the same number of degrees and codegrees. To cite this article: G.I. Lehrer, J. Michel, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Coleman automorphisms of holomorphs of completely reducible and almost simple groups

Let H be the holomorph of a finite group G. It is proved that every Coleman automorphism of H is inner whenever G is either completely reducible or almost simple; in particular, this is the case when G is either characteristically simple or simple. As an application, we obtain the normalizer the conjecture holds for integral group rings of holomorphs of such groups in question.