BBC+G

Organizers: János Pach, Dömötör Pálvölgyi, Géza Tóth

This is the joint Budapest Big Combinatorics + Geometry (BBC+G) Seminar of the Geometry Seminar of the Rényi Institute, the GeoScape Research Group and the Lendület Combinatorial Geometry (CoGe) Research Group.
The talks are typically on Friday 2-4 pm, in the Rényi Institute AND online, unless specified otherwise. This can change depending on the time zone of the speaker.
Zoom link for the online lectures: https://zoom.us/j/96029300722 and the password is the first 6 terms from the Fibonacci sequence starting with 11.
Recordings of past online talks of the BBC+G Seminar can be watched at the BBC+G video archive.

2022 Fall Semester - every Friday at 14:00 in the "Dog Room" of the Rényi Institute AND online (unless specified otherwise)

December 16, 2022, 2pm (CET)
István Lénárt: TBA

Abstract: TBA


December 9, 2022, 2pm (CET) online only!
António Girão: Monotone Arrays And A Multidimensional Ramsey Theorem

Abstract: A foundational result in Ramsey theory appears in a paper of Erd\H{o}s and Szekeres from 1935: any sequence of $n^2+1$ distinct real numbers contains either an increasing or decreasing subsequence of length $n+1$.   This simple result was one of the starting seeds for the development of Ramsey theory. There are a number of different ways to generalise the Erd\H{o}s-Szekeres Theorem  to higher dimensions but perhaps the most natural approach was developed thirty years ago by Fishburn and Graham. A {\em $d$-dimensional array} is an injective function $f$ from $A_1 \times \ldots \times A_d$ to $\mathbb{R}$ where $A_1, \ldots A_d$ are non-empty subsets of $\mathbb{Z}$; we say $f$ has {\em size} $|A_1|\times\dots\times|A_d|$; if $|A_i|=n$ for each $i$, it will be convenient to say that $f$ has {\em size} $[n]^d$. A multidimensional array is said to be \textit{monotone} if for each direction all the $1$-dimensional subarrays in that direction are increasing or decreasing.  In other words, for every $i$, one of the following holds:
For every choice of $a_j$, $j\ne i$, the function $f(a_1,\dots,a_{i-1},x,a_{i+1},\dots,a_d)$ is increasing in $x$.
For every choice of $a_j$, $j\ne i$, the function $f(a_1,\dots,a_{i-1},x,a_{i+1},\dots,a_d)$ is decreasing in $x$.
Let $M_d(n)$ be the smallest $N$ such that a $d$-dimensional array on $[N]^{d}$ contains a monotone $d$-dimensional subarray of size $[n]^d$. We will show how to improve the bounds on $M_d(n)$ recently proved by Buci\'c, Sudakov and Tran. More precisely, we will show that a doubly exponential upper bound holds in all dimensions.
Theorem. For every $d\geq 2$, there is $C_d>0$, such that for every positive $n$, $M_d(n)\leq 2^{n^{C_dn^{d-1}}}$.
Finally, we will see how this is intimately connected to a generalisation of Ramsey Theorem on the cartesian product of cliques. 

Bibliography:
António Girão, Gal Kronenberg, Alex Scott: A multidimensional Ramsey Theorem , arXiv


December 2, 2022, 2pm (CET) online only!
James Davies: Odd distances in colourings of the plane

Abstract: We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd distance from each other.

Bibliography:
James Davies: Odd distances in colourings of the plane, arXiv


November 25, 2022, 2pm (CET) online only!
Barnabás Janzer: Rotation inside convex Kakeya sets

Abstract: Let K be a convex body (a compact convex set) in $R^d$, that contains a copy of another body S in every possible orientation. Is it always possible to continuously move any one copy of S into another, inside K? As a stronger question, is it always possible to continuously select, for each orientation, one copy of S in that orientation? In this talk we answer these questions of Croft.

Bibliography:
Barnabás Janzer: Rotation inside convex Kakeya sets , arXiv


November 18, 2022, 2pm (CET)
József Solymosi: On the structure of pointsets with many collinear triples

Abstract: It is conjectured that if a finite set of points in the plane contains many collinear triples, then there is some structure in the set. We will show that under some combinatorial conditions, such pointsets have special configurations of triples, proving a case of Elekes' conjecture. Using the techniques applied in the proof, we show a density version of Jamison's theorem. If the number of distinct directions between many pairs of points of a point set in a convex position is small, then many points are on a conic.

Bibliography:
József Solymosi: On the structure of pointsets with many collinear triples , arXiv


November 4, 2022, 2pm (CET)
András Gyárfás: Two Ramsey problems on vertex-ordered complete graphs inspired by twisted drawings

Abstract: Two first-week exercises introducing Ramsey-type problems are:
1. In every 2-coloring of the edges of $K_n$ there is a monochromatic spanning tree.
2. In every 2-coloring of the edges of $K_{3n−1}$ there is a monochromatic matching of size n.
We discuss how these statements change for vertex-ordered complete graphs where independent edges can be nested, crossing or separated. Results and problems are from a recent joint work with János Barát and Géza Tóth.


October 28, 2022, 2pm (CET) online only!
Benny Sudakov: Evasive sets, covering by subspaces, and point-hyperplane incidences

Abstract: Given positive integers $k\leq d$ and a finite field $F$, a set $S\subset F^{d}$ is $(k,c)$-subspace evasive if every $k$-dimensional affine subspace contains at most $c$ elements of $S$. By a simple averaging argument, the maximum size of a $(k,c)$-subspace evasive set is at most $c |F|^{d-k}$. In this talk we discuss the construction of evasive sets, matching this bound. The existence of optimal evasive sets has several interesting consequences in combinatorial geometry. Using it we determine the minimum number of $k$-dimensional linear hyperplanes needed to cover the grid $[n]^{d}$. This extends the work by Balko, Cibulka, and Valtr, and settles a problem proposed by Brass, Moser, and Pach. Furthermore, we improve the best known lower bound on the maximum number of incidences between points and hyperplanes in dimension $d$ assuming their incidence graph avoids the complete bipartite graph $K_{t,t}$ for some large constant $t=t(d)$. Joint work with Istvan Tomon.

Bibliography:
Benny Sudakov, István Tomon: Evasive sets, covering by subspaces, and point-hyperplane incidences , arXiv


October 21, 2022, 2pm (CET)
Grigory Ivanov: Geometric representation of $1/s$-concave functions and duality

Abstract: We will discuss a simple way of representing $1/s$-concave functions on $\mathbb{R}^d$ as convex bodies in $\mathbb{R}^{d+1},$ which allows us to use both standard ideas of convexity and tricks from the study of log-concave functions. We will discuss the properties of polar functions as an application. In particular, we prove that the reciprocal of the integral of the polar function of a log-concave function is log-concave as a function of the center of polarity.

Bibliography:
Grigory Ivanov, Elisabeth M. Werner: Geometric representation of classes of concave functions and duality , arXiv


October 14, 2022, 2pm (CET) - online only!
Natan Rubin (Ben Gurion University): Two questions on crossings in geometric (hyper-)graphs

Abstract: We consider two long standing open problems in the study of edge intersections in geometric (hyper-)graphs.
1. Given a geometric graph with n vertices and n^{1+o(1)}t edges, do there exist t pairwise crossing edges?
2. Estimate the largest possible number f_d(n,h) so that a (d+1)-uniform geometric hypergraph in d-space with at least n^{d+1}h hyperedges (i.e., d-simplices) must contain f_d(n,h) simplices that are pierced by a single point.
The first question continues a long line of quasi-planarity results which positively settle it for near-constant t, whereas the second question comes hand in hand with the study of weak epsilon-nets and k-sets. (Any progress on the second question, a.k.a. the second selection theorem, would lead to better bounds for k-sets in dimension 5 and higher. )
The existing methods offer satisfactory and highly non-trivial answers for the very dense scenarios of both questions, which have been found lacking in the “intermediate range”.
The talk is partly based on joint work with J. Pach and G. Tardos.


October 7, 2022, 2pm (CET)
Dömötör Pálvölgyi: C-P3O: Orientation of convex sets and other good covers

Abstract: We introduce a novel definition of orientation on the triples of a family of pairwise intersecting planar convex sets and study its properties. In particular, we compare it to other systems of orientations on triples that satisfy a natural interiority condition. Such systems, P3O (partial 3-order), are a natural generalization of posets, and include the order types of planar point sets. Our main result is that P3O that emerge from points sets, p-P3O, and P3O that emerge from convex sets, C-P3O, do not contain each other. We also extend our orientation to other good covers from convex sets and study the resulting P3O's. Based on joint work with Ágoston, Damásdi, and Keszegh.

Bibliography:
Péter Ágoston, Gábor Damásdi, Balázs Keszegh, Dömötör Pálvölgyi: Orientation of convex sets, arXiv
Péter Ágoston, Gábor Damásdi, Balázs Keszegh, Dömötör Pálvölgyi: Orientation of good covers, arXiv


September 30, 2022, 2pm (CET) - online only!
Soumi Nandi: Colorful Helly theorem for piercing boxes with two points

Abstract: For any natural number $n$, a family $\mathcal{F}$ of subsets of a space $\mathbf{X}$ is said to be {\em $n$-pierceable}, if there exists $A\subseteq\mathbf{X}$ with $|A|\leq n$ such that for any $F\in\mathcal{F}$, $F\cap A\neq\emptyset$.
Helly's theorem, one of the fundamental results in discrete geometry, says that for any finite family $\mathcal{F}$ of convex sets in $\mathbb{R}^d$, if every $(d+1)$-tuple from $\mathcal{F}$ is $1$-pierceable, then the whole family $\mathcal{F}$ is $1$-pierceable. Unfortunately, for $n\geq 2$, a similar statement about the $n$-pierceable sets is not valid for general convex sets. Danzer and Grünbaum proved the first and one of the most important Helly type results on multi-pierceable families; viz. famlies of axis parallel boxes.
One important generalization of Helly's theorem is Colorful Helly's Theorem. In this talk, we shall prove a colorful version of Danzer and Grünbaum's $2$-pierceability result for families of axis parallel boxes. This work was jointly done with Sourav Chakraborty and Arijit Ghosh.

Bibliography:
Sourav Chakraborty, Arijit Ghosh, Soumi Nandi: Colorful Helly Theorem for Piercing Boxes with Two Points , arXiv


September 23, 2022, 2pm (CET)
Máté Matolcsi and Dániel Varga: The density of planar sets avoiding unit distances

Abstract: We will talk about our recent result settling an old conjecture of Paul Erdős: we prove that the density of any measurable planar set avoiding unit distances can not reach 1/4. Our solution is heavily computer-aided, and uses ideas from linear programming, graph theory, and harmonic analysis. This question is related to the famous Hadwiger-Nelson problem, and some of its variants. We will conclude by mentioning some still-unsettled conjectures that might be approached with our machinery. A joint work of Gergely Ambrus, Adrián Csiszárik, Máté Matolcsi, Dániel Varga and Pál Zsámboki. The talk is self-contained.

Bibliography:
Gergely Ambrus, Adrián Csiszárik, Máté Matolcsi, Dániel Varga, Pál Zsámboki: The density of planar sets avoiding unit distances, arXiv


September 16, 2022, 2pm (CET) - online only!
Dmitriy Zakharov (MIT and MIPT): Convex polytopes from fewer points

Abstract: Let $ES_d(n)$ denote the smallest integer such that any set of $ES_d(n)$ points in $R^d$ in general position contains n points in convex position. In 1960, Erdős and Szekeres showed that $ES_2(n)≥2^{n−2}+1$ holds, and famously conjectured that their construction is optimal. This was nearly settled by Suk in 2017, who showed that $ES_2(n)≤2^{n+o(n)}$. We show that $ES_d(n)=2^{o(n)}$ holds for all $d\ge 3$. Joint work with Cosmin Pohoata.

Bibliography:
Cosmin Pohoata, Dmitrii Zakharov: Convex polytopes from fewer points , arXiv


September 2, 2022, 2pm (CET)
Karim Adiprasito (Hebrew University and university of Copenhagen): Algebraic aspects of lattice polytopes

Abstract: Ehrhardt theory states that the number of lattice points in a dilated lattice polytope is polynomial in the dilation factor. I will discuss and resolve several conjectures concerning the coefficients of this polynomial.


August 26, 2022, 2pm (CET)
Matthew Kendall (Princeton University): Quantitative Helly-type theorems via sparse approximation

Abstract: Working on a topic whose research was initiated by Bárány, Katchalski and Pach in 1982, we study quantitative Helly-type theorems for the volume and the diameter of convex sets. We prove the following sparse approximation result for polytopes. Assume that Q is a polytope in John's position. Then there exist at most 2d vertices of Q whose convex hull Q' satisfies Q \subset - 2d^2 Q'. As a consequence, we retrieve the best bound for the quantitative Helly-type result for the volume, achieved by Brazitikos, and improve on the strongest bound for the quantitative Helly-type theorem for the diameter, shown by Ivanov and Naszódi: We prove that given a finite family F of convex bodies in R^d with intersection K, we may select at most 2d members of F such that their intersection has volume at most (cd)^(3d/2) vol K, and it has diameter at most 2 d^2 diam K, for some absolute constant c > 0. This a joint work with Víctor Hugo Almendra-Hernández and Gergely Ambrus.