The computations of some Schur indices

Let χ be an irreducible character of a finite groupG. Letp=∞ or a prime. Letm _p (χ) denote the Schur index of χ overQ _p , the completion ofQ atp. It is shown that ifx is ap′-element ofG such that for all irreducible charactersX _u ofG thenm _p (χ)/vbχ(x). This result provides an effective tool in computing Schur indices of characters ofG from a knowledge of the character table ofG. For instance, one can read off Benard’s Theorem which states that every irreducible character of the Weyl groupsW(E _n), n=6,7,8 is afforded by a rational representation. Several other applications are given including a complete list of all local Schur indices of all irreducible characters of all sporadic simple groups and their covering groups (there is still an open question concerning one character of the double cover of Suz). This work was partly supported by NSF Grant MCS-8201333.     

On graphs related to conjugacy classes of groups

LetG be a finite group. Attach toG the following two graphs: Γ — its vertices are the non-central conjugacy classes ofG, and two vertices are connected if their sizes arenot coprime, and Γ* — its vertices are the prime divisors of sizes of conjugacy classes ofG, and two vertices are connected if they both divide the size of some conjugacy class ofG. We prove that whenever Γ* is connected then its diameter is at most 3, (this result was independently proved in [3], for solvable groups) and Γ* is disconnected if and only ifG is quasi-Frobenius with abelian kernel and complements. Using the method of that proof we give an alternative proof to Theorems in [1],[2],[6], namely that the diameter of Γ is also at most 3, whenever the graph is connected, and that Γ is disconnected if and only ifG is quasi-Frobenius with abelian kernel and complements. As a result we conclude that both Γ and Γ* have at most two connected components. In [2],[3] it is shown that the above bounds are best possible. The content of this paper corresponds to a part of the author’s Ph.D. thesis carried out at the Tel Aviv University under the supervision of Prof. Marcel Herzog.     

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     

A measuring argument for finite permutation groups

LetG be a finite transitive permutation group on a finite setS. LetA be a nonempty subset ofS and denote the pointwise stabilizer ofA inG byC _G (A). Our main result is the following inequality: [G :C _G (A)]≥|G|^|A|/|S|. This paper is a part of the author’s Ph.D. thesis research, carried out at Tel Aviv University under the supervision of Professor Marcel Herzog.     

On zeros of characters of finite groups

For a finite group G and a non-linear irreducible complex character χ of G write υ(χ) = {g ∈ G | χ(g) = 0}. In this paper, we study the finite non-solvable groups G such that υ(χ) consists of at most two conjugacy classes for all but one of the non-linear irreducible characters χ of G. In particular, we characterize a class of finite solvable groups which are closely related to the above-mentioned question and are called solvable φ-groups. As a corollary, we answer Research Problem 2 in [Y.Berkovich and L.Kazarin: Finite groups in which the zeros of every non-linear irreducible character are conjugate modulo its kernel. Houston J. Math. 24 (1998), 619–630.] posed by Y.Berkovich and L.Kazarin.     

On some special measures on βG

LetG be a discrete abelian group,Ĝ the character group ofG, andl ^∞(G)^* the conjugate ofl ^∞(G) equipped with an Arens product. In many cases, we can find unitary functionsf such that χf is almost convergent to zero for all χ∈Ĝ. Some of these functions are then used to produce elements μ∈l ^∞(G)^* such that γμ=0 whenever γ is an annihilator ofC ₀(G). Regarded as Borel measures on βG, these elements satisfyxμ=0 for allx∈βG/G. They belong to the radical ofl ^∞(G)^*, and each of them generates a left ideal ofl ^∞(G)^* that contains no minimal left ideal.     

List 2-distance (Δ + 1)-coloring of planar graphs with girth at least 7

The trivial lower bound for the 2-distance chromatic number χ ₂(G) of a graph G with maximum degree Δ is Δ + 1. There are available some examples of the graphs with girth g ≤ 6 that have arbitrarily large Δ and χ ₂(G) ≥ Δ + 2. In the paper we improve the known restrictions on Δ and g under which a planar graph G has χ ₂(G) = Δ + 1.     

Fractional and integral colourings

LetG=(V, E) be an undirected graph andc any vector in ℤ ^V(G) ₊. Denote byχ(G _c) (resp.η(G _c)) the chromatic number (resp. fractional chromatic number) ofG with respect toc. We study graphs for whichχ(G _c)−[η(G _c)]⩽1. We show that for the class of graphs satisfyingχ(G _c)=[η(G _c)] (a class generalizing perfect graphs), an analogue of the Duplication Lemma does not hold. We also describe a 2-vertex cut decomposition procedure related to the integer decomposition property. We use this procedure to show thatχ(G _c)=[η(G _c)] for series-parallel graphs andχ(G _c)⩽[η(G _c)]+1 for graphs that do not have the 4-wheel as a minor. The work of this author was supported by the Natural Sciences and Engineering Research Council of Canada (NSERCC) under grant A9126.     

Irreducible disconnected systems in groups

LetG be an arbitrary group with a subgroupA. The subdegrees of (A, G) are the indices [A:A ∪A ⁹] (wheregεG). Equivalent definitions of that concept are given in [IP] and [K]. IfA is not normal inG and all the subdegrees of (A, G) are finite, we attach to (A, G) the common divisor graph Γ: its vertices are the non-unit subdegrees of (A, G), and two different subdegrees are joined by an edge iff they arenot coprime. It is proved in [IP] that Γ has at most two connected components. Assume that Γ is disconnected. LetD denote the subdegree set of (A, G) and letD ₁ be the set of all the subdegrees in the component of Γ containing min(D−{1}). We proved [K, Theorem A] that ifA is stable inG (a property which holds whenA or [G:A] is finite), then the setH={g ε G| [A:A ∪A ^g ] εD ₁ ∪ {1}} is a subgroup ofG. In this case we say thatA<H<G is a disconnected system (briefly: a system). In the current paper we deal with some fundamental types of systems. A systemA<H<G is irreducible if there does not exist 1<N△G such thatAN<H andAN/N<H/N<G/N is a system. Theorem A gives restrictions on the finite nilpotent normal subgroups ofG, whenG possesses an irreducible system. In particular, ifG is finite then Fit(G) is aq-group for a certain primeq. We deal also with general systems. Corollary (4.2) gives information about the structure of a finite groupG which possesses a system. Theorem B says that for any systemA<H<G,N _G (N _G (A))=N _G (A). Theorem C and Corollary C’ generalize a result of Praeger [P, Theorem 2]. The content of this paper corresponds to a part of the author’s Ph.D. thesis carried out at Tel Aviv University under the supervision of Prof. Marcel Herzog.     

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     

Semidefinite programming relaxations for graph coloring and maximal clique problems

The semidefinite programming formulation of the Lovász theta number does not only give one of the best polynomial simultaneous bounds on the chromatic number χ(G) or the clique number ω(G) of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming formulation can be tightened toward either χ(G) or ω(G) by adding several types of cutting planes. We explore several such strengthenings, and show that some of them can be computed with the same effort as the theta number. We also investigate computational simplifications for graphs with rich automorphism groups. Partial support by the EU project Algorithmic Discrete Optimization (ADONET), MRTN-CT-2003-504438, is gratefully acknowledged.     

The Entire Coloring of Series-Parallel Graphs

The entire chromatic number X_(vef)(G) of a plane graph G is the minimal number of colors needed for coloring vertices, edges and faces of G such that no two adjacent or incident elements are of the same color. Let G be a series-parallel plane graph, that is, a plane graph which contains no subgraphs homeomorphic to K_(4-) It is proved in this paper that X_(vef)(G)≤max{8, △(G) 2} and X_(vef)(G)=△ 1 if G is 2-connected and △(G)≥6.     

Cusp forms

LetG andH ⊂G be two real semisimple groups defined overQ. Assume thatH is the group of points fixed by an involution ofG. Letπ ⊂L ²(H\G) be an irreducible representation ofG and letf επ be aK-finite function. Let Γ be an arithmetic subgroup ofG. The Poincaré seriesP _f(g)=Σ_H∩ΓΓ f(γ{}itg) is an automorphic form on Γ\G. We show thatP _f is cuspidal in some cases, whenH ∩Γ\H is compact. Partially supported by NSF Grant # DMS 9103608.     

Injective (Δ + 1)-coloring of planar graphs with girth 6

A vertex coloring of a graph G is called injective if every two vertices joined by a path of length 2 get different colors. The minimum number χ _i (G) of the colors required for an injective coloring of a graph G is clearly not less than the maximum degree Δ(G) of G. There exist planar graphs with girth g ≥ 6 and χ _i = Δ+1 for any Δ ≥ 2. We prove that every planar graph with Δ ≥ 18 and g ≥ 6 has χ _i ≤ Δ + 1.     

The total chromatic number of regular graphs of high degree

The total chromatic number χT (G) of a graph G is the minimum number of colors needed to color the edges and the vertices of G so that incident or adjacent elements have distinct colors. We show that if G is a regular graph and d(G) 32 |V (G)| + 263 , where d(G) denotes the degree of a vertex in G, then χT (G) d(G) + 2.     

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)     

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     

Primes dividing the degrees of the real characters

Let G be a finite group and let Irr(G) denote the set of all complex irreducible characters of G. The Ito–Michler Theorem asserts that if a prime p does not divide the degree of any χ Irr(G) then a Sylow p-subgroup P of G is normal in G. We prove a real-valued version of this theorem, where instead of Irr(G) we only consider the subset Irr_rv(G) consisting of all real-valued irreducible characters of G. We also prove that the character degree graph associated to Irr_rv(G) has at most 3 connected components. Similar results for the set of real conjugacy classes of G have also been obtained. Part of this paper was done while the second author visited the Mathematics Department of the Università di Firenze. He would like to thank the Department for its hospitality. The authors are also grateful to F. Lübeck for helping them with some computer calculations. The research of the first author was partially supported by MIUR research program “Teoria dei gruppi ed applicazioni”. This research of the second author was partially supported by the Spanish Ministerio de Educación y Ciencia proyecto MTM2004-06067-C02-01. The third author gratefully acknowledges the support of the NSA and the NSF.     

Automorphisms of blocks of group algebras and character values

Let G be a finite group, χ an irreducible complex character of G and A(χ) the block ideal of the group algebra ℚG relatedℴ χ. The aim of this paper is to study the group Aut (A(χ)) of all ring (or ℚ-algebra) automorphisms of A(χ). Especially we are interested in the existence of subgroups of Aut (A(χ)), which are isomorphic to a given subgroup Γ of the Galois group of the field of character values ℚ(χ) over the rationals. In this context we prove some results related to character values.     

Analytic actions on compact surfaces and fixed points

 Consider an effective real analytic action of a connected Lie group G on a compact connected surface of Euler characteristic χ≠0. We show that if the action has no fixed point then χ≥1 and the Lie algebra 𝒢 of G is isomorphic either to a subalgebra of the affine algebra of ℝ², which is the extension of the ideal of constant vector fields by an irreducible linear subalgebra, or to sl(2,ℝ), o(3), sl(2,ℂ) and sl(3,ℝ). Received: 7 August 2001 Published online: 24 January 2003