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

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

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

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

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

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

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

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

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

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

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.

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

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.

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.

Abstract: Let $d \geq 2$ be a natural number. We determine the minimum possible size of the difference set $A-A$ in terms of $|A|$ for any sufficiently large finite subset $A$ of $\mathbb{R}^d$ that is not contained in a translate of a hyperplane. By a construction of Stanchescu, this is best possible and thus resolves an old question first raised by Uhrin. If time permits, we will also discuss some recent related results. Joint work with Jeck Lim.

Abstract: How many lines are needed to pierce each cell of the n*n chessboard? We give nontrivial upper and lower bounds, study related problems, and present an intriguing conjecture on the optimal number of lines. Joint work with I. Bárány, P. Frankl and D. Varga.

Abstract: Recently Zhao simplified Ortega-Moreno's proof of Fejes Tóth's zone conjecture. In this talk we present his simplification as well as a short proof of Ball's complex plank problem based on the same idea.

Abstract: We investigate order types of lines and $k$-flats in $R^d$. We give a definition for an order of $d-1$ oriented lines in $R^d$ as a permutation and show that two-sided stacked permutations are universal.

Abstract: We prove that given a finite collection of cylinders in $R^3$ with the property that any two of them intersect, there is a line intersecting an $\alpha$-fraction of the cylinders where $\alpha=1/14$ . This is a special case of an interesting conjecture.

Abstract: We consider various topological classes of graphs. A graph G belonging to the class C is saturated if adding any edge to G results in a graph not in C. A drawing of a graph G is k-planar if any edge is intersected by at most k other edges. A graph G is k-plane if it has a k-planar drawing. Any n-vertex planar graph has at most 3n-6 edges. On the other hand, any saturated planar graph has 3n-6 edges. Any n-vertex 1-planar drawing has at most 4n-8 edges. Here the saturated graphs are dramatically different from the ones with maximum number of edges. The number of edges in saturated 1-plane graphs and 1-planar drawings can be much less than 4n. This was first noticed about a decade ago. One can prove lower and upper bounds on the minimum number of edges in n-vertex saturated 1-plane graphs or 1-planar drawings. Similar problems can be considered for k-planar drawings, where k is at least 2. However, the proof methods are rather different and there are unexpected phenomenons as k grows. In the talk, we try to review the most recent developments. We concentrate on various interesting constructions. We give an overview of a few strategies proving lower bounds. Based on joint work with Géza Tóth.

Abstract: Sprouts (Brussels sprouts, resp.) are two-player topological games, invented by Michael Paterson and John Conway (1967). The games start with p dots (p crosses resp.), have simple rules, last for finitely many moves, and the player who makes the last move wins. In the misere versions, the player who makes the last move loses. We make an attempt to make such games colored, preserving the esthetical interest and balance of them. The analysis of these colored games is a joint work with Alason Lakhani, Haile Gilroy and Owen Henderschedt at Auburn University.

Abstract: Convex polyhedra whose translates tile the three-dimensional Euclidean space are called three-dimensional parallelohedra. Three-dimensional parallelohedra are among the best known convex polyhedra outside mathematics, their best known examples are the cube, the regular rhombic dodecahedron and the regular truncated octahedron. Despite this fact, in the presenter's knowledge, no isoperimetric problem has been proved for them in the literature. The aim of this note is to investigate isoperimetric-type problems for three-dimensional parallelohedra. Our main result states that among three-dimensional parallelohedra with unit volume the one with minimal mean width is the regular truncated octahedron. If time permits, in addition, we establish a connection between the edge lengths of three-dimensional parallelohedra and the edge densities of the translative mosaics generated by them, and use our method to prove that among translative, convex mosaics generated by a parallelohedron with a given volume, the one with minimal edge density is the face-to-face mosaic generated by cubes.

Abstract: I will present some new tricks about coloring geometric hypergraphs that we have developed with Gabor Damasdi. These will allow us to show that any finite set of planar points can be 3-colored such that any unit disk containing at least 666 points contains two differently colored points. Earlier it was known that 2 colors are not always sufficient and that for (non-unit) disks sometimes even 4 colors are needed. Our proof uses a generalization of the Erdos-Sands-Sauer-Woodrow conjecture. If time permits, I'll also sketch our proof for this generalization, which builds on the recent proof of the original ESSW conjecture of Bousquet, Lochet, and Thomasse.

Bibliography:
Gábor Damásdi, Dömötör Pálvölgyi: Three-chromatic geometric hypergraphs , arXiv

Abstract: We will discuss the following colorful Tverberg-type result (and its monochromatic version): For a pair x,y of points in $R^d$, denote by D(xy) the closed ball for which the segment xy is its diameter. For any n blue points and n red points in $R^d$, there is a red-blue matching M such that all the balls D(xy), where $xy\in M$, share a common point. Joint work with O.Pirahmad and A.Vasilevskii.

Abstract: We say that a tiling separates discs of a packing in the Euclidean plane, if each tile contains exactly one member of the packing. It is a known elementary geometric problem to show that for each locally finite packing of circular discs, there exists a separating tiling with convex polygons. In this paper we show that this separating property remains true for circle packings on the sphere and in the hyperbolic plane. Moreover, we show that in the Euclidean plane circles are the only convex discs, whose packings with similar copies can be always separated by polygonal tilings. The analogous statement is not true on the sphere and it is not known in the hyperbolic plane.

Abstract: Orthogonal representations have played a role in information theory, combinatorial optimization, rigidity theory and quantum physics. We start with a survey of these connections. Recent interest in this construction is motivated by graph limit theory. Limit objects of convergent graph sequences have been defined in the two extreme cases: graphons (limits of dense graph sequences) and graphings (limits of bounded-degree graph sequences). In the middle ranges, Markov chains seem to play an important role. An interesting example from this point of view is the Markov chain on the sphere in a fixed dimension, where a step is a move by 90 degrees in any direction. A basic question: is this object a limit of finite graphs (and in what sense)? To get an affirmative answer, we need to define the density of a given simple graph in the orthogonality graph. This leads to the problem of defining and computing a random orthogonal representation of this graph, which is an interesting and nontrivial issue on its own.

Abstract: The contact number of a packing of finitely many balls in Euclidean d-space is the number of touching pairs of balls in the packing. We give a brief survey on bounding the contact numbers of unit sphere packings in Euclidean d-space. A prominent subfamily of sphere packings is formed by the so-called totally separable sphere packings: here, a packing of balls in Euclidean d-space is called totally separable if any two balls can be separated by a hyperplane such that it is disjoint from the interior of each ball in the packing. Bezdek, Szalkai and Szalkai (Discrete Math. 339(2): 668-676, 2016) upper bounded the contact numbers of totally separable packings of n unit balls in Euclidean d-space in terms of n and d. In this paper we improve their upper bound and extend that new upper bound to the so-called locally separable packings of unit balls. We call a packing of unit balls a locally separable packing if each unit ball of the packing together with the unit balls that are tangent to it form a totally separable packing. In the plane, we prove a crystallization result by characterizing all locally separable packings of n unit disks having maximum contact number.

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.

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.

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

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.

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

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.

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.

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.

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.

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.

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.

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

Abstract: For a positive integer d, let S be a finite set of points in $R^d$ with no d+1 points on a common hyperplane. A set H of k points from S is a k-hole in S if all points from H lie on the boundary of the convex hull conv(H) of H and the interior of conv(H) does not contain any point from S. We study the expected number of holes in sets of n points drawn uniformly and independently at random from a convex body of unit volume. We provide several new bounds and show that they are tight. In some cases, we are able to determine the leading constants precisely, improving several previous results. The talk is based on two joint works with Martin Balko and Manfred Scheucher.

Abstract. This talk will survey recent results that describe graphs as subgraphs of products of simpler graphs. The starting point is the following theorem: every planar graph is a subgraph of the strong product of some treewidth 7 graph and a path. This result has been the key to solving several open problems, for example, regarding the queue-number and nonrepetitive chromatic number of planar graphs. The result generalises to provide a universal graph for planar graphs. In particular, if $T^7$ is the universal treewidth 7 graph (which is explicitly defined), then every countable planar graph is a subgraph of the strong product of $T^7$ and the infinite 1-way path. This result generalises in various ways for many sparse graph classes: graphs embeddable on a fixed surface, graphs excluding a fixed minor, map graphs, etc. For example, we prove that for every fixed graph $X$, there is an explicitly defined countable graph $G$ that contains every countable $X$-minor-free graph as a subgraph, and $G$ has several desirable properties such as every $n$-vertex subgraph of $G$ has a $O(\sqrt{n})$-separator. On the other hand, as a lower bound we strengthen a theorem of Pach (1981) by showing that if a countable graph $G$ contains every countable planar graph, then $G$ must contain an infinite complete graph as a minor.

Abstract: We give a new proof of Fejes Tóth's zone conjecture: for any sequence \(v_1,v_2,...,v_n\) of unit vectors in a real Hilbert space H, there exists a unit vector v in J such that \(|(v_k, v)| \ge sin( \pi / 2n)\) for all k. This can be seen as a sharp version of the plank theorem for real Hilbert spaces. Our approach is inspired by K. Ball's solution to the complex plank problem and thus unifies both the complex and the real solution under the same method.

Abstract: In this talk, we discuss a variety of problems and results for ordered, geometric andconvex geometric hypergraphs. We give a short proof of the following version of the Erdős-Ko-Rado Theorem for geometric hypergraphs: the maximum size of a family of triangles from a set P of n points in the plane, no three collinear and not containing two triangles which geometrically share at least one point, is
\(\Delta(n)=\frac{n(n-1)(n+1)}{24}\) if \(n\ge 3\) is odd,
\(\Delta(n)=\frac{n(n-2)(n+2)}{24}\) if \(n\ge 4\) is even,
For convex geometric hypergraphs – here the vertex set is the set of vertices of a regular n-gon – \(\Delta (n)\) is roughly the number of triangles containing the centroid of the n-gon. In this setting, we determine the extremal function for six of the eight possible pairs of triangles in convex position, and give bounds on the remaining two. These results extend earlier theorems of Aronov, Dujmovic, Morin, Ooms and da Silveira and answer some problems posed by Frankl and Kupavskii. We discuss some extensions to r-uniform hypergraphs.
Joint work with Z. Füredi, D. Mubayi and J. O’Neill.

Abstract: Let A,B be two families of vectors in R^d that both span it and such that \( < a, b > \) is either 0 or 1 for any a, b from A and B, respectively. We show that \(|A| |B| \le (d+1) 2^d\). This allows us to settle a conjecture by Bohn, Faenza, Fiorini, Fisikopoulos, Macchia, and Pashkovich (2015) concerning 2-level polytopes (polytopes such that for every facet-defining hyperplane H there is its translate H' such that H together with H' cover all vertices). The authors conjectured that for every d-dimensional 2-level polytope P the product of the number of vertices of P and the number of facets of P is at most \(d 2^{d+1}\), which we show to be true. Joint work with Stefan Weltge.

Abstract: A convex polyhedron is called monostable if it can rest in stable position only on one of its faces. In this talk we investigate three questions of Conway, regarding monostable polyhedra, from the open problem book of Croft, Falconer and Guy (Unsolved Problems in Geometry, Springer, New York, 1991), which first appeared in the literature in a 1969 paper. In this note we answer two of these problems and conjecture an answer for the third one. The main tool of our proof is a general theorem describing approximations of smooth convex bodies by convex polyhedra in terms of their static equilibrium points. As another application of this theorem, we prove the existence of a `polyhedral Gömböc', that is, a convex polyhedron with only one stable and one unstable point.

Abstract: The covering radius of a convex body in R^d is the minimal dilation factor that is needed for the integer lattice translates of the dilated body to cover R^d. As our main result, we describe a new algorithm for computing this quantity for rational polytopes, which is simpler, more efficient and easier to implement than the only prior algorithm of Kannan (1992). We consider a geometric interpretation of the famous Lonely Runner Conjecture in terms of covering radii of zonotopes, and apply our algorithm to prove the first open case of three runners with individual starting points.

Bibliogaphy:
Jana Cslovjecsek, Romanos Diogenes Malikiosis, Márton Naszódi, Matthias Schymura: Computing the covering radius of a polytope with an application to lonely runners, arXiv.

Abstract: The basis for the talk is the problem of eliminating all depth cycles in a set of n lines in 3-space. For two lines l_1, l_2 in 3-space (in general position), we say that l_1 lies below l_2 if the unique vertical line that meets both lines meets l_1 at a point below the point where it meets l_2. This depth relationship typically has cycles, which can be eliminated if we cut the lines into smaller pieces. A 30-year old problem asks for a sharp upper bound on the number of such cuts. After briefly mentioning older approaches, based on weaving patterns of lines, we show that this can be done with O(n^{3/2} polylog(n)) cuts, almost meeting the known worst-case lower bound Omega(n^{3/2}). (Joint work with Boris Aronov.) We then present a variety of related recent works: (a) We show that a similar approach yields a method for eliminating depth cycles in a set of pairwise disjoint triangles in 3-space. (This is the "real" problem that arises in applications to computer graphics.) (Joint work with Boris Aronov and Ed Miller.) (b) We discuss efficient algorithmic implementations of these techniques, covering results by Mark de Berg and by Boris Aronov, Esther Ezra, and Josh Zahl. (c) We give a surprising application of the technique for eliminating lenses in arrangements of n algebraic arcs in the plane, which in turn shows that the arcs can be cut into roughly n^{3/2} arcs, each pair of which intersect at most once. This leads to improved incidence bounds between points and curves in the plane. (Joint work with Josh Zahl.) (d) Finally, we touch upon a recent application of the technique, due to Zahl, of eliminating cycles in four dimensions, with applications to bounding the number of unit distances in three dimensions.

Abstract: The Hadwiger--Nelson problem is about determining the chromatic number of the plane (CNP), defined as the minimum number of colours needed to colour the plane so that no two points of distance 1 have the same colour. I will talk about the related problem for spheres, with a few natural restrictions on the colouring. Thomassen showed that with these restrictions, the chromatic number of all manifolds satisfying certain properties (including the plane and all spheres with a large enough radius) is at least 7. We prove that with these restrictions, the chromatic number of any sphere with a large enough radius is at least 8. This also gives a new lower bound for the minimum colours needed for colouring the 3-dimensional space with the same restrictions.

Abstract: The (p,q) theorem of Alon and Kleitman is a famous generalization of Helly’s classical theorem which is related to important concepts such as chi-boundedness and weak epsilon nets. It is of considerable interest to understand what types of general set systems admit a (p,q) theorem, and there are several conjectures (by Kalai, Meshulam, and others) surrounding this topic. In this talk I will survey some recent developments in this area, some of which are based on joint work with D.Lee and with X.Goaoc and Z.Patakova.

Abstract: Analogously to unit-distance graphs we define odd-distance graphs to be graphs that can be drawn in the plane with (possibly intersecting) straight line segments such that the length of each edge is an odd integer. Considerably less is known about odd-distance graphs than unit-distance graphs. For example we don't know if there is an upper bound on the chromatic number or not. In this talk we show an infinite family of graphs that are not odd-distance graphs. An n-wheel is a graph formed by connecting a new vertex to all vertices of a cycle of length n. Piepemeyer showed that $K_{n,n,n}$, and therefore any 3-colorable graph, is an odd-distance graph. In particular the 2n-wheel is an odd distance graph for any n. On the other hand it is well known that the 3-wheel ($K_4$) is not an odd-distance graph, and Rosenfeld and Le showed that the 5-wheel is also not an odd-distance graph. We show that the 2n+1-wheel is not an odd-distance graph for any n.

Abstract: Hedetniemi's conjecture stated (or states, if a conjecture is intemporal) that the chromatic number of a product of graphs is the minimum of the chromatic number of the factors. Last year, Yaroslav Shitov demolished this 53 year old conjecture in a 3 page paper. The chromatic numbers involved in his counterexamples were very large. However a few months ago found a way to avoid the asymptotic arguments used by Shitov, using instead some injective colourings of graphs at a crucial point of the argument. This allowed Xuding Zhu to show that the chromatic numbers of the counterexamples can be reasonably small. In his paper, the bound for the factors was 225, which may be further reduced if graphs exist with odd girth 7 and a large enough fractional chromatic number. Here we modify the argument again. Instead of injective colourings, we use colourings that are "wide'' in the sense of Simonyi and Tardos. In this way, we can prove the result in the title. Depending on the chromatic number of a certain graph with 13965 vertices, it is possible that the same argument gives a product of 12-chromatic graphs with chromatic number 11.

Abstract: Hedetniemi conjectured in 1966 that \(\chi(G \times H) = \min\{\chi(G), \chi(H)\}\) for all graphs \(G, H\). This conjecture received a lot of attention in the past half century and was eventually refuted by Shitov in 2019. The Poljak-Rödl function is defined as \(f(n) = \min\{\chi(G \times H): \chi(G)=\chi(H)=n\}\). It is obvious that \(f(n) \le n\) for all \(n\), and Hedetniemi’s conjecture is equivalent to say that \(f(n)=n\) for all integer \(n\). Now we know that \(f(n) < n\) for large \(n\). However, we do not know how small \(f(n)\) can be. In this talk, we will present new counterexamples to Hedetniemi's conjecture. We show that \(f(n) \le (\frac 12 + o(1))n\) and survey some other work related to Hedetniemi’s conjecture.