Erdős Center Seminar

In the Fall of 2023 the Erdős Center of the Rényi Institute organizes a special semester on Discrete Geometry and Convexity. In the framework of this program, we will run a special seminar, attended by the participants and all members of our institute interested in the subject. The talks are typically on Tuesday 10-12 am, in the Tondos room of the Rényi Institute.

Recordings of previous talks are available here: Rényi Video Portal

September 11, 2023, 10am(CET) Note that this talk is on Monday!!

Peter van Hintum and Marius Tiba (Oxford):  Sharp stability for the Brunn-Minkowski inequality for arbitrary sets

Abstract: The Brunn-Minkowski inequality states that for (open) sets $A$ and $B$ in $R^d$, we have $|A+B|^{1/d} \geq |A|^{1/d}+|B|^{1/d}$. Equality holds if and only if $A$ and $B$ are convex and homothetic sets in $R^d$. In this talk, we present a sharp stability result for the Brunn-Minkowski inequality, concluding a long line of research on this problem. We show that if we are close to equality in the Brunn-Minkowski inequality, then $A$ and $B$ are close to being homothetic and convex, establishing the exact dependency between the three notions of closeness. This is based on joint work with Alessio Figalli, Peter van Hintum, and Marius Tiba.

September 19, 2023, 10am(CET) 

Ji Zeng (UC San Diego): Disjoint faces in simple topological graphs

Abstract: A topological graph is a graph drawn in the plane such that its vertices are represented by points, and its edges are represented by non-self-intersecting curves connecting the corresponding points. A topological graph is simple if any two of its edges intersect at most once, either at a common endpoint or at a proper crossing point. A k-face generated by a topological graph is the open bounded region enclosed by the edges of a non-self-intersecting $k$-cycle.

We prove that every $n$-vertex complete simple topological graph generates at least $\Omega(n)$ pairwise disjoint 4-faces. This improves upon a recent result by Hubard and Suk. As an immediate corollary, every $n$-vertex complete simple topological graph drawn in the unit square generates a 4-face with area at most $O(1/n)$. This can be seen as a topological variant of Heilbronn's problem for 4-faces. We construct examples showing that our result is asymptotically tight. We also discuss the similar problem for $k$-faces with arbitrary $k>=3$.

September 26, 2023, 10am(CET) 

Arseniy Sagdeev (MIPT and Rényi Institute): Infinite sets in (non-)Euclidean Ramsey Theory.

Abstract: A classic result in Euclidean Ramsey Theory states that for every infinite set of points $M$, there exists a two-coloring of the Euclidean space (of an arbitrary dimension) such that no isometric copy of $M$ is monochromatic. We will see that the direct analogue of this result also holds in $\ell_p$ planes for all real $p>1$, but fails for all polygonal norms. In case $p=\infty$, we will even show that there exists a single infinite set $M$ such that some of its isometric copies are monochromatic whenever an $n$-dimensional space is colored in less than $\log(n)$ colors.

October 3, 2023, 10am(CET)

Travis Dillon (MIT): Peeling the grid

Abstract: To peel a finite point set in Euclidean space, remove the vertices of its convex hull. The number of times a point set must be peeled to remove all of its vertices is called the layer number of the set. After outlining previous work on random point sets and "evenly distributed" point sets, I will turn to the grid ${1,2,...,n}^d$, whose layer number remains unknown. The central results of this talk are two short proofs that significantly improve the bounds for the layer number of grids. We show as a consequence that the layer number of grids is linear in $d$.

October 10, 2023, 10am(CET)

Alexandre Louvet (Université Paris-Est): Delta-packings for finite VC-dimension set systems and application to discrepancy

Abstract: A $\delta$-packing of a set system $(X,F)$ is a sub-collection $P$ of $F$ such that both elements of any pair of $P^2$ are at symmetric difference at least $\delta$. We present an efficient algorithm to compute maximal $\delta$-packings of set systems with finite VC-dimension.

Set discrepancy is a basic problem for data approximation and optimization. The goal is to find a 2-coloring of $X$ with minimum discrepancy between the two colors over each set in $F$. We use our packing algorithm to improve the runtime of algorithms solving set discrepancy in the case of finite VC-dimension set systems.

October 17, 2023, 10am(CET)

Zichao Dong (Rényi Institute): Convex polytopes in non-elongated point sets in $\mathbb{R}^d$

Abstract: For any finite point set $P \subset \mathbb{R}^d$, we denote by $\text{diam}(P)$ the ratio of the largest to the smallest distances between pairs of points in $P$. Let $c_{d, \alpha}(n)$ be the largest integer $c$ such that any $n$-point set $P \subset \mathbb{R}^d$ in general position, satisfying $\text{diam}(P) < \alpha\sqrt[d]{n}$ (informally speaking, `non-elongated'), contains a convex $c$-polytope. Valtr proved that $c_{2, \alpha}(n) \approx \sqrt[3]{n}$, which is asymptotically tight in the plane. We generalize the results by establishing $c_{d, \alpha}(n) \approx n^{\frac{d-1}{d+1}}$. Along the way we generalize the definitions and analysis of convex cups and caps to higher dimensions, which may be of independent interest. Joint work with Boris Bukh. 

October 24, 2023, 10am(CET)

Boris Aronov (New York University): Sparse geometric graphs with small dilation

Abstract: Given a set $S$ of $n$ points in $R^D$, and an integer $k$ such that $0 ≤ k < n$, we show that a geometric graph with vertex set $S$, at most $n − 1 + k$ edges, maximum degree five, and dilation $O(n/(k + 1))$ can be computed in time $O(n log n)$. For any $k$, we also construct planar $n$-point sets for which any geometric graph with $n − 1 + k$ edges has dilation $Ω(n/(k + 1))$; a slightly weaker statement holds if the points of $S$ are required to be in convex position.

Joint work with Mark de Berg, Otfried Cheong, Joachim Gudmundsson, Herman Haverkort, Michiel Smid, Antoine Vigneron.  Appeared in Computational Geometry: Theory and applications 40 (2008) 207–219.

October 31, 2023, 10am(CET)

Gehér Panna (Eötvös University): 1-planar unit distance graphs

Abstract: A matchstick graph is a plane graph with edges drawn as unit distance line segments. This class of graphs was introduced by Harborth who conjectured that a matchstick graph on $n$ vertices can have at most $\lfloor 3n - \sqrt{12n - 3}\rfloor$ edges. Recently his conjecture was settled by Lavollée and Swanepoel. In this talk we consider $1$-planar unit distance graphs. We say that a graph is a $1$-planar unit distance graph if it can be drawn in the plane such that all edges are drawn as unit distance line segments while each of them are involved in at most one crossing. We show that such graphs on $n$ vertices can have at most $3n-\sqrt[4]{n}/10$ edges. Joint work with Géza Tóth.

November 7, 2023, 10am(CET)

Attila Jung (Eötvös University) : k-dimensional transversals to balls.

Abstract: We prove fractional Helly and $(p,k+2)$-theorems for $k$-flats intersecting Euclidean balls. For example, we show that if for a collection of balls from $R^d$ a constant fraction of the $(k+2)$-tuples of balls have a k-flat intersecting them, then there is a $k$-flat intersecting a constant fraction of all the balls. We show colorful, spherical, and infinite variants as well.

Joint work with Dömötör Pálvölgyi.

November 14, 2023

Graph Drawing and Combinatorial Geometry Workshop

November 21, 2023, 10am(CET)

Sergio Cabello: (University of Ljubljana): Packing d-dimensional balls into a (d+1)-dimensional container

Abstract: We consider the problems of finding in $d+1$ dimensions a minimum-volume axis-parallel box, a minimum-volume arbitrarily-oriented box and a minimum-volume convex body into which a given set of $d$-dimensional unit-radius balls can be packed under translations. We give a constant-factor approximation algorithm for each of these containers. We also show that for n such balls, a container of volume $O(n^{1−1/d})$ is always sufficient and sometimes necessary. Joint work with Helmut Alt, Otfried Cheong, Ji-won Park and Nadja Seiferth.

November 28, 2023, 10am(CET)

Shakhar Smorodinsky (Ben-Gurion University): Polychromatic Coloring of Subsets

Abstract: We study polychromatic colorings and prove results of the following nature: For every positive integer $k$ and any finite set of points in the plane, one can $k$-color the pairs of points so that every disc that contains at least $5^k$ points, also contains a pair of points from each of the $k$ color classes.
We generalize this result to arbitrary hypergraphs with bounded VC-dimension that satisfy some nice properties (such as shrinakability and coveribility). We prove that there exists a constant $c=c(d)$ so that the $d+1$ tuples in any such hypergraph with VC-dimension at most $d$ can be $k$-colored so that any hyperedge of size at least $c^k$ contains a $d+1$ tuple from each of the $k$ color classes.
 
We also study the relation of the polychromatic subsets coloring to the classical well studied notion of vertex polychromatic coloring. Finally, we show a relation of the subsets coloring to a recently introduced notion of $\epsilon-t$-nets.
Joint work with Milos Stojakovic

December 5, 2023, 10am(CET)

Gábor Damásdi (Rényi Institute): Saturation results around the Erdős–Szekeres problems

Abstract: We consider saturation problems related to the celebrated Erdős--Szekeres convex polygon problem. For each $n \ge 7$, we construct a planar point set of size $(7/8) \cdot 2^{n-2}$ which is saturated for convex $n$-gons. That is, the set contains no $n$ points in convex position while the addition of any new point creates such a configuration. This demonstrates that the  saturation number is smaller than the Ramsey number for the Erdős--Szekeres problem. The proof also shows that the original Erdős--Szekeres construction is indeed saturated.

    Our construction is based on a similar improvement for the saturation version of the cups-versus-caps theorem. Moreover, we consider the generalization of the cups-versus-caps theorem to monotone paths in ordered hypergraphs. In contrast to the geometric setting, we show that this abstract saturation number is always equal to the corresponding Ramsey number. 

Joint work with Zichao Dong, Manfred Scheucher and Ji Zeng.

December 12, 2023, 10am(CET)

Boris Bukh (Carnegie Mellon University): Convex holes and almost uniform distribution in the unit cube

Abstract:  or $P\subset \mathbb{R}^d$, a hole is any set of convexly independent points whose convex hull contains no other points. We will discuss constructions of large finite sets that contain no large holes. The key role will be played by subsets of $[0,1]^d$ that contain about the same number of points in every dyadic box of a fixed volume. Based on joint works with Ting-Wei Chao and Ron Holzman.