BBC+G

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

Budapest Big Combinatorics + Geometry (BBC+G) Seminar is the main seminar in whose organization our group takes active part.

It was initiated in 2020 as the joint seminar of the Geometry Seminar of the Rényi Institute, the GeoScape Research Group and the Combinatorial Geometry (CoGe) Research Group.
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.

2024 Spring Semester - every Friday usually at 14:15 in the "Dog Room" of the Rényi Institute

May 24, 2024, 2.15pm (CET)
Imre Bárány: A special balancing game, Victor Grinberg's question

Abstract: In a vector balancing game, on step k player 1 chooses a unit vector $v_k$ and player 2 chooses a sign $\epsilon_k$ in $\{-1,1\}$, and the position after n steps is $z_n=\sum_1^n \epsilon_k v_k$. Player 1's target is to make $||z_n||$ large and player 2's target is to make it small. We consider a special case of this game.


May 17, 2024, 2.15pm (CET) in the Main Lecture Hall of the Rényi Institute
Joel Spencer: Random Gems

Abstract: We give three gems of the Probabilistic Method. These problems have been worked on for decades but here we give some beautiful arguments -- illustrating the increasingly sophisticated applications of probability.

From Erdős in 1963: How big can $k$ be so that given any collection of less than $m=2^{n-1}k$ sets, all of size $n$, there exists a two-coloring of the underlying vertices so that none of the sets are monochromatic. Erdős randomly colored but others have done better, using an ingenious randomized algorithm.

From the speaker in 1985, while visiting the Rényi Institute. Given $n$ vectors $\vec{v_1},\ldots,\vec{v_n}\in R^n$, all with $L^{\infty}$ norm at most one, some signed sum $\pm\vec{v_1}\pm\cdots\pm\vec{v_n}$ has $L^{\infty}$ norm at most $K\sqrt{n}$, $K$ constant. The original proof was ``ugly", we give our choice for the Book proof, using a restricted Brownian motion.

From Bender, Canfield and McKay, 1990. Asymptotically, how many connected, labelled graphs are there with $n$ vertices and (say) $2n$ edges. We prefer our own proof, with van der Hofstad, using a Brownian Bridge.


May 3, 2024, 2.15pm (CET)
Gábor Tardos: Forbidden acyclic patterns in 0-1 matrices

Abstract: A zero-one matrix M is said to contain another zero-one matrix A if we can delete some rows and columns of M and replace some 1-entries with 0-entries such that the resulting matrix is A. The extremal function of A, denoted $ex(n, A)$, is the maximum number of 1-entries that an nXn zero-one matrix can have without containing A. The systematic study of this function for various patterns A goes back to the work of Furedi and Hajnal from 1992. The field has many connections to other areas such as classical Turan type extremal graph theory and Davenport-Schinzel theory and has many applications in mathematics and theoretical computer science. The problem has been particularly extensively studied for so-called acyclic matrices. Furedi and Hajnal conjectured an $O(n \log n)$ bound for them, while Pach and Tardos conjectured a weaker n polylog n bound. Pettie refuted the stronger conjecture with an acyclic pattern whose extremal function he showed to be $\Omega (n \log n \log \log n)$. In a recent joint work with Seth Pettie we found the extremal function $ex(n, A_k)$ asymptotically for certain simple 2Xk acyclic patterns to be $\Theta(n(\log n/\log \log n)^{k-2})$ for $k>3$. This shows that the Pach-Tardos conjecture is tight if true. The conjecture itself is still wide open.


April 26, 2024, 2.15pm (CET)
Gergely Kiss: The discrete Pompeiu problem in $\mathbb{R}^k$ and its consequences

Abstract: We study the discrete analogue of the integral geometric problem of Dimitrie Pompeiu. We say that a finite subset E of the Euclidean space is Pompeiu, whenever for a given function f the sum of the values of f on any congruent copy of E is zero, then f is identically zero. Although for sets of two or three elements the affirmative answer is easy, until recently, even for four-point sets the answer was not known. Applying harmonic analysis in some varieties connected to the problem and also some results on linear equations of units, we proved that every finite subset of $\mathbb{R}^k$ is Pompieu ($k>2$). The result has a strong consequence to the finite Steinhaus set problem posed by Steve Jackson. We also discuss the connections to problems in Euclidean Ramsey theory. It is a joint work with Miklós Laczkovich.


April 19, 2024, 2.15pm (CET)
Gyula Károlyi: A covering problem for Coxeter permutahedra

Abstract: An almost cover of a finite set of points is a collection of hyperplanes that together cover all points of the set except one. According to the celebrated Alon-Füredi theorem, every almost cover of the vertex set of an n-dimensional cube requires at least n hyperplanes. The vertex set of an aligned cube centered at the origin can be viewed as the orbit of a generic point under the action of the group generated by the reflections in the coordinate hyperplanes. In this talk we explore the extension of this theorem to Coxeter permutahedra, that is, for convex polytopes whose vertices form a generic orbit under the action of a finite reflection group. [No prior knowledge on root systems etc. are needed, everything will be carefully explained in the talk.]


April 12, 2024, 2.15pm (CET)
Zsolt Lángi: Honeycomb Conjecture in normed planes and an $\alpha$-convex variant of Dowker's theorem

Abstract: The Honeycomb Conjecture states that among tilings with unit area cells in the Euclidean plane, the average perimeter of a cell is minimal for a regular hexagonal tiling. This conjecture goes back to a book of the Roman polyhistor Varro, but it was proved only in the middle of the 20th century by L. Fejes Toth for convex tilings, and in the beginning of the 21th century by Hales for not necessarily convex tilings. It seems a natural question to ask whether in any normed plane, among tilings with unit area cells, the average perimeter is minimal for a tiling whose cells are translates of a given (not necessarily regular) hexagon. In this talk we investigate this question for convex tilings in normed planes. We show that the answer is affirmative in any normed plane for tilings with minimal average squared perimeter, and show that the original problem in general is related to an $\alpha$-convex variant of Dowker's theorem on the areas of polygons circumscribed about a plane convex body. Exploring this connection, we show that the same statement with average perimeter holds for any norm whose unit disk is a regular (2n)-gon with n not equal to 4,5,7. This is an ongoing joint project with Shanshan Wang.


April 5, 2024, 2.15pm (CET)
Dmitrii Zakharov: Lower bounds for incidences

Abstract: We consider a problem about lower bounding the number of incidences between points and tubes in the plane under natural spacing conditions. As a corollary of our results, we show that any collection of n points in the unit square contains three points forming a triangle of area at most n^{-7/6+o(1)}, improving on previous bounds. We discuss finite field and higher dimensional variants of the problem and the limitations of our method. Joint work with Alex Cohen and Cosmin Pohoata.


March 22, 2024, 2.15pm (CET)
Gábor Damásdi: Number of digons in arrangements of pairwise intersecting pseudo-circles

Abstract: Given an arrangement of pairwise intersecting pseudo-circles, digons are the faces in this arrangement that have two edges. A long-standing open conjecture of Branko Grünbaum from 1972 states that any simple arrangement of n pairwise intersecting pseudocircles in the plane can have at most 2n − 2 digons. Agarwal et al. proved this conjecture for arrangements of pairwise intersecting pseudocircles in which there is a common point surrounded by all pseudocircles. Recently, Felsner, Roch and Scheucher showed that Grünbaum’s conjecture is true for arrangements of pairwise intersecting pseudocircles in which there are three pseudocircles every pair of which create a digon. We show that the conjecture is true in general. Furthermore, we show that the digon-graph of the arrangement has a number of interesting properties. For example, even though it is not always planar, it is embeddable in the projective plane. Joint work with Eyal Ackerman, Gábor Damásdi, Eric Gottlieb, Balázs Keszegh, and Rebeka Raffay.


March 8, 2024, 2.15pm (CET)
Károly Böröczky: Almost optimal packings of equal spheres in dimensions 8 and 24

Abstract: The talk discusses how methods from Fourier analysis, Number Theory, Linear Algebra and Discrete Geometry lead to better understanding of dense packings of equal spheres in the 8 and 24 dimensional Euclidean space. I review the path leading to Maryna Viazovska's groundbreaking results concerning densest packings including contributions by Kepler, Lagrange, Gauss, Thue, Laszlo Fejes Toth, Cohn, and describe the structure of almost optimal packings. The latter is a joint result with Danylo Radchenko and Joao Ramos.


March 1, 2024, 2.15pm (CET)
Arsenii Sagdeev: Canonical results in Ramsey theory

Abstract: A typical problem in Ramsey theory is to show that every r-coloring of a sufficiently large 'domain' contains a monochromatic copy of some fixed 'configuration'. In a canonical setting, the number of colors is unbounded, but the goal is to find either a monochromatic, or a rainbow copy. We will discuss classic canonical versions of the Ramsey, Van der Waerden, and Hales-Jewett theorems, as well as our new developments in Euclidean Ramsey theory, and pose several open problems. Joint work with Panna Gehér and Géza Tóth.


February 23, 2024, 2.15pm (CET)
Géza Tóth: Crossing numbers of crossing-critical graphs

Abstract: A graph $G$ is $k$-crossing-critical if $\mbox{cr}(G)\ge k$, but for any edge $e$ of $G$, $\mbox{cr}(G-e)< k$. In 1993 Richter and Thomassen conjectured that for any $k$-crossing-critical graph $G$, $\mbox{cr}(G)\le k+c\sqrt{k}$ and proved that $\mbox{cr}(G)\le 5k/2+16$. We improve it to $\mbox{cr}(G)\le 2k+6\sqrt{k}+47$ and review some related results. Joint work with János Barát.


February 16, 2024, 2.15pm (CET)
Daniel Kráľ: Depth parameters of matroids

Abstract: Width parameters of graphs play a crucial role in algorithmic and structural graph theory, in particular, they are fundamental notions in the theory of graph minors and in fixed parameter complexity. For example, the celebrated theorem of Courcelle asserts that every monadic second order property can be tested in polynomial time when inputs are restricted to classes of graphs of bounded tree-width. Another important graph parameter is tree-depth, which appears in many contexts related to sparsity of graphs.
In this talk, we will survey structural and algorithmic results concerning matroid analogues of tree-width and tree-depth of graphs, particularly focusing on branch-depth and contraction$^*$-depth. For example, we will present recent structural results demonstrating the closure properties of these two parameters. At the end of the talk, we discuss the relation of the presented concepts to discrete optimization. In particular, we will present matroid based algorithms that uncover a hidden Dantzig-Wolfe-like structure of an input instance (if such structure is present) and transform instances of integer programming to equivalent ones, which are amenable to the existing tools in integer programming.
The most recent results presented in the talk are based on joint work with Marcin Briański, Jacob Cooper, Timothy F. N. Chan, Martin Koutecký, Ander Lamaison, Kristýna Pekárková and Felix Schröder.


January 19, 202, 2.15pm (CET)
József Solymosi: Additive structure in convex translates

Abstract: Let P be a set of points in the plane, and S is a strictly convex set of points. In this talk, we show that if P contains many translates of S, then these translates must come from a generalized arithmetic progression of low dimension. We also discuss an application to the unit distance conjecture.