Some results on minimal sumset sizes in finite non-abelian groups

Let G be a group. We study the minimal sumset (or product set) size μG(r,s)=min{|A⋅B|}, where A,B range over all subsets of G with cardinality r,s respectively. The function μG has recently been fully determined in [S. Eliahou, M. Kervaire, A. Plagne, Optimally small sumsets in finite abelian groups, J. Number Theory 101 (2003) 338-348; S. Eliahou, M. Kervaire, Minimal sumsets in infinite abelian groups, J. Algebra 287 (2005) 449-457] for G abelian. Here we focus on the largely open case where G is finite non-abelian. We obtain results on μG(r,s) in certain ranges for r and s, for instance when r?3 or when r+s?|G|−1, and under some more technical conditions. (See Theorem 4.4.) We also compute μG for a few non-abelian groups of small order. These results extend the Cauchy-Davenport theorem, which determines μG(r,s) for G a cyclic group of prime order.     

Minimum product set sizes in nonabelian groups of order pq

Let G be a nonabelian group of order pq, where p and q are distinct odd primes. We analyze the minimum product set cardinality μG(r,s)=min|AB|, where A and B range over all subsets of G of cardinalities r and s, respectively. In this paper, we completely determine μG(r,s) in the case where G has order 3p and conjecture that this result can be extended to all nonabelian groups of order pq. We also prove that for every nonabelian group of order pq there exist 1?r,s?pq such that μG(r,s)>μZ/pqZ(r,s).     

Artin's L-functions and one-dimensional characters

Let K/Q be a finite Galois extension with the Galois group G, let χ₁,…,χr be the irreducible non-trivial characters of G, and let A be the C-algebra generated by the Artin L-functions L(s,χ₁),…,L(s,χr). Let B be the subalgebra of A generated by the L-functions corresponding to induced characters of non-trivial one-dimensional characters of subgroups of G. We prove: (1) B is of Krull dimension r and has the same quotient field as A; (2) B=A iff G is M-group; (3) the integral closure of B in A equals A iff G is quasi-M-group.     

The game of arboricity

Using a fixed set of colors C, Ann and Ben color the edges of a graph G so that no monochromatic cycle may appear. Ann wins if all edges of G have been colored, while Ben wins if completing a coloring is not possible. The minimum size of C for which Ann has a winning strategy is called the game arboricity of G, denoted by A_g(G). We prove that A_g(G)?3k for any graph G of arboricity k, and that there are graphs such that A_g(G)?2k-2. The upper bound is achieved by a suitable version of the activation strategy, used earlier for the vertex coloring game. We also provide two other strategies based on induction and acyclic colorings.     

Representations and cohomology for Frobenius-Lusztig kernels

Let U_ζ be the quantum group (Lusztig form) associated to the simple Lie algebra g, with parameter ζ specialized to an ?-th root of unity in a field of characteristic p>0. In this paper we study certain finite-dimensional normal Hopf subalgebras U_ζ(G_r) of U_ζ, called Frobenius-Lusztig kernels, which generalize the Frobenius kernels G_r of an algebraic group G. When r=0, the algebras studied here reduce to the small quantum group introduced by Lusztig. We classify the irreducible U_ζ(G_r)-modules and discuss their characters. We then study the cohomology rings for the Frobenius-Lusztig kernels and for certain nilpotent and Borel subalgebras corresponding to unipotent and Borel subgroups of G. We prove that the cohomology ring for the first Frobenius-Lusztig kernel is finitely-generated when g has type A or D, and that the cohomology rings for the nilpotent and Borel subalgebras are finitely-generated in general.     

Integral trees of diameter 6

A graph G is called integral if all eigenvalues of its adjacency matrix A(G) are integers. In this paper, the trees T(p,q)•T(r,m,t) and K_1,s•T(p,q)•T(r,m,t) of diameter 6 are defined. We determine their characteristic polynomials. We also obtain for the first time sufficient and conditions for them to be integral. To do so, we use number theory and apply a computer search. New families of integral trees of diameter 6 are presented. Some of these classes are infinite. They are different from those in the existing literature. We also prove that the problem of finding integral trees of diameter 6 is equivalent to the problem of solving some Diophantine equations. We give a positive answer to a question of Wang et al. [Families of integral trees with diameters 4, 6 and 8, Discrete Appl. Math. 136 (2004) 349-362].     

Minimal sumsets in finite solvable groups

Given a group G and positive integers r,s≤|G|, we denote by μ_G(r,s) the least possible size of a product set AB={ab∣a∈A,b∈B}, where A,B run over all subsets of G of size r,s, respectively. While the function μ_G is completely known when G is abelian [S. Eliahou, M. Kervaire, Minimal sumsets in infinite abelian groups, Journal of Algebra 287 (2005) 449-457], it is largely unknown for G non-abelian, in part because efficient tools for proving lower bounds on μ_G are still lacking in that case. Our main result here is a lower bound on μ_G for finite solvable groups, obtained by building it up from the abelian case with suitable combinatorial arguments. The result may be summarized as follows: if G is finite solvable of order m, then μ_G(r,s)≥μ_G^′(r,s), where G^′ is any abelian group of the same order m. Equivalently, with our knowledge of μ_G^′, our formula reads .One nice application is the full determination of the function μ_G for the dihedral group G=D_n and all n≥1. Up to now, only the case where n is a prime power was known. We prove that, for all n≥1, the group D_n has the same μ-function as an abelian group of order |D_n|=2n.     

Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?_u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph.     

Metrizable refinements of group topologies and the pseudo-intersection number

The pseudo-intersection number, denoted p, is the minimum cardinality of a family A⊆P(ω) having the strong finite intersection property but no infinite pseudo-intersection. For every countable topologizable group G, let pG denote the minimum character of a nondiscrete Hausdorff group topology on G which cannot be refined to a nondiscrete metrizable group topology. We show that pG=p.     

Group algebra series and coboundary modules

The shift action on the 2-cocycle group Z²(G,C) of a finite group G with coefficients in a finitely generated abelian group C has several useful applications in combinatorics and digital communications, arising from the invariance of a uniform distribution property of cocycles under the action. In this article, we study the shift orbit structure of the coboundary subgroup B²(G,C) of Z²(G,C). The study is placed within a well-known setting involving the Loewy and socle series of a group algebra over G. We prove new bounds on the dimensions of terms in such series. Asymptotic results on the size of shift orbits are also derived; for example, if C is an elementary abelian p-group, then almost all shift orbits in B²(G,C) are maximal-sized for large enough finite p-groups G of certain classes.     

Broué's conjecture for non-principal 3-blocks of finite groups

In representation theory of finite groups, there is a well-known and important conjecture due to M. Broué. He conjectures that, for any prime p, if a p-block A of a finite group G has an abelian defect group D, then A and its Brauer correspondent p-block B of N_G(D) are derived equivalent. We demonstrate in this paper that Broué's conjecture holds for two non-principal 3-blocks A with elementary abelian defect group D of order 9 of the O'Nan simple group and the Higman-Sims simple group. Moreover, we determine these two non-principal block algebras over a splitting field of characteristic 3 up to Morita equivalence.     

Equidimensionality of convolution morphisms and applications to saturation problems

Fix a split connected reductive group G over a field k, and a positive integer r. For any r-tuple of dominant coweights μi of G, we consider the restriction mμ_• of the r-fold convolution morphism of Mirkovic-Vilonen to the twisted product of affine Schubert varieties corresponding to μ_•. We show that if all the coweights μi are minuscule, then the fibers of mμ_• are equidimensional varieties, with dimension the largest allowed by the semi-smallness of mμ_•. We derive various consequences: the equivalence of the non-vanishing of Hecke and representation ring structure constants, and a saturation property for these structure constants, when the coweights μi are sums of minuscule coweights. This complements the saturation results of Knutson-Tao and Kapovich-Leeb-Millson. We give a new proof of the P-R-V conjecture in the “sums of minuscules” setting. Finally, we generalize and reprove a result of Spaltenstein pertaining to equidimensionality of certain partial Springer resolutions of the nilpotent cone for GLn.     

Multiplicative versions of Klyachko’s theorem in finite factors

Let A and B be invertible positive elements in a II₁-factor A, and let μ_s(·) be the singular number on A. We prove that

exp_∫Klogμ_s(AB)ds?exp_∫Ilogμ_s(A)ds·exp_∫Jlogμ_s(B)ds,     

Lower bounds for the game colouring number of partial k-trees and planar graphs

This paper discusses the game colouring number of partial k-trees and planar graphs. Let col_g(PT_k) and col_g(P) denote the maximum game colouring number of partial k trees and the maximum game colouring number of planar graphs, respectively. In this paper, we prove that col_g(PT_k)=3k+2 and col_g(P)?11. We also prove that the game colouring number col_g(G) of a graph is a monotone parameter, i.e., if H is a subgraph of G, then col_g(H)?col_g(G).     

Self-duality in the class of precompact groups

A topological Abelian group G is called (strongly) self-dual if there exists a topological isomorphism Φ:G→G^∧ of G onto the dual group G^∧ (such that Φ(x)(y)=Φ(y)(x) for all x,y∈G). We prove that every countably compact self-dual Abelian group is finite. It turns out, however, that for every infinite cardinal κ with κω=κ, there exists a pseudocompact, non-compact, strongly self-dual Boolean group of cardinality κ.     

Surjections on Grassmannians preserving pairs of elements with bounded distance

Let m and k be two fixed positive integers such that m>k?2. Let V be a left vector space over a division ring with dimension at least m+k+1. Let G_m(V) be the Grassmannian consisting of all m-dimensional subspaces of V. We characterize surjective mappings T from G_m(V) onto itself such that for any A,B in G_m(V), the distance between A and B is not greater than k if and only if the distance between T(A) and T(B) is not greater than k.     

Identifications in modular group algebras

Let G be a group, S a subgroup of G, and F a field of characteristic p. We denote the augmentation ideal of the group algebra FG by ω(G). The Zassenhaus-Jennings-Lazard series of G is defined by D_n(G)=G∩(1+ωⁿ(G)). We give a constructive proof of a theorem of Quillen stating that the graded algebra associated with FG is isomorphic as an algebra to the enveloping algebra of the restricted Lie algebra associated with the D_n(G). We then extend a theorem of Jennings that provides a basis for the quotient ωⁿ(G)/ωⁿ⁺¹(G) in terms of a basis of the restricted Lie algebra associated with the D_n(G). We shall use these theorems to prove the main results of this paper. For G a finite p-group and n a positive integer, we prove that G∩(1+ω(G)ωⁿ(S))=D_n+1(S) and G∩(1+ω²(G)ωⁿ(S))=D_n+2(S)D_n+1(S∩D₂(G)). The analogous results for integral group rings of free groups have been previously obtained by Gruenberg, Hurley, and Sehgal.     

On a particular case of the inconsistent linear matrix equation AX+YB=C

We consider the linear matrix equation AX+YB=C where A,B, and C are given matrices of dimensions (r+1)×r, s×(s+1), and (r+1)×(s+1), respectively, and rank A = r, rank B = s. We give a connection between the least-squares solution and the solution which minimizes an arbitrary norm of the residual matrix C?AX? YB.     

Properties of two-dimensional sets with small sumset

We give tight lower bounds on the cardinality of the sumset of two finite, nonempty subsets A,B⊆R² in terms of the minimum number h₁(A,B) of parallel lines covering each of A and B. We show that, if h₁(A,B)?s and |A|?|B|?2s²−3s+2, then

     

Abelian groups admitting a Fréchet-Urysohn pseudocompact topological group topology

We show that every Abelian group G with r₀(G)=|G|=|G|^ω admits a pseudocompact Hausdorff topological group topology T such that the space (G,T) is Fréchet-Urysohn. We also show that a bounded torsion Abelian group G of exponent n admits a pseudocompact Hausdorff topological group topology making G a Fréchet-Urysohn space if for every prime divisor p of n and every integer k≥0, the Ulm-Kaplansky invariant f_p,k of G satisfies (f_p,k)^ω=f_p,k provided that f_p,k is infinite and f_p,k>f_p,i for each i>k.Our approach is based on an appropriate dense embedding of a group G into a Σ-product of circle groups or finite cyclic groups.