Universite Libre de Bruxelles

This talk will focus on the following two related problems:
    (1) What is the minimum number of edges in a graph containing all $n$-vertex planar graphs as subgraphs? A simple construction of Babai, Erdos, Chung, Graham, and Spencer (1982) has $O(n^{3/2})$ edges, which is the best known upper bound.
    (2) What is the minimum number of *vertices* in a graph containing all $n$-vertex planar graphs as *induced* subgraphs? Here steady progress has been achieved over the years, culminating in a $O(n^{4/3})$ bound due to Bonamy, Gavoille, and Pilipczuk (2019).
    As it turns out, a bound of $n^{1+o(1)}$ can be achieved for each of these two problems. The two constructions are somewhat different but are based on a common technique. In this talk I will first give a gentle introduction to the area and then sketch these constructions. The talk is based on joint works with Vida Dujmović, Louis Esperet, Cyril Gavoille, Piotr Micek, and Pat Morin.

I will describe joint work with Bruno Premoselli which gives a new existence theorem for negatively curved Einstein 4-manifolds, which are obtained by smoothing the singularities of hyperbolic cone metrics. Let (M_k) be a sequence of compact 4-manifolds and let g_k be a hyperbolic cone metric on M_k with cone angle \alpha (independent of k) along a smooth surface S_k. We make the following assumptions:

1. The injectivity radius i(k) of M_k tends to infinity (where in defining injectivity radius we ignore those geodesics which hit the cone singularity)

2. The normal injectivity radius of S_k is at least i(k)/2.

3. The area of the singular locii satisfy A(S_k)\leq C \exp(5 i(k)/2) for some C independent of k.

When these assumptions hold, we prove that for all large k, M_k carries a smooth Einstein metric of negative curvature. The proof involves a gluing theorem and a parameter dependent implicit function theorem (where k is the parameter). As I will explain, negative curvature plays an essential role in the proof. (For those who may be aware of our arxiv preprint, https://arxiv.org/abs/1802.00608 [arxiv.org], the work
I will describe has a new feature, namely we now treat all cone angles, and not just those which are greater than 2\pi. This gives lots more examples of Einstein 4-manifolds.)

When a liquid drop is deposited over a solid surface whose temperature is sufficiently above the boiling point of the liquid, the drop does not experience nucleate boiling but rather levitates over a thin layer of its own vapor. This is known as the Leidenfrost effect. Whilst highly undesirable in certain cooling applications, because of a drastic decrease of the energy transferred between the solid and the evaporating liquid due to poor heat conductivity of the vapor, this effect can be of great interest in many other processes profiting from this absence of contact with the surface that considerably reduces the friction and confers an extreme mobility on the drop. During this presentation, I hope to provide a good vision of some of the knowledge on this subject through some recent studies that we have done. First, I will present a simple fitting-parameter-free theory of the Leidenfrost effect, successfully validated with experiments, covering the full range of stable shapes, i.e., from small quasi-spherical droplets to larger puddles floating on a pocketlike vapor film. Then, I will discuss the end of life of these drops that appear either to explode or to take-off. Finally, I will show that the Leidenfrost effect can also be observed over hot baths of non-volatile liquids. The understanding of the latter situation, compare to the classical Leidenfrost effect on solid substrate, provides new insights on the phenomenon, whether it concerns levitation or its threshold.

Twistor spaces were originally devised as a way to use techniques of complex geometry to study 4-dimensional Riemannian manifolds. In this talk I will show that they also make it possible to apply techniques from symplectic geometry.  In the first part of the talk I will explain that when the 4-manifold satisfies a certain curvature inequality, its twistor space carries a natural symplectic structure. In the second part of the talk I will discuss some results in Riemannian geometry which can be proved via the symplectic geometry of the twistor space. Finally, if there is time, I will end with some speculation
about potential future applications, involving Poincaré—Einstein 4-manifolds, minimal surfaces and distinguished closed curves in their conformal infinities

Incomplete Cholesky factorizations are commonly used as black-box preconditioners for the iterative solution of large sparse symmetric positive definite linear systems. Traditionally, incomplete 
factorizations are obtained by dropping (i.e., replacing by zero) some entries of the factors during the factorization process. Here we consider a less common way to approximate the factors : through low-rank approximations of some off-diagonal blocks. We focus more specifically on approximation schemes that satisfy the orthogonality condition: the approximation should be orthogonal to the corresponding approximation error.

The resulting incomplete Cholesky factorizations have attractive theoretical properties. First, the underlying factorization process can be shown breakdown-free. Further, the condition number of the 
preconditioned system, that characterizes the convergence rate of standard iterative schemes, can be shown bounded as a function of the accuracy of individual approximations. Hence, such a bound can benefit from better approximations, but also from some algorithmic peculiarities. Eventually, the above results can be shown to hold for any symmetric positive definite system matrix.

On the practical side, we consider a particular variant of the preconditioner. It relies on a nested dissection ordering of unknowns to  insure an attractive memory usage and operations count. Further, it exploits in an algebraic way the low-rank structure present in system matrices that arise from PDE discretizations. A preliminary implementation of the method is compared with similar Cholesky and 
incomplete Cholesky factorizations based on dropping of individual entries.

We revisit the problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time sorting algorithm achieving this bound up to a constant factor. They established a crucial link between the entropy of the input partial order and the information-theoretic lower bound. However, their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it unpractical. We develop efficient algorithms for sorting under partial information, derived from approximation and exact algorithms for computing the partial order entropy.

This is joint work with S. Fiorini, G. Joret, R. Jungers, and I. Munro.

Algebraic multigrid methods are nowadays popular to solve linear systems arising from the discretization of elliptic PDEs. They try to combine the efficiency of well tuned specific schemes like classical (geometric-based) multigrid methods, with the ease of use of general purpose preconditioning techniques. This requires to define automatic coarsening procedures, which set up an hierarchy of coarse representations of the problem at hand using only information from the system matrix.

In this talk, we focus on aggregation-based algebraic multigrid methods. With these, the coarse unknowns are simply formed by grouping variables in disjoint subset called aggregates.

In the first part of the talk, we consider symmetric M-matrices with nonnegative row-sum. We show how aggregates can then be formed in such a way that the resulting method satisfies a prescribed bound on its convergence rate. That is, instead of the classical paradigm that applies an algorithm and then performs its analysis, the analysis is integrated in the set up phase so as to enforce minimal quality requirements. As a result, we obtain one of the first algebraic multigrid method with full convergence proof. The efficiency of the method is further illustrated by numerical results performed on finite difference or linear finite element discretizations of second order elliptic PDEs; the set of problems includes problems with jumps, anisotropy, reentering corners and/or unstructured meshes, sometimes with local refinement.

In the second part of the talk, we discuss nonsymmetric problems. We show how the previous approach can be extended to M-matrices with row- and column-sum both nonnegative, which includes some stable discretizations of convection-diffusion equations with divergence free convective flow. Some (preliminary) numerical results are also presented.

This is joint work with Artem Napov.

In the first part of my presentation, I plan to review several applications modelled by delay differential equations (DDEs) starting from familiar examples such as traffic flow problems to physiology and industrial problems. Although delay differential equations have the reputation to be difficult mathematical problems, there is a renewed interest for both old and new problems modelled by DDEs. In the second part of my talk, I’ll emphasize the need of developing asymptotic tools for DDEs in order to guide our numerical simulations and help our physical understanding. I illustrate these ideas by considering the response of optical optoelectronic oscillators that have been studied both experimentally and numerically.