An algorithm for 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 give an efficient algorithm for finding a maximum collection of vertex-disjoint A-paths each of non-zero weight. When A = V this problem is equivalent to the maximum matching problem. This research was partially conducted during the period Chudnovsky served as a Clay Mathematics Institute Long-Term Prize Fellow. The research was supported in part by the Natural Sciences and Engineering Council of Canada.     

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.     

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     

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

Isometric embeddings of Johnson graphs in Grassmann graphs

Let V be an n-dimensional vector space (4≤n<∞) and let G_k(V){\mathcal{G}}_{k}(V) be the Grassmannian formed by all k-dimensional subspaces of V. The corresponding Grassmann graph will be denoted by Γ _k (V). We describe all isometric embeddings of Johnson graphs J(l,m), 1<m<l−1 in Γ _k (V), 1<k<n−1 (Theorem 4). As a consequence, we get the following: the image of every isometric embedding of J(n,k) in Γ _k (V) is an apartment of G_k(V){\mathcal{G}}_{k}(V) if and only if n=2k. Our second result (Theorem 5) is a classification of rigid isometric embeddings of Johnson graphs in Γ _k (V), 1<k<n−1.     

Finiteness properties of chevalley groups overFq[t]

LetG be a simple Chevalley group of rankn and Γ=G( ). Then the finiteness length of Γ shall be determined by studying the action of Γ on the Bruhat-Tits buildingX ofG . This is always possible provided that certain subcomplexes of the links of simplices inX are spherical. As a consequence, one obtains that Γ is of typeF _n−1 but not of typeFP _n ifG is of typeA _n, B_n, C_n orD _n andq≥2²ⁿ⁻¹.     

Uniform Boundedness of Torsion Subgroups of Linear Groups

The torsion conjecture says： for any abelian variety A defined over a number field k, the order of the torsion subgroup of A（k） is bounded by a constant C（k,d） which depends only on the number field k and the dimension d of the abelian variety. The torsion conjecture remains open in general. However, in this paper, a short argument shows that the conjecture is true for more general fields if we consider linear groups instead of abelian varieties. If G is a connected linear algebraic group defined over a field k which is finitely generated over Q,Г is a torsion subgroup of G（k）. Then the order of Г is bounded by a constant C＇（k, d） which depends only on k and the dimension d of G.     

Mader’s Conjecture On Extremely Critical Graphs

A non-complete graph G is called an (n,k)-graph if it is n-connected but G—X is not (n−|X|+1)-connected for any X ⊂V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K_2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism). Here we prove this conjecture.     

Thek-centrum shortest path problem

Thek-Centrum Shortest Path Problem (kCSP[s, t]) is to minimize the sum of thek longest arcs in any (simple)s−t path containing at leastk arcs, wherek is a positive integer.kCSP is introduced and is shown to be NP-Hard, although it is polynomially solvable ifk is constrained to be no greater than the number of arcs in ans−t path with fewest arcs. Some properties of the problem are studied and a new weakly dual problem is also introduced.     

On Independent Cycles in a Bipartite Graph

 Let G=(V ₁,V ₂;E) be a bipartite graph with 2k≤m=|V ₁|≤|V ₂|=n, where k is a positive integer. We show that if the number of edges of G is at least (2k−1)(n−1)+m, then G contains k vertex-disjoint cycles, unless e(G)=(2k−1)(n−1)+m and G belongs to a known class of graphs. Received: December 9, 1998 Final version received: June 2, 1999     

Deformations of complex structures on Γ/SL 2(C)

LetG be a connected complex semisimple Lie group. Let Γ be a cocompact lattice inG. In this paper, we show that whenG isSL ₂(C), nontrivial deformations of the canonical complex structure onX exist if and only if the first Betti number of the lattice Γ is non-zero. It may be remarked that for a wide class of arithmetic groups Γ, one can find a subgroup Γ′ of finite index in Γ, such that Γ′/[Γ′,Γ′] is finite (it is a conjecture of Thurston that this is true for all cocompact lattices inSL(2, C)). We also show thatG acts trivially on the coherent cohomology groupsH ⁱ(Γ/G, O) for anyi≥0.     

A 2-factor with Short Cycles Passing Through Specified Independent Vertices in Graph

For a graph G, we define σ₂(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k of length at most four such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k. And show if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k, V(C ₁) ∪...∪ V(C _k ) = V(G), and |C _i | ≤ 4 for all 1 ≤ i ≤ k − 1. The condition of degree sum σ₂(G) ≥ n + k − 1 is sharp. Received: December 20, 2006. Final version received: December 12, 2007.     

Solving the path cover problem on circular-arc graphs by using an approximation algorithm

A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs.     

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.     

On the existence of spines for ${\mathbb{Q}}${\mathbb{Q}}-rank 1 groups

Let X = Γ \G/ K be an arithmetic quotient of a symmetric space of non-compact type. In the case that G has -rank 1, we construct Γ-equivariant deformation retractions of D = G/K onto a set D₀. We prove that D₀ is a spine, having dimension equal to the virtual cohomological dimension of Γ. In fact, there is a (k − 1)-parameter family of such deformation retractions, where k is the number of Γ -conjugacy classes of rational parabolic subgroups of G. The construction of the spine also gives a way to construct an exact fundamental domain for Γ.     

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     

Preemptive Scheduling of Equal-Length Jobs in Polynomial Time

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.     

On a Spanning Tree with Specified Leaves

Let k ≥ 2 be an integer. We show that if G is a (k + 1)-connected graph and each pair of nonadjacent vertices in G has degree sum at least |G| + 1, then for each subset S of V(G) with |S| = k, G has a spanning tree such that S is the set of endvertices. This result generalizes Ore’s theorem which guarantees the existence of a Hamilton path connecting any two vertices. Dedicated to Professor Hikoe Enomoto on his 60th birthday.     

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.     

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