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.

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

May 26, 2023, 2pm (CET)
TBA: TBA

Abstract: TBA


May 19, 2023, 2pm (CET)
TBA: TBA

Abstract: TBA


May 12, 2023, 2pm (CET)
TBA: TBA

Abstract: TBA


May 5, 2023, 2pm (CET)
Ferenc Fodor: TBA

Abstract: TBA


April 28, 2023, 2pm (CET)
István Tomon: TBA

Abstract: TBA


April 21, 2023, 2pm (CET)
Rainie Bozzai: Colorful vector balancing

Abstract: The vector balancing problem, in which one is given a collection of vectors in a d-dimensional unit norm ball and selects signs {-1,+1} so that the norm of the signed sum of the vectors becomes minimal, has been studied extensively for both general and specific norms. Answering a question originally posed by Barany and Grinberg in 1981, we extend results for both the Euclidean norm and the maximum norm to a colorful setting. In this setting one is given color classes of vectors in the unit ball of a norm on $R^d$, with the condition that 0 is contained in the Minkowski sum of the convex hulls of the color classes. The goal is to select one vector of each color so that the norm of the sum of the selected vectors is as small, i.e. uniformly bounded from above. For the Euclidean norm, we use linear algebraic and probabilistic techniques to prove that there is always a selection of vectors whose sum has Euclidean norm at most $\sqrt(d)$. For the maximum norm we use a random walk algorithm to prove the asymptotically optimal upper bound $O(\sqrt(d))$. These estimates agree with the ones for the original vector balancing problem, and as such, are known to be asymptotically optimal.
This is a joint work with Gergely Ambrus.


April 14, 2023, 2pm (CET)
Matija Bucić: Unit and distinct distances in typical norms

Abstract: Erdős' unit distance problem and Erdős' distinct distances problem are among the most classical and well-known open problems in all of discrete mathematics. They ask for the maximum number of unit distances, or the minimum number of distinct distances, respectively, determined by n points in the Euclidean plane. The question of what happens in these problems if one considers normed spaces other than Euclidean space has been raised in the 1980s by Ulam and Erdős and attracted a lot of attention over the years. We give an essentially tight answer to both questions for almost all norms on R^d, in a certain Baire categoric sense.
Our results settle, in a strong and somewhat surprising form, problems and conjectures of Brass, of Matousek, and of Brass-Moser-Pach. The proofs combine combinatorial, probabilistic and geometric ideas with tools from Linear Algebra, Topology and Algebraic Geometry.
Joint work with Noga Alon and Lisa Sauermann.


April 7, 2023, 2pm (CET) - online only!
Alfredo Hubard: From crossings to areas and back

Abstract: This talk will center on an analogue of Heilbronn's triangle problem for simple topological complete graphs. These are drawings of the complete graph in the plane in which every pair of edges intersect at most once. The motivating question is whether there exists a function t(n) that goes to 0 when n goes to infinity, such that for any simple complete topological graph contained in a region of area 1, there exists a triangle of area at most t(n). I will give an answer to this question based on recent joint work with Andrew Suk. I will put it in context with other results in quantitative topology in which areas of regions, and intersections between faces mingle.

Bibliography:
Alfredo Hubard, Andrew Suk: Quantitative Steinitz Theorem: Disjoint faces in simple drawings of the complete graph and topological Heilbronn problems, arXiv


March 31, 2023, 2pm (CET)
Mónika Csikós: An improved algorithm to construct spanning paths with low crossing numbers

Abstract: Abstract: Given a hypergraph $H = (V,\mathcal E)$, we consider the problem of finding a spanning path of $V$ such that each hyperedge in $\mathcal E$ crosses few edges of the path (we say that a hyperedge $h \in \mathcal E$ crosses the edge $\{x,y\}$ iff $|h \cap \{x,y\} | = 1$). This structure was originally introduced for geometric range searching in the 1980s and has found applications in various fields, including algorithmic graph theory and combinatorial data approximation. The seminal work of Chazelle and Welzl (1989) provided an algorithm that for any hypergraph with $n$ vertices, $m$ edges, and dual VC-dimension $d$, constructs a spanning path with crossing number $O(n^{1 - 1/d})$ in time $O(n^3 m)$. Since then, despite several advances for geometric hypergraphs, the general algorithm for abstract hypergraphs remained unimproved. We propose a new sampling-based algorithm which is applicable to any finite hypergraph with dual VC-dimension $d$ and provides a spanning path with expected crossing number $O(n^{1-1/d})$ in time $O(n^{1/d} m + n^{2 + 1/d})$ resulting in an $n^{2-1/d}$ factor speed-up on the construction time (assuming $m \geq n$). Joint work with Nabil H. Mustafa.

Bibliography:


March 24, 2023, 2pm (CET)
Adrian Dumitrescu: On a traveling salesman problem for points in the unit cube

Abstract: Let $X$ be an $n$-element point set in the $k$-dimensional unit cube $[0,1]^k$, $k \geq 2$. According to an old result of Bollobás and Meir (1992), there exists a tour $x_1, x_2, \ldots, x_n$ through the $n$ points, such that $\left(\sum_{i=1}^n |x_i - x_{i+1}|^k \right)^{1/k} \leq c_k$, where $|x-y|$ is the Euclidean distance between $x$ and $y$, and $c_k$ is an absolute constant that depends only on $k$ ($x_{n+1} \equiv x_1$). From the other direction, for every $k \geq 2$ and $n \geq 2$, there exist $n$ points in $[0,1]^k$, such that their shortest tour satisfies $\left(\sum_{i=1}^n |x_i - x_{i+1}|^k \right)^{1/k} = 2^{1/k} \cdot \sqrt{k}$. For the plane, the best constant is $c_2=2$ and this is the only exact value known. The authors showed that one can take $c_k = 9 \left(\frac23 \right)^{1/k} \cdot \sqrt{k}$ for every $k \geq 3$ and conjectured that the best constant is $c_k = 2^{1/k} \cdot \sqrt{k}$, for every $k \geq 2$. Here we significantly improve the upper bound and show that one can take $c_k = 3 \sqrt5 \left(\frac23 \right)^{1/k} \cdot \sqrt{k}$; this bound is constructive. We also show that $c_3 \geq 2^{7/6}$, which disproves their conjecture for $k=3$. The improvement is based on a new lemma that is a key ingredient in bounding from above the weight of a minimum spanning tree of a point set.
Connections to matching problems, power assignment problems, suitable algorithms, and other related problems are discussed in this context. A slightly revised version of the Bollobás-Meir conjecture is proposed as a replacement.


March 22, 2023, 11am (CET) - MTA main building (in Hungarian)
János Pach: A teve és a ló: alacsony dimenziós kombinatorika – székfoglaló előadás

March 21-24, 2023, 2pm (CET) - BME
12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications March 21-24, 2023, Budapest, Hungary

March 17, 2023, 2pm (CET)
Márton Naszódi: Quantitative Steinitz theorems

Abstract: The classical Steinitz theorem states that if the origin belongs to the interior of the convex hull of a set $S$ in $\mathbb{R}^d$, then there are at most $2d$ points of $S$ whose convex hull contains the origin in the interior. B\'ar\'any, Katchalski and Pach proved the following quantitative version. Let $Q$ be a convex polytope in $\mathbb{R}^d$ containing the standard Euclidean unit ball $B$. Then there exist at most $2d$ vertices of $Q$ whose convex hull $Q^\prime$ satisfies $r B \subset Q^\prime$ with $r\geq d^{-2d}$. They conjectured that $r\geq c d^{-1/2}$ holds with a universal constant $c>0$. We show the first polynomial lower bound on $r$, and also present an upper bound. Joint work with Grigory Ivanov.

Bibliography:
Grigory Ivanov, Márton Naszódi: Quantitative Steinitz Theorem: A polynomial bound, arXiv


March 10, 2023, 2pm (CET) - online only!
Jean Cardinal: Improved Algebraic Degeneracy Testing

Abstract: In the classical linear degeneracy testing problem, we are given n real numbers and a k-variate linear polynomial F, for some constant k, and have to determine whether there exist k numbers $a_1,\dots,a_k$ from the set such that $F(a_1,\dots,a_k)=0$. We consider a generalization of this problem in which F is an arbitrary constant-degree polynomial, we are given k sets of n numbers, and have to determine whether there exists a k-tuple of numbers, one in each set, on which F vanishes. We give the first improvements over the naïve $O^*(n^{k−1})$ algorithm for this problem (where the $O^∗()$ notation omits subpolynomial factors), in both the real RAM and algebraic decision tree models of computation. All our results rely on an algebraic generalization of the standard meet-in-the-middle algorithm for k-SUM, powered by recent algorithmic advances in the polynomial method for semi-algebraic range searching. In fact, our main technical result is much more broadly applicable, as it provides a general tool for detecting incidences and other interactions between points and algebraic surfaces in any dimension. In particular, it yields an efficient algorithm for a general, algebraic version of Hopcroft's point-line incidence detection problem in any dimension.
This is joint work with Micha Sharir.

Bibliography:
Jean Cardinal, Micha Sharir: Improved Algebraic Degeneracy Testing, arXiv


March 3, 2023, 2pm (CET)
Gergely Ambrus: Critical central sections of the cube

Abstract: Volumes of central hyperplane sections of the d-dimensional cube Q_d have been studied for over a century. Following the work of Hensley, and Vaaler, K. Ball proved in 1986 that the sections of maximal volume are normal to the main diagonal of a 2-dimensional face. Sections orthogonal to the main diagonal of a k-dimensional face are called k-diagonal. In 2021, Bartha, Fodor and González Merino proved that the volumes of k-diagonal sections form a monotone increasing sequence for k>=3. One may study the volume of central sections as a function of the normal vector. It has been naturally conjectured that critical directions with respect to the volume function are diagonal. First, we give an analytic characterization of critical directions that has also been proved independently by Ivanov and Tsiutsiurupa. Based on this result, we determine critical sections of Q_d up to d<=4, which show that for d=4, there exist non-diagonal critical directions. Then proceed to prove that, surprisingly, there exist full-dimensional, non-diagonal critical directions for every d>=4. This disproves the above long-standing conjecture. The arguments use Fourier analytic, geometric, stochastic, and combinatorial methods. In particular, one of the key tools is a generalization of asymptotic bounds on second-order Eulerian numbers obtained by Leusier and Nicolas in 1992. Partly joint work with Barnabás Gárgyán.

Bibliography:
Gergely Ambrus: Critical central sections of the cube, arXiv


February 24, 2023, 2pm (CET) - online only!
Adrian Dumitrescu: Peeling Sequences

Abstract: Given an $n$-element point set in the plane, in how many ways can it be peeled off until no point remains? Only one extreme point can be removed at a time. The answer obviously depends on the point set. If the points are in convex position, there are exactly $n!$ ways, which is the maximum number of ways for $n$ points. But what is the minimum number? After failing to obtain a good estimate, we examine how the above removal procedure may reveal information about the distance from convexity of a given point set. We look at other methods as well.

Bibliography:
Adrian Dumitrescu: Peeling Sequences, arXiv


February 17, 2023, 2pm (CET)
Gábor Kun: A polynomial removal lemma for posets

Abstract: Alon and Shapira proved that every monotone class of graphs is strongly testable. In other words, for every (possibly infinite) set F of forbidden subgraphs and every eps>0 there exists C(eps) such that for every graph G if the subgraph induced by C(eps) vertices chosen uniformly at random is with probability at least half F-free, then we can obtain an F-free graph G' on V(G) by the removal of at most eps|V(G)|^2 edges. The dependence of C(eps) on eps might be astronomical. We show that for posets C(eps) can be a polynomial of eps. Hence classes of posets defined by forbidden subposets are easily testable (according to the definition of Alon and Fox). Our results apply to comparability graphs, too. Joint work with Panna Fekete.


February 10, 2023, 2pm (CET)
Arsenii Sagdeev: Cutting corners

Abstract: We will discuss one simple argument leading to the following:
1) lower bound on the minimum number of colors needed to color R^n such that no unit equilateral triangle is monochromatic;
2) upper bounds on the maximum number of subsets of [n] no k of which form a weak-sunflower;
3) (perhaps the shortest) proof of the Frankl-Rődl theorem that states that the size of every family of r-element subsets of [n] no 2 of which share exactly s elements is 'small'.

Bibliography:
Andrey Kupavskii, Arsenii Sagdeev, Dmitrii Zakharov: Cutting corners, arXiv