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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

Abstract: Abstract: In a d-dimensional point set P, a hole is any subset of convexly independent points of P whose convex hull contains no other points. We will discuss constructions of large finite sets that contain no large holes. The key role will be played by subsets of [0,1]^d that contain about the same number of points in every dyadic box of a fixed volume. Based on joint works with Ting-Wei Chao and Ron Holzman.

Abstract: As a variant of the celebrated Szemerédi--Trotter theorem, Guth and Katz proved that $m$ points and $n$ lines in $\mathbb{R}^3$ with at most $\sqrt{n}$ lines in a common plane must determine at most $O(m^{1/2}n^{3/4})$ incidences for $n^{1/2}\leq m\leq n^{3/2}$. This upper bound is asymptotically tight and has an important application in Erdős distinct distances problem. We characterize the extremal constructions towards the Guth--Katz bound by proving that such a large dense point-line arrangement must contain a $k$-clique in general position provided $m \ll n$. This is an analog of a result by Solymosi for extremal Szemerédi--Trotter constructions in the plane. Joint work with with Andrew Suk.

Abstract: Let $\cal C$ be a set of curves in the plane such that no three curves in $\cal C$ intersect at a single point and every pair of curves in $\cal C$ intersect at exactly one point which is either a crossing or a touching point. J\'anos Pach conjectured that the number of pairs of curves in $\cal C$ that touch each other is $O(|\cal C|)$. We prove this conjecture for $x$-monotone curves. Joint work with Eyal Ackerman.

Bibliography:
Eyal Ackerman, Balázs Keszegh: On the number of tangencies among 1-intersecting curves, arXiv

Abstract: An integer program is an optimization problem of the form $\max \{c^T x ： Ax = b, x ∈\mathbb{Z}_+\}$ where $A \in \mathbb{Z}^{m ×n}$ and $b \in \mathbb{Z}^m$. The complexity of integer programming is a showcase for innovative methods in mathematics and computer science involving, for example, the geometry of numbers as well as recent lower bound techniques, based on assumptions like the exponential-time hypothesis. In this talk, I will survey some recent developments concerning pseudopolynomial time algorithms for integer programming in the case, where the constraint matrix has a small number of rows. Furthermore, I will present an efficient pseudopolynomial time algorithm for general ∀-∃-statements involving few constraints. Based on joint work with Eleonore Bach (EPFL) and Robert Weismantel (ETH).

Abstract: In this talk, we discuss a general method to approach a certain class of Turán-type problems, which complements the existing Delta-system method and junta approximation method. We refer to it as the ‘spread approximations method’. The method is based on the notion of r-spread families and builds on the recent breakthrough result of Alweiss, Lovett, Wu and Zhang for the Erdos–Rado Sunflower Conjecture. We will present some of its applications to questions for families of different classes of objects: sets, permutations, partitions, complexes.

Abstract: The dimension of a partially ordered set $P$ (poset for short) is the minimum positive integer $d$ such that $P$ is isomorphic to a subposet of $R^d$ with the natural product order. Dimension is arguably the most widely studied measure of complexity of posets and standard examples in posets are the canonical structure forcing dimension to be large. In many ways, dimension for posets is analogous to chromatic number for graphs with standard examples in posets playing the role of cliques in graphs. However, planar graphs have chromatic number at most four, while posets with planar diagrams may have arbitrarily large dimension. The key feature of all known constructions is that large dimension is forced by a large standard example. Since the early 1980s, the question of whether every poset of large dimension and a planar diagram contains a large standard example has been a critical challenge in posets theory with very little progress over the years. More recently, the analogous question has been considered for the broader class of posets with planar cover graphs. We answer both questions in the affirmative by proving that for every poset $P$: (1) if $P$ has a planar diagram, then $dim(P) \le 128 se(P) + 512$, and (2) if $P$ has a planar cover graph, then $dim(P) = O( se^8(P) )$, where $dim(P)$ stands for the dimension of $P$ and $se(P)$ stands for the maximum order of a standard example in $P$. Joint work with Heather Blake, Jędrzej Hodor, Michał Seweryn and William T. Trotter.

Abstract: A packing of translates of a convex body is called separable if any two translates can be separated by a hyperplane that does not intersect the interior of any translate of the packing. This notion was introduced by Gábor Fejes Tóth and László Fejes Tóth in 1973, and studied mostly by considering the density of such packings. More recently, Károly Bezdek and others considered the combinatorial properties of the contact graphs of totally separable packings. In a contact graph of a packing, the vertices are the translates, and two vertices are joined when the two translates touch. We will discuss the maximum degree (Hadwiger number), minimum degree, and total number of edges (contact number) of these graphs. In particular, we completely settle the problem of determining the maximum number of edges of a contact graph of $n$ translates of a convex disc in the plane, for each convex disc. This is joint work with Márton Naszódi.

Abstract: Motivated by general probability theory, we say that the set $X$ in $\mathbb{R}^d$ is antipodal of rank $k$, if for any $k+1$ elements $q_1,\ldots q_{k+1}\in X$, there is an affine map from $\mathrm{conv} X$ to the $k$-dimensional simplex $\Delta_k$ that maps $q_1,\ldots q_{k+1}$ onto the $k+1$ vertices of $\Delta_k$. For $k=1$, it coincides with the well-studied notion of (pairwise) antipodality introduced by Klee.
We consider the following natural generalization of Klee's problem on antipodal sets: What is the maximum size of an antipodal set of rank $k$ in $\mathbb{R}^d$? We present a geometric characterization of antipodal sets of rank $k$ and adapting the argument of Danzer and Grünbaum originally developed for the $k=1$ case, we prove an upper bound which is exponential in the dimension. We point out that this problem can be
connected to a classical question in computer science on finding perfect hashes, and it provides a lower bound on the maximum size, which is also exponential in the dimension.
Joint work with Zsombor Szilágyi and Mihály Weiner.

Abstract: We revisit the algorithmic problem of finding a triangle in a graph "Triangle Detection", and examine its relation to other problems such as "3Sum" and "Independent set". We discuss several new algorithms:
(I) An algorithm which given a graph $G=(V,E)$ performs one of the following tasks in $O(m+n)$ (i.e., linear) time: (i) compute a $Omega(1/\sqrt{n})$-approximation of "Maximum Independent Set" in G or (ii) find a triangle in G.
(II) The above result suggests the following broader research direction: if it is difficult to find (A) or (B) separately, can one find one of the two efficiently? This motivates the "dual pair" concept we introduce. We discuss and provide several instances of dual-pair approximation.
(III) We give improved arboricity-sensitive running times for counting and/or detection of copies of $K_l$, for small $l$ at least 4. Our new algorithms are faster than all previous algorithms in certain high-range arboricity intervals for every $l$ at least 7.
Part of this, like (III) above, is based on joint work with Andrzej Lingas (Lund University, Sweden)

Abstract: Motivated by the problem of redistricting, we study area-preserving reconfigurations of connected subdivisions of a simple polygon. A connected subdivision of a polygon R, called a district map, is a set of interior disjoint connected polygons called districts whose union equals R. We consider the recombination as the reconfiguration move which takes a subdivision and produces another by merging two adjacent districts, and by splitting them into two connected polygons of the same area as the original districts. The complexity of a map is the number of vertices in the boundaries of its districts. Given two maps with k districts, with complexity $O(n)$, and a perfect matching between districts of the same area in the two maps, we show constructively that $(\log n)^{O(\log k)}$ recombination moves are sufficient to reconfigure one into the other. We also show that $\Omega(\log n)$ recombination moves are sometimes necessary when k=3. Joint work with Hugo A. Akitaya, Andrei Gonczi, Diane L. Souvaine, and Thomas Weighill.

Bibliography:
Hugo A. Akitaya, Andrei Gonczi, Diane L. Souvaine, Csaba D. Tóth, Thomas Weighill: Reconfiguration of Polygonal Subdivisions via Recombination, arXiv

Abstract: A class $\mathcal F$ of graphs is $\chi$-bounded if there is a function $f$ such that $\chi(H) \le f(\omega(H))$ for all induced subgraphs $H$ of a graph in $\mathcal F$. If $f$ can be chosen to be a polynomial, we say that $\mathcal F$ is polynomially $\chi$-bounded. Esperet proposed a conjecture that every $\chi$-bounded class of graphs is polynomially $\chi$-bounded. This conjecture has been disproved; it has been shown that there are classes of graphs that are $\chi$-bounded but not polynomially $\chi$-bounded. As an attempt to recover the conjecture of Esperet, we introduce Pollyanna classes of graphs. A class $\mathcal C$ of graphs is Pollyanna if $\mathcal C \cap \mathcal F$ is polynomially $\chi$-bounded for every $\chi$-bounded class $\mathcal F$ of graphs. We investigate which classes of graphs are Pollyanna. Joint work with Maria Chudnovsky, Linda Cook, and Sang-il Oum.

Abstract: We consider paths in the plane governed by the following rules: (a) There is a finite set of states. (b) For each state q, there is a finite set S(q) of allowable "steps" ((i,j),q′). This means that from any point (x,y) in state q, we can move to (x+i,y+j) in state q′. We want to count the number of paths that go from (0,0) in some starting state q0 to the point (n,0) without ever going below the x-axis. Under some natural technical onditions, I conjecture that the number of these paths is asymptotically equal to $C^n/\sqrt{n}^3$, and I will show how to compute the growth constant C. I will discuss how lattice paths with states can be used to model asymptotic counting problems for some non-crossing geometric structures (such as trees, matchings, triangulations) on certain structured point sets. These problems come up in extremal constructions in discrete geometry, and they have been formulated in terms of so-called production matrices. This has been ongoing joint work with Andrei Asinowski and Alexander Pilz.

Abstract: There has been quite a lot of work done recently in various generalized models of random polytopes in convex bodies. One such model is when one takes n independent identically distributed uniform random points from a suitable convex body and considers the intersection of all congruent closed balls that contain the points. The resulting intersection is called a random ball-polytope (disc-polygon in the plane). In this talk we discuss the behaviour of the vertex number of random disc-polygons. We prove series expansions for the expectation of the vertex number and area of random disc-polygons depending on the degree of smoothness of the boundary of the convex disc. Joint work with N. Montenegro (University of Szeged, Hungary).

Abstract: I will talk about two interesting constructions in combinatorial geometry. (1) There exists a configuration of $n$ axis-parallel boxes in $\mathbb{R}^d$ with at most $(\log n)^{1-o(1)}$ pairwise intersecting members and at most $n/(\log n)^{d-1-o(1)}$ pairwise disjoint members. This addresses several old questions about the piercing, coloring, and Ramsey properties of boxes, reducing the persistent logarithmic gap in these problems to double-logarithmic. (2) There exists a configuration of $n$ lines in $\mathbb{R}^3$, whose intersection graph is triangle-free of chromatic number $\Omega(n^{1/15})$. This addresses a problem of Pach, Tardos, and T\'oth in a strong sense and is the first construction of a triangle-free intersection graph of simple geometric objects with polynomial chromatic number. Both constructions are based on the following simple idea. Take a configuration with a certain rich structure, and then randomly sparsify it!

Bibliography:
István Tomon: Lower bounds for piercing and coloring boxes, arXiv
István Tomon: Geometric constructions: lines and boxes, arXiv

Abstract: The vector balancing problem, in which one is given a collection of vectors in a d-dimensional unit norm ball and selects signs {-1,+1} so that the norm of the signed sum of the vectors becomes minimal, has been studied extensively for both general and specific norms. Answering a question originally posed by Barany and Grinberg in 1981, we extend results for both the Euclidean norm and the maximum norm to a colorful setting. In this setting one is given color classes of vectors in the unit ball of a norm on $R^d$, with the condition that 0 is contained in the Minkowski sum of the convex hulls of the color classes. The goal is to select one vector of each color so that the norm of the sum of the selected vectors is as small, i.e. uniformly bounded from above. For the Euclidean norm, we use linear algebraic and probabilistic techniques to prove that there is always a selection of vectors whose sum has Euclidean norm at most $\sqrt(d)$. For the maximum norm we use a random walk algorithm to prove the asymptotically optimal upper bound $O(\sqrt(d))$. These estimates agree with the ones for the original vector balancing problem, and as such, are known to be asymptotically optimal.
This is a joint work with Gergely Ambrus.

Abstract: Erdős' unit distance problem and Erdős' distinct distances problem are among the most classical and well-known open problems in all of discrete mathematics. They ask for the maximum number of unit distances, or the minimum number of distinct distances, respectively, determined by n points in the Euclidean plane. The question of what happens in these problems if one considers normed spaces other than Euclidean space has been raised in the 1980s by Ulam and Erdős and attracted a lot of attention over the years. We give an essentially tight answer to both questions for almost all norms on R^d, in a certain Baire categoric sense.
Our results settle, in a strong and somewhat surprising form, problems and conjectures of Brass, of Matousek, and of Brass-Moser-Pach. The proofs combine combinatorial, probabilistic and geometric ideas with tools from Linear Algebra, Topology and Algebraic Geometry.
Joint work with Noga Alon and Lisa Sauermann.

Bibliography:
Noga Alon, Matija Bucić, Lisa Sauermann: Unit and distinct distances in typical norms, arXiv

Abstract: This talk will center on an analogue of Heilbronn's triangle problem for simple topological complete graphs. These are drawings of the complete graph in the plane in which every pair of edges intersect at most once. The motivating question is whether there exists a function t(n) that goes to 0 when n goes to infinity, such that for any simple complete topological graph contained in a region of area 1, there exists a triangle of area at most t(n). I will give an answer to this question based on recent joint work with Andrew Suk. I will put it in context with other results in quantitative topology in which areas of regions, and intersections between faces mingle.

Bibliography:
Alfredo Hubard, Andrew Suk: Quantitative Steinitz Theorem: Disjoint faces in simple drawings of the complete graph and topological Heilbronn problems, arXiv

Abstract: Abstract: Given a hypergraph $H = (V,\mathcal E)$, we consider the problem of finding a spanning path of $V$ such that each hyperedge in $\mathcal E$ crosses few edges of the path (we say that a hyperedge $h \in \mathcal E$ crosses the edge $\{x,y\}$ iff $|h \cap \{x,y\} | = 1$). This structure was originally introduced for geometric range searching in the 1980s and has found applications in various fields, including algorithmic graph theory and combinatorial data approximation. The seminal work of Chazelle and Welzl (1989) provided an algorithm that for any hypergraph with $n$ vertices, $m$ edges, and dual VC-dimension $d$, constructs a spanning path with crossing number $O(n^{1 - 1/d})$ in time $O(n^3 m)$. Since then, despite several advances for geometric hypergraphs, the general algorithm for abstract hypergraphs remained unimproved. We propose a new sampling-based algorithm which is applicable to any finite hypergraph with dual VC-dimension $d$ and provides a spanning path with expected crossing number $O(n^{1-1/d})$ in time $O(n^{1/d} m + n^{2 + 1/d})$ resulting in an $n^{2-1/d}$ factor speed-up on the construction time (assuming $m \geq n$). Joint work with Nabil H. Mustafa.

Abstract: Let $X$ be an $n$-element point set in the $k$-dimensional unit cube $[0,1]^k$, $k \geq 2$. According to an old result of Bollobás and Meir (1992), there exists a tour $x_1, x_2, \ldots, x_n$ through the $n$ points, such that $\left(\sum_{i=1}^n |x_i - x_{i+1}|^k \right)^{1/k} \leq c_k$, where $|x-y|$ is the Euclidean distance between $x$ and $y$, and $c_k$ is an absolute constant that depends only on $k$ ($x_{n+1} \equiv x_1$). From the other direction, for every $k \geq 2$ and $n \geq 2$, there exist $n$ points in $[0,1]^k$, such that their shortest tour satisfies $\left(\sum_{i=1}^n |x_i - x_{i+1}|^k \right)^{1/k} = 2^{1/k} \cdot \sqrt{k}$. For the plane, the best constant is $c_2=2$ and this is the only exact value known. The authors showed that one can take $c_k = 9 \left(\frac23 \right)^{1/k} \cdot \sqrt{k}$ for every $k \geq 3$ and conjectured that the best constant is $c_k = 2^{1/k} \cdot \sqrt{k}$, for every $k \geq 2$. Here we significantly improve the upper bound and show that one can take $c_k = 3 \sqrt5 \left(\frac23 \right)^{1/k} \cdot \sqrt{k}$; this bound is constructive. We also show that $c_3 \geq 2^{7/6}$, which disproves their conjecture for $k=3$. The improvement is based on a new lemma that is a key ingredient in bounding from above the weight of a minimum spanning tree of a point set.
Connections to matching problems, power assignment problems, suitable algorithms, and other related problems are discussed in this context. A slightly revised version of the Bollobás-Meir conjecture is proposed as a replacement.

Abstract: The classical Steinitz theorem states that if the origin belongs to the interior of the convex hull of a set $S$ in $\mathbb{R}^d$, then there are at most $2d$ points of $S$ whose convex hull contains the origin in the interior. B\'ar\'any, Katchalski and Pach proved the following quantitative version. Let $Q$ be a convex polytope in $\mathbb{R}^d$ containing the standard Euclidean unit ball $B$. Then there exist at most $2d$ vertices of $Q$ whose convex hull $Q^\prime$ satisfies $r B \subset Q^\prime$ with $r\geq d^{-2d}$. They conjectured that $r\geq c d^{-1/2}$ holds with a universal constant $c>0$. We show the first polynomial lower bound on $r$, and also present an upper bound. Joint work with Grigory Ivanov.

Bibliography:
Grigory Ivanov, Márton Naszódi: Quantitative Steinitz Theorem: A polynomial bound, arXiv

Abstract: In the classical linear degeneracy testing problem, we are given n real numbers and a k-variate linear polynomial F, for some constant k, and have to determine whether there exist k numbers $a_1,\dots,a_k$ from the set such that $F(a_1,\dots,a_k)=0$. We consider a generalization of this problem in which F is an arbitrary constant-degree polynomial, we are given k sets of n numbers, and have to determine whether there exists a k-tuple of numbers, one in each set, on which F vanishes. We give the first improvements over the naïve $O^*(n^{k−1})$ algorithm for this problem (where the $O^∗()$ notation omits subpolynomial factors), in both the real RAM and algebraic decision tree models of computation. All our results rely on an algebraic generalization of the standard meet-in-the-middle algorithm for k-SUM, powered by recent algorithmic advances in the polynomial method for semi-algebraic range searching. In fact, our main technical result is much more broadly applicable, as it provides a general tool for detecting incidences and other interactions between points and algebraic surfaces in any dimension. In particular, it yields an efficient algorithm for a general, algebraic version of Hopcroft's point-line incidence detection problem in any dimension.
This is joint work with Micha Sharir.

Bibliography:
Jean Cardinal, Micha Sharir: Improved Algebraic Degeneracy Testing, arXiv

Abstract: Volumes of central hyperplane sections of the d-dimensional cube Q_d have been studied for over a century. Following the work of Hensley, and Vaaler, K. Ball proved in 1986 that the sections of maximal volume are normal to the main diagonal of a 2-dimensional face. Sections orthogonal to the main diagonal of a k-dimensional face are called k-diagonal. In 2021, Bartha, Fodor and González Merino proved that the volumes of k-diagonal sections form a monotone increasing sequence for k>=3. One may study the volume of central sections as a function of the normal vector. It has been naturally conjectured that critical directions with respect to the volume function are diagonal. First, we give an analytic characterization of critical directions that has also been proved independently by Ivanov and Tsiutsiurupa. Based on this result, we determine critical sections of Q_d up to d<=4, which show that for d=4, there exist non-diagonal critical directions. Then proceed to prove that, surprisingly, there exist full-dimensional, non-diagonal critical directions for every d>=4. This disproves the above long-standing conjecture. The arguments use Fourier analytic, geometric, stochastic, and combinatorial methods. In particular, one of the key tools is a generalization of asymptotic bounds on second-order Eulerian numbers obtained by Leusier and Nicolas in 1992. Partly joint work with Barnabás Gárgyán.

Bibliography:
Gergely Ambrus: Critical central sections of the cube, arXiv

Abstract: Given an $n$-element point set in the plane, in how many ways can it be peeled off until no point remains? Only one extreme point can be removed at a time. The answer obviously depends on the point set. If the points are in convex position, there are exactly $n!$ ways, which is the maximum number of ways for $n$ points. But what is the minimum number? After failing to obtain a good estimate, we examine how the above removal procedure may reveal information about the distance from convexity of a given point set. We look at other methods as well.

Bibliography:
Adrian Dumitrescu: Peeling Sequences, arXiv

Abstract: Alon and Shapira proved that every monotone class of graphs is strongly testable. In other words, for every (possibly infinite) set F of forbidden subgraphs and every eps>0 there exists C(eps) such that for every graph G if the subgraph induced by C(eps) vertices chosen uniformly at random is with probability at least half F-free, then we can obtain an F-free graph G' on V(G) by the removal of at most eps|V(G)|^2 edges. The dependence of C(eps) on eps might be astronomical. We show that for posets C(eps) can be a polynomial of eps. Hence classes of posets defined by forbidden subposets are easily testable (according to the definition of Alon and Fox). Our results apply to comparability graphs, too. Joint work with Panna Fekete.

Abstract: We will discuss one simple argument leading to the following:
1) lower bound on the minimum number of colors needed to color R^n such that no unit equilateral triangle is monochromatic;
2) upper bounds on the maximum number of subsets of [n] no k of which form a weak-sunflower;
3) (perhaps the shortest) proof of the Frankl-Rődl theorem that states that the size of every family of r-element subsets of [n] no 2 of which share exactly s elements is 'small'.

Bibliography:
Andrey Kupavskii, Arsenii Sagdeev, Dmitrii Zakharov: Cutting corners, arXiv

Abstract: In two-dimensional Euclidean space a general triangle is considered a simplex. In my talk I choose the right triangle instead and show that the corresponding multi-rectangular shapes do exist in every n-dimensional Euclidean space. I define the hypotenuse and legs in these Pythagorean shapes and derive the generalized Pythagorean Theorem to determine the volume from the legs without calculating the Cayley-Menger determinant. These multi-rectangular simplices can be used for an alternative construction of n-dimensional geometries and the theory of determinants.

Abstract: A foundational result in Ramsey theory appears in a paper of Erdős and Szekeres from 1935: any sequence of $n^2+1$ distinct real numbers contains either an increasing or decreasing subsequence of length $n+1$.   This simple result was one of the starting seeds for the development of Ramsey theory. There are a number of different ways to generalise the Erdős-Szekeres Theorem  to higher dimensions but perhaps the most natural approach was developed thirty years ago by Fishburn and Graham. A {\em $d$-dimensional array} is an injective function $f$ from $A_1 \times \ldots \times A_d$ to $\mathbb{R}$ where $A_1, \ldots A_d$ are non-empty subsets of $\mathbb{Z}$; we say $f$ has {\em size} $|A_1|\times\dots\times|A_d|$; if $|A_i|=n$ for each $i$, it will be convenient to say that $f$ has {\em size} $[n]^d$. A multidimensional array is said to be \textit{monotone} if for each direction all the $1$-dimensional subarrays in that direction are increasing or decreasing.  In other words, for every $i$, one of the following holds:
For every choice of $a_j$, $j\ne i$, the function $f(a_1,\dots,a_{i-1},x,a_{i+1},\dots,a_d)$ is increasing in $x$.
For every choice of $a_j$, $j\ne i$, the function $f(a_1,\dots,a_{i-1},x,a_{i+1},\dots,a_d)$ is decreasing in $x$.
Let $M_d(n)$ be the smallest $N$ such that a $d$-dimensional array on $[N]^{d}$ contains a monotone $d$-dimensional subarray of size $[n]^d$. We will show how to improve the bounds on $M_d(n)$ recently proved by Bucić, Sudakov and Tran. More precisely, we will show that a doubly exponential upper bound holds in all dimensions.
Theorem. For every $d\geq 2$, there is $C_d>0$, such that for every positive $n$, $M_d(n)\leq 2^{n^{C_dn^{d-1}}}$.
Finally, we will see how this is intimately connected to a generalisation of Ramsey Theorem on the cartesian product of cliques. 

Bibliography:
António Girão, Gal Kronenberg, Alex Scott: A multidimensional Ramsey Theorem, arXiv

Abstract: We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd distance from each other.

Bibliography:
James Davies: Odd distances in colourings of the plane, arXiv

Abstract: Let K be a convex body (a compact convex set) in $R^d$, that contains a copy of another body S in every possible orientation. Is it always possible to continuously move any one copy of S into another, inside K? As a stronger question, is it always possible to continuously select, for each orientation, one copy of S in that orientation? In this talk we answer these questions of Croft.

Bibliography:
Barnabás Janzer: Rotation inside convex Kakeya sets, arXiv

Abstract: It is conjectured that if a finite set of points in the plane contains many collinear triples, then there is some structure in the set. We will show that under some combinatorial conditions, such pointsets have special configurations of triples, proving a case of Elekes' conjecture. Using the techniques applied in the proof, we show a density version of Jamison's theorem. If the number of distinct directions between many pairs of points of a point set in a convex position is small, then many points are on a conic.

Bibliography:
József Solymosi: On the structure of pointsets with many collinear triples, arXiv

Abstract: Two first-week exercises introducing Ramsey-type problems are:
1. In every 2-coloring of the edges of $K_n$ there is a monochromatic spanning tree.
2. In every 2-coloring of the edges of $K_{3n−1}$ there is a monochromatic matching of size n.
We discuss how these statements change for vertex-ordered complete graphs where independent edges can be nested, crossing or separated. Results and problems are from a recent joint work with János Barát and Géza Tóth.

Abstract: Given positive integers $k\leq d$ and a finite field $F$, a set $S\subset F^{d}$ is $(k,c)$-subspace evasive if every $k$-dimensional affine subspace contains at most $c$ elements of $S$. By a simple averaging argument, the maximum size of a $(k,c)$-subspace evasive set is at most $c |F|^{d-k}$. In this talk we discuss the construction of evasive sets, matching this bound. The existence of optimal evasive sets has several interesting consequences in combinatorial geometry. Using it we determine the minimum number of $k$-dimensional linear hyperplanes needed to cover the grid $[n]^{d}$. This extends the work by Balko, Cibulka, and Valtr, and settles a problem proposed by Brass, Moser, and Pach. Furthermore, we improve the best known lower bound on the maximum number of incidences between points and hyperplanes in dimension $d$ assuming their incidence graph avoids the complete bipartite graph $K_{t,t}$ for some large constant $t=t(d)$. Joint work with István Tomon.

Bibliography:
Benny Sudakov, István Tomon: Evasive sets, covering by subspaces, and point-hyperplane incidences, arXiv

Abstract: We will discuss a simple way of representing $1/s$-concave functions on $\mathbb{R}^d$ as convex bodies in $\mathbb{R}^{d+1},$ which allows us to use both standard ideas of convexity and tricks from the study of log-concave functions. We will discuss the properties of polar functions as an application. In particular, we prove that the reciprocal of the integral of the polar function of a log-concave function is log-concave as a function of the center of polarity.

Bibliography:
Grigory Ivanov, Elisabeth M. Werner: Geometric representation of classes of concave functions and duality, arXiv

Abstract: We consider two long standing open problems in the study of edge intersections in geometric (hyper-)graphs.
1. Given a geometric graph with n vertices and n^{1+o(1)}t edges, do there exist t pairwise crossing edges?
2. Estimate the largest possible number f_d(n,h) so that a (d+1)-uniform geometric hypergraph in d-space with at least n^{d+1}h hyperedges (i.e., d-simplices) must contain f_d(n,h) simplices that are pierced by a single point.
The first question continues a long line of quasi-planarity results which positively settle it for near-constant t, whereas the second question comes hand in hand with the study of weak epsilon-nets and k-sets. (Any progress on the second question, a.k.a. the second selection theorem, would lead to better bounds for k-sets in dimension 5 and higher. )
The existing methods offer satisfactory and highly non-trivial answers for the very dense scenarios of both questions, which have been found lacking in the “intermediate range”.
The talk is partly based on joint work with J. Pach and G. Tardos.

Abstract: We introduce a novel definition of orientation on the triples of a family of pairwise intersecting planar convex sets and study its properties. In particular, we compare it to other systems of orientations on triples that satisfy a natural interiority condition. Such systems, P3O (partial 3-order), are a natural generalization of posets, and include the order types of planar point sets. Our main result is that P3O that emerge from points sets, p-P3O, and P3O that emerge from convex sets, C-P3O, do not contain each other. We also extend our orientation to other good covers from convex sets and study the resulting P3O's. Based on joint work with Ágoston, Damásdi, and Keszegh.

Bibliography:
Péter Ágoston, Gábor Damásdi, Balázs Keszegh, Dömötör Pálvölgyi: Orientation of convex sets, arXiv
Péter Ágoston, Gábor Damásdi, Balázs Keszegh, Dömötör Pálvölgyi: Orientation of good covers, arXiv

Abstract: For any natural number $n$, a family $\mathcal{F}$ of subsets of a space $\mathbf{X}$ is said to be {\em $n$-pierceable}, if there exists $A\subseteq\mathbf{X}$ with $|A|\leq n$ such that for any $F\in\mathcal{F}$, $F\cap A\neq\emptyset$.
Helly's theorem, one of the fundamental results in discrete geometry, says that for any finite family $\mathcal{F}$ of convex sets in $\mathbb{R}^d$, if every $(d+1)$-tuple from $\mathcal{F}$ is $1$-pierceable, then the whole family $\mathcal{F}$ is $1$-pierceable. Unfortunately, for $n\geq 2$, a similar statement about the $n$-pierceable sets is not valid for general convex sets. Danzer and Grünbaum proved the first and one of the most important Helly type results on multi-pierceable families; viz. famlies of axis parallel boxes.
One important generalization of Helly's theorem is Colorful Helly's Theorem. In this talk, we shall prove a colorful version of Danzer and Grünbaum's $2$-pierceability result for families of axis parallel boxes. This work was jointly done with Sourav Chakraborty and Arijit Ghosh.

Bibliography:
Sourav Chakraborty, Arijit Ghosh, Soumi Nandi: Colorful Helly Theorem for Piercing Boxes with Two Points, arXiv

Abstract: We will talk about our recent result settling an old conjecture of Paul Erdős: we prove that the density of any measurable planar set avoiding unit distances can not reach 1/4. Our solution is heavily computer-aided, and uses ideas from linear programming, graph theory, and harmonic analysis. This question is related to the famous Hadwiger-Nelson problem, and some of its variants. We will conclude by mentioning some still-unsettled conjectures that might be approached with our machinery. A joint work of Gergely Ambrus, Adrián Csiszárik, Máté Matolcsi, Dániel Varga and Pál Zsámboki. The talk is self-contained.

Bibliography:
Gergely Ambrus, Adrián Csiszárik, Máté Matolcsi, Dániel Varga, Pál Zsámboki: The density of planar sets avoiding unit distances, arXiv

Abstract: Let $ES_d(n)$ denote the smallest integer such that any set of $ES_d(n)$ points in $R^d$ in general position contains n points in convex position. In 1960, Erdős and Szekeres showed that $ES_2(n)≥2^{n−2}+1$ holds, and famously conjectured that their construction is optimal. This was nearly settled by Suk in 2017, who showed that $ES_2(n)≤2^{n+o(n)}$. We show that $ES_d(n)=2^{o(n)}$ holds for all $d\ge 3$. Joint work with Cosmin Pohoata.

Bibliography:
Cosmin Pohoata, Dmitrii Zakharov: Convex polytopes from fewer points, arXiv

Abstract: Ehrhardt theory states that the number of lattice points in a dilated lattice polytope is polynomial in the dilation factor. I will discuss and resolve several conjectures concerning the coefficients of this polynomial.

Abstract: Working on a topic whose research was initiated by Bárány, Katchalski and Pach in 1982, we study quantitative Helly-type theorems for the volume and the diameter of convex sets. We prove the following sparse approximation result for polytopes. Assume that Q is a polytope in John's position. Then there exist at most 2d vertices of Q whose convex hull Q' satisfies Q \subset - 2d^2 Q'. As a consequence, we retrieve the best bound for the quantitative Helly-type result for the volume, achieved by Brazitikos, and improve on the strongest bound for the quantitative Helly-type theorem for the diameter, shown by Ivanov and Naszódi: We prove that given a finite family F of convex bodies in R^d with intersection K, we may select at most 2d members of F such that their intersection has volume at most (cd)^(3d/2) vol K, and it has diameter at most 2 d^2 diam K, for some absolute constant c > 0. This a joint work with Víctor Hugo Almendra-Hernández and Gergely Ambrus.

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.

Bibliography:
Eyal Ackerman, Balázs Keszegh, Dömötör Pálvölgyi: On tangencies among planar curves with an application to coloring L-shapes, arXiv

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.

Bibliography:
Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky: On Multicolour Ramsey Numbers and Subset-Colouring of Hypergraphs, arXiv

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.

Bibliography:
Endre Csóka, Zoltán L. Blázsik, Zoltán Király, Dániel Lenger: Upper bounds for the necklace folding problems, arXiv

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.