alfredo.hubard at inria.fr
I am currently a researcher at the GUDHI project at INRIA.
I am splitting my time between Paris and Sophia-Antipolis at Universite Marne la Vallee-Paris Est and Inria, respectively. I was a postdoc at Ecole Normale Superior and I spent a few months at KAIST as a visitor.
Algorthmique et programation (TP).
Introduction to Ramsey theory and extremal graph theory.
I completed my Ph.D. in September 2011 at the Courant Institute of Mathematical Sciences under advisement of Janos Pach and Boris Aronov.
My work is in discrete geometry and its interactions with other branches of mathematics and computer science. Current interests revolve around geometric and topological embeddings of simplicial complexes, face numbers and metric geometry with an eye on probability and topological data analysis.
- Shortest path embeddings of graphs on surfaces. (with V. Kaluža, A. de Mesmay and M. Tancer) Extended abstract in SoCG 2016. Accepted to Discrete and Computational Geometry.
"One Ring to rule them all, One Ring to find them". Given a surface S, is there a metric m such that every graph that is topologically embeddable in S, can be embedded with edges represented by shortest paths? This is the question. The answer is yes for the sphere or plane, by the theorems of Fary or Tutte, yes in the projective plane by the theorem of Koebe-Andreev-Thurston, yes in the torus and Klein bottle by case analysis with irreducible triangulations. For the Klein bottle the first metric you try doesn't work, and we can prove it (it is much more difficult to prove this then the aforementioned results). For larger genus we dont know. We prove that a random metric of constant curvature does not work with probability tending to 1 as the genus goes to infinity. We also construct a constant -1 curvature metric for which one can represent every embeddable graph, by an embedding in which each edge is the concatenation of $O(g)$ shortest paths.
- Limits of order types (with X. Goaoc, R. de Joannis de Verclos, J.S. Sereni and J. Volec). Extended abstract in SoCG 2015.
In this paper we applied the ideas around limits of combinatorial structures to combinatorial geometry. Razborov's flag algebras lead to improved bounds on an old Erdős problem. Upon observing that measures in space that do not charge hyperplanes define limits of order types, we wonder if measures may play the role that graphons play in the case of limits of graphs as developed by Borgs, Chayes, Lovász, Sós, Szegedy and Vesztergombi. The short answer is no, but in the subpace of uniform measures on convex bodies the answer is yes. Finally, we find an intriguing (but easy) connection between Cantor measures and the Sylvester problem of points in convex position.
- Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces (with E. Colin de Verdiere and A. de Mesmay) Extended abstract in SoCG 2014. Discrete and Computational Geometry.
Discrete and contiunous systolic geometry are (almost) the same thing. In this paper we showed that the concept of edge-width from topological graph theory is the same as the systole from Riemannian geometry, reducing a conjecture of Przytycka and Przytycki from 1993 to a theorem of Buser and Sarnak. Reductions from Gromov's asymptotic estimate for surfaces to Hutchinson's theorem and back follow similarly. In higher dimensions, we derive a systolic inequality for simplicial complexes. While in two dimensions volume might be discretised to faces or vertices, in higher dimension we do not know if there are manifolds for which it can be discretised to vertices. Back to surfaces, we make algorithmic a theorem of Buser on short pants decomposition and we show that there is does not exist one map to cut every triangulation effectively. We do it by the probabilistic method (following an idea of Guth, Parlier and Young) random triangulations are quantitatively hard to cut by a map.
- Realization spaces of arrangements of convex bodies (with M. Dobbins and A. Holmsen) Extended abstract in SoCG 2015.
There is tradeoff between topological and combiantorial complexity of realization spaces of combinatorial types. In this paper we show that this is the case for arrangements of convex bodies in the plane embedding Mnev's universality into a larger context. The starting point was a dual interpretation of the Folkman-Lawrence representation theorem of oriented matroid theory. Taking the pseudolines as support functions of a family of bodies (that can be easily made convex) we obtain convex bodies. The objectives are different, but there is strong resemblance to double pseudo line arrangements that appeared (previously) in the work of Pocchiola in collaboration with Habert and Pilaud.
- Regular systems of paths and families of convex sets in convex position (with M. Dobbins and A. Holmsen), Transactions of the American Mathematical Society.
Ramsey theorem can work as a microscope to find new combinatorial structures. In this paper we solved a conjecture of Pach and Toth from 2000 in the positive.
The conjecture states that for each k there exists a number l(k) and a function f(n,k) such that among any f convex bodies whose boundaries intersect at most k times, if each l-tuple is in convex position, then there are at least n of them in convex position. Pach and Tóth showed that l(2)=3 and l(4)=4, we guessed that l(k) would grow with k but in fact l(k)=5 for all k>4. To solve the conjecture we had to go quite far from the usual ideas in geometric Ramsey theory, extremal combinatorics and combinatorial geometry. We classified "regular systems of paths" which are related to Young tableaux, combinatorics on words and so on. I think they are more interesting than the conjecture itself.
- The Erdős-Szekeres problem for non-crossing convex sets (with M. Dobbins and A. Holmsen), Mathematika.
Among any n non crossing convex bodies in the plane there are at least ¼ log n of them in convex position.
In this paper we revealed the topological nature of a conjecture of Bisztriczky and Fejes Tóth connecting it to a conjecture of Goodman and Pollack. Combining this view with a kind of "one dimensional Dehn lemma" or "pumping lemma" we obtain big quantitative improvements with (arguably) simpler proofs on generalisations of the Erdős-Szekeres theorem for non-crossing convex bodies. We also improve on variants of the Erdős-Szekeres theorem with new proofs that hold in more generality. The Erdős-Szekeres theorem and its proofs are so beautiful that there is a whole industry of generalisations, what makes this paper somehow unique among them is that we decrease the number of variants instead of increasing them.
- Convex Equipartitions: The Spicy Chicken Theorem (with R. Karasev and B. Aronov), Geometria Dedicata.
It is possible to cut a chicken into a prime power number of pieces so that all have the same meat and the same spicy crust, in dimension two, this corresponds to the same area and the same perimeter. This is the prime power case the Nandakumar and Ramana Rao conjecture (very popular in the field when I was a student). The main new idea is to use optimal transport and/or dually (generalized Voronoi) power diagrams to reduce the problem to a Borsuk-Ulam type theorem on the configuration space of points in space.
Our results generalize to the sphere and the hyperbolic space and there are a number of corollaries, but probably the most exciting part is that we rediscovered a version of what Memarian calls the Gromov-Borsuk-Ulam theorem. Maybe there is a way to generalize the Waist of the sphere theorem with the aid of optimal transport.
The Borsuk-Ulam type result that we reduce the conjecture to was discovered by D. Fuchs, V. Vassiliev in the plane for powers of 2 and general prime power respectively, Karasev observed that this proof generalizes to every dimension. Answering to some skepticism among some discrete geometers about the work of these topologists, in this paper we provided an "Euler class-free" version of the Fuchs-Vassiliev proof that works in every dimension.
- Space crossing numbers(with B. Bukh), Extended abstract in SoCG 2011.
Combinatorics, Probability and Computing.
Any topological drawing in three dimensional space of a graph with many edges has many "space crossings". These space crossings should have been called "quadrisecants" following the knot theory literature, these are fourtuples of vertex disjoint edges that are stabbed by a single line in space. We combine linking numbers and the Thom class of the tangent bundle of the sphere with graph minors and with the famous probabilistic amplifying trick to obtain the main result. We also did some stair case convexity and in an appendix we proved a version of the same type lemma that was later improved by Fox, Pach and Suk. This paper is related to my favorite question in the field: how many faces can a d-simplicial complex embedded in 2d can have?
- Slicing convex sets and measures by a hyperplane. (with I. Barany and J. Jeronimo), Discrete and Computational Geometry.
In this paper we refine the famous Ham-Sandwich theorem by assuming that the measures are in a special position. If d measures in d dimensional space are "well separated" then one can cut them by a hyperplane in any prescribed fractions. Barany communicated a conjecture of us to Kincses who later generalized our result and a result of Cappell, Goodman, Pach, Pollack, Sharir and Wenger. Kincses showed that if the measures are proportional to uniform distributions on smooth strictly convex bodies, then the space of alpha cuts is a differentiable sphere dimension d-k, where k is the number of convex bodies.
- Order Types of Convex Bodies. (with L. Montejano, E. Mora and A. Suk), Order.
Among every very large family of non-crossing convex bodies, there is a large subfamily in convex position. The results of this paper were essentially contained in my bachelor thesis under the advisement of Luis Montejano that won the Sotero Prieto prize for the best mathematics thesis of the year in Mexico. We provided a new proof of a theorems of Bisztriczky and Fejes Tóth and Pach and Tóth on this topic. These results were much improved later in my collaboration with Michael G. Dobbins and Andreas Holmsen.
One tangential observation made in this paper is that the monotone subsequence theorem and the happy end theorem can be generalised to hyper graphs of any rank. This was later rediscovered by Matousek and Elias on one hand and by Fox, Pach, Sudakov, and Suk on the other. The Book proof of this generalisation was found by Moshkovitz and Shapira. The underlying structure is that of a signotope as in the work of Felsner.
- Computational Geometry and Topology for Data Analysis (Winter school with J.D.Boissonnat and F. Chazal).