Profiles
All my publications are listed here, but you can also find them in various corners of the Internet:Co-authors
Publications
Preprints
-
Concentration for Poisson U-statistics
Gilles Bonnet and Anna GusakovaAbstract
In this article we obtain concentration inequalities for Poisson $U$-statistics $F_m(f,\eta)$ of order $m\ge 1$ with kernels $f$ under general assumptions on $f$ and the intensity measure $\gamma \Lambda$ of underlying Poisson point process $\eta$. The main result are new concentration bounds of the form $$\mathbb{P}(|F_m ( f , \eta) -\mathbb{E} F_m ( f , \eta)| \ge t)\leq 2\exp(-I(\gamma,t)),$$ where $I(\gamma,t)$ satisfies $I(\gamma,t)=\Theta(t^{1\over m}\log t)$ as $t\to\infty$ and $\gamma$ is fixed. The function $I(\gamma,t)$ is given explicitly in terms of parameters of the assumptions satisfied by $f$ and $\Lambda$. One of the key ingredients of the proof are fine bounds for the centred moments of $F_m(f,\eta)$. We discuss the optimality of obtained bounds and consider a number of applications related to Gilbert graphs and Poisson hyperplane processes in constant curvature spaces.
Link(s)
-
Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes
(Journal version)
Gilles Bonnet, Daniel Dadush, Uri Grupel, Sophie Huiberts and Galyna LivshytsAbstract
The combinatorial diameter $\operatorname{diam}(P)$ of a polytope $P$ is the maximum shortest path distance between any pair of vertices. In this paper, we provide upper and lower bounds on the combinatorial diameter of a random “spherical” polytope, which is tight to within one factor of dimension when the number of inequalities is large compared to the dimension. More precisely, for an $n$-dimensional polytope $P$ defined by the intersection of $m$ i.i.d.\ half-spaces whose normals are chosen uniformly from the sphere, we show that $\operatorname{diam}(P)$ is $\Omega(nm^{\frac{1}{n-1}})$ and $O(n^2 m^{\frac{1}{n-1}} + n^5 4^n)$ with high probability when $m \geq 2^{\Omega(n)}$. For the upper bound, we first prove that the number of vertices in any fixed two dimensional projection sharply concentrates around its expectation when $m$ is large, where we rely on the $\Theta(n^2 m^{\frac{1}{n-1}})$ bound on the expectation due to Borgwardt [Math. Oper. Res., 1999]. To obtain the diameter upper bound, we stitch these \textit{shadows paths} together over a suitable net using worst-case diameter bounds to connect vertices to the nearest shadow. For the lower bound, we first reduce to lower bounding the diameter of the dual polytope $P^\circ$, corresponding to a random convex hull, by showing the relation $\operatorname{diam}(P) \geq (n-1)(\operatorname{diam}(P^\circ)-2)$. We then prove that the shortest path between any ``nearly’’ antipodal pair vertices of $P^\circ$ has length $\Omega(m^{\frac{1}{n-1}})$.
Link(s)
Published
2024
-
Glass-like Caging with Random Planes
Physical Review E, no 109
Gilles Bonnet, Patrick Charbonneau and Giampaolo FolenaAbstract
The richness of the mean-field solution of simple glasses leaves many of its features challenging to interpret. A minimal model that illuminates glass physics the same way the random energy model clarifies spin glass behavior would therefore be beneficial. Here, we propose such a real-space model that is amenable to infinite-dimensional $d\rightarrow\infty$ analysis and is exactly solvable in finite $d$ in some regimes. By joining analysis with numerical simulations, we uncover geometrical signatures of the dynamical and jamming transitions and obtain insight into the origin of activated processes. Translating these findings into the context of standard glass formers further reveals the role played by non-convexity in the emergence of Gardner and jamming physics.
Link(s)
2023
-
Limit theory of sparse random geometric graphs in high dimensions
Stochastic Processes and their Applications, vol 163, 203-236
Gilles Bonnet, Christian Hirsch, Daniel Rosen and Daniel WillhalmAbstract
We study topological and geometric functionals of $l_\infty$-random geometric graphs on the high-dimensional torus in a sparse regime, where the expected number of neighbors decays exponentially in the dimension. More precisely, we establish moment asymptotics, functional central limit theorems and Poisson approximation theorems for certain functionals that are additive under disjoint unions of graphs. For instance, this includes simplex counts and Betti numbers of the Rips complex, as well as general subgraph counts of the random geometric graph. We also present multi-additive extensions that cover the case of persistent Betti numbers of the Rips complex.
Keywords
Random geometric graph, High dimension, Functional central limit theorem, Poisson approximation, Betti numbers.
Link(s)
2022
-
Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes
(Proceeding)
Proceeding of the 38th International Symposium on Computational Geometry (SoCG 2022), no 18, 18:1-18:15
Gilles Bonnet, Daniel Dadush, Uri Grupel, Sophie Huiberts and Galyna LivshytsAbstract
The combinatorial diameter $\operatorname{diam}(P)$ of a polytope $P$ is the maximum shortest path distance between any pair of vertices. In this paper, we provide upper and lower bounds on the combinatorial diameter of a random “spherical” polytope, which is tight to within one factor of dimension when the number of inequalities is large compared to the dimension. More precisely, for an $n$-dimensional polytope $P$ defined by the intersection of $m$ i.i.d.\ half-spaces whose normals are chosen uniformly from the sphere, we show that $\operatorname{diam}(P)$ is $\Omega(nm^{\frac{1}{n-1}})$ and $O(n^2 m^{\frac{1}{n-1}} + n^5 4^n)$ with high probability when $m \geq 2^{\Omega(n)}$. For the upper bound, we first prove that the number of vertices in any fixed two dimensional projection sharply concentrates around its expectation when $m$ is large, where we rely on the $\Theta(n^2 m^{\frac{1}{n-1}})$ bound on the expectation due to Borgwardt [Math. Oper. Res., 1999]. To obtain the diameter upper bound, we stitch these \textit{shadows paths} together over a suitable net using worst-case diameter bounds to connect vertices to the nearest shadow. For the lower bound, we first reduce to lower bounding the diameter of the dual polytope $P^\circ$, corresponding to a random convex hull, by showing the relation $\operatorname{diam}(P) \geq (n-1)(\operatorname{diam}(P^\circ)-2)$. We then prove that the shortest path between any ``nearly’’ antipodal pair vertices of $P^\circ$ has length $\Omega(m^{\frac{1}{n-1}})$.
Keywords
Random Polytopes, Combinatorial Diameter, Hirsch Conjecture.
Link(s)
-
Facets of spherical random polytopes
Mathematische Nachrichten, vol 295, 1901–1933
Gilles Bonnet and Eliza O'ReillyAbstract
Facets of the convex hull of $n$ independent random vectors chosen uniformly at random from the unit sphere in $\mathbb{R}^d$ are studied. A particular focus is given on the height of the facets as well as the expected number of facets as the dimension increases. Regimes for $n$ and $d$ with different asymptotic behavior of these quantities are identified and asymptotic formulas in each case are established. Extensions of some known results in fixed dimension to the case where dimension tends to infinity are described.
Link(s)
Image(s)
Video
-
Weak convergence of the intersection point process of Poisson hyperplanes
Annales de l'Institut Henri Poincaré (B) Probabilités et Statistique, vol 58, no 2, 1208-1227
Anastas Baci, Gilles Bonnet and Christoph ThäleAbstract
This paper deals with the intersection point process of a stationary and isotropic Poisson hyperplane process in $\mathbb{R}^d$ of intensity $t>0$, where only hyperplanes that intersect a centred ball of radius $R>0$ are considered. Taking $R=t^{-\frac{d}{d+1}}$ it is shown that this point process converges in distribution, as $t\to\infty$, to a Poisson point process on $\mathbb{R}^d\setminus{0}$ whose intensity measure has power-law density proportional to $|x|^{-(d+1)}$ with respect to the Lebesgue measure. A bound on the speed of convergence in terms of the Kantorovich-Rubinstein distance is provided as well. In the background is a general functional Poisson approximation theorem on abstract Poisson spaces. Implications on the weak convergence of the convex hull of the intersection point process and the convergence of its $f$-vector are also discussed, disproving and correcting thereby a conjecture of Devroye and Toussaint [J.\ Algorithms 14.3 (1993), 381–394] in computational geometry.
Visualization
In the Geogebra applet below you can visualize the intersection process derived from up to 30 i.i.d. lines uniformly distributed among the lines intersecting the unit disc. If you have some troubles with the zoom, you can also try to follow this link and click on the bottom right of the applet to activate the full screen mode.
Keywords
convex hull, integral geometry, intersection point process, Poisson hyperplane process, Poisson point process approximation, rate of convergence, weak convergence.
Link(s)
Image(s)
Video
2021
-
Phase transition for the volume of high-dimensional random polytopes
Random Structures and Algorithms, vol 58, 648-663
Gilles Bonnet, Zakhar Kabluchko and Nicola TurchiAbstract
The beta polytope $P_{n,d}^\beta$ is the convex hull of $n$ i.i.d. random points distributed in the unit ball of $\mathbb{R}^d$ according to a density proportional to $(1-\lVert{x}\rVert^2)^{\beta}$ if $\beta>-1$ (in particular, $\beta=0$ corresponds to the uniform distribution in the ball), or uniformly on the unit sphere if $\beta=-1$. We show that the expected normalized volumes of high-dimensional beta polytopes exhibit a phase transition and we describe its shape. We derive analogous results for the intrinsic volumes of beta polytopes and, when $\beta=0$, their number of vertices.
Keywords
Beta distribution, convex hull, expected volume, phase transition, random polytopes.
Link(s)
Image(s)
Video
-
Sharp inequalities for the mean distance of random points in convex bodies
Advances in Mathematics, vol 386, 27 pages
Gilles Bonnet, Anna Gusakova, Christoph Thäle and Dmitry ZaporozhetsAbstract
For a convex body $K\subset\mathbb{R}^d$ the mean distance $\Delta(K)=\mathbb{E}|X-Y|$ is the expected Euclidean distance of two independent and uniformly distributed random points $X,Y\in K$. Optimal lower and upper bounds for ratio between $\Delta(K)$ and the first intrinsic volume $V_1(K)$ of $K$ (normalized mean width) are derived and degenerate extremal cases are discussed. The argument relies on Riesz’s rearrangement inequality and the solution of an optimization problem for powers of concave functions. The relation with results known from the existing literature is reviewed in detail.
Keywords
Concave funcion, convex body, geometric extremum problem, geometric inequality, intrinsic volume, mean distance, Riesz rearrangement inequality, sharp geometric inequality.
Link(s)
Image(s)
2020
-
The maximal degree in a Poisson-Delaunay graph
Bernoulli, vol 26, no 2, 948-979
Gilles Bonnet and Nicolas ChenavierAbstract
We investigate the maximal degree in a Poisson-Delaunay graph in $\mathbf{R}^d$, $d\geq 2$, over all nodes in the window $\mathbf{W}_\rho:= \rho^{1/d}[0,1]^d$ as $\rho$ goes to infinity. The exact order of this maximum is provided in any dimension. In the particular setting $d=2$, we show that this quantity is concentrated on two consecutive integers with high probability. An extension of this result is discussed when $d\geq 3$.
Keywords
degree, Delaunay graph, extreme values, Poisson point process.
Link(s)
Image(s)
2019
-
Threshold phenomena for high-dimensional random polytopes
Communications in Contemporary Mathematics, vol 21, no 5, 30 pages
Gilles Bonnet, Giorgos Chasapis, Julian Grote, Daniel Temesvari and Nicola TurchiAbstract
Let $X_1,\ldots,X_N$, $N>n$, be independent random points in $\mathbb{R}^n$, distributed according to the so-called beta or beta-prime distribution, respectively. We establish threshold phenomena for the volume, intrinsic volumes, or more general measures of the convex hulls of these random point sets, as the space dimension $n$ tends to infinity. The dual setting of polytopes generated by random halfspaces is also investigated.
Keywords
Beta distribution, beta-prime distribution, convex bodies, isotropic log-concave measures, phase transition, random polytopes, volume threshold.
Link(s)
Image(s)
2018
-
Cells with many facets in a Poisson hyperplane tessellation
Advances in Mathematics, vol 324, 203-240
Gilles Bonnet, Pierre Calka and Matthias ReitznerAbstract
Let $Z$ be the typical cell of a stationary Poisson hyperplane tessellation in $\mathbb{R}^d$. The distribution of the number of facets $f(Z)$ of the typical cell is investigated. It is shown, that under a well-spread condition on the directional distribution, the quantity $n^{\frac{2}{d-1}}\sqrt[n]{\mathbb{P}(f(Z)=n)}$ is bounded from above and from below. When $f(Z)$ is large, the isoperimetric ratio of $Z$ is bounded away from zero with high probability. These results rely on one hand on the Complementary Theorem which provides a precise decomposition of the distribution of $Z$ and on the other hand on several geometric estimates related to the approximation of polytopes by polytopes with fewer facets. From the asymptotics of the distribution of $f(Z)$, tail estimates for the so-called $\Phi$ content of $Z$ are derived as well as results on the conditional distribution of $Z$ when its $\Phi$ content is large.
Keywords
Poisson hyperplane tessellation, random polytopes, typical cell, directional distribution, Complementary Theorem, D.G. Kendall's problem.
Link(s)
Image(s)
-
Polytopal approximation of elongated convex bodies
Advances in Geometry, vol 18, no 1, 105-114
Gilles BonnetAbstract
This paper presents bounds for the best approximation, with respect to the Hausdorff metric, of a convex body $K$ by a circumscribed polytope $P$ with a given number of facets. These bounds are of particular interest if $K$ is elongated. To measure the elongation of the convex set, its isoperimetric ratio $ V_j(K)^{1/j} V_i(K)^{-1/i} $ is used.
Keywords
polytopal approximation, elongated convex bodies, isoperimetric ratio, δ-net.
Link(s)
Image(s)
-
Small cells in a Poisson hyperplane tessellation
Advances in Applied Mathematics, vol 95, 31-52
Gilles BonnetAbstract
Until now, little was known about properties of small cells in a Poisson hyperplane tessellation. The few existing results were either heuristic or applying only to the two dimensional case and for very specific size functionals and directional distributions. This paper fills this gap by providing a systematic study of small cells in a Poisson hyperplane tessellation of arbitrary dimension, arbitrary directional distribution $\varphi$ and with respect to an arbitrary size functional $\Sigma$. More precisely, we investigate the distribution of the typical cell $Z$, conditioned on the event $ { \Sigma(Z) < a }$, where $a\to0$ and $\Sigma$ is a size functional, i.e. a functional on the set of convex bodies which is continuous, not identically zero, homogeneous of degree $k>0$, and increasing with respect to set inclusion. We focus on the number of facets and the shape of such small cells. We show in various general settings that small cells tend to minimize the number of facets and that they have a non degenerated limit shape distribution which depends on the size $\Sigma$ and the directional distribution. We also exhibit a class of directional distribution for which cells with small inradius do not tend to minimize the number of facets.
Keywords
Poisson hyperplane tessellation, typical cell, small cells, number of facets, shape, size functional.
Link(s)
Image(s)
2017
-
Monotonicity of facet numbers of random convex hulls
Journal of Mathematical Analysis and Applications, vol 455, no 2, 1351-1364
Gilles Bonnet, Julian Grote, Daniel Temesvari, Christoph Thäle, Nicola Turchi and Florian WespiAbstract
Let $X_1,\ldots,X_n$ be independent random points that are distributed according to a probability measure on $\mathbb{R}^d$ and let $P_n$ be the random convex hull generated by $X_1,\ldots,X_n$ ($n\geq d+1$). Natural classes of probability distributions are characterized for which, by means of Blaschke-Petkantschin formulae from integral geometry, one can show that the mean facet number of $P_n$ is strictly monotonically increasing in $n$.
Keywords
Blaschke–Petkantschin formula, mean facet number, random convex hull.
Link(s)
Image(s)
Theses
2016
-
PhD thesis
Poisson hyperplane tessellation: Asymptotic probabilities of the zero and typical cells
Gilles Bonnet
Supervisor: Prof. Matthias ReitznerAbstract
We consider the distribution of the zero and typical cells of a (homogeneous) Poisson hyperplane tessellation. We give a direct proof adapted to our setting of the well known Complementary Theorem. We provide sharp bounds for the tail distribution of the number of facets. We also improve existing bounds for the tail distribution of size measurements of the cells, such as the volume or the mean width. We improve known results about the generalised D.G. Kendall’s problem, which asks about the shape of large cells. We also show that cells with many facets cannot be close to a lower dimensional convex body. We tacle the much less study problem of the number of facets and the shape of small cells. In order to obtain the results above we also develop some purely geometric tools, in particular we give new results concerning the polytopal approximation of an elongated convex body.
Keywords
stochastic geometry, convex geometry, tessellation, mosaic, random tessellation, Poisson hyperplane tessellation, zero cell, typical cell, asymptotic probabilities, D.G. Kendall's problem, Complementary Theorem, polytopal approximation, delta-net, elongated convex bodies, geometric integral transformation formulae, facets, phi-Content, center, shape, tail distribution, small cells.
Link(s)
Image(s)
2013
-
Master thesis
Amoebas of algebraic hyper-surfaces
Gilles Bonnet
Supervisor: Prof. Martin SombraAbstract
This thesis completed my Master of Advanced Mathematics from the University of Barcelona.
2009
-
Master thesis
Introduction à la Géométrie Algébrique
Gilles Bonnet
Supervisor: Prof. Liu QingAbstract
This thesis completed my Master of Mathematics from the University of Bordeaux.