A note on character kernels in finite groups of prime power order

In this note, we classify the finite groups of prime power order for which all nonlinear irreducible character kernels constitute a chain with respect to inclusion. Received: 6 April 2007     

Diperfect graphs

Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ₁, μ₂, ..., μ_k such tht |μ_i ∩S|=1 for alli. Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic number; here again, we do not know if there exists an optimal coloring (S ₁,S ₂, ...,S _k) and a path μ such that |μ ∩S _i|=1 for alli. In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the perfect graph conjecture. Dedicated to Tibor Gallai on his seventieth birthday     

Even degree characters in principal blocks

We characterise finite groups such that for an odd prime p all the irreducible characters in its principal p-block have odd degree. We show that this situation does not occur in non-abelian simple groups of order divisible by p unless $p=7$ and the group is $M_{22}$. As a consequence we deduce that if $p\ne 7$ or if $M_{22}$ is not a composition factor of a group G, then the condition above is equivalent to $G/{\mathbf{O}}_{p^{\prime }}(G)$ having odd order.     

Colorings and orientations of graphs

Bounds for the chromatic number and for some related parameters of a graph are obtained by applying algebraic techniques. In particular, the following result is proved: IfG is a directed graph with maximum outdegreed, and if the number of Eulerian subgraphs ofG with an even number of edges differs from the number of Eulerian subgraphs with an odd number of edges then for any assignment of a setS(v) ofd+1 colors for each vertexv ofG there is a legal vertex-coloring ofG assigning to each vertexv a color fromS(v).Research supported in part by a United States-Israel BSF Grant and by a Bergmann Memorial Grant.     

Counting characters of small degree in upper unitriangular groups

Let U_n denote the group of upper n×n unitriangular matrices over a fixed finite field of order q. That is, U_n consists of upper triangular n×n matrices having every diagonal entry equal to 1. It is known that the degrees of all irreducible complex characters of U_n are powers of q. It was conjectured by Lehrer that the number of irreducible characters of U_n of degree q^e is an integer polynomial in q depending only on e and n. We show that there exist recursive (for n) formulas that this number satisfies when e is one of 1,2 and 3, and thus show that the conjecture is true in those cases.     

Whitney preserving maps on finite graphs

For a Whitney preserving map f:X→G we show the following: (a) If X is arcwise connected and G is a graph which is not a simple closed curve, then f is a homeomorphism; (b) If X is locally connected and G is a simple closed curve, then X is homeomorphic to either the unit interval [0,1], or the unit circle S¹. As a consequence of these results, we characterize all Whitney preserving maps between finite graphs. We also show that every hereditarily weakly confluent Whitney preserving map between locally connected continua is a homeomorphism.     

Minimal orientations of colour critical graphs

In 1966 T. Gallai asked whether every criticalk-chromatic graph possesses an orientation having just one directed path of lengthk–1. In this note we show that in general the answer is negative, but also that the answer is affirmative whenk5 and the graph has maximal degree at mostk.     

Strongly connective degree sets I: nonabelian solvable quotients

When G is a finite nonabelian group, we associate the common-divisor graph (G) with G by letting nontrivial degrees in cd(G) be the vertices and making distinct vertices adjacent if they have a common nontrivial divisor. A set of vertices for this graph is said to be strongly connective for cd(G) if there is some prime which divides every member of and every vertex outside of is adjacent to some member of When G has a nonabelian solvable quotient, we show that if (G) is connected and has a diameter of at most 2, then indeed cd(G) has a strongly connective subset.Received: 7 July 2004; revised: 5 October 2004     

Eigenvalues and degree deviation in graphs

Let G be a graph with n vertices and m edges and let μ(G) = μ₁(G) ? ? ? μ_n(G) be the eigenvalues of its adjacency matrix. Set s(G)=∑_u∈V(G)∣d(u)-2m/n∣. We prove that

     

Strongly connective degree sets II: perfect derived subgroups

When G is a finite nonabelian group, we associate the common-divisor graph with G by letting nontrivial degrees in cd(G) = {χ(1) | χ∈Irr(G)} be the vertices and making distinct vertices adjacent if they have a common nontrivial divisor. A set of vertices for this graph is said to be strongly connective for cd(G) if there is some prime which divides every member of , and every vertex outside of is adjacent to some member of . When G is nonsolvable, we provide sufficiency conditions for cd(G) to have a strongly connective subset. We also extend a previously known result about groups with nonabelian solvable quotients, and prove for arbitrary groups G that if the associated graph is connected and has a diameter bounded by 2, then indeed cd(G) has a strongly connective subset. The major focus is on when the derived subgroup G′ is perfect. Received: 23 July 2005     

Unoriented Laplacian maximizing graphs are degree maximal

A connected graph is said to be unoriented Laplacian maximizing if the spectral radius of its unoriented Laplacian matrix attains the maximum among all connected graphs with the same number of vertices and the same number of edges. A graph is said to be threshold (maximal) if its degree sequence is not majorized by the degree sequence of any other graph (and, in addition, the graph is connected). It is proved that an unoriented Laplacian maximizing graph is maximal and also that there are precisely two unoriented Laplacian maximizing graphs of a given order and with nullity 3. Our treatment depends on the following known characterization: a graph G is threshold (maximal) if and only if for every pair of vertices u,v of G, the sets N(u)?{v},N(v)?{u}, where N(u) denotes the neighbor set of u in G, are comparable with respect to the inclusion relation (and, in addition, the graph is connected). A conjecture about graphs that maximize the unoriented Laplacian matrix among all graphs with the same number of vertices and the same number of edges is also posed.     

An affirmative answer to a question of Ciliberto

We give an example of a nondegeneraten-dimensional smooth projective varietyX inP ²ⁿ⁺¹ with the canonical bundle ample a varietyX whose tangent variety TanX has dimension less than 2n over an algebraically closed field of any characteristic whenn≥9. This varietyX is not ruled by lines and the embedded tangent space at a general point ofX intersectsX at some other points, so that this yields an affirmative answer to a question of Ciliberto.     

Orthogonal representations over finite fields and the chromatic number of graphs

We study the relationship between the minimum dimension of an orthogonal representation of a graph over a finite field and the chromatic number of its complement. It turns out that for some classes of matrices defined by a graph the 3-colorability problem is equivalent to deciding whether the class defined by the graph contains a matrix of rank 3 or not. This implies the NP-hardness of determining the minimum rank of a matrix in such a class. Finally we give for any class of matrices defined by a graph that is interesting in this respect a reduction of the 3-colorability problem to the problem of deciding whether or not this class contains a matrix of rank equal to three.The author is financially supported by the Cooperation Centre Tilburg and Eindhoven Universities.     

Morita equivalence of Isaacs correspondence for blocks of finite groups

We show that a p-block of a finite group and its Isaacs correspondent are Morita equivalent. Received: 22 August 2001     

An answer to a question on the convolution of functions

Let G be a locally compact group. Recently, G?a¸b and Strobin [2] asked when f*g exists for all \({f, g \in L^p(G)}\) , and also: is the set \({\{(f,g)\in L^p(G) \times L^p(G): f\ast g \in L^p(G)\}}\) σ-c-lower porous (in particular, meager) for \({p\in(1,2]}\) ? In this paper, we answer these questions. In particular, we prove that if 1 <  p <  ∞, 1 ≤  q < ∞, and G is a non-unimodular locally compact group, then the set \({\{(f, g) \in L^p(G) \times L^q(G): f * g}\) is not λ -a.e. finite on G} is a residual set in L ^p (G) ×  L ^q (G).     

Breaking the rhythm on graphs

We study graph colorings avoiding periodic sequences with large number of blocks on paths. The main problem is to decide, for a given class of graphs F, if there are absolute constants t,k such that any graph from the class has a t-coloring with no k identical blocks in a row appearing on a path. The minimum t for which there is some k with this property is called the rhythm threshold of F, denoted by t(F). For instance, we show that the rhythm threshold of graphs of maximum degree at most d is between (d+1)/2 and d+1. We give several general conditions for finiteness of t(F), as well as some connections to existing chromatic parameters. The question whether the rhythm threshold is finite for planar graphs remains open.     

On multiplicative graphs and the product conjecture

We study the following problem: which graphsG have the property that the class of all graphs not admitting a homomorphism intoG is closed under taking the product (conjunction)? Whether all undirected complete graphs have the property is a longstanding open problem due to S. Hedetniemi. We prove that all odd undirected cycles and all prime-power directed cycles have the property. The former result provides the first non-trivial infinite family of undirected graphs known to have the property, and the latter result verifies a conjecture of Ne?et?il and Pultr These results allow us (in conjunction with earlier results of Ne?et?il and Pultr [17], cf also [7]) to completely characterize all (finite and infinite, directed and undirected) paths and cycles having the property. We also derive the property for a wide class of 3-chromatic graphs studied by Gerards, [5].