Sur la systole de la sphère au voisinage de la métrique standard

We study the systolic area (defined as the ratio of the area over the square of the systole) of the 2-sphere endowed with a smooth Riemannian metric as a function of this metric. This function, bounded from below by a positive constant over the space of metrics, admits the standard metric g ₀ as a critical point, although it does not achieve the conjectured global minimum: we show that for each tangent direction to the space of metrics at g ₀, there exists a variation by metrics corresponding to this direction along which the systolic area can only increase.      

The Effect of Surface Tension on the Moore Singularity of Vortex Sheet Dynamics

We investigate the regularization of Moore’s singularities by surface tension in the evolution of vortex sheets and its dependence on the Weber number (which is inversely proportional to surface tension coefficient). The curvature of the vortex sheet, instead of blowing up at finite time t ₀, grows exponentially fast up to a O(We) limiting value close to t ₀. We describe the analytic structure of the solutions and their self-similar features and characteristic scales in terms of the Weber number in a O(We⁻¹) neighborhood of the time at which, in absence of surface tension effects, Moore’s singularity would appear. Our arguments rely on asymptotic techniques and are supported by full numerical simulations of the PDEs describing the evolution of vortex sheets.     

Q ℒ,q-Scales in a Hyperbolic Setting

Q_p -scales arise in complex analysis as an interpolation scale between BMO, Bloch and Dirichlet spaces. They were generalized to the n-dimensional case by means of the conformal group of the unit ball and a modified fundamental solution of the Laplacian; however, this operator is no longer invariant under the action of group in consideration. In this talk we propose an approach to Q _ℒ,q-scales for homogeneous hyperbolic manifolds using a fundamental solution for the (α -homogeneous) hyperbolic Dirac operator based on a spherical Radon transform. We present also some properties of this scales. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Microlocal Analysis of the Geometric Separation Problem

Image data are often composed of two or more geometrically distinct constituents; in galaxy catalogs, for instance, one sees a mixture of pointlike structures (galaxy superclusters) and curvelike structures (filaments). It would be ideal to process a single image and extract two geometrically “pure” images, each one containing features from only one of the two geometric constituents. This seems to be a seriously underdetermined problem but recent empirical work achieved highly persuasive separations. We present a theoretical analysis showing that accurate geometric separation of point and curve singularities can be achieved by minimizing the ?₁ norm of the representing coefficients in two geometrically complementary frames: wavelets and curvelets. Driving our analysis is a specific property of the ideal (but unachievable) representation where each content type is expanded in the frame best adapted to it. This ideal representation has the property that important coefficients are clustered geometrically in phase space, and that at fine scales, there is very little coherence between a cluster of elements in one frame expansion and individual elements in the complementary frame. We formally introduce notions of cluster coherence and clustered sparsity and use this machinery to show that the underdetermined systems of linear equations can be stably solved by ?₁ minimization; microlocal phase space helps organize the calculations that cluster coherence requires. © 2012 Wiley Periodicals, Inc.     

Quantifying curvelike structures of measures by using L2 Jones quantities

We study the curvelike structure of special measures on ?ⁿ in a multiscale fashion. More precisely, we consider the existence and construction of a sufficiently short curve with a sufficiently large measure. Our main tool is an L₂ variant of Jones' β numbers, which measure the scaled deviations of the given measure from a best approximating line at different scales and locations. The Jones function is formed by adding the squares of the L₂ Jones numbers at different scales and the same location. Using a special L₂ Jones function, we construct a sufficiently short curve with a sufficiently large measure. The length and measure estimates of the underlying curve are expressed in terms of the size of this Jones function. © 2003 Wiley Periodicals, Inc.     

A characterization of graphs without long induced paths

In a connected graph define the k-center as the set of vertices whose distance from any other vertex is at most k. We say that a vertex set S d-dominates G if for every vertex x there is a y ∈ S whose distance from x is at most d. Call a graph P_t-free if it does not contain a path on t vertices as an induced subgraph. We prove that a connected graph is P_2k-1-free (P_2k-free) if and only if each of its connected induced subgraphs H satisfy the following property: The k-center of H (k - 1)-dominates ((k - 2)-dominates) H. Moreover, we show that the subgraph induced by the (t - 3)-center in any P_t-free connected graph is again connected and has diameter at most t - 3.     

Note on a conjecture of toft

A conjecture of Toft [17] asserts that any 4-critical graph (or equivalently, every 4-chromatic graph) contains a fully odd subdivision ofK ₄. We show that if a graphG has a degree three nodev such thatG-v is 3-colourable, then eitherG is 3-colourable or it contains a fully oddK ₄. This resolves Toft's conjecture in the special case where a 4-critical graph has a degree three node, which is in turn used to prove the conjecture for line-graphs. The proof is constructive and yields a polynomial algorithm which given a 3-degenerate graph either finds a 3-colouring or exhibits a subgraph that is a fully odd subdivision ofK ₄. (A graph is 3-degenerate if every subgraph has some node of degree at most three.)     

Caps with free pairs of points

We say that two points x, y of a cap C form a free pair of points if any plane containing x and y intersects C in at most three points. For given N and q, we denote by m₂⁺ (N, q) the maximum number of points in a cap of PG(N, q) that contains at least one free pair of points. It is straightforward to prove that m₂⁺ (N, q) ≤ (q^N-1 + 2q − 3)/(q − 1), and it is known that this bound is sharp for q = 2 and all N. We use geometric constructions to prove that this bound is sharp for all q when N ≤ 4. We briefly survey the motivation for constructions of caps with free pairs of points which comes from the area of statistical experimental design. Research supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) and MITACS NCE of Canada.     

A functional limit theorem for random graphs with applications to subgraph count statistics

We consider a random graph that evolves in time by adding new edges at random times (different edges being added at independent and identically distributed times). A functional limit theorem is proved for a class of statistics of the random graph, considered as stochastic processes. the proof is based on a martingale convergence theorem. the evolving random graph allows us to study both the random graph model K_{n, p}, by fixing attention to a fixed time, and the model K_{n, N}, by studying it at the random time it contains exactly N edges. in particular, we obtain the asymptotic distribution as n → ∞ of the number of subgraphs isomorphic to a given graph G, both for K_{n, p} (p fixed) and K_{n, N} (N/(ⁿ₂)→ p). the results are strikingly different; both models yield asymptotically normal distributions, but the variances grow as different powers of n (the variance grows slower for K_n, N; the powers of n usually differ by 1, but sometimes by 3). We also study the number of induced subgraphs of a given type and obtain similar, but more complicated, results. in some exceptional cases, the limit distribution is not normal.     

The first Steklov eigenvalue, conformal geometry, and minimal surfaces

We consider the relationship of the geometry of compact Riemannian manifolds with boundary to the first nonzero eigenvalue σ₁ of the Dirichlet-to-Neumann map (Steklov eigenvalue). For surfaces Σ with genus γ and k boundary components we obtain the upper bound σ₁L(∂Σ)?2(γ+k)π. For γ=0 and k=1 this result was obtained by Weinstock in 1954, and is sharp. We attempt to find the best constant in this inequality for annular surfaces (γ=0 and k=2). For rotationally symmetric metrics we show that the best constant is achieved by the induced metric on the portion of the catenoid centered at the origin which meets a sphere orthogonally and hence is a solution of the free boundary problem for the area functional in the ball. For a general class of (not necessarily rotationally symmetric) metrics on the annulus, which we call supercritical, we prove that σ₁(Σ)L(∂Σ) is dominated by that of the critical catenoid with equality if and only if the annulus is conformally equivalent to the critical catenoid by a conformal transformation which is an isometry on the boundary. Motivated by the annulus case, we show that a proper submanifold of the ball is immersed by Steklov eigenfunctions if and only if it is a free boundary solution. We then prove general upper bounds for conformal metrics on manifolds of any dimension which can be properly conformally immersed into the unit ball in terms of certain conformal volume quantities. We show that these bounds are only achieved when the manifold is minimally immersed by first Steklov eigenfunctions. We also use these ideas to show that any free boundary solution in two dimensions has area at least π, and we observe that this implies the sharp isoperimetric inequality for free boundary solutions in the two-dimensional case.     

Estimating the distance to a monotone function

In standard property testing, the task is to distinguish between objects that have a property 𝒫 and those that are ε‐far from 𝒫, for some ε > 0. In this setting, it is perfectly acceptable for the tester to provide a negative answer for every input object that does not satisfy 𝒫. This implies that property testing in and of itself cannot be expected to yield any information whatsoever about the distance from the object to the property. We address this problem in this paper, restricting our attention to monotonicity testing. A function f : {1,…,n} ↦ R is at distance ε_f from being monotone if it can (and must) be modified at ε_fn places to become monotone. For any fixed δ > 0, we compute, with probability at least 2/3, an interval [(1/2 − δ)ε,ε] that encloses ε_f. The running time of our algorithm is O(ε_f⁻¹ log log ε_f^{− 1} log n), which is optimal within a factor of loglog ε_f⁻¹ and represents a substantial improvement over previous work. We give a second algorithm with an expected running time of O(ε_f⁻¹ log nlog log log n). Finally, we extend our results to multivariate functions. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

The scaling window of the 2‐SAT transition

We consider the random 2‐satisfiability (2‐SAT) problem, in which each instance is a formula that is the conjunction of m clauses of the form x∨y, chosen uniformly at random from among all 2‐clauses on n Boolean variables and their negations. As m and n tend to infinity in the ratio m/n→α, the problem is known to have a phase transition at α_c=1, below which the probability that the formula is satisfiable tends to one and above which it tends to zero. We determine the finite‐size scaling about this transition, namely the scaling of the maximal window W(n, δ)=(α_?(n,δ), α₊(n,δ)) such that the probability of satisfiability is greater than 1?δ for α<α_? and is less than δ for α>α₊. We show that W(n,δ)=(1?Θ(n^?1/3), 1+Θ(n^?1/3)), where the constants implicit in Θ depend on δ. We also determine the rates at which the probability of satisfiability approaches one and zero at the boundaries of the window. Namely, for m=(1+ε)n, where ε may depend on n as long as |ε| is sufficiently small and |ε|n^1/3 is sufficiently large, we show that the probability of satisfiability decays like exp(?Θ(nε³)) above the window, and goes to one like 1?Θ(n^?1|ε|^?3 below the window. We prove these results by defining an order parameter for the transition and establishing its scaling behavior in n both inside and outside the window. Using this order parameter, we prove that the 2‐SAT phase transition is continuous with an order parameter critical exponent of 1. We also determine the values of two other critical exponents, showing that the exponents of 2‐SAT are identical to those of the random graph. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 201–256 2001     

The topology at infinity of Out(Fn)

We construct a bordification of Outer Space analogous to the Borel-Serre bordification of symmetric spaces. As an application, we show that Out(F _n ) is (2n-5)-connected at infinity and that it is a virtual duality group of dimension 2n-3. Oblatum 4-III-1998 & 2-XII-1999?Published online: 21 February 2000     

Random subgraphs of finite graphs: I. The scaling window under the triangle condition

We study random subgraphs of an arbitrary finite connected transitive graph ?? obtained by independently deleting edges with probability 1 ? p. Let V be the number of vertices in ??, and let Ω be their degree. We define the critical threshold p_c = p_c (??, λ) to be the value of p for which the expected cluster size of a fixed vertex attains the value λV^1/3, where λ is fixed and positive. We show that, for any such model, there is a phase transition at p_c analogous to the phase transition for the random graph, provided that a quantity called the triangle diagram is sufficiently small at the threshold p_c. In particular, we show that the largest cluster inside a scaling window of size |p ? p_c| = Θ(Ω^?1V^?1/3) is of size Θ(V^2/3), while, below this scaling window, it is much smaller, of order O(?^?2 log(V?³)), with ? = Ω(p_c ? p). We also obtain an upper bound O(Ω(p ? p_c)V) for the expected size of the largest cluster above the window. In addition, we define and analyze the percolation probability above the window and show that it is of order Θ(Ω(p ? p_c)). Among the models for which the triangle diagram is small enough to allow us to draw these conclusions are the random graph, the n‐cube and certain Hamming cubes, as well as the spread‐out n‐dimensional torus for n > 6. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Graph diameter in long‐range percolation

We study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^dWe study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^d$. We focus on the cases when an edge between x and y is added with probability decaying with the Euclidean distance as |x ? y|^?s+o(1) when |x ? y| → ∞. For s ∈ (d, 2d) we show that the graph diameter for the graph reduced to a box of side L scales like (log L)^Δ+o(1) where Δ^?1 := log₂(2d/s). In particular, the diameter grows about as fast as the typical graph distance between two vertices at distance L. We also show that a ball of radius r in the intrinsic metric on the (infinite) graph will roughly coincide with a ball of radius exp{r^1/Δ+o(1)} in the Euclidean metric. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 210‐227, 2011     

Crown-free Lattices and Their Related Graphs

This paper investigates links between some classes of graphs and some classes of lattices. We show that a co-atomic lattice is crown-free (i.e. dismantlable) if and only if it is a maximal clique lattice of a strongly chordal graph. We also prove that each crown-free lattice that is not a chain contains at least two incomparable doubly-irreducible elements x ₁ and x ₂ such that ↑ x ₁ and ↑ x ₂ are chains.     

On minors of graphs with at least 3n −4 edges

A point disconnecting set S of a graph G is a nontrivial m-separator, where m = |S|, if the connected components of G - S can be partitioned into two subgraphs, each of which has at least two points. A 3-connected graph is quasi 4-connected if it has no nontrivial 3-separators. Suppose G is a graph having n ≥ 6 points. We prove three results: (1) If G is quasi 4-connected with at least 3n - 4 edges, then the graph K^?₁, obtained from K₆ by deleting an edge, is a minor of G. (2) If G has at least 3n - 4 edges then either K^?₆ or the graph obtained by pasting two disjoint copies of K₅ together along a triangle is a minor of G. (3) If the minimum degree of G is at least 6, then K^?₆ is a minor of G. © 1993 John Wiley & Sons, Inc.     

Maximal surfaces and the universal Teichmüller space

We show that any element of the universal Teichmüller space is realized by a unique minimal Lagrangian diffeomorphism from the hyperbolic plane to itself. The proof uses maximal surfaces in the 3-dimensional anti-de Sitter space. We show that, in AdS _n+1, any subset E of the boundary at infinity which is the boundary at infinity of a space-like hypersurface bounds a maximal space-like hypersurface. In AdS₃, if E is the graph of a quasi-symmetric homeomorphism, then this maximal surface is unique, and it has negative sectional curvature. As a by-product, we find a simple characterization of quasi-symmetric homeomorphisms of the circle in terms of 3-dimensional projective geometry.     

On stable self‐similar blowup for equivariant wave maps

We consider corotational wave maps from (3 + 1) Minkowski space into the 3‐sphere. This is an energy supercritical model that is known to exhibit finite‐time blowup via self‐similar solutions. The ground state self‐similar solution f₀ is known in closed form, and according to numerics, it describes the generic blowup behavior of the system. We prove that the blowup via f₀ is stable under the assumption that f₀ does not have unstable modes. This condition is equivalent to a spectral assumption for a linear second order ordinary differential operator. In other words, we reduce the problem of stable blowup to a linear ODE spectral problem. Although we are unable at the moment to verify the mode stability of f₀ rigorously, it is known that possible unstable eigenvalues are confined to a certain compact region in the complex plane. As a consequence, highly reliable numerical techniques can be applied and all available results strongly suggest the nonexistence of unstable modes, i.e., the assumed mode stability of f₀. © 2011 Wiley Periodicals, Inc.     

Resolution trajectorielle et analyse numerique des equations differentielles stochastiques

Let (ξ_t) be the solution of the S.D.E. (E) of Section 1. Doss [3] has shown the existence of a difFerentiable function h and of a differentiate process parametrized by the process W,γ(W,t), such that: ξ_t = h(γ(W, t), W_t). For all continuous functions u, X_t is defined by: X_t = h(γ(u, t) u_t). We develop a scheme of approximation of X_t (Theorems 2-6 and 3-4). This scheme has th following properties:?

1)it does not explicitly involve γ or h; this property is crucial, because,generally, h is not explicitly known, and its numerical approximation would be costly.

2)it converges to X_t, provided that u has bounded quadratic variation.

3)for u = W, it coincides with a scheme proposed by Milshtein [6] for quadratic-mean approximation.

Further, we give an estimate of the error due to this scheme.