BBC+G

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 GeoScape Research 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

June 8, 2021
Part of the Round the World Relay in Combinatorics:
László Lovász: TBA

May 28, 2021, 2 pm (CET)
TBA

May 21, 2021, 2 pm (CET)
Károly Bezdek : TBA

May 14, 2021, 2 pm (CET)
Balázs Keszegh: On tangencies among planar curves

Abstract: We prove that there are $O(n)$ tangencies among any set of $n$ red and blue planar curves in which every pair of curves intersects at most once and no two curves of the same color intersect. If every pair of curves may intersect more than once, then it is known that the number of tangencies could be super-linear. However, we show that a linear upper bound still holds if we replace tangencies by pairwise disjoint connecting curves that all intersect a certain face of the arrangement of red and blue curves. The latter result has an application for the following problem studied by Keller, Rok and Smorodinsky [Disc. Comput. Geom. (2020)] in the context of conflict-free coloring of string graphs: what is the minimum number of colors that is always sufficient to color the members of any family of $n$ grounded L-shapes such that among the L-shapes intersected by any L-shape there is one with a unique color? They showed that $O(\log^3 n)$ colors are always sufficient and that $\Omega(\log n)$ colors are sometimes necessary. We improve their upper bound to $O(\log^2 n)$. Joint work with Eyal Ackerman and Dömötör Pálvölgyi.


May 7, 2021, 2 pm (CET)
Chaya Keller: On multicolor Ramsey numbers and subset-coloring of hypergraphs

Abstract: The multicolor hypergraph Ramsey number $R_k(s,r)$ is the minimal n, such that in any k-coloring of all r-element subsets of [n], there is a subset of size s, all whose r-subsets are monochromatic. We present a new "stepping-up lemma" for $R_k(s,r)$: If $R_k(s,r)>n$, then $R_{k+3}(s+1,r+1)>2^n$. Using the lemma, we improve some known lower bounds on multicolor hypergraph Ramsey numbers. Furthermore, given a hypergraph $H=(V,E)$, we consider the Ramsey-like problem of coloring all r-subsets of $V$ such that no hyperedge of size >r is monochromatic. We provide upper and lower bounds on the number of colors necessary in terms of the chromatic number $\chi(H)$. In particular, we show that this number is $O(log^{(r-1)} (r \chi(H)) + r)$, where $log^{(m)}$ denotes m-fold logarithm. Joint work with Bruno Jartoux, Shakhar Smorodinsky, and Yelena Yuditsky.


April 30, 2021, 2 pm (CET)
Imre Bárány: Erdős-Szekeres theorem for k-flats

Abstract: We extend the famous Erdős-Szekeres theorem to k-flats in $R^d$.


April 23, 2021, 2 pm (CET)
TBA

April 16, 2021, 2 pm (CET)
Endre Csóka: Upper bounds for the necklace folding problems

Abstract: A necklace can be considered as a cyclic list of n red and n blue beads in an arbitrary order, and the goal is to fold it into two and find a large cross-free matching of pairs of beads of different colors. We give a counterexample for a conjecture about the necklace folding problem, also known as the separated matching problem. The conjecture (given independently by three sets of authors) states that $\mu = 2/3$ , where µ is the ratio of the ‘covered’ beads to the total number of beads. We refute this conjecture by giving a construction which proves that $\mu \le 2 − \sqrt 2 < 0.5858$. Our construction also applies to the homogeneous model: when we are matching beads of the same color. Moreover, we also consider the problem where the two color classes do not necessarily have the same size. Joint work with Zoltán L. Blázsik, Zoltán Király, Dániel Lenger.


April 9, 2021
EuroCG 2021

April 2, 2021, 2 pm (CET)
Madhu Sudan (Harvard): (Deterministic) Communication Amid Uncertainty

Abstract: Most natural communication among humans is characterized by a lack of perfect understanding among the communicating players. Arguably this lack of perfect understanding plays a significant role in the development of human languages, which tend to have bendable rules, ambiguous dictionaries, and seemingly needless redundancies. In this series of works we explore one mathematical question that arises from such communication amid uncertainty. We consider a case of a sender of information attempting to compress information before sending it to the receiver, in a setting where the sender and receiver have moderate, but not perfect, agreement on the distribution from which the message is chosen. In case of perfect agreement, a scheme like Huffman coding would compress the information down to its entropy. What happens with imperfect agreement? We will show some randomized and deterministic schemes that achieve some non-trivial compression. We will mention some intriguing open problems in the deterministic setting (which we believe to be harder and possibly more insightful in this setting). Based on joint works with Elad Haramaty (Technion), Brendan Juba (MIT/Harvard), Adam Kalai (MSR), and Sanjeev Khanna (U.Penn.)


March 26, 2021, 2 pm (CET)
Pablo Soberón: Quantitative Helly theorems

Abstract: Given a family of convex sets in R^d, how do we know that their intersection has a large volume or a large diameter? A large family of results in combinatorial geometry, called Helly-type theorems, characterize families of convex sets whose intersections are not empty. During this talk we will describe how some bootstrapping arguments allow us to extend classic results to describe when the intersection of a family of convex sets in R^d is quantifiably large. The work presented in this talk was done in collaboration with Travis Dillon, Jack Messina, Sherry Sarkar, and Alexander Xue.


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$.