On bar frameworks,stress matrices and semidefinite programming

A bar framework G(p) in r-dimensional Euclidean space is a graph G on the vertices 1, 2, . . . , n, where each vertex i is located at point p ⁱ in \mathbbR^r{\mathbb{R}^r} . Given a framework G(p) in \mathbbR^r{\mathbb{R}^r} , a problem of great interest is that of determining whether or not there exists another framework G(q), not obtained from G(p) by a rigid motion, such that ||q ⁱ − q ^j ||² = ||p ⁱ − p ^j ||² for each edge (i, j) of G. This problem is known as either the global rigidity problem or the universal rigidity problem depending on whether such a framework G(q) is restricted to be in the same r-dimensional space or not. The stress matrix S of a bar framework G(p) plays a key role in these and other related problems. In this paper, semidefinite programming (SDP) theory is used to address, in a unified manner, several problems concerning universal rigidity. New results are presented as well as new proofs of previously known theorems. In particular, we use the notion of SDP non-degeneracy to obtain a sufficient condition for universal rigidity, and we show that this condition yields the previously known sufficient condition for generic universal rigidity. We present new results concerning positive semidefinite stress matrices and we use a semidefinite version of Farkas lemma to characterize bar frameworks that admit a nonzero positive semidefinite stress matrix S.     

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.     

On the rigidity of molecular graphs

The rigidity of squares of graphs in three-space has important applications to the study of flexibility in molecules. The Molecular Conjecture, posed in 1984 by T.-S. Tay and W. Whiteley, states that the square G ² of a graph G of minimum degree at least two is rigid if and only if G has six spanning trees which cover each edge of G at most five times. We give a lower bound on the degrees of freedom of G ² in terms of forest covers of G. This provides a self-contained proof that the existence of the above six spanning trees is a necessary condition for the rigidity of G ². In addition, we prove that the truth of the Molecular Conjecture would imply that our lower bound is tight, and would also imply that a conjecture of Jacobs on ‘independent’ squares is valid. This work was supported by an International Joint Project grant from the Royal Society. Supported by the MTA-ELTE Egerváry Research Group on Combinatorial Optimization and the Hungarian Scientific Research Fund grant no. T049671, T60802.     

Gersten conjecture for equivariant K-theory and applications

For a reductive group scheme G over a regular semi-local ring A, we prove the Gersten conjecture for the equivariant K-theory. As a consequence, we show that if F is the field of fractions of A, then K^G₀(A) @ K^G₀(F){K^G_0(A) \cong K^G_0(F)}, generalizing the analogous result for a dvr by Serre (Inst Hautes études Sci Publ Math 34:37–52, 1968). We also show the rigidity for the K-theory with finite coefficients of a Henselian local ring in the equivariant setting. We use this rigidity theorem to compute the equivariant K-theory of algebraically closed fields.     

Flows, fixed points and rigidity for Kleinian groups

The main application of the techniques developed in this paper is to prove a relative version of Mostow rigidity, called pattern rigidity. For a cocompact group G, by a G-invariant pattern we mean a G-invariant collection of closed proper subsets of the boundary of hyperbolic space which is discrete in the space of compact subsets minus singletons. Such a pattern arises for example as the collection of translates of limit sets of finitely many infinite index quasiconvex subgroups of G. We prove that (in dimension at least three) for G ₁, G ₂ cocompact Kleinian groups, any quasiconformal map pairing a G ₁-invariant pattern to a G ₂-invariant pattern must be conformal. This generalizes a previous result of Schwartz who proved rigidity in the case of limit sets of cyclic subgroups, and Biswas and Mj (Pattern rigidity in hyperbolic spaces: duality and pd subgroups, arxiv:math.GT/08094449, 2008) who proved rigidity for Poincare Duality subgroups. Pattern rigidity is a consequence of the study conducted in this paper of the closed group of homeomorphisms of the boundary of real hyperbolic space generated by a cocompact Kleinian group G ₁ and a quasiconformal conjugate h ^?1 G ₂ h of a cocompact group G ₂. We show that if the conjugacy h is not conformal then this group contains a flow, i.e. a non-trivial one parameter subgroup. Mostow rigidity is an immediate consequence.     

Critical extreme points of the 2-edge connected spanning subgraph polytope

In this paper we study the extreme points of the polytope P(G), the linear relaxation of the 2-edge connected spanning subgraph polytope of a graph G. We introduce a partial ordering on the extreme points of P(G) and give necessary conditions for a non-integer extreme point of P(G) to be minimal with respect to that ordering. We show that, if is a non-integer minimal extreme point of P(G), then G and can be reduced, by means of some reduction operations, to a graph G' and an extreme point of P(G') where G' and satisfy some simple properties. As a consequence we obtain a characterization of the perfectly 2-edge connected graphs, the graphs for which the polytope P(G) is integral. Received: May, 2004 Part of this work has been done while the first author was visiting the Research Institute for Discrete Mathematics, University of Bonn, Germany.     

Some smooth Finsler deformations of hyperbolic surfaces

Given a closed hyperbolic Riemannian surface, the aim of the present paper is to describe an explicit construction of smooth deformations of the hyperbolic metric into Finsler metrics that are not Riemannian and whose properties are such that the classical Riemannian results about entropy rigidity, marked length spectrum rigidity and boundary rigidity all fail to extend to the Finsler category.     

Bounded Direction–Length Frameworks

A direction–length framework is a pair (G,p) where G=(V;D,L) is a ‘mixed’ graph whose edges are labelled as ‘direction’ or ‘length’ edges and p is a map from V to ℝ ^d for some d. The label of an edge uv represents a direction or length constraint between p(u) and p(v). Let G ⁺ be obtained from G by adding, for each length edge e of G, a direction edge with the same end vertices as e. We show that (G,p) is bounded if and only if (G ⁺,p) is infinitesimally rigid. This gives a characterization of when (G,p) is bounded in terms of the rank of the rigidity matrix of (G ⁺,p). We use this to characterize when a mixed graph is generically bounded in ℝ ^d . As an application we deduce that if (G,p) is a globally rigid generic framework with at least two length edges and e is a length edge of G then (G∖e,p) is bounded.     

A Note on Range-Restricted Circuit Covers

 Let Cone(G), Int.Cone(G) and Lat(G) be the cone, the integer cone and the lattice of the incidence vectors of the circuits of graph G. A good range is a set ?⊆ℕ such that Cone (G)∩Lat (G)∩?^E⊆Int.Cone(G) for every graph G(V,E). We give a counterexample to a conjecture of Goddyn [1] stating that ℕ\{1} is a good range. Received: November 26, 1997     

Tensor products of singular representations and an extension of the $ \theta $-correspondence

In this paper we consider the problem of decomposing tensor products of certain singular unitary representations of a semisimple Lie group G. Using explicit models for these representations (constructed earlier by one of us) we show that the decomposition is controlled by a reductive homogeneous space . Our procedure establishes a correspondence between certain unitary representations of G and those of . This extends the usual -correspondence for dual reductive pairs. As a special case we obtain a correspondence between certain representations of real forms of E ₇ and F ₄.     

Strong Arens irregularity of Beurling algebras with a locally convex topology

Let G be a locally compact group with a weight function ω. Recently, we have shown that the Banach space L₀^∞ (G,1/ω) can be identified with the strong dual of L¹(G, ω)equipped with some locally convex topologies τ. Here we use this duality to introduce an Arens multiplication on (L¹(G, ω), τ)**, and prove that the topological center of (L¹(G, ω), τ)** is (L¹(G, ω); this enables us to conclude that (L¹(G, ω), τ) is Arens regular if and only if G is discrete. We also give a characterization for Arens regularity of L₀^∞ (G, 1/ω)¹. Received: 8 March 2005     

The Rost invariant has trivial kernel for quasi-split groups of low rank

For G a simple simply connected algebraic group defined over a field F, Rost has shown that there exists a canonical map . This includes the Arason invariant for quadratic forms and Rost's mod 3 invariant for exceptional Jordan algebras as special cases. We show that R _G has trivial kernel if G is quasi-split of type E ₆ or E ₇. A case-by-case analysis shows that it has trivial kernel whenever G is quasi-split of low rank. Received: November 1, 2000     

Essential cohomology of finite groups

In this paper we prove that a finite group G with Cohen-Macaulay mod p cohomology will have non-trivial undetectable elements in if and only if G is a p-group such that every element of order p in G is central. Applications and examples are also provided. Received: April 18, 1996     

An unfeasible matching problem

LetG be a bipartite graph with natural edge weights, and letW be a function from the set of vertices ofG into natural numbers. AW-matching ofG is a subset of the set of edges ofG such that for each vertexv the total weight of edges in the subset incident tov does not exceedW(v). Letm be a natural number. We show that the problem of deciding whether there is aW-matching inG whose total weight is not less thanm is NP-complete even ifG is bipartite and its edge weights as well as theW(v)-constraints are constantly bounded.     

Rigidity of Conformal Iterated Function Systems

The paper extends the rigidity of the mixing expanding repellers theorem of D. Sullivan announced at the 1986 IMC. We show that, for a regular conformal, satisfying the Open Set Condition, iterated function system of countably many holomorphic contractions of an open connected subset of a complex plane, the Radon–Nikodym derivative d/dm has a real-analytic extension on an open neighbourhood of the limit set of this system, where m is the conformal measure and is the unique probability invariant measure equivalent with m. Next, we introduce the concept of nonlinearity for iterated function systems of countably many holomorphic contractions. Several necessary and sufficient conditions for nonlinearity are established. We prove the following rigidity result: If h, the topological conjugacy between two nonlinear systems F and G, transports the conformal measure m _F to the equivalence class of the conformal measure m _G , then h has a conformal extension on an open neighbourhood of the limit set of the system F. Finally, we prove that the hyperbolic system associated to a given parabolic system of countably many holomorphic contractions is nonlinear, which allows us to extend our rigidity result to the case of parabolic systems.     

The Bass Conjecture and Group von Neumann Algebras

The precise relationship between the Bass conjecture for the Hattori–Stallings trace for projective ZG-modules and the map from reduced K-theory of ZG to reduced K-theory of the von Neumann algebra, NG, of G, of G is determined. As a consequence it is shown this map is zero for all groups G. It is also shown that the map induced on K-theory from the inclusion of NG to the ring of closed, densely defined operators affiliated to NG is an isomorphism. Together with the above result, this gives some positive evidence for the validity of the Division Ring Conjecture for torsion free groups.     

图和线图的谱性质

Let G be a simple connected graph with n vertices and m edges,Lo be the line graph of G and λ1(LG)≥λ2 (LG)≥...≥λm(LG) be the eigenvalues of the graph LG,.. In this paper, the range of eigenvalues of a line graph is considered. Some sharp upper bounds and sharp lower bounds of the eigenvalues of Lc. are obtained. In oarticular,it is oroved that-2cos(π/n)≤λn-1(LG)≤n-4 and λn(LG)=-2 if and only if G is bipartite.     

Zassenhaus Conjecture (ZC1) on torsion units of integral group rings for some metabelian groups

We prove a conjecture of Zassenhaus that every normalized torsion unit of the integral group ring ZG of a finite group G is rationally conjugate to a group element for some metabelian groups including metacyclic groups G containing a normal cyclic group A such that G/A is cyclic of prime power order. The relative prime case was done in [11]. Received: 21 April 2005