Simplicity of Lyapunov spectra: proof of the Zorich-Kontsevich conjecture

We prove the Zorich–Kontsevich conjecture that the non-trivial Lyapunov exponents of the Teichmüller ow on (any connected component of a stratum of) the moduli space of Abelian differentials on compact Riemann surfaces are all distinct. By previous work of Zorich and Kontsevich, this implies the existence of the complete asymptotic Lagrangian flag describing the behavior in homology of the vertical foliation in a typical translation surface. Work carried out within the Brazil–France Agreement in Mathematics. Avila is a Clay Research Fellow. Viana is partially supported by Pronex and Faperj.     

The loop expansion of the Kontsevich integral, the null-move and S-equivalence

The Kontsevich integral of a knot is a graph-valued invariant which (when graded by the Vassiliev degree of graphs) is characterized by a universal property; namely it is a universal Vassiliev invariant of knots. We introduce a second grading of the Kontsevich integral, the Euler degree, and a geometric null-move on the set of knots. We explain the relation of the null-move to S-equivalence, and the relation to the Euler grading of the Kontsevich integral. The null-move leads in a natural way to the introduction of trivalent graphs with beads, and to a conjecture on a rational version of the Kontsevich integral, formulated by the second author and proven in Geom. Top 8 (2004) 115 (see also Kricker, preprint 2000, math/GT.0005284).     

Matrix Models: Geometry of Moduli Spaces and Exact Solutions

We study the connection between characteristics of moduli spaces of Riemann surfaces with marked points and matrix models. The Kontsevich matrix model describes intersection indices on continuous moduli spaces, and the Kontsevich–Penner matrix model describes intersection indices on discretized moduli spaces. Analyzing the constraint algebras satisfied by various generalized Kontsevich matrix models, we derive time transformations that establish exact relations between different models appearing in mathematical physics. We solve the Hermitian one-matrix model using the moment technique in the genus expansion and construct a recursive procedure for solving this model in the double scaling limit.     

G ∞-Formality Theorem in Terms of Graphs and Associated Chevalley–Eilenberg–Harrison Cohomology #

In 1997, M. Kontsevich proved the L _∞-formality conjecture (which implies the existence of star-products for any Poisson manifold) using graphs. A year later, D. Tamarkin gave another proof of a more general conjecture (for G _∞-structures) using operads and cohomological methods. In this article, we show how Tamarkin's construction can be written using graphs. For that, we introduce a generalization of Kontsevich graphs on which we define a “Chevalley–Eilenberg–Harrison” complex. We show that this complex on graphs is related to the “Chevalley–Eilenberg–Harrison” complex for maps on polyvector fields, which is trivial and give Tamarkin's formality theorem as a consequence. This formality reduces to an L _∞-formality.     

The obstruction to the existence of a loopless star product

We show that there is an obstruction to the existence of a star product defined by Kontsevich graphs without directed cycles.     

Noncommutative Batalin–Vilkovisky geometry and matrix integrals

I study the new type of supersymmetric matrix models associated with any solution to the quantum master equation of the noncommutative Batalin–Vilkovisky geometry. The asymptotic expansion of the matrix integrals gives homology classes in the Kontsevich compactification of the moduli spaces, which I associated with the solutions to the quantum master equation in my previous paper. I associate with the Bernstein–Leites matrix superalgebra equipped with an odd differentiation, whose square is nonzero, the family of cohomology classes of the compactification. This family is the generating function for the products of the tautological classes. The simplest example of my matrix integrals in the case of dimension zero is a supersymmetric extension of the Kontsevich model of 2-dimensional gravity.     

On denominators of the Kontsevich integral and the universal perturbative invariant of 3-manifolds

 The integrality of the Kontsevich integral and perturbative invariants is discussed. It is shown that the denominator of the degree n part of the Kontsevich integral of any knot or link is a divisor of (2!3!…n!)⁴(n+1)!. We prove this by establishing the existence of a Drinfeld's associator in the space of chord diagrams with special denominators. We also show that the denominator of the degree n part of the universal perturbative invariant of homology 3-spheres is not divisible by any prime greater than 2n+1. Oblatum 20-VI-1997 & 28-IV-1998 / Published online: 12 November 1998     

Hamilton cycles in highly connected and expanding graphs

In this paper we prove a sufficient condition for the existence of a Hamilton cycle, which is applicable to a wide variety of graphs, including relatively sparse graphs. In contrast to previous criteria, ours is based on two properties only: one requiring expansion of “small” sets, the other ensuring the existence of an edge between any two disjoint “large” sets. We also discuss applications in positional games, random graphs and extremal graph theory.     

Wheels, wheeling, and the Kontsevich integral of the Unknot

We conjecture an exact formula for the Kontsevich integral of the unknot, and also conjecture a formula (also conjectured independently by Deligne [De]) for the relation between the two natural products on the space of uni-trivalent diagrams. The two formulas use the related notions of “Wheels” and “Wheeing”. We prove these formulas ‘on the level of Lie algebras’ using standard techniques from the theory of Vassiliev invariants and the theory of Lie algebras. In a brief epilogue we report on recent proofs of our full conjectures, by Kontsevich [Ko2] and by DBN, DPT, and T. Q. T. Le, [BLT]. This paper is available electronically     

Automorphisms of random graphs with specified vertices

Conditions are found under which the expected number of automorphisms of a large random labelled graph with a given degree sequence is close to 1. These conditions involve the probability that such a graph has a given subgraph. One implication is that the probability that a random unlabelledk-regular simple graph onn vertices has only the trivial group of automorphisms is asymptotic to 1 asn → ∞ with 3≦k=O(n ^1/2−c). In combination with previously known results, this produces an asymptotic formula for the number of unlabelledk-regular simple graphs onn vertices, as well as various asymptotic results on the probable connectivity and girth of such graphs. Corresponding results for graphs with more arbitrary degree sequences are obtained. The main results apply equally well to graphs in which multiple edges and loops are permitted, and also to bicoloured graphs. Research of the second author supported by U. S. National Science Foundation Grant MCS-8101555, and by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowships Scheme. Current address: Mathematics Department, University of Auckland, Auckland, New Zealand.     

On random mapping patterns

Random mapping patterns may be represented by unlabelled directed graphs in which each point has out-degree one. We determine the asymptotic behaviour of various parameters associated with such graphs, such as the expected number of points belonging to cycles and the expected number of components. Dedicated to Paul Erdős on his seventieth birthday     

Asymptotic expansion formulas for functionals of ε-Markov processes with a mixing property

The ε-Markov process is a general model of stochastic processes which includes nonlinear time series models, diffusion processes with jumps, and many point processes. With a view to applications to the higher-order statistical inference, we will consider a functional of the ε-Markov process admitting a stochastic expansion. Arbitrary order asymptotic expansion of the distribution will be presented under a strong mixing condition. Applying these results, the third order asymptotic expansion of theM-estimator for a general stochastic process will be derived. The Malliavin calculus plays an essential role in this article. We illustrate how to make the Malliavin operator in several concrete examples. We will also show that the thirdorder expansion formula (Sakamoto and Yoshida (1998, ISM Cooperative Research Report, No. 107, 53–60; 1999, unpublished)) of the maximum likelihood estimator for a diffusion process can be obtained as an example of our result.     

Some Turán type results on the hypercube

For graphs H,G a classical problem in extremal graph theory asks what proportion of the edges of H a subgraph may contain without containing a copy of G. We prove some new results in the case where H is a hypercube. We use a supersaturation technique of Erd?s and Simonivits to give a characterization of a set of graphs such that asymptotically the answer is the same when G is a member of this set and when G is a hypercube of some fixed dimension. We apply these results to a specific set of subgraphs of the hypercube called Fibonacci cubes. Additionally, we use a coloring argument to prove new asymptotic bounds on this problem for a different set of graphs. Finally we prove a new asymptotic bound for the case where G is the cube of dimension 3.     

Isospectral polygons, planar graphs and heat content

Given a pair of planar isospectral, nonisometric polygons constructed as a quotient of the plane by a finite group, we construct an associated pair of planar isospectral, nonisometric weighted graphs. Using the natural heat operators on the weighted graphs, we associate to each graph a heat content. We prove that the coefficients in the small time asymptotic expansion of the heat content distinguish our isospectral pairs. As a corollary, we prove that the sequence of exit time moments for the natural Markov chains associated to each graph, averaged over starting points in the interior of the graph, provides a collection of invariants that distinguish isospectral pairs in general.

     

Asymptotic expansions of logarithmic-exponential functions

The aim of this paper is to study the asymptotic expansion of real functions which are finite compositions of globally subanalytic maps with the exponential function and the logarithmic function. This is done thanks to a preparation theorem in the spirit of those that exist for analytic functions (Weierstrass) or subanalytic functions (Parusinśki). The main consequence is that logarithmic-exponential functions admit convergent asymptotic expansion in the scale of real power functions. We also deduce a partial answer to a conjecture of van den Dries and Miller. Received: 19 March 2002     

Analytic combinatorics of connected graphs

We enumerate the connected graphs that contain a number of edges growing linearly with respect to the number of vertices. So far, only the first term of the asymptotics and a bound on the error were known. Using analytic combinatorics, that is, generating function manipulations, we derive a formula for the coefficients of the complete asymptotic expansion. The same result is derived for connected multigraphs.     

Asymptotic decay of solutions of the liouville equation under perturbations

We consider the Cauchy problem for a perturbed Liouville equation. An asymptotic solution is constructed with respect to the perturbation parameter by the two-scale expansion method; this construction can be applied over long time intervals. The main result is the definition of a deformation of the leading term of the asymptotic expansion within a slow time scale. Translated frommatematicheskie Zametki, Vol. 68, No. 2, pp. 195–209, August, 2000.     

Contact processes on scale-free networks

We investigate the contact process on random graphs generated from the configuration model for scale-free complex networks with the power law exponent β E （2, 3]. Using the neighborhood expansion method, we show that, with positive probability, any disease with an infection rate λ 〉 0 can survive for exponential time in the number of vertices of the graph. This strongly supports the view that stochastic scale-free networks are remarkably different from traditional regular graphs, such as, Z^d and classical Erdos-Renyi random graphs.     

Enumeration of matchings in families of self-similar graphs

The number of matchings of a graph G is an important graph parameter in various contexts, notably in statistical physics (dimer-monomer model). Following recent research on graph parameters of this type in connection with self-similar, fractal-like graphs, we study the asymptotic behavior of the number of matchings in families of self-similar graphs that are constructed by a very general replacement procedure. Under certain conditions on the geometry of the graphs, we are able to prove that the number of matchings generally follows a doubly exponential growth. The proof depends on an independence theorem for the number of matchings that has been used earlier to treat the special case of Sierpiński graphs. We also further extend the technique to the matching-generating polynomial (equivalent to the partition function for the dimer-monomer model) and provide a variety of examples.     

Local theory of extrapolation methods

In this paper we discuss the theory of one-step extrapolation methods applied both to ordinary differential equations and to index 1 semi-explicit differential-algebraic systems. The theoretical background of this numerical technique is the asymptotic global error expansion of numerical solutions obtained from general one-step methods. It was discovered independently by Henrici, Gragg and Stetter in 1962, 1964 and 1965, respectively. This expansion is also used in most global error estimation strategies as well. However, the asymptotic expansion of the global error of one-step methods is difficult to observe in practice. Therefore we give another substantiation of extrapolation technique that is based on the usual local error expansion in a Taylor series. We show that the Richardson extrapolation can be utilized successfully to explain how extrapolation methods perform. Additionally, we prove that the Aitken-Neville algorithm works for any one-step method of an arbitrary order s, under suitable smoothness.