Graphs of actions on R-trees

LetG be a finitely generated group acting on anR-treeT. First assume that the action is free, and minimal (there is no proper invariant subtree), or more generally that it satisfies a certain finiteness condition. Then it may be described as agraph of transitive actions: the action may be recovered from a finite graph, together with additional data; in particular, every vertexv carries an action (G _v, T_v) whose orbits are dense. For the action (G, T), it follows for instance that the closure of any orbit is a discrete union of closed subtrees: it cannot meet a segment in a Cantor set. Now let ℓ be the length function for an arbitrary action ofG. For ɛ>0 small enough, the subgroupG(ɛ)⊂G generated by elementsg withg is independent of ɛ, andG/G(ɛ) is free. Several interpretations are given for the rank ofG/G(ɛ).     

Super Connectivity of Line Graphs and Digraphs

The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.     

Bounds on smooth matrix coefficients on L 2-spaces

Let G be a semisimple Lie group with a finite number of connected components and a finite center. Let K be a maximal compact subgroup. Let X be a smooth G-space equipped with a G-invariant measure. In this paper, we give upper bounds for K-finite and ${\mathfrak k}Let G be a semisimple Lie group with a finite number of connected components and a finite center. Let K be a maximal compact subgroup. Let X be a smooth G-space equipped with a G-invariant measure. In this paper, we give upper bounds for K-finite and \mathfrak k{\mathfrak k}-smooth matrix coefficients of the regular representation L ²(X) under an assumption about supp(L²(X)) ?[^(G)]_K{{\rm supp}(L^2(X)) \cap \hat G_K}. Furthermore, we show that this bound holds for unitary representations that are weakly contained in L ²(X). Our result generalizes a result of Cowling–Haagerup–Howe (J Reine Angew Math 387:97–110, 1988). As an example, we discuss the matrix coefficients of the O(p, q) representation L²(\mathbbR^p+q){L^2(\mathbb{R}^{p+q})}.     

Choosability of graphs with infinite sets of forbidden differences

The notion of the list-T-coloring is a common generalization of the T-coloring and the list-coloring. Given a set of non-negative integers T, a graph G and a list-assignment L, the graph G is said to be T-colorable from the list-assignment L if there exists a coloring c such that the color c(v) of each vertex v is contained in its list L(v) and |c(u)-c(v)|∉T for any two adjacent vertices u and v. The T-choice number of a graph G is the minimum integer k such that G is T-colorable for any list-assignment L which assigns each vertex of G a list of at least k colors.We focus on list-T-colorings with infinite sets T. In particular, we show that for any fixed set T of integers, all graphs have finite T-choice number if and only if the T-choice number of K₂ is finite. For the case when the T-choice number of K₂ is finite, two upper bounds on the T-choice number of a graph G are provided: one being polynomial in the maximum degree of the graph G, and the other being polynomial in the T-choice number of K₂.     

On the centralizer ofK in the universal enveloping algebra of SO(n,1) and SU(n,1)

LetG _o be a non compact real semisimple Lie group with finite center, and letU U(g) ^K denote the centralizer inU U(g) of a maximal compact subgroupK _o ofG _o. To study the algebraU U(g) ^K , B. Kostant suggested to consider the projection mapP:U U(g)→U(k)⊗U(a), associated to an Iwasawa decompositionG _o=K _o A _o N _o ofG _o, adapted toK _o. WhenP is restricted toU U(g) ^K J. Lepowsky showed thatP becomes an injective anti-homomorphism ofU U(g) ^K intoU(k) ^M ⊗U(a). HereU(k) ^M denotes the centralizer ofM _o inU(k),M _o being the centralizer ofA _o inK _o. To pursue this idea further it is necessary to have a good characterization of the image ofU U(g) ^K inU(k)^M×U(a). In this paper we describe such image whenG _o=SO(n,1)_e or SU(n,1). This is acomplished by establishing a (minimal) set of equations satisfied by the elements in the image ofU U(g) ^K , and then proving that they are enough to characterize such image. These equations are derived on one hand from the intertwining relations among the principal series representations ofG _o given by the Kunze-Stein interwining operators, and on the other hand from certain imbeddings among Verma modules. This approach should prove to be useful to attack the general case. Supported in part by Fundación Antorchas     

Set vertex colorings and joins of graphs

For a nontrivial connected graph G, let c: V (G) → ℕ be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v of G, the neighborhood color set NC(v) is the set of colors of the neighbors of v. The coloring c is called a set coloring if NC(u) ≠ NC(v) for every pair u, v of adjacent vertices of G. The minimum number of colors required of such a coloring is called the set chromatic number x _s (G). A study is made of the set chromatic number of the join G+H of two graphs G and H. Sharp lower and upper bounds are established for x _s (G + H) in terms of x _s (G), x _s (H), and the clique numbers ω(G) and ω(H).     

The Sigma Chromatic Number of a Graph

For a nontrivial connected graph G, let ${c: V(G)\to {{\mathbb N}}}For a nontrivial connected graph G, let c: V(G)? \mathbb N{c: V(G)\to {{\mathbb N}}} be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.     

Tame comodule type,roiter bocses,and a geometry context for coalgebras

We study the class of coalgebras C of fc-tame comodule type introduced by the author. With any basic computable K-coalgebra C and a bipartite vector v = (v′|v″) ∈ K ₀(C) × K ₀(C), we associate a bimodule matrix problem Mat ^v _C (ℍ), an additive Roiter bocs B ^C _v , an affine algebraic K-variety Comod ^C _v , and an algebraic group action G ^C _v × Comod ^C _v → Comod ^C _v . We study the fc-tame comodule type and the fc-wild comodule type of C by means of Mat ^v _C (ℍ), the category rep _K (B ^C _v ) of K-linear representations of B ^C _v , and geometry of G ^C _v -orbits of Comod ^C _v . For computable coalgebras C over an algebraically closed field K, we give an alternative proof of the fc-tame-wild dichotomy theorem. A characterization of fc-tameness of C is given in terms of geometry of G ^C _v -orbits of Comod _v . In particular, we show that C is fc-tame of discrete comodule type if and only if the number of G ^C _v -orbits in Comod ^C _v is finite for every v = (v′|v″) ∈ K ₀(C) × K ₀(C).     

List Point Arboricity of Dense Graphs

Let G be a simple graph. The point arboricity ρ(G) of G is defined as the minimum number of subsets in a partition of the point set of G so that each subset induces an acyclic subgraph. The list point arboricity ρ _l (G) is the minimum k so that there is an acyclic L-coloring for any list assignment L of G which |L(v)| ≥ k. So ρ(G) ≤ ρ _l (G) for any graph G. Xue and Wu proved that the list point arboricity of bipartite graphs can be arbitrarily large. As an analogue to the well-known theorem of Ohba for list chromatic number, we obtain ρ _l (G + K _n ) = ρ(G + K _n ) for any fixed graph G when n is sufficiently large. As a consequence, if ρ(G) is close enough to half of the number of vertices in G, then ρ _l (G) = ρ(G). Particularly, we determine that , where K _2(n) is the complete n-partite graph with each partite set containing exactly two vertices. We also conjecture that for a graph G with n vertices, if then ρ _l (G) = ρ(G). Research supported by NSFC (No.10601044) and XJEDU2006S05.     

Unique ergodicity of flows on homogeneous spaces

LetG be a unimodular Lie group, Γ a co-compact discrete subgroup ofG and ‘a’ a semisimple element ofG. LetT _a be the mapgΓ →ag Γ:G/Γ →G/Γ. The following statements are pairwise equivalent: (1) (T _a, G/Γ,θ) is weak-mixing. (2) (T _a, G/Γ) is topologically weak-mixing. (3) (G ^u, G/Γ) is uniquely ergodic. (4) (G ^u, G/Γ,θ) is ergodic. (5) (G ^u, G/Γ) is point transitive. (6) (G ^u, G/Γ) is minimal. If in additionG is semisimple with finite center and no compact factors, then the statement “(T _a, G/Γ,θ) is ergodic” may be added to the above list. The authors were partially supported by NSF grant MCS 75-05250.     

A Note on L（2, 1）-labelling of Trees

An L(2,1)-labelling of a graph G is a function from the vertex set V (G) to the set of all nonnegative integers such that |f(u) f(v)| ≥ 2 if d G (u,v)=1 and |f(u) f(v)| ≥ 1 if d G (u,v)=2.The L(2,1)-labelling problem is to find the smallest number,denoted by λ(G),such that there exists an L(2,1)-labelling function with no label greater than it.In this paper,we study this problem for trees.Our results improve the result of Wang [The L(2,1)-labelling of trees,Discrete Appl.Math.154 (2006) 598-603].     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

On signed distance-k-domination in graphs

The signed distance-k-domination number of a graph is a certain variant of the signed domination number. If v is a vertex of a graph G, the open k-neighborhood of v, denoted by N _k (v), is the set N _k (v) = {u: u ≠ v and d(u, v) ⩽ k}. N _k [v] = N _k (v) ⋃ {v} is the closed k-neighborhood of v. A function f: V → {−1, 1} is a signed distance-k-dominating function of G, if for every vertex . The signed distance-k-domination number, denoted by γ _k,s (G), is the minimum weight of a signed distance-k-dominating function on G. The values of γ _2,s (G) are found for graphs with small diameter, paths, circuits. At the end it is proved that γ _2,s (T) is not bounded from below in general for any tree T.     

On quasi-similarity of subnormal operators

For a compact subset K in the complex plane, let Rat(K) denote the set of the rational functions with poles off K. Given a finite positive measure with support contained in K, let R2(K,v) denote the closure of Rat(K) in L2(v) and let Sv denote the operator of multiplication by the independent variable z on R2(K, v), that is, Svf = zf for every f∈R2(K, v). SupposeΩis a bounded open subset in the complex plane whose complement has finitely many components and suppose Rat(Ω) is dense in the Hardy space H2(Ω). Letσdenote a harmonic measure forΩ. In this work, we characterize all subnormal operators quasi-similar to Sσ, the operators of the multiplication by z on R2(Ω,σ). We show that for a given v supported onΩ, Sv is quasi-similar to Sσif and only if v/■Ω■σ and log(dv/dσ)∈L1(σ). Our result extends a well-known result of Clary on the unit disk.     

Possible limit laws for entrance times of an ergodic aperiodic dynamical system

LetG denote the set of decreasingG: ℝ→ℝ withGэ1 on ]−∞,0], and ƒ ₀ ^∞ G(t)dt⩽1. LetX be a compact metric space, andT: X→X a continuous map. Let μ denone aT-invariant ergodic probability measure onX, and assume (X, T, μ) to be aperiodic. LetU⊂X be such that μ(U)>0. Let τ _U (x)=inf{k⩾1:T ^k xεU}, and defineG _U (t)=1/u(U)u({xεU:u(U)τU(x)>t),tεℝ We prove that for μ-a.e.x∈X, there exists a sequence (U _n ) _n≥1 of neighbourhoods ofx such that {x}=∩ _n U _n , and for anyG ∈G, there exists a subsequence (n _k ) _k≥1 withG _{U n k} ↑U weakly. We also construct a uniquely ergodic Toeplitz flowO(x ^∞,S, μ), the orbit closure of a Toeplitz sequencex ^∞, such that the above conclusion still holds, with moreover the requirement that eachU _n be a cylinder set. In memory of Anzelm Iwanik     

The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

Lacunary Fourier series and a qualitative uncertainty principle for compact Lie groups

We define lacunary Fourier series on a compact connected semisimple Lie group G. If f ∈ L ¹(G) has lacunary Fourier series and f vanishes on a non empty open subset of G, then we prove that f vanishes identically. This result can be viewed as a qualitative uncertainty principle.     

Real loci of based loop groups

Let (G, K) be a Riemannian symmetric pair of maximal rank, where G is a compact simply connected Lie group and K is the fixed point set of an involutive automorphism σ. This induces an involutive automorphism τ of the based loop space Ω(G). There exists a maximal torus T ⊂ G such that the canonical action of T × S ¹ on Ω(G) is compatible with τ (in the sense of Duistermaat). This allows us to formulate and prove a version of Duistermaat’s convexity theorem. Namely, the images of Ω(G) and Ω(G) ^τ (fixed point set of τ) under the T × S ¹ moment map on Ω(G) are equal. The space Ω(G) ^τ is homotopy equivalent to the loop space Ω(G/K) of the Riemannian symmetric space G/K. We prove a stronger form of a result of Bott and Samelson which relates the cohomology rings with coefficients in \mathbbZ₂ {\mathbb{Z}_2} of Ω(G) and Ω(G/K). Namely, the two cohomology rings are isomorphic, by a degree-halving isomorphism (Bott and Samelson [BS] had proved that the Betti numbers are equal). A version of this theorem involving equivariant cohomology is also proved. The proof uses the notion of conjugation space in the sense of Hausmann, Holm, and Puppe [HHP].     

On the Connection Between the Projection and the Extension of a Parallelotope

This paper presents a result concerning the connection between the parallel projection P _v,H of a parallelotope P along the direction v (into a transversal hyperplane H) and the extension P + S(v), meaning the Minkowski sum of P and the segment S(v) = {λv | −1 ≤ λ ≤ 1}. A sublattice L _v of the lattice of translations of P associated to the direction v is defined. It is proved that the extension P + S(v) is a parallelotope if and only if the parallel projection P _v,H is a parallelotope with respect to the lattice of translations L _v,H , which is the projection of the lattice L _v along the direction v into the hyperplane H.     

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.