Orbit equivalence and permutation groups defined by unordered relations

For a set Ω an unordered relation on Ω is a family R of subsets of Ω. If R is such a relation we let G(R)\mathcal{G}(R) be the group of all permutations on Ω that preserve R, that is g belongs to G(R)\mathcal{G}(R) if and only if x∈R implies x ^g ∈R. We are interested in permutation groups which can be represented as G=G(R)G=\mathcal{G}(R) for a suitable unordered relation R on Ω. When this is the case, we say that G is defined by the relation R, or that G is a relation group. We prove that a primitive permutation group ≠Alt(Ω) and of degree ≥11 is a relation group. The same is true for many classes of finite imprimitive groups, and we give general conditions on the size of blocks of imprimitivity, and the groups induced on such blocks, which guarantee that the group is defined by a relation.     

Adjoint bi-continuous semigroups and semigroups on the space of measures

For a given bi-continuous semigroup (T(t)) _t⩾0 on a Banach space X we define its adjoint on an appropriate closed subspace X° of the norm dual X′. Under some abstract conditions this adjoint semigroup is again bi-continuous with respect to the weak topology σ(X°,X). We give the following application: For Ω a Polish space we consider operator semigroups on the space C_b(Ω) of bounded, continuous functions (endowed with the compact-open topology) and on the space M(Ω) of bounded Baire measures (endowed with the weak*-topology). We show that bi-continuous semigroups on M(Ω) are precisely those that are adjoints of bi-continuous semigroups on C_b(Ω). We also prove that the class of bi-continuous semigroups on C_b(ω) with respect to the compact-open topology coincides with the class of equicontinuous semigroups with respect to the strict topology. In general, if is not a Polish space this is not the case.     

Erd?s-Ko-Rado theorem for irreducible imprimitive reflection groups

Let Ω be a finite set, and let G be a permutation group on Ω. A subset H of G is called intersecting if for any σ, π ∈ H, they agree on at least one point. We show that a maximal intersecting subset of an irreducible imprimitive reflection group G(m, p, n) is a coset of the stabilizer of a point in {1, …, n} provided n is sufficiently large.     

Conjugation of injections by permutations

Let Ω be a countably infinite set, Inj(Ω) the monoid of all injective endomaps of Ω, and Sym(Ω) the group of all permutations of Ω. Also, let f,g,h∈Inj(Ω) be any three maps, each having at least one infinite cycle. (For instance, this holds if f,g,h∈Inj(Ω)∖Sym(Ω).) We show that there are permutations a,b∈Sym(Ω) such that h=afa ⁻¹ bgb ⁻¹ if and only if |Ω∖(Ω)f|+|Ω∖(Ω)g|=|Ω∖(Ω)h|. We also prove a generalization of this statement that holds for infinite sets Ω that are not necessarily countable.     

Real loci of based loop groups

Let (G, K) be a Riemannian symmetric pair of maximal rank, where G is a compact simply connected Lie group and K is the fixed point set of an involutive automorphism σ. This induces an involutive automorphism τ of the based loop space Ω(G). There exists a maximal torus T ⊂ G such that the canonical action of T × S ¹ on Ω(G) is compatible with τ (in the sense of Duistermaat). This allows us to formulate and prove a version of Duistermaat’s convexity theorem. Namely, the images of Ω(G) and Ω(G) ^τ (fixed point set of τ) under the T × S ¹ moment map on Ω(G) are equal. The space Ω(G) ^τ is homotopy equivalent to the loop space Ω(G/K) of the Riemannian symmetric space G/K. We prove a stronger form of a result of Bott and Samelson which relates the cohomology rings with coefficients in \mathbbZ₂ {\mathbb{Z}_2} of Ω(G) and Ω(G/K). Namely, the two cohomology rings are isomorphic, by a degree-halving isomorphism (Bott and Samelson [BS] had proved that the Betti numbers are equal). A version of this theorem involving equivariant cohomology is also proved. The proof uses the notion of conjugation space in the sense of Hausmann, Holm, and Puppe [HHP].     

Undirected power graphs of semigroups

The undirected power graph G(S) of a semigroup S is an undirected graph whose vertex set is S and two vertices a,b∈S are adjacent if and only if a≠b and a ^m =b or b ^m =a for some positive integer m. In this paper we characterize the class of semigroups S for which G(S) is connected or complete. As a consequence we prove that G(G) is connected for any finite group G and G(G) is complete if and only if G is a cyclic group of order 1 or p ^m . Particular attention is given to the multiplicative semigroup ℤ _n and its subgroup U _n , where G(U _n ) is a major component of G(ℤ _n ). It is proved that G(U _n ) is complete if and only if n=1,2,4,p or 2p, where p is a Fermat prime. In general, we compute the number of edges of G(G) for a finite group G and apply this result to determine the values of n for which G(U _n ) is planar. Finally we show that for any cyclic group of order greater than or equal to 3, G(G) is Hamiltonian and list some values of n for which G(U _n ) has no Hamiltonian cycle.     

Torsion in Boundary Coinvariants and K -Theory for Affine Buildings

Let (G, I, N, S) be an affine topological Tits system, and let Γ be a torsion-free cocompact lattice in G. This article studies the coinvariants H ₀(Γ; C(Ω,Z)), where Ω is the Furstenberg boundary of G. It is shown that the class [1] of the identity function in H ₀(Γ; C(Ω, Z)) has finite order, with explicit bounds for the order. A similar statement applies to the K ₀ group of the boundary crossed product C ^*-algebra C(Ω)Γ. If the Tits system has type ? ₂, exact computations are given, both for the crossed product algebra and for the reduced group C ^*-algebra.     

The Sigma Chromatic Number of a Graph

For a nontrivial connected graph G, let ${c: V(G)\to {{\mathbb N}}}For a nontrivial connected graph G, let c: V(G)? \mathbb N{c: V(G)\to {{\mathbb N}}} be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.     

Optimal Subgroups and Applications to Nilpotent Elements

Let G be a reductive group acting on an affine variety X, let x ∈ X be a point whose G-orbit is not closed, and let S be a G-stable closed subvariety of X which meets the closure of the G-orbit of x but does not contain x. In this paper we study G. R. Kempf’s optimal class Ω _G (x; S) of cocharacters of G attached to the point x; in particular, we consider how this optimality transfers to subgroups of G. Suppose K is a G-completely reducible subgroup of G which fixes x, and let H = C _G (K)⁰. Our main result says that the H-orbit of x is also not closed, and the optimal class Ω _H (x; S) for H simply consists of the cocharacters in Ω _G (x; S) which evaluate in H. We apply this result in the case that G acts on its Lie algebra via the adjoint representation to obtain some new information about cocharacters associated with nilpotent elements in good characteristic.     

The chromatic number of the product of two 4-chromatic graphs is 4

For any graphG and numbern≧1 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) ≠g(b). The graph of all such functions is the colouring graph ℒ(G) ofG. We establish first that χ(G)=n+1 implies χ(ℒ(G))=n iff χ(G ×H)=n+1 for all graphsH with χ(H)≧n+1. Then we will prove that indeed for all 4-chromatic graphsG χ(ℒ(G))=3 which establishes Hedetniemi’s [3] conjecture for 4-chromatic graphs. This research was supported by NSERC grant A7213     

Central extensions of current groups

 In this paper we study central extensions of the identity component G of the Lie group C ^∞ (M,K) of smooth maps from a compact manifold M into a Lie group K which might be infinite-dimensional. We restrict our attention to Lie algebra cocycles of the form ω(ξ,η)=[κ(ξ,dη)], where κ:𝔨×𝔨→Y is a symmetric invariant bilinear map on the Lie algebra 𝔨 of K and the values of ω lie in Ω¹(M,Y)/dC ^∞ (M,Y). For such cocycles we show that a corresponding central Lie group extension exists if and only if this is the case for M=𝕊¹. If K is finite-dimensional semisimple, this implies the existence of a universal central Lie group extension of G. The groups Diff(M) and C ^∞ (M,K) act naturally on G by automorphisms. We also show that these smooth actions can be lifted to smooth actions on the central extension if it also is a central extension of the universal covering group G˜ of G. Received: 11 April 2002 / Revised version: 28 August 2002 / Published online: 28 March 2003     

Movement of Intransitive Permutation Groups Having Maximum Degree

Let G be a permutation group on a set Ω with no fixed points in,and m be a positive integer.Then the movement of G is defined as move(G):=sup Γ {|Γg\Γ| | g ∈ G}.It was shown by Praeger that if move(G) = m,then |Ω| 3m + t-1,where t is the number of G-orbits on.In this paper,all intransitive permutation groups with degree 3m+t-1 which have maximum bound are classified.Indeed,a positive answer to her question that whether the upper bound |Ω| = 3m + t-1 for |Ω| is sharp for every t > 1 is given.     

Proprietes generiques de processus croises

LetS _φ be the skew product transformation(x, g)↦(Sx, gφ(x)) defined on Ω×G, where Ω is a compact metric space,G a compact metric group with its Haar measureh. IfS is a μ-continuous transformation where μ is a Borel measure on Ω, ergodic with respect toS, we study the setE ₀ of μ-continuous applications φ:Ω→G such that μ⩀h is ergodic (with respect toS _φ). For example,E ₀ is residual in the group of μ-continuous applications from Ω toG with the uniform convergence topology. We also study the weakly mixing case. Some arithmetic applications are given.     

Irreducibility and Mixed Boundary Conditions

In this paper we consider positive semigroups on L^p(Ω) generated by elliptic operators A subject to mixed Dirichlet-Neumann boundary conditions on non-smooth domains Ω. We show in particular that these semigroups as well as those generated by multiplicative perturbations bA of A are irreducible, provided b ∈ L^∞(Ω) is real and satisfies b ≥ δ for some δ > 0. In memoriam Helmut H. Schaefer     

Alternating and Sporadic Simple Groups are Determined by Their Character Degrees

Let G be a finite group. Denote by Irr(G) the set of all irreducible complex characters of G. Let cd(G) be the set of all irreducible complex character degrees of G forgetting multiplicities, that is, cd(G) = {χ(1) : χ ∈ Irr(G)} and let cd ^*(G) be the set of all irreducible complex character degrees of G counting multiplicities. Let H be an alternating group of degree at least 5, a sporadic simple group or the Tits group. In this paper, we will show that if G is a non-abelian simple group and cd(G) í cd(H)cd(G)\subseteq cd(H) then G must be isomorphic to H. As a consequence, we show that if G is a finite group with cd^*(G) í cd^*(H)cd^*(G)\subseteq cd^*(H) then G is isomorphic to H. This gives a positive answer to Question 11.8 (a) in (Unsolved problems in group theory: the Kourovka notebook, 16th edn) for alternating groups, sporadic simple groups or the Tits group.     

On finite simple groups and Kneser graphs

For a finite group G let Γ(G) be the (simple) graph defined on the elements of G with an edge between two (distinct) vertices if and only if they generate G. The chromatic number of Γ(G) is considered for various non-solvable groups G.     

On the prime graph of <Emphasis Type="Italic">PSL</Emphasis>(2, <Emphasis Type="Italic">p</Emphasis>) where <Emphasis Type="Italic">p</Emphasis> > 3 is a prime number

Let G be a finite group. We define the prime graph Γ(G) as follows. The vertices of Γ(G) are the primes dividing the order of G and two distinct vertices p, q are joined by an edge if there is an element in G of order pq. Recently M. Hagie [5] determined finite groups G satisfying Γ(G) = Γ(S), where S is a sporadic simple group. Let p > 3 be a prime number. In this paper we determine finite groups G such that Γ(G) = Γ(PSL(2, p)). As a consequence of our results we prove that if p > 11 is a prime number and p ≢ 1 (mod 12), then PSL(2, p) is uniquely determined by its prime graph and so these groups are characterizable by their prime graph. The third author was supported in part by a grant from IPM (No. 84200024).     

Acyclic edge colorings of planar graphs and seriesparallel graphs

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1. This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation of Shandong Province (Grant No. Y2008A20).     

On Two Theorems of Finite Solvable Groups

For a finite group G, let T（G） denote a set of primes such that a prime p belongs to T（G） if and only if p is a divisor of the index of some maximal subgroup of G. It is proved that if G satisfies any one of the following conditions： （1） G has a p-complement for each p∈T（G）; （2）│T（G）│= 2： （3） the normalizer of a Sylow p-subgroup of G has prime power index for each odd prime p∈T（G）; then G either is solvable or G/Sol（G）≌PSL（2, 7） where Sol（G） is the largest solvable normal subgroup of G.     

When do random subsets decompose a finite group?

Let A, B be two random subsets of a finite group G. We consider the event that the products of elements from A and B span the whole group, i.e. [AB ∪ BA = G]. The study of this event gives rise to a group invariant we call Θ(G). Θ(G) is between 1/2 and 1, and is 1 if and only if the group is abelian. We show that a phase transition occurs as the size of A and B passes √Θ(G)|G| log |G|; i.e. for any ɛ > 0, if the size of A and B is less than (1 − ɛ)√Θ(G)|G| log |G|, then with high probability AB ∪ BA ≠ G. If A and B are larger than (1 + ɛ)√Θ(G)|G| log |G|, then AB ∪ BA = G with high probability.