Final Day of the Bézout Labex, November 19, 2024:

For the end of the Bézout Labex, a scientific meeting is organized, on the campus of Cité Descartes, Marne-la-Vallée (RER Noisy-Champs) – amphithéâtre Maurice Gross, ground floor of bâtiment Copernic, where some among the people that were important to the Labex are invited to give a talk: two former members, four former invited professors and two former students.

Abstracts:

Lucia Caramellino (Universita Tor Vergata, Roma): Regularization lemmas and applications.
Abstract: The talk focuses on some regularization lemmas and their consequences, for example their use to handle the convergence in the total variation distance. These results were originally developed in some papers with V. Bally and G. Poly and are perhaps the most substantial part of a twenty-year collaboration with the LAMA-Université Gustave Eiffel, made possible also thanks to the support of the Bézout Labex. Several applications will be discussed, including some recent ones.

Djalil Chafaï (DMA, ENS – PSL): Aspects of the Cutoff Phenomenon for Diffusions.
Abstract: The cutoff phenomenon, conceptualized in the context of finite Markov chains, states that for certain linear evolution equations, started from a point, the distance towards a long time equilibrium may become more and more abrupt in high dimensional state spaces and for certain choices of initial conditions. This can be seen as a critical competition between trend to equilibrium and initial condition. This talk is about the cutoff phenomenon for a few classes of linear and nonlinear diffusions.

Evgenii Chzhen (CNRS, Orsay): Gradient estimation for zero-order optimization
Abstract: I will give a short introduction into zero-order optimization via (randomized) gradient estimation based purely on function values. Starting from classical Kiefer–Wolfowitz algorithm towards more modern methods based on Gaussian smoothing and Stokes’ theorem, I will eventually present an estimator that uses randomisation on $\ell_1$ sphere and describe its’ theoretical (and maybe practical) advantages over previously used estimators. I will try to highlight how the variance of many randomized estimators can be analysed via Poincaré-type inequalities.
The talk is mainly introductory and the most recent results are developed with A. Akhavan, M. Pontil, A. Tsybakov.

Xavier Goaoc (Université de Lorraine, Nancy): Intersection patterns of topological set systems.
Abstract: The fractional Helly theorem of Katchalski, Liu and Kalai asserts that if in a family of convex sets in R^d, a positive proportion of the (d+1)-tuples have nonempty intersection, then a positive fraction of the sets have a point in common. In this talk, I will dicuss a conjecture of Kalai and Meshulam asserting that a similar property holds for arbitrary topological set systems under a condition of bounded “homological VC-dimension”.

Hélène Langlois (LAMA): Kernels and quasi-kernels in directed graphs.
Abstract: In directed graph theory, a kernel is an independent subset of vertices that absorbs every outside vertex. While certain graphs, like directed perfect graphs without directed cycles of length 3, ensure the existence of a kernel, the algorithmic complexity of finding one in this class remains an open question. This presentation explores recent advances in the search for kernels and also discuss quasi-kernels, a concept introduced by Chvátal and Lovász, which exist in all directed graphs but have not been thoroughly studied algorithmically. Key questions will be addressed, such as the minimal size of a quasi-kernel, inspired by a conjecture by Erdős and Székely.

Leonid Pastur (King’s College, London – Institute for Low Temperatures Physics and Engineering, Kharkiv): Dynamics of Qubits in Random Matrix Environment.
Abstract: We consider a model of a quantum system of two qubits embedded into an environment assuming that the environment is described by hermitian random matrices of size N. We obtain the large-N limit of the time-dependent reduced density matrix of qubits. We then use an analog of the Bogolyubov-van Hove (aka Born-Markov) asymptotic regime of statistical mechanics. The regime does not imply in general the Markovian dynamics of the reduced density matrix of our model and allows for analytical and numerical analysis of the evolution of widely used quantifiers of quantum correlations, mainly entanglement. We find a variety of interesting patterns of qubit dynamics. The patterns demonstrate the important role of the environment in the enhancement and the diversification of the evolution of quantum correlations. Presented results can also be viewed as a manifestation of the universality of certain properties of the decoherent qubit evolution that have been found in various exact and approximate versions of the models where the environment is described by free bosons.

Sylvia Serfaty (Courant Institute, New-York): Mean-field limits for Coulomb-type dynamics.
Abstract: We consider a system of N points in singular interaction of Coulomb or Riesz type, evolving by gradient flow or conservative flow (such as the point vortex system in 2D) with or without noise. We describe the convergence to the mean-field limit by a modulated energy method, that relies on a commutator estimate. We also discuss the question of obtaining global-in-time convergence.

Uli Wagner (Institute of Science and Technology Austria): Topology and Hardness of $4$-colouring $G$-colourable graphs.
Abstract: Deciding whether a given input graph is $3$-colorable is one of the original NP-complete problems. A long-standing conjecture asserts that the following relaxation of this question, called the approximate graph colouring problem, remains NP-hard for all constants $k\geq 3$: Distinguish between graphs that are $3$-colorable and graphs that are not even $k$-colorable. Khanna, Linial, and Safra proved this for $k=4$, and the current record, NP-hardness for $k=5$, was established only quite recently by Bulín, Krokhin, and Opršal. 
Here, we consider the following generalization of this problem to graph homomorphism. Fox a fixed graph $G$, the $G$-coloring problem is the problem of deciding whether a given input graph admits a graph homomorphism (an edge preserving map between the vertex sets) to $G$ (the case where $G=K_k$, the complete graph on $k$ vertices, corresponds to $k$-colorability). A classical result of Hell and Nešetřil from 1990 asserts that $G$-coloring is NP-hard for every fixed finite, non-bipartite, loop-less graph $G$. 
Brakensiek and Guruswami conjectured that this hardness extends to the following promise graph homomorphism problem (which includes the approximate graph coloring problem as a special case): Fix a pair of non-bipartite loop-less graphs $G$ and $H$ such that there is a homomorphism from $G$ to $H$. Then it is NP-hard to distinguish graphs that are $G$-colorable from graphs that are not even $H$-colorable. We confirm this conjecture in the case when both $G$ and $G$ are $4$-colourable. This is a common generalisation of the aforementioned result of Khanna, Linial, and Safra, and of more recent work of Krokhin and Opršal (which establishes the case where $G$ and $H$ are $3$-colorable). 
The result is obtained by combining an algebraic methods for studying the complexity of a broader class of \emph{promise constraint satisfaction problems} with methods from topological combinatorics and equivariant obstruction theory. 
Joint work with Sergey Avvakumov, Marek Filakovský, Jakub Opršal, and Gianluca Tasinato

Organization

Scientific committee: Raphaël Danchin, Matthieu Fradelizi, Benjamin Jourdain, Cyril Nicaud

Organizing committee: Matthieu Fradelizi, Nathalie Gambiny, Cyril Nicaud,