The Littlewood-Gowers problem

The paper has two main parts. To begin with, suppose that G is a compact abelian group. Chang’s Theorem can be viewed as a structural refinement of Bessel’s inequality for functions ƒ ∈ L ²(G). We prove an analogous result for functions ƒ ∈ A(G), where A(G) is the space endowed with the norm , and generalize this to the approximate Fourier transform on Bohr sets. As an application of the first part of the paper, we improve a recent result of Green and Konyagin. Suppose that p is a prime number and A ⊂ ℤ/pℤ has density bounded away from 0 and 1 by an absolute constant. Green and Konyagin have shown that ‖χ _A ‖ _A(ℤ/pℤ) ≫ ɛ (log p)^1/3−ɛ; we improve this to ‖χ _A ‖ _A(ℤ/pℤ) ≫ ɛ (log p)^1/2−ɛ. To put this in context, it is easy to see that if A is an arithmetic progression, then ‖χ _A ‖ _A(ℤ/pℤ) ≪ log p.     

On the description of overgroups of E(m,R)?E(n,R)

The subgroups E(m,R) ⊗ E(n,R) ≤ H ≤ G = GL(mn,R) are studied under the assumption that the ring R is commutative and m, n ≥ 3. The group GL _m ⊗GL _n is defined by equations, the normalizer of the group E(m,R) ⊗ E(n,R) is calculated, and with each intermediate subgroup H it is associated a uniquely determined lower level (A,B,C), where A,B,C are ideals in R such that mA,A ² ≤ B ≤ A and nA,A ² ≤ C ≤ A. The lower level specifies the largest elementary subgroup satisfying the condition E(m, n,R, A,B,C) ≤ H. The standard answer to this problem asserts that H is contained in the normalizer N _G (E(m,n,R, A,B,C)). Bibliography: 46 titles.     

On finite groups whose every proper normal subgroup is a union of a given number of conjugacy classes

Let G be a finite group andA be a normal subgroup ofG. We denote by ncc(A) the number ofG-conjugacy classes ofA andA is calledn-decomposable, if ncc(A)= n. SetK _G = {ncc(A)|A ⊲ G}. LetX be a non-empty subset of positive integers. A groupG is calledX-decomposable, ifK _G =X. Ashrafi and his co-authors [1-5] have characterized theX-decomposable non-perfect finite groups forX = {1, n} andn ≤ 10. In this paper, we continue this problem and investigate the structure ofX-decomposable non-perfect finite groups, forX = {1, 2, 3}. We prove that such a group is isomorphic to Z₆, D₈, Q₈, S₄, SmallGroup(20, 3), SmallGroup(24, 3), where SmallGroup(m, n) denotes the mth group of ordern in the small group library of GAP [11].     

Zeros in Tables of Characters for the Groups <Emphasis Type="Italic">S</Emphasis><Subscript>n</Subscript> and <Emphasis Type="Italic">A</Emphasis><Subscript>n</Subscript>. II

Let P(n) be the set of all partitions of a natural number n. In the representation theory of symmetric groups, for every partition α ∈ P(n), the partition h(α) ∈ P(n) is defined so as to produce a certain set of zeros in the character table for S_n. Previously, the analog f(α) of h(α) was obtained pointing out an extra set of zeros in the table mentioned. Namely, h(α) is greatest (under the lexicographic ordering ≤) of the partitions β of n such that χ^α(g_β) ≠ 0, and f(α) is greatest of the partitions γ of n that are opposite in sign to h(α) and are such that χ^α(g_γ) ≠ 0, where χ^α is an irreducible character of S_n, indexed by α, and g_β is an element in the conjugacy class of S_n, indexed by β. For α ∈ P(n), under some natural restrictions, here, we construct new partitions h′(α) and f′(α) of n possessing the following properties. (A) Let α ∈ P(n) and n ⩾ 3. Then h′(α) is identical is sign to h(α), χ^α(g_h′(α)) ≠ 0, but χ^α(g_γ) = 0 for all γ ∈ P(n) such that the sign of γ coincides with one of h(α), and h′(α) < γ < h(α). (B) Let α ∈ P(n), α ≠ α′, and n ⩾ 4. Then f′(α) is identical in sign to f(α), χ^α(g_f′(α)) ≠ 0, but χ^α(g_γ) = 0 for all γ ∈ P(n) such that the sign of γ coincides with one of f(α), and f′(α) < γ < f(α). The results obtained are then applied to study pairs of semiproportional irreducible characters in A_n. Supported by RFBR grant No. 04-01-00463. __________ Translated from Algebra i Logika, Vol. 44, No. 6, pp. 643–663, November–December, 2005.     

Structure of augmentation quotients of finite homocyclic abelian groups

Let G be a finite abelian group and its Sylow p-subgroup a direct product of copies of a cyclic group of order p~r,i.e.,a finite homocyclic abelian group.LetΔ~n (G) denote the n-th power of the augmentation idealΔ(G) of the integral group ring ZG.The paper gives an explicit structure of the consecutive quotient group Q_n(G)=Δ~n(G)/Δ~(n 1)(G) for any natural number n and as a consequence settles a problem of Karpilovsky for this particular class of finite abelian groups.     

The <Emphasis Type="Italic">p</Emphasis>-rank of Ext<Subscript>ℤ</Subscript>(<Emphasis Type="Italic">G</Emphasis>, ℤ) in certain models of <Emphasis Type="Italic">ZFC</Emphasis>

We prove that if the existence of a supercompact cardinal is consistent with ZFC, then it is consistent with ZFC that the p-rank of Ext _ℤ(G, ℤ) is as large as possible for every prime p and for any torsion-free Abelian group G. Moreover, given an uncountable strong limit cardinal μ of countable cofinality and a partition of Π (the set of primes) into two disjoint subsets Π₀ and Π₁, we show that in some model which is very close to ZFC, there is an almost free Abelian group G of size 2^μ = μ⁺ such that the p-rank of Ext _ℤ(G, ℤ) equals 2^μ = μ⁺ for every p ∈ Π₀ and 0 otherwise, that is, for p ∈ Π₁. Number 874 in Shelah’s list of publications. Supported by the German-Israeli Foundation for Scientific Research & Development project No. I-706-54.6/2001. Supported by a grant from the German Research Foundation DFG. __________ Translated from Algebra i Logika, Vol. 46, No. 3, pp. 369–397, May–June, 2007.     

On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

On a cardinal group invariant related to decompositions of Abelian groups

For each Abelian groupG, a cardinal invariant χ(G) is introduced and its properties are studied. In the special caseG = ? ⁿ , the cardinalχ(? ⁿ ) is equal to the minimal cardinality of an essential subset of ? ⁿ , i.e., a of a subsetA ? ? ⁿ such that, for any coloring of the group ? ⁿ inn colors, there exists an infinite one-color subset that is symmetric with respect to some pointα ofA. The estimaten( ^{n +} l)/2 ≤χ(? ⁿ ) < 2n is proved for alln and the relationχ(? ⁿ ) =n(n + 1)/2 forn ≤ 3. The structure of essential subsets of cardinalityχ(? ⁿ ) in ? ⁿ is completely described forn ≤ 3.     

Some zero-sum constants with weights

For an abelian group G, the Davenport constant D(G) is defined to be the smallest natural number k such that any sequence of k elements in G has a nonempty subsequence whose sum is zero (the identity element). Motivated by some recent developments around the notion of Davenport constant with weights, we study them in some basic cases. We also define a new combinatorial invariant related to (ℤ/nℤ) ^d , more in the spirit of some constants considered by Harborth and others and obtain its exact value in the case of (ℤ/nℤ)² where n is an odd integer.     

Group Chromatic Number of Graphs without K5-Minors

 Let G be a graph with a fixed orientation and let A be a group. Let F(G,A) denote the set of all functions f: E(G) ↦A. The graph G is A -colorable if for any function f∈F(G,A), there is a function c: V(G) ↦A such that for every directed e=u v∈E(G), c(u)−c(v)≠f(e). The group chromatic numberχ₁(G) of a graph G is the minimum m such that G is A-colorable for any group A of order at least m under a given orientation D. In [J. Combin. Theory Ser. B, 56 (1992), 165–182], Jaeger et al. proved that if G is a simple planar graph, then χ₁(G)≤6. We prove in this paper that if G is a simple graph without a K ₅-minor, then χ₁(G)≤5. Received: August 18, 1999 Final version received: December 12, 2000     

A Generalization of the Gallai–Roy Theorem

 A well-known and essential result due to Roy ([4], 1967) and independently to Gallai ([3], 1968) is that if D is a digraph with chromatic number χ(D), then D contains a directed path of at least χ(D) vertices. We generalize this result by showing that if ψ(D) is the minimum value of the number of the vertices in a longest directed path starting from a vertex that is connected to every vertex of D, then χ(D) ≤ψ(D). For graphs, we give a positive answer to the following question of Fajtlowicz: if G is a graph with chromatic number χ(G), then for any proper coloring of G of χ(G) colors and for any vertex v∈V(G), there is a path P starting at v which represents all χ(G) colors. Received: May 20, 1999 Final version received: December 24, 1999     

On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters

Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!].     

On Group Chromatic Number of Graphs

Let G be a graph and A an Abelian group. Denote by F(G, A) the set of all functions from E(G) to A. Denote by D an orientation of E(G). For f ∈ F(G,A), an (A,f)-coloring of G under the orientation D is a function c : V(G)↦A such that for every directed edge uv from u to v, c(u)−c(v) ≠ f(uv). G is A-colorable under the orientation D if for any function f ∈ F(G, A), G has an (A, f)-coloring. It is known that A-colorability is independent of the choice of the orientation. The group chromatic number of a graph G is defined to be the least positive integer m for which G is A-colorable for any Abelian group A of order ≥m, and is denoted by χ_g(G). In this note we will prove the following results. (1) Let H₁ and H₂ be two subgraphs of G such that V(H₁)∩V(H₂)=∅ and V(H₁)∪V(H₂)=V(G). Then χ_g(G)≤min{max{χ_g(H₁), max_v∈V(H2)deg(v,G)+1},max{χ_g(H₂), max_u∈V(H1) deg (u, G) + 1}}. We also show that this bound is best possible. (2) If G is a simple graph without a K_3,3-minor, then χ_g(G)≤5.     

The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity

Total colorings of graphs of order 2n having maximum degree 2n−2

Let χ _t (G) and †(G) denote respectively the total chromatic number and maximum degree of graphG. Yap, Wang and Zhang proved in 1989 that ifG is a graph of orderp having †(G)≥p−4, then χ _t (G≤Δ(G)+2. Hilton has characterized the class of graphG of order 2n having †(G)=2n−1 such that χ _t (G=Δ(G)+2. In this paper, we characterize the class of graphsG of order 2n having †(G)=2n−2 such that χ _t (G=Δ(G)+2 Research supported by National Science Council of the Republic of China (NSC 79-0208-M009-15)     

On Some Sets of Group Functions

Let G be a group, let A be an Abelian group, and let n be an integer such that n –1. In the paper, the sets _n (G,A) of functions from G into A of degree not greater than n are studied. In essence, these sets were introduced by Logachev, Sal'nikov, and Yashchenko. We describe all cases in which any function from G into A is of bounded (or not necessarily bounded) finite degree. Moreover, it is shown that if G is finite, then the study of the set _n (G,A) is reduced to that of the set n(G/O ^p (G),A _p ) for primes p dividing G/G. Here O ^p (G) stands for the p-coradical of the group G, A _p for the p-component of A, and G for the commutator subgroup of G.     

On Some Three-Color Ramsey Numbers

 In this paper we study three-color Ramsey numbers. Let K _i,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G ₁, G ₂ and G ₃, if r(G ₁, G ₂)≥s(G ₃), then r(G ₁, G ₂, G ₃)≥(r(G ₁, G ₂)−1)(χ(G ₃)−1)+s(G ₃), where s(G ₃) is the chromatic surplus of G ₃; (ii) (k+m−2)(n−1)+1≤r(K _1,k , K _1,m , K _n )≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K _k,m , K _k,m , K _n )≤c(n/logn), and r(C _2m , C _2m , K _n )≤c(n/logn) ^m/(m−1) for sufficiently large n. Received: July 25, 2000 Final version received: July 30, 2002 RID="*" ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of education ministry of China, and the foundations of Jiangsu Province Acknowledgments. The authors are grateful to the referee for his valuable comments. AMS 2000 MSC: 05C55     

Irreducible Algebraic Sets in Metabelian Groups

We present the construction for a u-product G₁ ○ G₂ of two u-groups G₁ and G₂, and prove that G₁ ○ G₂ is also a u-group and that every u-group, which contains G₁ and G₂ as subgroups and is generated by these, is a homomorphic image of G₁ ○ G₂. It is stated that if G is a u-group then the coordinate group of an affine space Gⁿ is equal to G ○ F_n, where F_n is a free metabelian group of rank n. Irreducible algebraic sets in G are treated for the case where G is a free metabelian group or wreath product of two free Abelian groups of finite ranks. __________ Translated from Algebra i Logika, Vol. 44, No. 5, pp. 601–621, September–October, 2005. Supported by RFBR grant No. 05-01-00292, by FP “Universities of Russia” grant No. 04.01.053, and by RF Ministry of Education grant No. E00-1.0-12.     

On the cohomological characterization of real free pro-2-groups

The aim of this note is to give a cohomological characterization of the real free pro-2-groups. Thereal free pro-2-groups are the free pro-2-product of copies of ℤ/2ℤ with a free pro-2-group. They are characterized as the pro-2-groupsG for which there exists a character χ₀, whose kernel is a free pro-2-group, such that χ₀∪χ=χ∪χ, for every χ∈H ¹(G). We discuss the naturalness of these conditions and we state some relations between them and field arithmetic properties. Supported by a grant from CNPq-Brasil. This article was processed by the author using the LATEX style filecljour1 from Springer-Verlag.     

Wavelet expansions of fractal measures

Let μ be a measure on ℝⁿ that satisfies the estimate μ(B _r(x))≤cr ^α for allx ∈ ℝⁿ and allr ≤ 1 (B _r(x) denotes the ball of radius r centered atx. Let ϕ _j,k ^(ɛ) (x)=2 ^nj2ϕ^(ɛ)(2 ^j x-k) be a wavelet basis forj ∈ ℤ, κ ∈ ℤⁿ, and ∈ ∈E, a finite set, and letP _j (T)=Σ_ɛ,k <T,ϕ _j,k ^(ɛ) >ϕ _j,k ^(ɛ) denote the associated projection operators at levelj (T is a suitable measure or distribution). Iff ∈Ls ^p(dμ) for 1 ≤p ≤ ∞, we show thatP _j(f dμ) ∈ L^p(dx) and ||P _j (fdμ)||L _p(dx)≤c2 ^{j((n-α)/p′))}||f||L _p(dμ) for allj ≥ 0. We also obtain estimates for the limsup and liminf of ||P _j (fdμ)||L _p(dx) under more restrictive hypotheses. Communicated by Guido Weiss