BBC+G Seminar

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

Starting September 2020, this is the joint Budapest Big Combinatorics + Geometry (BBC+G) Seminar of the Geometry Seminar of the Rényi Institute, the ERC Geometric Combinatorics group and the Lendület Combinatorial Geometry (CoGe) Research Group.
The talks are typically on Friday 2-4 pm, but 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.

2021 Spring Semester - online

April 9, 2021
EuroCG 2021

April 2, 2021, 2 pm (CET)
TBA

Abstract: TBA


March 26, 2021, 2 pm (CET)
Pablo Soberón: TBA

Abstract: TBA


March 19, 2021, 2 pm (CET)
Ramon van Handel: Some unusual extremal problems in convexity and combinatorics

Abstract: It is a basic fact of convexity that the volume of convex bodies is a polynomial, whose coefficients (the mixed volumes) contain many familiar geometric parameters as special cases. A deep result of convex geometry, the Alexandrov-Fenchel inequality, states that these coefficients are log-concave. This result proves to have striking connections with other areas of mathematics: for example, the appearance of log-concave sequences in many combinatorial problems may be understood as a consequence of the Alexandrov-Fenchel inequality and its algebraic analogues. There is a long-standing problem surrounding the Alexandrov-Fenchel inequality that has remained open since the original works of Minkowski (1903) and Alexandrov (1937): in what cases is equality attained? In convexity, this question corresponds to the solution of certain unusual isoperimetric problems, whose extremal bodies turn out to be numerous and strikingly bizarre. In combinatorics, an answer to this question would provide nontrivial information on the type of log-concave sequences that can arise in combinatorial applications. In recent work with Y. Shenfeld, we succeeded to settle the equality cases completely in the setting of convex polytopes. I will aim to describe this result, and to illustrate its potential combinatorial implications through a question of Stanley on the combinatorics of partially ordered sets.


March 12, 2021
Workshop on Euclidean Ramsey Theory

March 5, 2021, 4 pm (CET)
James Davies: Circle graphs are quadratically chi-bounded

Abstract: We prove that the chromatic number of a circle graph with clique number $\omega$ is at most $7 \omega^2$. Joint work with Rose McCarty.


February 26, 2021, 2 pm (CET)
Wolfgang Mulzer: Long Alternating Paths Exist

Abstract: Let P be a set of 2n points in convex position, such that n points are colored red and n points are colored blue. A non-crossing alternating path on P of length l is a sequence $p_1, ..., p_l$ of l points from P so that (i) all points are pairwise distinct; (ii) any two consecutive points $p_i, p_{i+1}$ have different colors; and (iii) any two segments $p_i p_{i+1}$ and $p_j p_{j+1}$ have disjoint relative interiors, for $i \ne j$. We show that there is an absolute constant eps > 0, independent of n and of the coloring, such that P always admits a non-crossing alternating path of length at least $(1 + \epsilon)n$. The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least $(1 + \epsilon)n$ points of P. This is a properly colored matching whose segments are pairwise disjoint and intersected by a common line. For both versions, this is the first improvement of the easily obtained lower bound of n by an additive term linear in n. The best known published upper bounds are asymptotically of order $4n/3 + o(n)$. Based on joint work with Pavel Valtr.


February 19, 2021, 2 pm (CET)
Barak Weiss (Tel Aviv University): New bounds on the covering density of lattices

Abstract: We obtain new upper bounds on the minimal density of lattice coverings of $R^n$ by dilates of a convex body $K$. We also obtain bounds on the probability (with respect to the natural Haar-Siegel measure on the space of lattices) that a randomly chosen lattice $L$ satisfies $L+K=R^n$. As a step in the proof, we utilize and strengthen results on the discrete Kakeya problem. Joint work with Or Ordentlich and Oded Regev.


February 12, 2021, 2 pm (CET)
Sergey Avvakumov: A subexponential size ${\mathbb R}P^n$

Abstract: A practical way to encode a manifold is to triangulate it. Among all possible triangulations it makes sense to look for the minimal one, which for the purpose of this talk means using the least number of vertices. Consider now a family of manifolds such as $S^n$, ${\mathbb R}P^n$, $SO_n$, etc. A natural question is how the size of the minimal triangulation depends on $n$? Surprisingly, except for the trivial case of $S^n$, our best lower and upper bounds are very far apart. For ${\mathbb R}P^n$ the current best lower and upper bounds are around $n^2$ and $\phi^n$, respectively, where $\phi$ is the golden ratio. In this talk I will present the first triangulation of ${\mathbb R}P^n$ with a subexponential, $\sqrt{n}^\sqrt{n}$, number of vertices. I will also state several open problems related to the topic. This is a joint work with Karim Adiprasito and Roman Karasev.


February 5, 2021, 2 pm (CET)
Natan Rubin: Stronger bounds for weak Epsilon-Nets

Abstract: Given a finite point set $P$ in $R^d$, and $\epsilon>0$ we say that a point set $N$ in $R^d$ is a weak $\epsilon$-net if it pierces every convex set $K$ with $|K\cap P|\geq \epsilon |P|$. Let $d\geq 3$. We show that for any finite point set in $R^d$, and any $\epsilon>0$, there exists a weak $\epsilon$-net of cardinality $O(1/\epsilon^{d-1/2+\delta})$, where $\delta>0$ is an arbitrary small constant. This is the first improvement of the bound of $O^*(1/\epsilon^d)$ that was obtained in 1994 by Chazelle, Edelsbrunner, Grini, Guibas, Sharir, and Welzl for general point sets in dimension $d\geq 3$.