Lower degree bounds for modular invariants and a question of I. Hughes

We prove two statements. The first one is a conjecture of Ian Hughes which states that iff ₁, ..., f_n are primary invariants of a finite linear groupG, then the least common multiple of the degrees of thef _i is a multiple of the exponent ofG.The second statement is about vector invariants: IfG is a permutation group andK a field of positive characteristicp such thatp divides |G|, then the invariant ringK[V ^m]^G ofm copies of the permutation moduleV overK requires a generator of degreem(p–1). This improves a bound given by Richman [6], and implies that there exists no degree bound for the invariants ofG that is independent of the representation.     

(g,f)-Factorizations of graphs orthogonal to [1,2]-subgraph

LetG be a simple graph. Letg(x) andf(x) be integer-valued functions defined onV(G) withf(x)g(x)1 for allxV(G). It is proved that ifG is an (mg+m–1,mf–m+1)-graph andH is a [1,2]-subgraph withm edges, then there exists a (g,f)-factorization ofG orthogonal toH.This work is supported by China Postdoctoral Science Foundation and Shandong Youth Science Foundation.     

Pseudodifferential Operators on Prehomogeneous Vector Spaces

ABSTRACT

Let G be a connected, linear algebraic group defined over ?, acting regularly on a finite dimensional vector space V over ? with ?-structure V _?. Assume that V possesses a Zariski-dense orbit, so that (G, ?, V) becomes a prehomogeneous vector space over ?. We consider the left regular representation π of the group of ?-rational points G _? on the Banach space C₀(V _?) of continuous functions on V _? vanishing at infinity, and study the convolution operators π(f), where f is a rapidly decreasing function on the identity component of G _?. Denote the complement of the dense orbit by S, and put S _? = S ∩ V _?. It turns out that, on V _? ? S _?, π(f) is a smooth operator. If S _? = {0}, the restriction of the Schwartz kernel of π(f) to the diagonal defines a homogeneous distribution on V _? ? {0}. Its nonunique extension to V _? can then be regarded as a trace of π(f). If G is reductive, and S and S _? are irreducible hypersurfaces, π(f) corresponds, on each connected component of V _? ? S _?, to a totally characteristic pseudodifferential operator. In this case, the restriction of the Schwartz kernel of π(f) to the diagonal defines a distribution on V _? ? S _? given by some power |p(m)| ^s of a relative invariant p(m) of (G, ?, V) and, as a consequence of the Fundamental Theorem of Prehomogeneous Vector Spaces, its extension to V _?, and the complex s-plane, satisfies functional equations similar to those for local zeta functions. A trace of π(f) can then be defined by subtracting the singular contributions of the poles of the meromorphic extension.     

Intrinsic metric preserving maps on partially ordered groups

In [11] Pap proved that a surjective mapf from an abelian lattice ordered groupG ₁ onto an abelian Archimedean lattice ordered group G₂ which preserves non-zero intrinsic metricsd ₁, andd ₂ onG ₁ andG ₂, respectively (i.e.d ₁(x,y)=d₁(z, t) implies d₂(f(x)f(y))= d₂(f(z),f(t))) and satisfiesf(0)=0 is a homomorphism and put the question whether that assertion is true in the case that G₂ is a non-Archimedean lattice ordered group. In this paper it is proved that a surjective map from an abelian directedG ₁ onto a directed group G₂ such thatf(0)=0 is a homomorphism if ¦x –y ¦=¦z – t¦ implies ¦f(x) –f(y)¦=¦f(z) –f(t)¦ and it is shown that the answer to the question of Pap is positive.Presented by M. Henriksen.     

Decomposition of Graphs into (g, f)-Factors

Let G be a multigraph, g and f be integer-valued functions defined on V(G). Then a graph G is called a (g, f)-graph if g(x)≤deg _G(x)≤f(x) for each x∈V(G), and a (g, f)-factor is a spanning (g, f)-subgraph. If the edges of graph G can be decomposed into (g, f)-factors, then we say that G is (g, f)-factorable. In this paper, we obtained some sufficient conditions for a graph to be (g, f)-factorable. One of them is the following: Let m be a positive integer, l be an integer with l=m (mod 4) and 0≤l≤3. If G is an -graph, then G is (g, f)-factorable. Our results imply several previous (g, f)-factorization results. Revised: June 11, 1998     

P-amenable locally compact groups

LetG denote a locally compact group andP(G) [P _c (G)] the topological semigroup of absolutely continuous [absolutely continuous and compactly supported] probability measures onG. We say thatG isP-amenable [P _c -amenable] if the topological semigroupP(G)[P _c (G)] is amenable. Some combinatorial properties of this class of groups are studied. The relationship between amenability andP-amenability ofG is investigated. It is shown that for a connected solvableP _c -amenable groupG, G has polynomial growth if, and only if,P _c (S)={fP _c (G)suppfS} is amenable for any open subsemigroupS ofG.This paper contains a part of the author's doctoral thesis at the State University of New York at Albany. The author wishes to thank ProfessorJoe Jenkins for his valuable suggestions and encouragement during the course of this work.     

On the asymptotic directions of thes-dimensional optimum gradient method

The optimums-gradient method for minimizing a positive definite quadratic functionf(x) onE _n has long been known to converge fors ≧+1. For theses the author studies the directions from which the iteratesx _k approach their limit, and extends tos>1 a theory proved byAkaike fors=1. It is shown thatf (x _k ) can never converge to its minimum value faster than linearly, except in degenerate cases where it attains the minimum in one step. Research sponsored by the U.S. Office of Naval Research under project NR 044211. Dedicated to ProfessorHeinrich Brinkmann for his seventieth birthday.     

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.     

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     

Large Vertex-Disjoint Cycles in a Bipartite Graph

Let s≥2 and k be two positive integers. Let G=(V ₁,V ₂;E) be a bipartite graph with |V ₁|=|V ₂|=n≥s k and the minimum degree at least (s−1)k+1. When s=2 and n >2k, it is proved in [5] that G contains k vertex-disjoint cycles. In this paper, we show that if s≥3, then G contains k vertex-disjoint cycles of length at least 2s. Received: March 2, 1998 Revised: October 26, 1998     

Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints

We consider a canonical Ramsey type problem. An edge‐coloring of a graph is called m‐good if each color appears at most m times at each vertex. Fixing a graph G and a positive integer m, let f(m, G) denote the smallest n such that every m‐good edge‐coloring of K_n yields a properly edge‐colored copy of G, and let g(m, G) denote the smallest n such that every m‐good edge‐coloring of K_n yields a rainbow copy of G. We give bounds on f(m, G) and g(m, G). For complete graphs G = K_t, we have c₁mt²/ln t ≤ f(m, K_t) ≤ c₂mt², and cmt³/ln t ≤ g(m, K_t) ≤ cmt³/ln t, where c₁, c₂, c, c are absolute constants. We also give bounds on f(m, G) and g(m, G) for general graphs G in terms of degrees in G. In particular, we show that for fixed m and d, and all sufficiently large n compared to m and d, f(m, G) = n for all graphs G with n vertices and maximum degree at most d. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

On the set of discrete subgroups of bounded covolume in a semisimple group

In this noteG is a locally compact group which is the product of finitely many groups G_s(k_s)(s∈S), where k_s is a local field of characteristic zero and G_s an absolutely almost simplek _s-group, ofk _s-rank ≥1. We assume that the sum of the r_s is ≥2 and fix a Haar measure onG. Then, given a constantc > 0, it is shown that, up to conjugacy,G contains only finitely many irreducible discrete subgroupsL of covolume ≥c (4.2). This generalizes a theorem of H C Wang for real groups. His argument extends to the present case, once it is shown thatL is finitely presented (2.4) and locally rigid (3.2).     

Balanced decomposition of a vertex-colored graph

A balanced vertex-coloring of a graph G is a function c from V(G) to {−1,0,1} such that ∑{c(v):v∈V(G)}=0. A subset U of V(G) is called a balanced set if U induces a connected subgraph and ∑{c(v):v∈U}=0. A decomposition V(G)=V₁∪?∪V_r is called a balanced decomposition if V_i is a balanced set for 1≤i≤r.In this paper, the balanced decomposition number f(G) of G is introduced; f(G) is the smallest integer s such that for any balanced vertex-coloring c of G, there exists a balanced decomposition V(G)=V₁∪?∪V_r with |V_i|≤s for 1≤i≤r. Balanced decomposition numbers of some basic families of graphs such as complete graphs, trees, complete bipartite graphs, cycles, 2-connected graphs are studied.     

Signed 2-independence in graphs

A function f : V→{−1,1} defined on the vertices of a graph G=(V,E) is a signed 2-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every vV, f(N[v])1, where N[v] consists of v and every vertex adjacent to v. The weight of a signed 2-independence function is f(V)=∑f(v), over all vertices vV. The signed 2-independence number of a graph G, denoted α_s²(G), equals the maximum weight of a signed 2-independence function of G. In this paper, we establish upper bounds for α_s²(G) in terms of the order and size of the graph, and we characterize the graphs attaining these bounds. For a tree T, upper and lower bounds for α_s²(T) are established and the extremal graphs characterized. It is shown that α_s²(G) can be arbitrarily large negative even for a cubic graph G.     

Weakly symmetric spaces and bounded symmetric domains

LetG be a connected, simply-connected, real semisimple Lie group andK a maximal compactly embedded subgroup ofG such thatD=G/K is a hermitian symmetric space. Consider the principal fiber bundleM=G/K _s G/K, whereK _s is the semisimple part ofK=K _s ·Z _K ⁰ andZ _K ⁰ is the connected center ofK. The natural action ofG onM extends to an action ofG ¹=G×Z _K ⁰ . We prove as the main result thatM is weakly symmetric with respect toG ¹ and complex conjugation. In the case whereD is an irreducible classical bounded symmetric domain andG is a classical matrix Lie group under a suitable quotient, we provide an explicit construction ofM=D×S ¹ and determine a one-parameter family of Riemannian metrics onM invariant underG ¹. Furthermore,M is irreducible with respect to . As a result, this provides new examples of weakly symmetric spaces that are nonsymmetric, including those already discovered by Selberg (cf. [M]) for the symplectic case and Berndt and Vanhecke [BV1] for the rank-one case.Research partially supported by an NSF grant. The author wishes to thank the International Erwin Schroedinger Institute for its hospitality during the preparation of this paper.     

Galerkin method and optimal error algorithms in hilbert spaces

Summary We consider operator equations of the formLu=f, whereL belongs to the class of linear, bounded (by a constantM) and coercive (with a constantm) operators from a Hilbert spaceV onto its dualV ^* andf belongs to a Hilbert spaceWV ^*. We study optimality of the Galerkin methodP _n ^* Lu _n =P _n ^* f, whereu _n V _n ,V _n is subspace ofV, P _n is the orthogonal projector ontoV _n andP _n ^* is dual toP _n . We show that the Galerkin method is quasi optimal independently of the choice of the subspaceV _n and the spaceW ifM>m. In the caseM=m, optimality of the method depends strongly on the choice ofV _n andW. Therefore we define a new algorithm which is always optimal (independently of the choice ofV _n andW and relations betweenM andm).     

(g, f)-factorizations orthogonal to a subgraph in graphs

LetG be a graph with vertex setV (G) and edge setE (G), and letg andf be two integer-valued functions defined on V(G) such thatg(x)⩽(x) for every vertexx ofV(G). It was conjectured that ifG is an (mg +m - 1,mf -m+1)-graph andH a subgraph ofG withm edges, thenG has a (g,f)-factorization orthogonal toH. This conjecture is proved affirmatively. Project supported by the National Natural Science Foundation of China.     

A lower bound on the total signed domination numbers of graphs

Let G be a finite connected simple graph with a vertex set V(G)and an edge set E(G). A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1}.The weight of f is W(f)=∑_(x∈V)(G)∪E(G))f(X).For an element x∈V(G)∪E(G),we define f[x]=∑_(y∈NT[x])f(y).A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1} such that f[x]≥1 for all x∈V(G)∪E(G).The total signed domination numberγ_s~*(G)of G is the minimum weight of a total signed domination function on G. In this paper,we obtain some lower bounds for the total signed domination number of a graph G and compute the exact values ofγ_s~*(G)when G is C_n and P_n.     

Convolution quotients of nonnegative functions

LetG be a locally compact commutative Hausdorff group andf a function belonging toL ₁(G). If the integral off with respect to the Haar measure is positive, then one can find a nonnegative (not identically 0) functiong such that the convolution off andg is also nonnegative.     

Embedding Semigroups with Associate Subgroups into Semidirect Products

A semigroup S is said to have an associate subgroup G if, for each s ∈ S, there is a unique s* ∈ G such that ss*s = s. If the identity 1 _G of G is medial, i.e., c1 _G c = c holds for each c being a product of idempotents, we show that S is isomorphic to a certain subsemigroup of a semidirect product of an idempotent generated semigroup C by G. If additionally S is orthodox, we may choose C to be a band, belonging to the band variety, generated by the band of idempotents of S.