Irreducible linear subgroups generated by pairs of matrices with large irreducible submodules

We call an element of a finite general linear group GL(d, q) fat if it leaves invariant and acts irreducibly on a subspace of dimension greater than d/2. Fatness of an element can be decided efficiently in practice by testing whether its characteristic polynomial has an irreducible factor of degree greater than d/2. We show that for groups G with SL(d, q) ≤ G ≤ GL(d, q) most pairs of fat elements from G generate irreducible subgroups, namely we prove that the proportion of pairs of fat elements generating a reducible subgroup, in the set of all pairs in G × G, is less than q ^−d+1. We also prove that the conditional probability to obtain a pair (g ₁, g ₂) in G × G which generates a reducible subgroup, given that g ₁, g ₂ are fat elements, is less than 2q ^−d+1. Further, we show that any reducible subgroup generated by a pair of fat elements acts irreducibly on a subspace of dimension greater than d/2, and in the induced action the generating pair corresponds to a pair of fat elements.     

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.     

On the distributive radical of an Archimedean lattice-ordered group

Let G be an Archimedean ℓ-group. We denote by G ^d and R _D (G) the divisible hull of G and the distributive radical of G, respectively. In the present note we prove the relation (R _D (G)) ^d = R _D (G ^d ). As an application, we show that if G is Archimedean, then it is completely distributive if and only if it can be regularly embedded into a completely distributive vector lattice.     

Some extremal results in cochromatic and dichromatic theory

For a graph G, the cochromatic number of G, denoted z(G), is the least m for which there is a partition of the vertex set of G having order m. where each part induces a complete or empty graph. We show that if {G_n} is a family of graphs where G_n has o(n² log²(n)) edges, then z(G_n) = o(n). We turn our attention to dichromatic numbers. Given a digraph D, the dichromatic number of D is the minimum number of parts the vertex set of D must be partitioned into so that each part induces an acyclic digraph. Given an (undirected) graph G, the dichromatic number of G, denoted d(G), is the maximum dichromatic number of all orientations of G. Let m be an integer; by d(m) we mean the minimum size of all graphs G where d(G) = m. We show that d(m) = θ(m² ln²(m)).     

Generators of Simple Lie Algebras and the Lower Rank of Some Pro-P Groups

Abstract

Let  be a simple classical Lie algebra over a field F of characteristic p > 7. We show that > d () = 2, where d() is the number of generators of . Let G be a profinite group. We say that G has lower rank ≤ l, if there are {G _α} open subgroups which from a base for the topology at the identity and each G _α is generated (topologically) by no more than l elements. There is a standard way to associate a Lie algebra L(G) to a finitely generated (filtered) pro-p group G. Suppose L(G) ?  ? tF _p [t], where  is a simple Lie algebra over F _p , the field of p elements. We show that the lower rank of G is ≤ d () + 1. We also show that if  is simple classical of rank r and p > 7 or p 2r ² ? r, then the lower rank is actually 2.     

On (p a , p b , p a , p a-b )-Relative Difference Sets

This paper provides new exponent and rank conditions for the existence of abelian relative (p ^a,p ^b,p ^a,p ^a–b)-difference sets. It is also shown that no splitting relative (2^2c,2^d,2^2c,2^2c–d)-difference set exists if d > c and the forbidden subgroup is abelian. Furthermore, abelian relative (16, 4, 16, 4)-difference sets are studied in detail; in particular, it is shown that a relative (16, 4, 16, 4)-difference set in an abelian group G Z₈ × Z₄ × Z₂ exists if and only if exp(G) 4 or G = Z₈ × (Z₂)³ with N Z₂ × Z₂.     

A degree sum condition for longest cycles in 3‐connected graphs

For a graph G, we denote by d_G(x) and κ(G) the degree of a vertex x in G and the connectivity of G, respectively. In this article, we show that if G is a 3‐connected graph of order n such that d_G(x) + d_G(y) + d_G(z) ≥ d for every independent set {x, y, z}, then G contains a cycle of length at least min{d ? κ(G), n}. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 277–283, 2007     

Bounded Direction–Length Frameworks

A direction–length framework is a pair (G,p) where G=(V;D,L) is a ‘mixed’ graph whose edges are labelled as ‘direction’ or ‘length’ edges and p is a map from V to ℝ ^d for some d. The label of an edge uv represents a direction or length constraint between p(u) and p(v). Let G ⁺ be obtained from G by adding, for each length edge e of G, a direction edge with the same end vertices as e. We show that (G,p) is bounded if and only if (G ⁺,p) is infinitesimally rigid. This gives a characterization of when (G,p) is bounded in terms of the rank of the rigidity matrix of (G ⁺,p). We use this to characterize when a mixed graph is generically bounded in ℝ ^d . As an application we deduce that if (G,p) is a globally rigid generic framework with at least two length edges and e is a length edge of G then (G∖e,p) is bounded.     

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

Root Sublattices and Torus-Restriction of Prehomogeneous Vector Spaces Associated with Dynkin Quivers

For a Dynkin quiver Γ with r vertices, a subset S of the vertices of Γ, and an r-tuple d = (d⁽¹⁾, d⁽²⁾,…, d^(r)) of positive integers, we define a “torus-restricted” representation (G_S, R _d (Γ)) in natural way. Here we put G_S = G₁ × G₂ × … ×G_r, where each G_i is either SL(d⁽ⁱ⁾) or GL(d⁽ⁱ⁾) according to S containing i or not. In this paper, for a prescribed torus-restriction S, we give a necessary and sufficient condition on d that R _d (Γ) has only finitely many G_S-orbits. This can be paraphrased as a condition whether or not d is contained in a certain lattice spanned by positive roots of Γ. We also discuss the prehomogeneity of (G_S, R _d (Γ)).     

The Number of Independent Sets in a Graph with Small Maximum Degree

Let ind(G) be the number of independent sets in a graph G. We show that if G has maximum degree at most 5 then

Linearity of Zp[[t]]-Perfect Groups

Let G be a _p[[t]]-standard group of level 1. Then G is _p[[t]]-perfect if its lower central series is given by powers of the maximal ideal (p, t), i.e. if _n(G) = G((p,t)ⁿ). We prove that a _p[[t]]-perfect group is linear by imitating the proof that a _p[[t]]-standard group is linear.     

A Finitary Version of Gromov’s Polynomial Growth Theorem

We show that for some absolute (explicit) constant C, the following holds for every finitely generated group G, and all d > 0: If there is some R ₀ > exp(exp(Cd ^C )) for which the number of elements in a ball of radius R ₀ in a Cayley graph of G is bounded by R₀^d{R_0^d} , then G has a finite-index subgroup which is nilpotent (of step < C ^d ). An effective bound on the finite index is provided if “nilpotent” is replaced by “polycyclic”, thus yielding a non-trivial result for finite groups as well.     

The Erdös-Jacobson-Lehel conjecture on potentiallyP k-graphic sequence is true

A variation in the classical Turan extrernal problem is studied. A simple graphG of ordern is said to have propertyPk if it contains a clique of sizek+1 as its subgraph. Ann-term nonincreasing nonnegative integer sequence π=(d₁, d₂,⋯, d₂) is said to be graphic if it is the degree sequence of a simple graphG of ordern and such a graphG is referred to as a realization of π. A graphic sequence π is said to be potentiallyP _k-graphic if it has a realizationG having propertyP _k . The problem: determine the smallest positive even number σ(k, n) such that everyn-term graphic sequence π=(d₁, d₂,…, d₂) without zero terms and with degree sum σ(π)=(d ₁+d ₂+ …+d ₂) at least σ(k,n) is potentially P_k-graphic has been proved positive. Project supported by the National Natural Science Foundation of China (Grant No. 19671077) and the Doctoral Program Foundation of National Education Department of China.     

Fan-type theorem for path-connectivity

A graphG is said to bek-path-connected if every pair of distinct vertices inG are joined by a path of length at leastk. We prove that if max{deg _G ^x , deg _G ^y }k for every pair of verticesx,y withd _G (x,y)=2 in a 2-connected graphG, whered _G (x,y) is the distance betweenx andy inG, thenG isk-path-connected.     

Distinguishing Cartesian powers of graphs

The distinguishing number D(G) of a graph is the least integer d such that there is a d‐labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G ≠ K₂, K₃ with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 ( 1 ), #N17] on powers of prime graphs, and results of Klav?ar and Zhu [Eu J Combin, to appear]. More generally, we also prove that d(G □ H) = 2 if G and H are relatively prime and |H| ≤ |G| < 2^|H| ? |H|. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 250–260, 2006     

Involutory Automorphisms of Groups of Odd Order

The following theorem is proved. Let G be a finite group of odd order admitting an involutory automorphism φ. Suppose that G has derived length d and that C_G(φ) is nilpotent of class c. Assume that C_G(φ) is a m-generator. Then [G,φ]^′ is nilpotent of {c,d,m}-bounded class.     

Strong Arens irregularity of Beurling algebras with a locally convex topology

Let G be a locally compact group with a weight function ω. Recently, we have shown that the Banach space L₀^∞ (G,1/ω) can be identified with the strong dual of L¹(G, ω)equipped with some locally convex topologies τ. Here we use this duality to introduce an Arens multiplication on (L¹(G, ω), τ)**, and prove that the topological center of (L¹(G, ω), τ)** is (L¹(G, ω); this enables us to conclude that (L¹(G, ω), τ) is Arens regular if and only if G is discrete. We also give a characterization for Arens regularity of L₀^∞ (G, 1/ω)¹. Received: 8 March 2005     

Isometric cycles,cutsets, and crowning of bridged graphs

A graph G is bridged if every cycle C of length at least 4 has vertices x,y such that d_G(x,y) < d_C(x,y). A cycle C is isometric if d_G(x,y) = d_C(x,y) for all x,y ∈ V(C). We show that every graph contractible to a graph with girth g has an isometric cycle of length at least g. We use this to show that every minimal cutset S in a bridged graph G induces a connected subgraph. We introduce a “crowning” construction to enlarge bridged graphs. We use this to construct examples showing that for every connected simple graph H with girth at least 6 (including trees), there exists a bridged graph G such that G has a unique minimum cutset S and that G[S] = H. This provides counterexamples to Hahn's conjecture that d_G(u,v) ≤ 2 when u and v lie in a minimum cutset in a bridged graph G. We also study the convexity of cutsets in bridged graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 161–170, 2003     

Irredundance in inflated graphs

The inflation G_I of a graph G with n(G) vertices and m(G) edges is obtained by replacing every vertex of degree d of G by a clique K_d. We study the lower and upper irredundance parameters ir and IR of an inflation. We prove in particular that if γ denotes the domination number of a graph, γ(G_I) − ir(G_I) can be arbitrarily large, IR(G_I) ≤ m(G) and IR(G_I) ≤ n²(G)/4. These results disprove a conjecture of Dunbar and Haynes (Congr. Num. 118 (1996), 143–154) and answer another open question. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 97–104, 1998