Existence of subgraph with orthogonal (g,f)-factorization

Simple graphs are considered. Let G be a graph andg(x) andf(x) integer-valued functions defined on V(G) withg(x)⩽f(x) for everyxɛV(G). For a subgraphH ofG and a factorizationF=|F ₁,F ₂,⃛,F ₁| ofG, if |E(H)∩E(F ₁)|=1,1⩽i⩽j, then we say thatF orthogonal toH. It is proved that for an (mg(x)+k,mf(x) -k)-graphG, there exists a subgraphR ofG such that for any subgraphH ofG with |E(H)|=k,R has a (g,f)-factorization orthogonal toH, where 1⩽k<m andg(x)⩾1 orf(x)⩾5 for everyxɛV(G). Project supported by the Chitia Postdoctoral Science Foundation and Chuang Xin Foundation of the Chinese Academy of Sciences.     

(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.     

On toughness and (g, f)-factors in bipartite graphs

Let G be a bipartite graph andg and f be two positive integer-valued functions defined on vertex setV(G) ofG such thatg(x) ≤ f(x) for anyx ? V(G). In this paper, a new isolated toughness ofG is defined and some sufficient conditions related to the new toughness forG to have (g,f )-factors are obtained. Furthermore, these results are proved to be sharp in some sense.     

A New Result on Alspach's Problem

Let G be a simple graph. Let g(x) and f(x) be integer-valued functions defined on V(G) with g(x)≥2 and f(x)≥5 for all x∈V(G). It is proved that if G is an (mg+m−1, mf−m+1)-graph and H is a subgraph of G with m edges, then there exists a (g,f)-factorization of G orthogonal to H. Received: January 19, 1996 Revised: November 11, 1996     

（g, f）-Factorizations Randomly Orthogonal to a Subgraph in Graphs

Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integervalued functions defined on V(G) such that 2k - 2 ≤g(x)≤f(x) for all x∈V(G). Let H be a subgraph of G with mk edges. In this paper, it is proved that every (mg m-1,mf-m 1)-graph G has (g, f)-factorizations randomly k-orthogonal to H under some special conditions.     

Randomly Orthogonal (g,f)-factorizations in Graphs

Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integer-valued functions defined on V(G) such that 2k − 2 ≤ f(x) for all x ∈ V(G). Let H be a subgraph of G with mk edges. In this paper it is proved that every (mg + m − 1,mf − m + 1)-graph G has (g,f)-factorizations randomly k-orthogonal to H and shown that the result is best possible.     

On the Cauchy difference on normed spaces

LetX be a real linear normed space, (G, +) be a topological group, andK be a discrete normal subgroup ofG. We prove that if a continuous at a point or measurable (in the sense specified later) functionf:X →G fulfils the condition:f(x +y) -f(x) -f(y) ∈K whenever ‖x‖ = ‖y‖, then, under some additional assumptions onG,K, andX, there esists a continuous additive functionA :X →G such thatf(x) -A(x) ∈K.     

On Lie algebra decompositions related to spherical homogeneous spaces

LetG be a connected, reductive, linear algebraic group over an algebraically closed fieldk of characteristik zero. LetH ₁ andH ₂ be two spherical subgroups ofG. It is shown that for allg in a Zariski open subset ofG one has a Lie algebra decomposition g = h₁ + Adg ? h₂, where a is the Lie algebra of a torus and dim a ≤ min (rankG/H ₁,rankG/H ₂). As an application one obtains an estimate of the transcendence degree of the fieldk(G/H ₁ xG/H ₂) ^G for the diagonal action ofG. Ifk = ? andG _a is a real form ofG defined by an antiholomorphic involution σ :G→G then for a spherical subgroup H ? G and for allg in a Hausdorff open subset ofG one has a decomposition g = g_a + a Adg ? h, where a is the Lie algebra of σ-invariant torus and dim a ≤ rankG/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.     

A wavelike functional equation of Pexider type

Summary. Let (G, +) and (H, +) be abelian groups such that the equation 2u = v 2u = v is solvable in both G and H. It is shown that if f₁, f₂, f₃, f₄, : G ×G ? H f_1, f_2, f_3, f_4, : G \times G \longrightarrow H satisfy the functional equation f₁(x + t, y + s) + f₂(x - t, y - s) = f₃(x + s, y - t) + f₄(x - s, y + t) for all x, y, s, t ? G x, y, s, t \in G , then f₁, f₂, f₃, and f₄ are given by f₁ = w + h, f₂ = w - h, f₃ = w + k, f₄ = w - k where w : G ×G ? H w : G \times G \longrightarrow H is an arbitrary solution of f (x + t, y + s) + f (x - t, y - s) = f (x + s, y - t) + f (x - s, y + t) for all x, y, s, t ? G x, y, s, t \in G , and h, k : G ×G ? H h, k : G \times G \longrightarrow H are arbitrary solutions of D_y,t³g(x,y) = 0 \Delta_{y,t}^{3}g(x,y) = 0 and D_x,t³g(x,y) = 0 \Delta_{x,t}^{3}g(x,y) = 0 for all x, y, s, t ? G x, y, s, t \in G .     

A Generalization of Orthogonal Factorizations in Graphs

Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integer-valuated functions defined on V(G) such that g(x) ≤f(x) for all x∈V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤d _H (x) ≤f(x) for all x∈V(G). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let = {F ₁, F ₂, ..., F _m } be a factorization of G and H be a subgraph of G with mr edges. If F _i , 1 ≤i≤m, has exactly r edges in common with H, then is said to be r-orthogonal to H. In this paper it is proved that every (mg + kr, mf−kr)-graph, where m, k and r are positive integers with k < m and g≥r, contains a subgraph R such that R has a (g, f)-factorization which is r-orthogonal to a given subgraph H with kr edges. This research is supported by the National Natural Science Foundation of China (19831080) and RSDP of China     

Binding number and minimum degree for the existence of (g,f,n)-critical graphs

Let G be a graph of order p. The binding number of G is defined as $\mbox{bind}(G):=\min\{\frac{|N_{G}(X)|}{|X|}\mid\emptyset\neq X\subseteq V(G)\,\,\mbox{and}\,\,N_{G}(X)\neq V(G)\}$ . Let g(x) and f(x) be two nonnegative integer-valued functions defined on V(G) with g(x)≤f(x) for any x∈V(G). A graph G is said to be (g,f,n)-critical if G?N has a (g,f)-factor for each N?V(G) with |N|=n. If g(x)≡a and f(x)≡b for all x∈V(G), then a (g,f,n)-critical graph is an (a,b,n)-critical graph. In this paper, several sufficient conditions on binding number and minimum degree for graphs to be (a,b,n)-critical or (g,f,n)-critical are given. Moreover, we show that the results in this paper are best possible in some sense.     

The classification of complete graphsK n onf-coloring

Anf-coloring of a graphG=(V, E) is a coloring of edge setE such that each color appears at each vertexv ∈ V at mostf(v) times. The minimum number of colors needed tof-colorG is called thef-chromatic index χ′ _f (G) ofG. Any graphG hasf-chromatic index equal to Δ _f (G) or Δ _f (G) + 1 where $\Delta _f (G) = \mathop {\max }\limits_{v \in V} \left\{ {\left\lceil {\frac{{d(v)}}{{f(v)}}} \right\rceil } \right\}$ . If χ′ _f (G) = Δ _f (G), thenG is ofC _f 1; otherwiseG is ofC _f 2. In this paper, the classification problem of complete graphs onf-coloring is solved completely.     

Polar actions on Hilbert space

An isometricH-action on a Riemannian manifoldX is calledpolar if there exists a closed submanifoldS ofX that meets everyH-orbit and always meets orbits orthogonally (S is called a section). LetG be a compact Lie group equipped with a biinvariant metric,H a closed subgroup ofG ×G, and letH act onG isometrically by (h ₁,h ₂) ·x = h ₁ xh ₂ ⁻¹ · LetP(G, H) denote the group ofH ¹-pathsg: [0, 1] →G such that (g(0),g (1)) ∈H, and letP(G, H) act on the Hilbert spaceV = H ⁰([0, 1], g) isometrically byg * u = gug ⁻¹ −g′g ⁻¹. We prove that if the action ofH onG is polar with a flat section then the action ofP(G, H) onV is polar. Principal orbits of polar actions onV are isoparametric submanifolds ofV and are infinite-dimensional generalized real or complex flag manifolds. We also note that the adjoint actions of affine Kac-Moody groups and the isotropy action corresponding to an involution of an affine Kac-Moody group are special examples ofP(G, H)-actions for suitable choice ofH andG. Work supported partially by NSF Grant DMS 8903237 and by The Max-Planck-Institut für Mathematik in Bonn.     

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     

Automorphisms of finite groups of bounded rank

LetG be a finite group admitting an automorphismα withm fixed points. Suppose every subgroup ofG isr-generated. It is shown that (1)G has a characteristic soluble subgroupH whose index is bounded in terms ofm andr, and (2) if the orders ofα andG are coprime, then the derived length ofH is also bounded in terms ofm andr. To Professor John Thompson, in honor of his outstanding achievements     

Regular and normal closure operators and categorical compactness for groups

For a class of groupsF, closed under formation of subgroups and products, we call a subgroupA of a groupG F-regular provided there are two homomorphismsf, g: G » F, withF F, so thatA = {x G |f(x) =g(x)}.A is calledF-normal providedA is normal inG andG/A F. For an arbitrary subgroupA ofG, theF-regular (respectively,F-normal) closure ofA inG is the intersection of allF-regular (respectively,F-normal) subgroups ofG containingA. This process gives rise to two well behaved idempotent closure operators.A groupG is calledF-regular (respectively,F-normal) compact provided for every groupH, andF-regular (respectively,F-normal) subgroupA ofG × H, ₂(A) is anF-regular (respectively,F-normal) subgroup ofH. This generalizes the well known Kuratowski-Mrówka theorem for topological compactness.In this paper, theF-regular compact andF-normal compact groups are characterized for the classesF consisting of: all torsion-free groups, allR-groups, and all torsion-free abelian groups. In doing so, new classes of groups having nice properties are introduced about which little is known.     

Semigroup actions on homogeneous spaces

LetG be a connected semi-simple Lie group with finite center andS⊄G a subsemigroup with interior points. LetG/L be a homogeneous space. There is a natural action ofS onG/L. The relationx≤y ify ∈Sx, x, y ∈G/L, is transitive but not reflexive nor symmetric. Roughly, a control set is a subsetD ⊄G/L, inside of which reflexivity and symmetry for ≤ hold. Control sets are studied inG/L whenL is the minimal parabolic subgroup. They are characterized by means of the Weyl chambers inG meeting intS. Thus, for eachw ∈W, the Weyl group ofG, there is a control setD _w .D ₁ is the only invariant control set, and the subsetW(S)={w:D _w =D ₁} turns out to be a subgroup. The control sets are determined byW(S)/W. The following consequences are derived: i)S=G ifS is transitive onG/H, i.e.Sx=G/H for allx ∈G/H. HereH is a non discrete closed subgroup different fromG andG is simple. ii)S is neither left nor right reversible ifS #G iii)S is maximal only if it is the semigroup of compressions of a subset of some minimal flag manifold. Research partially supported by CNPq grant n^o 50.13.73/91-8     

Orthogonal factorizations of digraphs

Let G be a digraph with vertex set V(G) and arc set E(G) and let g = (g ⁻, g ⁺) and ƒ = (ƒ ⁻, ƒ ⁺) be pairs of positive integer-valued functions defined on V(G) such that g ⁻(x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ ƒ ⁺(x) for each x ∈ V(G). A (g, ƒ)-factor of G is a spanning subdigraph H of G such that g ⁻(x) ⩽ id _H (x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ od _H (x) ⩽ ƒ ⁺(x) for each x ∈ V(H); a (g, ƒ)-factorization of G is a partition of E(G) into arc-disjoint (g, ƒ)-factors. Let = {F ₁, F ₂,…, F _m} and H be a factorization and a subdigraph of G, respectively. is called k-orthogonal to H if each F _i , 1 ⩽ i ⩽ m, has exactly k arcs in common with H. In this paper it is proved that every (mg+m−1,mƒ−m+1)-digraph has a (g, f)-factorization k-orthogonal to any given subdigraph with km arcs if k ⩽ min{g ⁻(x), g ⁺(x)} for any x ∈ V(G) and that every (mg, mf)-digraph has a (g, f)-factorization orthogonal to any given directed m-star if 0 ⩽ g(x) ⩽ f(x) for any x ∈ V(G). The results in this paper are in some sense best possible.      

Classes caracteristiques de Γ(G,H)-structures et finitude de leur evaluation

LetG be a Lie group andH a closed subgroup ofG. We denote by (G,H) the groupoïd of germs of left translations ofG over the homogeneous spaceG/H.LetV be a compact manifold andx the universal characteristic class of dimensionk which belongs to the vector spaceH _cont ^k ((G, H)).The evaluation ofx over all the (G, H)-structures overV determines a subsetA _{(G, H)} (x, V) of the vector spaceH ^k (V;).We show that in some cases this set is finite.