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.

2022 Spring Semester - every Friday at 14:00 in Main Hall of the Rényi Institute and online

27-28 May, 2022
2022 Szeged Workshop on Convexity

May 20, 2022, 2 pm (CET)
Károly Bezdek: On the separable Tammes problem

Abstract: A family of spherical caps of the 2-dimensional unit sphere is called a totally separable packing if any two spherical caps can be separated by a great circle which is disjoint from the interior of each spherical cap in the packing. The separable Tammes problem asks for the largest density of given number of congruent spherical caps forming a totally separable packing in the 2-dimensional unit sphere. The talk surveys the status of this problem and its dual on thinnest totally separable coverings. Discrete geometry methods are combined with convexity ones. This is a joint work with Z. Langi (Tech. Univ., Budapest).


May 13, 2022, 2 pm (CET)
Balázs Keszegh: The number of tangencies between two families of curves

Abstract: We prove that the number of tangencies between the members of two families, each of which consists of $n$ pairwise disjoint curves, can be as large as $\Omega(n^{4/3})$. From a conjecture about $0$-$1$ matrices it would follow that if the families are doubly-grounded then this bound is sharp. We also show that if the curves are required to be $x$-monotone, then the maximum number of tangencies is $\Theta(n\log n)$, which improves a result by Pach, Suk, and Treml. Joint work with Dömötör Pálvölgyi.

Bibliography:
Balázs Keszegh, Dömötör Pálvölgyi: The number of tangencies between two families of curves , arXiv


May 6, 2022, 2 pm (CET)
István Miklós: Fast transformations of Latin squares, half-regular factorizations and edge colorings of bipartite graphs in small steps

Abstract: Jacobson and Matthew gave perturbations that are necessary and sufficient to transform any n × n Latin square to any another n × n Latin square. In some sense, these perturbations are small: a perturbation changes at most 3 rows. In some sense, they are large: unlimited number of columns might be affected by a single perturbation. These perturbations can be used in a Markov chain Monte Carlo framework to generate random Latin squares. Based on certain properties of the so-emerging Markov chain, these perturbations can be considered as small ones. They also can be considered as fast in the sense that a small number of such perturbations are sufficient to transform any Latin square into any another one.

We show that similar perturbations are possible for half-regular factorizations of complete bipartite graphs and edge colorings of bipartite graphs. That is, we give perturbations that are necessary and sufficient to transform any half-regular factorization of a complete bipartite graph into another half-regular factorization of the same complete bipartite graph. A perturbation affects at most 3 vertices in the first (regular) vertex class and unlimited number of vertices in the second vertex class. These perturbations can be applied in a Markov chain Monte Carlo framework to generate random factorizations, and can be considered as small perturbations. Furthermore, they can be considered as fast because a small number of perturbations are sufficient to transform any factorization into any another one.

Similarly, we give perturbations that are necessary and sufficient to transform any edge k-coloring to another edge k-coloring of a bipartite graph with maximum degree ∆ ≤ k. A perturbation affects at most 3 colors and unlimited number of edges. They can be applied in a Markov chain Monte Carlo framework to generate random edge colorings, and they can be considered as small perturbations. Also, they are fast: a small number of perturbations are sufficient to transform any edge k-colorings into another one. A special case is when the bipartite graph is k-regular, and it is easy to see that this case is equivalent with the completion of Latin rectangles.

Joint work with former BSM students Mark Aksen, Kathleen Zhou and Letong Hong.

Bibliography:
Jacobson, M.T., Matthews, P. (1996) Generating uniformly distributed random Latin squares. Journal of Combinatorial Designs 4(6):404-437.
Aksen, M. Miklós, I., Zhou, K. (2017) Half-regular factorizations of the complete bipartite graph. Discrete Applied Mathematics 230:21-33.
Hong, L. Miklós, I. (2021) A Markov chain on the solution space of edge-colorings of bipartite graphs. https://arxiv.org/abs/2103.11990


April 29, 2022, 2 pm (CET)
Artem Zvavitch (Kent State University): Volume product and Mahler conjecture for convex bodies

Abstract: Let K be convex, symmetric, with respect to the origin, body in $R^n$. One of the major open problems in convex geometry is to understand the connection between the volumes of K and the polar body $K^∗$. The Mahler conjecture is related to this problem and it asks for the minimum of the volume product $vol(K)vol(K^* )$. In 1939, Santalo proved that the maximum of the volume product is attained on the Euclidean ball. About the same time Mahler conjectured that the minimum should be attained on the unit cube or its dual - cross-polytope. Mahler himself proved the conjectured inequality in $R^2$. The question was recently solved by H. Iriyeh, M. Shibata, in dimension 3. The conjecture is open starting from dimension 4. In this talk I will discuss main properties and ideas related to the volume product and a few different approaches to Mahler conjecture. I will also present ideas of a shorter solution for three dimensional case (this is a part of a joint work with Matthieu Fradelizi, Alfredo Hubard, Mathieu Meyer and Edgardo Roldán-Pensado).

Bibliography:
Balázs Keszegh, Dömötör Pálvölgyi: The number of tangencies between two families of curves , arXiv


April 22, 2022, 3 pm (CET)
Manfred Scheucher: Erdős-Szekeres-type problems in the real projective plane

Abstract: In this talk we consider point sets in the real projective plane $\mathbb RP^2$ and explore variants of classical extremal problems about planar point sets in this setting, with a main focus on Erdős-Szekeres-type problems. We provide asymptotically tight bounds for a variant of the Erdős-Szekeres theorem about point sets in convex position in $\mathbb RP^2$, which was initiated by Harborth and M\"oller in 1994. The notion of convex position in $\mathbb RP^2$ agrees with the definition of convex sets introduced by Steinitz in 1913. An affine $k$-hole in a finite set $S \subseteq \mathbb{R}^2$ is a set of $k$ points from $S$ in convex position with no point of $S$ in the interior of their convex hull. After introducing a new notion of $k$-holes for points sets from $\mathbb RP^2$, called projective $k$-holes, we find arbitrarily large finite sets of points from $\mathbb RP^2$ with no projective 8-holes, providing an analogue of a classical result by Horton from 1983. Since 6-holes exist in sufficiently large point sets, only the existence of projective $7$-holes remains open. Similar as in the affine case, Horton sets only have quadratically many projective $k$-holes for $k \leq 7$. However, in general the number of $k$-holes can be substantially larger in $\mathbb RP^2$ than in $\mathbb{R}^2$ and we construct sets of $n$ points from $\mathbb{R}^2 \subset \mathbb RP^2$ with $\Omega(n^{3-3/5k})$ projective $k$-holes and only $O(n^2)$ affine $k$-holes for every $k \in \{3,\dots,6\}$. Last but not least, we discuss several other results, for example about projective holes in random point sets in $\mathbb RP^2$ and about some algorithmic aspects. The study of extremal problems about point sets in $\mathbb RP^2$ opens a new area of research, which we support by posing several open problems. This is joint work with Martin Balko and Pavel Valtr, to appear at SoCG 2022.

Bibliography:
Martin Balko, Manfred Scheucher, Pavel Valtr: Erdős-Szekeres-type problems in the real projective plane , arXiv


April 8, 2022, 2 pm (CET)
Xavier Goaoc: No weak epsilon nets for lines and convex sets in space

Abstract: We prove that there exist no weak $\epsilon$-nets of constant size for lines and convex sets in $R^d$. This is joint work with Otfried Cheong and Andreas Holmsen.

Bibliography:
Otfried Cheong, Xavier Goaoc, Andreas F. Holmsen: No weak epsilon nets for lines and convex sets in space , arXiv


April 1, 2022, 2 pm (CET)
Vsevolod Voronov: On the chromatic number of 2-dimensional spheres

Abstract: Consider the problem of the chromatic number of a two-dimensional sphere, namely, the smallest number of colours required to paint $S^2(r)$ such that any two points of the sphere at unit distance apart have different colours. It is easy to see that the chromatic number of sphere $\chi(S^2(r))$ depends on radius. G. Simmons in 1976 suggested that if $r>1/2$ then $\chi(S^2(r)) \geq 4$, and thus $\chi(S^2(r)) = 4$ for $r \in (1/2, r^*)$. The main topic of the talk will be the proof of Simmons' conjecture. The proof is technically rather simple and, apart from elementary geometrical constructions, is based on the Borsuk-Ulam theorem. In addition, possible generalisations and some related results will be discussed.

Bibliography:
Danila Cherkashin, Vsevolod Voronov: On the chromatic number of 2-dimensional spheres , arXiv


March 25, 2022, 2 pm (CET)
Daniel McGinnis: A family of convex sets in the plane satisfying the $(4,3)$-property can be pierced by nine points.

Abstract: A family of sets is said to have the $(p,q)$-property if for every $p$ sets, $q$ of them have a common point. It was shown by Alon and Kleitman that if $\mathcal{F}$ is a finite family of convex sets in $\mathbb{R}^d$ and $q\geq d+1$, then there is come constant $c_d(p,q)$ number of points that pierces each set in $\mathcal{F}$. A problem of interest is to improve the bounds on the numbers $c_d(p,q)$. Here, we show that $c_2(4,3)\leq 9$, which improves the previous upper bound of 13 by Gyárfás, Kleitman, and Tóth. The proof combines a topological argument and a geometric analysis.

Bibliography:
Daniel McGinnis: A family of convex sets in the plane satisfying the (4,3)-property can be pierced by nine points , arXiv


March 18, 2022, 2 pm (CET)
Márió Szegedy: Budgeted Steiner Networks: Three Terminals with Equal Path Weights

Abstract: Given a set of terminals in 2D/3D, the network with the shortest total length that connects all terminals is a Steiner tree. On the other hand, with enough budget, every terminal can be connected to every other terminals via a straight edge, yielding a complete graph over all terminals. In this work, we study a generalization of Steiner trees asking what happens in between these two extremes. Focusing on three terminals with equal pairwise path weights, we characterize the full evolutionary pathway between the Steiner tree and the complete graph, which contains intriguing intermediate structures. Joint work with Jingjin Yu.

Bibliography:
Mario Szegedy, Jingjin Yu: Budgeted Steiner Networks: Three Terminals with Equal Path Weights , arXiv


March 11, 2022, 2 pm (CET)
Nicolas Bousquet: Fast transformations between colorings

Abstract: Given a graph G=(V,E), a k-coloring is an assignment of colors in {1,...,k} to vertices such that adjacent vertices receive distinct colors. Proving the existence of k-colorings received a considerable in the last decades. In this talk, we will focus on the existence of transformations between colorings rather than finding coloring themselves. A transformation between two colorings c_1,c_2 is a sequence of proper colorings starting in c_1 and ending in c_2 such that consecutive colorings differ on exactly one vertex. We will first motivate this problem by explaining its relation with enumeration and random generation. We will then overview some recent results of the field together with intuitions of their proofs.

Bibliography:
Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, Mikaël Rabie: Short and local transformations between (Δ+1)-colorings , arXiv


March 4, 2022, 2 pm (CET)
Imre Bárány: Orientation preserving maps of the n by n grid

Abstract: For a finite set $A\subset {\mathbb R}^2$, a map $\varphi: A \to {\mathbb R}^2$ is orientation preserving if for every non-collinear triple $u,v,w \in A$ the orientation of the triangle $u,v,w$ is the same as that of the triangle $\varphi(u),\varphi(v),\varphi(w)$. We prove that for every $n \in {\mathbb N}$ and for every $\epsilon>0$ there is $N=N(n,\epsilon)\in {\mathbb N}$ such that the following holds. Assume that $\varphi :G(N)\to {\mathbb R}^2$ is an orientation preserving map where $G(N)$ is the grid $\{(i,j)\in {\mathbb Z}: -N \le i,j\le N\}$. Then there is an affine transformation $\psi :{\mathbb R}^2 \to {\mathbb R}^2$ and $z_0 \in {\mathbb Z}$ such that $z_0+G(n)\subset G(N)$ and $\|\varphi (z)-\psi(z)\|<\epsilon$ for every $z \in z_0+G(n)$. This result was previously proved in a completely different way by Nešetřil and Valtr, without obtaining any bound on $N$. Our proof gives $N(n,\epsilon)=O(n^4\epsilon^{-2})$. Joint work with Attila Por and Pavel Valtr.


February 25, 2022, 2 pm (CET)
Sophie Spirkl: A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

Abstract: Abstract: I will present a counterexample to the following well-known conjecture: for every k, r, every graph G with clique number at most k and sufficiently large chromatic number contains a triangle-free induced subgraph with chromatic number at least r. I will also discuss some related results (including the construction of Brianski, Davies, and Walczak disproving Esperet's conjecture on polynomial chi-boundedness). Based on joint work with Alvaro Carbonero, Patrick Hompe, and Ben Moore.

Bibliography:
Alvaro Carbonero, Patrick Hompe, Benjamin Moore, Sophie Spirkl: A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number , arXiv
Marcin Briański, James Davies, Bartosz Walczak: Separating polynomial χ-boundedness from χ-boundedness , arXiv


February 18, 2022, 2 pm (CET)
Márton Naszódi: Löwner's problem for log-concave functions and beyond

Abstract: The class of logarithmically concave functions is a natural extension of the class of convex sets in Euclidean $d$-space. Several notions and results on convex sets have been extended to this wider class. We study how the problem of the smallest volume affine image of a given convex body $L$ that contains another given convex body $K$ can be phrased and solved for functions. Joint work with Grigory Ivanov and Igor Tsiutsiurupa.


February 11, 2022, 2 pm (CET)
Alexandr Polyanskii: Polynomial plank covering problem

Abstract: A special case of Bang's plank covering theorem asserts: For any collection of $n$ hyperplanes in the Euclidean space, there is a point in the unit ball at distance at least $1/n$ from the union of the hyperplanes. We are going to discuss the following polynomial generalization of this result (and its relation to the plank covering results of Yufei Zhao and Oscar Ortego-Moreno): For every nonzero polynomial $P\in \mathbb R[x_1, \ldots, x_d]$ of degree $n$, there is a point of the unit ball in $\mathbb R^d$ at distance at least $1/n$ from the zero set of the polynomial $P$. Joint work with Alexey Glazyrin and Roman Karasev.