Packing Non-Zero A-Paths In Group-Labelled Graphs

Let G=(V,E) be an oriented graph whose edges are labelled by the elements of a group Γ and let A⊂V. An A-path is a path whose ends are both in A. The weight of a path P in G is the sum of the group values on forward oriented arcs minus the sum of the backward oriented arcs in P. (If Γ is not abelian, we sum the labels in their order along the path.) We are interested in the maximum number of vertex-disjoint A-paths each of non-zero weight. When A = V this problem is equivalent to the maximum matching problem. The general case also includes Mader's S-paths problem. We prove that for any positive integer k, either there are k vertex-disjoint A-paths each of non-zero weight, or there is a set of at most 2k −2 vertices that meets each of the non-zero A-paths. This result is obtained as a consequence of an exact min-max theorem. These results were obtained at a workshop on Structural Graph Theory at the PIMS Institute in Vancouver, Canada. This research was partially conducted during the period the first author served as a Clay Mathematics Institute Long-Term Prize Fellow.     

Path-closed sets

Given a digraphG = (V, E), call a node setT ⊆V path-closed ifv, v′ εT andw εV is on a path fromv tov′ impliesw εT. IfG is the comparability graph of a posetP, the path-closed sets ofG are the convex sets ofP. We characterize the convex hull of (the incidence vectors of) all path-closed sets ofG and its antiblocking polyhedron inR ^v , using lattice polyhedra, and give a minmax theorem on partitioning a given subset ofV into path-closed sets. We then derive good algorithms for the linear programs associated to the convex hull, solving the problem of finding a path-closed set of maximum weight sum, and prove another min-max result closely resembling Dilworth’s theorem.     

Path extendable graphs

A pathP in a graphG is said to beextendable if there exists a pathP’ inG with the same endvertices asP such thatV(P)⊆V (P’) and |V(P’)|=|V(P)|+1. A graphG ispath extendable if every nonhamiltonian path inG is extendable. We investigate the extent to which known sufficient conditions for a graph to be hamiltonian-connected imply the extendability of paths in the graph. Several theorems are proved: for example, it is shown that ifG is a graph of orderp in which the degree sum of each pair of non-adjacent vertices is at leastp+1 andP is a nonextendable path of orderk inG thenk≤(p+1)/2 and 〈V (P)〉≅K _k orK _k −e. As corollaries of this we deduce that if δ(G)≥(p+2)/2 or if the degree sum of each pair of nonadjacent vertices inG is at least (3p−3)/2 thenG is path extendable, which strengthen results of Williamson [13].     

Up–down representations and ergodic theory in nilpotent Lie groups

Let G be a connected and simply connected nilpotent Lie group and A a closed connected subgroup of G. Let Γ be a discrete cocompact subgroup of G. In the first part of this paper we give the direct integral decomposition of the up–down representation . As a consequence, we establish a necessary and sufficient condition for A to act ergodically on G/Γ in the case when Γ is a lattice subgroup of G and A is a one-parameter subgroup of G.     

Maximum andk-th maximal spanning trees of a weighted graph

LetA be a maximum spanning tree andP be an arbitrary spanning tree of a connected weighted graphG. Then we prove that there exists a bijectionψ fromA/P intoP/A such that for any edgea∈A/P, (P/ψ(a)) ∪a is a spanning tree ofG whose weight is greater than or equal to that ofP. We apply this theorem to some problems concerning spanning trees of a weighted graph.     

Distribution of lattice orbits on homogeneous varieties

Given a lattice Γ in a locally compact group G and a closed subgroup H of G, one has a natural action of Γ on the homogeneous space V = H\ G. For an increasing family of finite subsets {Γ _T : T > 0}, a dense orbit υ· Γ, υ∈V and compactly supported function φ on V, we consider the sums . Understanding the asymptotic behavior of S _φ,υ (T) is a delicate problem which has only been considered for certain very special choices of H,G and {Γ _T }. We develop a general abstract approach to the problem, and apply it to the case when G is a Lie group and either H or G is semisimple. When G is a group of matrices equipped with a norm, we have where G _T = {g ∈G: ||g|| < T} and Γ _T = G _T ∩ Γ. We also show that the asymptotics of S _{φ, υ} (T) is governed by where ν is an explicit limiting density depending on the choice of υ and || · ||. Submitted: March 2005 Revision: April 2006 Accepted: June 2006     

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.     

Fitting Height and Character Degree Graphs

Given a group G, Γ(G) is the graph whose vertices are the primes that divide the degree of some irreducible character and two vertices p and q are joined by an edge if pq divides the degree of some irreducible character of G. By a definition of Lewis, a graph Γ has bounded Fitting height if the Fitting height of any solvable group G with Γ(G)=Γ is bounded (in terms of Γ). In this note, we prove that there exists a universal constant C such that if Γ has bounded Fitting height and Γ(G)=Γ then h(G)≤C. This solves a problem raised by Lewis. Research supported by the Spanish Ministerio de Educación y Ciencia, MTM2004-06067-C02-01 and MTM2004-04665, the FEDER and Programa Ramón y Cajal.     

Affinely equivalent complete flat manifolds

Let E _Aff(Γ,G, m) be the set of affine equivalence classes of m-dimensional complete flat manifolds with a fixed fundamental group Γ and a fixed holonomy group G. Let n be the dimension of a closed flat manifold whose fundamental group is isomorphic to Γ. We describe E _Aff(Γ,G, m) in terms of equivalence classes of pairs (ε, ρ), consisting of epimorphisms of Γ onto G and representations of G in ℝ ^m-n . As an application we give some estimates of card E _Aff(Γ,G, m).     

Schwarz operators of minimal surfaces spanning polygonal boundary curves

This paper examines the Schwarz operator A and its relatives Ȧ, Ā and Ǡ that are assigned to a minimal surface X which maps consequtive arcs of the boundary of its parameter domain onto the straight lines which are determined by pairs P _j , P _j+1 of two adjacent vertices of some simple closed polygon . In this case X possesses singularities in those boundary points which are mapped onto the vertices of the polygon Γ. Nevertheless it is shown that A and its closure Ā have essentially the same properties as the Schwarz operator assigned to a minimal surface which spans a smooth boundary contour. This result is used by the author to prove in [Jakob, Finiteness of the set of solutions of Plateau’s problem for polygonal boundary curves. I.H.P. Analyse Non-lineaire (in press)] the finiteness of the number of immersed stable minimal surfaces which span an extreme simple closed polygon Γ, and in [Jakob, Local boundedness of the set of solutions of Plateau’s problem for polygonal boundary curves (in press)] even the local boundedness of this number under sufficiently small perturbations of Γ.     

Logarithm laws for flows on homogeneous spaces

In this paper we generalize and sharpen D. Sullivan’s logarithm law for geodesics by specifying conditions on a sequence of subsets {A _t  | t∈ℕ} of a homogeneous space G/Γ (G a semisimple Lie group, Γ an irreducible lattice) and a sequence of elements f _t of G under which #{t∈ℕ | f _t x∈A _t } is infinite for a.e. x∈G/Γ. The main tool is exponential decay of correlation coefficients of smooth functions on G/Γ. Besides the general (higher rank) version of Sullivan’s result, as a consequence we obtain a new proof of the classical Khinchin-Groshev theorem on simultaneous Diophantine approximation, and settle a conjecture recently made by M. Skriganov. Oblatum 27-VII-1998 & 2-IV-1999 / Published online: 5 August 1999     

On a graph related to permutability in finite groups

For a finite group G we define the graph Γ(G) to be the graph whose vertices are the conjugacy classes of cyclic subgroups of G and two conjugacy classes ${\mathcal {A}, \mathcal {B}}For a finite group G we define the graph Γ(G) to be the graph whose vertices are the conjugacy classes of cyclic subgroups of G and two conjugacy classes A, B{\mathcal {A}, \mathcal {B}} are joined by an edge if for some A ? A, B ? B A{A \in \mathcal {A},\, B \in \mathcal {B}\, A} and B permute. We characterise those groups G for which Γ(G) is complete.     

A Higgs bundle on a Hermitian symmetric space,II

Let M : = Γ\G/K be the quotient of an irreducible Hermitian symmetric space G/K by a torsionfree cocompact lattice G ì G{\Gamma \subset G}. Let V be a complex irreducible representation of G. We give a Hodge decomposition of the cohomology of the Γ-module V in terms of the cohomologies of automorphic vector bundles on M associated to the Lie algebra cohomologies H*(\mathfrak p⁺ ,V){H*({\mathfrak p}^{+} ,V)}.     

Divergent trajectories and ℚ-rank

The author proves a conjecture of the author: IfG is a semisimple real algebraic defined over ℚ, Γ is an arithmetic subgroup (with respect to the given ℚ-structure) andA is a diagonalizable subgroup admitting a divergent trajectory inG/Γ, then dimA≤ rank_ℚ G.     

Irreducible disconnected systems in groups

LetG be an arbitrary group with a subgroupA. The subdegrees of (A, G) are the indices [A:A ∪A ⁹] (wheregεG). Equivalent definitions of that concept are given in [IP] and [K]. IfA is not normal inG and all the subdegrees of (A, G) are finite, we attach to (A, G) the common divisor graph Γ: its vertices are the non-unit subdegrees of (A, G), and two different subdegrees are joined by an edge iff they arenot coprime. It is proved in [IP] that Γ has at most two connected components. Assume that Γ is disconnected. LetD denote the subdegree set of (A, G) and letD ₁ be the set of all the subdegrees in the component of Γ containing min(D−{1}). We proved [K, Theorem A] that ifA is stable inG (a property which holds whenA or [G:A] is finite), then the setH={g ε G| [A:A ∪A ^g ] εD ₁ ∪ {1}} is a subgroup ofG. In this case we say thatA<H<G is a disconnected system (briefly: a system). In the current paper we deal with some fundamental types of systems. A systemA<H<G is irreducible if there does not exist 1<N△G such thatAN<H andAN/N<H/N<G/N is a system. Theorem A gives restrictions on the finite nilpotent normal subgroups ofG, whenG possesses an irreducible system. In particular, ifG is finite then Fit(G) is aq-group for a certain primeq. We deal also with general systems. Corollary (4.2) gives information about the structure of a finite groupG which possesses a system. Theorem B says that for any systemA<H<G,N _G (N _G (A))=N _G (A). Theorem C and Corollary C’ generalize a result of Praeger [P, Theorem 2]. The content of this paper corresponds to a part of the author’s Ph.D. thesis carried out at Tel Aviv University under the supervision of Prof. Marcel Herzog.     

Rigidity problem for lattices in solvable Lie groups

The paper concerns rigidity problem for lattices in simply connected solvable Lie groups. A lattice Γ⊂G is said to be rigid if for any isomorphism ϕ:Γ→Γ′ with another lattice Γ′⊂G there exists an automorphism which extends ϕ. An effective rigidity criterion is proved which generalizes well-known rigidity theorems due to Malcev and Saito. New examples of rigid and nonrigid lattices are constructed. In particular, we construct: a) rigid lattice Γ⊂G which is not Zariski dense in the adjoint representation ofG, b) Zariski dense lattice Γ⊂G which is not rigid, c) rigid virtually nilpotent lattice Γ in a solvable nonnilpotent Lie groupG.     

The structure of a kind of connected components with oriented cycles and semi-stable vertices

LetF be an algebraically closed field. A be a finite-dimensional algebra overF,Γ _A be the Auslander-Reiten quiver ofA,Γ be a connected component of Γ _A with oriented cycles and semi-stable vertices and each non-stable vertex In Γ be a projective-injective vertex. The structure of Γ is studied. Projcct supported by Chinese Postdoctor Fund.     

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.     

Distinguishing labeling of the actions of almost simple groups

Suppose Γ is a group acting on a set X, written as (Γ,X). An r-labeling f: X→{1,2, ..., r} of X is called distinguishing for (Γ,X) if for all σ∈Γ,σ≠1, there exists an element x∈X such that f(x)≠f(x ^σ ). The distinguishing number d(Γ,X) of (Γ,X) is the minimum r for which there is a distinguishing r-labeling for (Γ,X). If Γ is the automorphism group of a graph G, then d(Γ,V (G)) is denoted by d(G), and is called the distinguishing number of the graph G. The distinguishing set of Γ-actions is defined to be D*(Γ)={d(Γ,X): Γ acts on X}, and the distinguishing set of Γ-graphs is defined to be D(Γ)={d(G): Aut(G)≅Γ}. This paper determines the distinguishing set of Γ-actions and the distinguishing set of Γ-graphs for almost simple groups Γ.     

Packing cycles with modularity constraints

We prove that for all positive integers k, there exists an integer N =N(k) such that the following holds. Let G be a graph and let Γ an abelian group with no element of order two. Let γ: E(G)→Γ be a function from the edges of G to the elements of Γ. A non-zero cycle is a cycle C such that Σ _e∈E(C) γ(e) ≠ 0 where 0 is the identity element of Γ. Then G either contains k vertex disjoint non-zero cycles or there exists a set X ⊆ V (G) with |X| ≤N(k) such that G−X contains no non-zero cycle.