Anchored expansion and random walk

This paper studies anchored expansion, a non-uniform version of the strong isoperimetric inequality. We show that every graph with i-anchored expansion contains a subgraph with isoperimetric (Cheeger) constant at least i. We prove a conjecture by Benjamini, Lyons and Schramm (1999) that in such graphs the random walk escapes with a positive lim inf speed. We also show that anchored expansion implies a heat-kernel decay bound of order exp(—cn ^1/3). Submitted: September 1999, Revision: January 2000.     

A second-order bundle method to minimize the maximum eigenvalue function

In this paper we present a nonsmooth algorithm to minimize the maximum eigenvalue of matrices belonging to an affine subspace of n×n symmetric matrices. We show how a simple bundle method, the approximate eigenvalue method can be used to globalize the second-order method developed by M.L. Overton in the eighties and recently revisited in the framework of the ?-Lagrangian theory. With no additional assumption, the resulting algorithm generates a minimizing sequence. A geometrical and constructive proof is given. To prove that quadratic convergence is achieved asymptotically, some strict complementarity and non-degeneracy assumptions are needed. We also introduce new variants of bundle methods for semidefinite programming. Received: February 9, 1998 / Accepted: May 2, 2000?Published online September 20, 2000     

Extremal properties of some geometric processes

In this paper some isoperimetric inequalities for stationary random tessellations are discussed. At first, classical results on deterministic tessellations in the Euclidean plane are extended to the case of random tessellations. An isoperimetric inequality for the random Poisson polygon is derived as a consequence of a theorem of Davidson concerning an extremal property of tessellations generated by random lines inR ². We mention extremal properties of stationary hyperplane tessellations inR ^d related to Davidson's result in cased=2. Finally, similar problems for random arrangements ofr-flats inR ^d are considered (r).This work was done while the author was visiting the University of Strathclyde in Glasgow.     

The effect of concentrating potentials in some singularly perturbed problems

The equation with boundary Dirichlet zero data is considered in a bounded domain . Under the assumption that concentrates, as , round a manifold and that f is a superlinear function, satisfying suitable growth assumptions, the existence of multiple distinct positive solutions is proved. Received: 19 December 2000 / Accepted: 8 May 2001 / Published online: 5 September 2002     

Newton's problem of the body of minimal resistance under a single-impact assumption

We consider the problem of the body of minimal resistance as formulated in [2], Sect. 5: minimize , where is the unit disc of , in the class of radial functions satisfying a geometrical property (1), corresponding to a single-impact assumption ( is a given parameter). We prove the existence of a critical value of M. For , there exist a unique local minimizer of the functional. For , the set of local minimizers is not compact in , though they all achieve the same value of the functional. Received February 15, 2000 / Accepted May 2, 2000 / Published online September 14, 2000     

On the Complexity of Computing Error Bounds

We consider the cost of estimating an error bound for the computed solution of a system of linear equations, i.e., estimating the norm of a matrix inverse. Under some technical assumptions we show that computing even a coarse error bound for the solution of a triangular system of equations costs at least as much as testing whether the product of two matrices is zero. The complexity of the latter problem is in turn conjectured to be the same as matrix multiplication, matrix inversion, etc. Since most error bounds in practical use have much lower complexity, this means they should sometimes exhibit large errors. In particular, it is shown that condition estimators that: (1) perform at least one operation on each matrix entry; and (2) are asymptotically faster than any zero tester, must sometimes over or underestimate the inverse norm by a factor of at least , where n is the dimension of the input matrix, k is the bitsize, and where either or grows faster than any polynomial in n . Our results hold for the RAM model with bit complexity, as well as computations over rational and algebraic numbers, but not real or complex numbers. Our results also extend to estimating error bounds or condition numbers for other linear algebra problems such as computing eigenvectors. September 10, 1999. Final version received: August 23, 2000.     

Box and Packing Dimensions of Typical Compact Sets

 Let (X,ρ) be a complete metric space and let dim A be the upper box dimension of the set . We show that packing dimension of the typical (in the sense of Baire category) compact set is at least . (Received 27 March 2000; in revised form 5 June 2000)     

On the first cohomology of arithmetic groups

We study the restriction to smaller subgroups, of cohomology classes on arithmetic groups (possibly after moving the class by Hecke correspondences), especially in the context of first cohomology of arithmetic groups. We obtain vanishing results for the first cohomology of cocompact arithmetic lattices in SU(n,1) which arise from hermitian forms over division algebras D of degree p ², p an odd prime, equipped with an involution of the second kind. We show that it is not possible for a ‘naive’ restriction of cohomology to be injective in general. We also establish that the restriction map is injective at the level of first cohomology for non co-compact lattices, extending a result of Raghunathan and Venkataramana for co-compact lattices. Received: 14 September 2000 / Accepted: 6 June 2001     

Finite order q-invariants of immersions of surfaces into 3-space

Given a surface F, we are interested in valued invariants of immersions of F into , which are constant on each connected component of the complement of the quadruple point discriminant in . Such invariants will be called “q-invariants.” Given a regular homotopy class , we denote by the space of all q-invariants on A of order . We show that ifF is orientable, then for each regular homotopy class A and each n, $\dim (V_n (A) / V_{n-1}(A) ) \leq 1$. Received June 15, 1999; in final form September 22, 1999 / Published online October 30, 2000     

Adelic version of Margulis arithmeticity theorem

We generalize Margulis's S-arithmeticity theorem to the case when S can be taken as an infinite set of primes. Let R be the set of all primes including infinite one and set . Let S be any subset of R. For each , let be a connected semisimple adjoint -group and be a compact open subgroup for each finite prime . Let denote the restricted topological product of 's, with respect to 's. Note that if S is finite, . We show that if , any irreducible lattice in is a rational lattice. We also present a criterion on the collections and for to admit an irreducible lattice. In addition, we describe discrete subgroups of generated by lattices in a pair of opposite horospherical subgroups. Received: 30 November 2000 / Revised version: 2 April 2001 / Published online: 24 September 2001     

d‐homogeneous and d‐ultrahomogeneous linear spaces

A linear space S is d‐homogeneous if, whenever the linear structures induced on two subsets S₁ and S₂ of cardinality at most d are isomorphic, there is at least one automorphism of S mapping S₁ onto S₂. S is called d‐ultrahomogeneous if each isomorphism between the linear structures induced on two subsets of cardinality at most d can be extended into an automorphism of S. We have proved in [11;] (without any finiteness assumption) that every 6‐homogeneous linear space is homogeneous (that is d‐homogeneous for every positive integer d). Here we classify completely the finite nontrivial linear spaces that are d‐homogeneous for d ≥ 4 or d‐ultrahomogeneous for d ≥ 3. We also prove an existence theorem for infinite nontrivial 4‐ultrahomogeneous linear spaces. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 321–329, 2000     

Relèvement galoisien des revêtements¶de courbes nodales

Let R be a complete discrete valuation ring of mixed characteristics, with algebraically closed residue field k. We study the existence problem of equivariant liftings to R of Galois covers of nodal curves over k. Using formal geometry, we show that this problem is actually a local one. We apply this local-to-global principle to obtain new results concerning the existence of such liftings. Received: 10 February 2000 / Revised version: 13 September 2000     

Laufer's vanishing theorem for embedded CR manifolds

Let D be a sufficiently small open subset of a generic CR manifold in . We show that the cohomology groups are either zero or infinite dimensional. Received: 2 May 2000; in final form: 6 September 2000 / Published online: 28 February 2002     

Doubling and Tripling Constructions for Defining Sets in Steiner Triple Systems

 A minimal defining set of a Steiner triple system on v points (STS(v)) is a partial Steiner triple system contained in only this STS(v), and such that any of its proper subsets is contained in at least two distinct STS(v)s. We consider the standard doubling and tripling constructions for STS(2v+1) and STS(3v) from STS(v) and show how minimal defining sets of an STS(v) gives rise to minimal defining sets in the larger systems. We use this to construct some new families of defining sets. For example, for Steiner triple systems on 3 ⁿ points, we construct minimal defining sets of volumes varying by as much as 7 ⁿ⁻² . Received: September 16, 2000 Final version received: September 13, 2001 RID="*" ID="*" Research supported by the Australian Research Council A49937047, A49802044     

On the flatness of models of certain Shimura varieties of PEL-type

Consider a PEL-Shimura variety associated to a unitary group that splits over an unramified extension of . Rapoport and Zink have defined a model of the Shimura variety over the ring of integers of the completion of the reflex field at a place lying over p, with parahoric level structures at p. We show that this model is flat, as conjectured by Rapoport and Zink, and that its special fibre is reduced. Received: 11 September 2000 / Published online: 24 September 2001     

On a theorem of Wiener

 Wiener has shown that an integrable function on the circle T which is square integrable near the identity and has nonnegative Fourier transform, is square integrable on all of T. In the last 30 years this has been extended by the work of various authors step by step. The latest result states that, in a suitable reformulation, Wiener's theorem with ``p-integrable' in place of ``square integrable' holds for all even p and fails for all other p  (1, ∞) in the case of a general locally compact abelian group. We extend this to all IN-groups (locally compact groups with at least one invariant compact neighbourhood) and show that an extension to all locally compact groups is not possible: Wiener's theorem fails for all p < ∞ in the case of the ax + b-group. Received: 12 September 2000 Mathematics Subject Classification (2000): 43A35     

On the Loebl–Komlós–Sós conjecture

The Loebl–Komlós–Sós conjecture says that any graph G on n vertices with at least half of vertices of degree at least k contains each tree of size k. We prove that the conjecture is true for paths as well as for large values of k(k ≥ n − 3). © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 269–276, 2000     

Shape-driven nested Markov tessellations

A new and rather broad class of stationary random tessellations of the d-dimensional Euclidean space is introduced, which we call shape-driven nested Markov tessellations. Locally, these tessellations are constructed by means of a spatio-temporal random recursive split dynamics governed by a family of Markovian split kernel, generalizing thereby the – by now classical – construction of iteration stable random tessellations. By providing an explicit global construction of the tessellations, it is shown that under suitable assumptions on the split kernels (shape-driven), there exists a unique time-consistent whole-space tessellation-valued Markov process of stationary random tessellations compatible with the given split kernels. Beside the existence and uniqueness result, the typical cell and some aspects of the first-order geometry of these tessellations are in the focus of our discussion.     

High‐girth cubic graphs are homomorphic to the Clebsch graph

We give a (computer assisted) proof that the edges of every graph with maximum degree 3 and girth at least 17 may be 5‐colored (possibly improperly) so that the complement of each color class is bipartite. Equivalently, every such graph admits a homomorphism to the Clebsch graph (Fig. 1 ). Hopkins and Staton [J Graph Theory 6(2) (1982), 115–121] and Bondy and Locke [J Graph Theory 10(4) (1986), 477–504] proved that every (sub)cubic graph of girth at least 4 has an edge‐cut containing at least of the edges. The existence of such an edge‐cut follows immediately from the existence of a 5‐edge‐coloring as described above; so our theorem may be viewed as a coloring extension of their result (under a stronger girth assumption). Every graph which has a homomorphism to a cycle of length five has an above‐described 5‐edge‐coloring; hence our theorem may also be viewed as a weak version of Ne?et?il's Pentagon Problem (which asks whether every cubic graph of sufficiently high girth is homomorphic to C₅). Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 66: 241—259, 2011