BBC+G Seminar

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.

Abstract: The (usual) crossing number of a graph is the minimum number of edge crossings over all drawings. We compare some different versions of this parameter and show some results about their relationships.

Bibliogaphy:
Removing even crossings, pdf
Thirteen Problems on Crossing Numbers, pdf
On the Pair-Crossing Number, pdf
Note on the Pair-crossing Number and the Odd-crossing Number, pdf
A better bound for the pair-crossing number, pdf
Decidability of string graphs, pdf

Abstract: How long a monotone path can one always find in any edge-ordering of the complete graph \(K_n\)? This question was first asked by Chvátal and Komlós in 1971. It seems to have interesting applications to geometry - for instance, it can be translated into a problem about non-crossing paths in certain geometric graphs. The prevailing conjecture is that one can always find a monotone path of linear length, but the best known lower bound is \(n^{1 - o(1)}\).

Bibliogaphy:
Matija Bucic, Matthew Kwan, Alexey Pokrovskiy, Benny Sudakov, Tuan Tran, Adam Zsolt Wagner: Nearly-linear monotone paths in edge-ordered graphs, arXiv.

Abstract: For every positive integer n, we construct a Hasse diagram with n vertices and chromatic number \(\Omega(n^{1/4})\), which significantly improves on the previously known best constructions of Hasse diagrams having chromatic number \(\Theta(\log n)\), but still leaves a significant gap, as the best upper bound is \(\tilde\Omega(n^{1/2})\). The proof uses a simple statement from the theory of forbidden matrix patterns. Is it possible to extend the lower bound for 2-dimensional posets, i.e., for Delaunay graphs of rectangles?

Bibliogaphy:
Andrew Suk, István Tomon: Hasse diagrams with large chromatic number, arXiv.

Abstract: Teramoto et al. [Inserting points uniformly at every instance. IEICE Transactions, 2006.] defined a spatial uniformity measure of a finite point set in a unit square in \(\mathbb{R}^2\) called gap ratio. We generalize the definition of this measure over all metric spaces. The generalized definition is basically a ratio between the covering radius and the packing radius of points in the given metric space. A uniform distribution of points according to this measure gives a thin covering and a tight packing i.e., low gap ratio. This gives rise to the question of sampling points while minimising the gap ratio. We solve optimization related questions about selecting uniform point samples from metric spaces, which may be continuous or discrete. In the optimization framework, we study
- lower bounds on gap ratio for different metric spaces;
- hardness results;
- approximation algorithms and hardness of approximation results;
- existence of core sets for both the static and streaming point set.

Bibliogaphy:
Arijit Bishnu, Sameer Desai, Arijit Ghosh, Mayank Goswami, Subhabrata Paul: Uniformity of point samples in metric spaces using gap ratio, arXiv.

Abstract: A family of closed simple (i.e., Jordan) curves is \(m\)-intersecting if any pair of its curves have at most \(m \) points of common intersection. We say that a pair of such curves {\it touch} if they intersect at a single point of common tangency. We show that any \( m \) -intersecting family of \( n \) curves in general position in the plane contains \( O\left(n^{2-\frac{1}{3m+15}}\right) \) touching pairs (A family of Jordan curves is in general position if no three of its curves pass through the same point, and no two of them overlap. The constant of proportionality with the \( O(\cdot) \) -notation may depend on \( m\)).
Furthermore, we use the string separator theorem of Fox and Pach in order to establish the following Crossing Lemma for contact graphs of Jordan curves: Let \( \Gamma \) be an \( m\)-intersecting family of closed Jordan curves in general position in the plane with exactly \( T=\Omega(n) \) touching pairs of curves, then the curves of \( \Gamma\) determine \( \Omega\left(T\cdot\left(\frac{T}{n}\right)^{\frac{1}{9m+45}}\right)\) intersection points.

Bibliogaphy:
Maya Bechler-Speicher: A Crossing Lemma for Families of Jordan Curves with a Bounded Intersection Number , arXiv.

Abstract: We study the growth of \(r_k\), the k-th Radon number, in convexity spaces. If \(r_2\) is finite, we present an improved upper bound on r_k. We also investigate Eckhoff's conjecture on the growth of r_k, which has been proven to be true when \(r_2 = 3\). However, when \(r_2 = 4\), we construct a family of convexity spaces where Echkoff's conjecture fails.

Bibliogaphy:
B. Bukh: Radon partitions in convexity spaces , arXiv.

Abstract: We consider intersection hypergraphs defined on a finite family S of n (possibly intersecting) axis-parallel segments by a finite family of pairwise disjoint curves C such that every curve has an endpoint which lies in the same connected region of \(\mathbb{R}^2\setminus S\). We call such a family of curves grounded. We show that such a hypergraph has at most \(O(n)\) hyperedges of size 2. We further show, using a general framework, how this implies further properties of such a hypergraph: it has \(O(k^c n)\) hyperedges of size at most \(k\) and can be properly colored with \(O(1)\) colors. These results imply respective results about intersection hypergraphs defined on a finite family of grounded L-shapes by another finite family of grounded L-shapes (an L-shape is grounded if its top endpoint lies on the \(x\)-axis), improving a recent result of Keller, Rok and Smorodinsky.
Joint work with Eyal Ackerman and Dömötör Pálvölgyi.

Abstract: We define an abstraction of convex sets, called convexity space, and show that if the natural generaliation of Radon's theorem holds, then so does the Tverberg theorem, Helly's theorem, the colorful Helly theorem, the fractional Helly theorem, and thus there are also weak eps-nets. We also study the so-called Eckhoff's conjecture about the growth rate of \(r_k\), the \(k\)-th partition number aka \(k\)-th Radon number aka \(k\)-th Tverberg number.

Bibliogaphy:
N. Alon, G. Kalai, J. Matoušek, and R. Meshulam, Transversal Numbers for Hypergraphs Arising in Geometry. , Advances in Applied Mathematics 29: 79-101 (2002).
J. Eckhoff, The partition conjecture , Discrete Mathematics 221: 61-78 (2000).
A. F. Holmsen and Dong-Gyu Lee: Radon numbers and the fractional Helly theorem , arXiv.
B. Bukh: Radon partitions in convexity spaces , arXiv.
A. F. Holmsen: Large cliques in hypergraphs with forbidden substructures , arXiv.

Abstract: We define an abstraction of convex sets, called convexity space, and show that if the natural generaliation of Radon's theorem holds, then so does the Tverberg theorem, Helly's theorem, the colorful Helly theorem, the fractional Helly theorem, and thus there are also weak eps-nets. We also study the so-called Eckhoff's conjecture about the growth rate of \(r_k\), the \(k\)-th partition number aka \(k\)-th Radon number aka \(k\)-th Tverberg number.

Bibliogaphy:
N. Alon, G. Kalai, J. Matoušek, and R. Meshulam, Transversal Numbers for Hypergraphs Arising in Geometry. , Advances in Applied Mathematics 29: 79-101 (2002).
J. Eckhoff, The partition conjecture , Discrete Mathematics 221: 61-78 (2000).
A. F. Holmsen and Dong-Gyu Lee: Radon numbers and the fractional Helly theorem , arXiv.
B. Bukh: Radon partitions in convexity spaces , arXiv.
A. F. Holmsen: Large cliques in hypergraphs with forbidden substructures , arXiv.

Abstract: We prove some natural generalizations of well known Ramsey-type results for abstract graphs, for graphs drawn in the plane. An example: It is well known that for every graph G, either G or its complement is connected. So, G or its complement contains a spanning tree. We show that every geometric graph (graph drawn with straight line segments as edges) or its complement contains a NONCROSSING spanning tree.

Bibliography:
G. Károlyi, J. Pach, G. Tóth: Ramsey-Type Results for Geometric Graphs, I , Discrete and Computational Geometry 18 (1997), 247-255. Also in: Proceedings of the 12th Annual ACM Symposium on Computational Geometry 1996, 359-365.
G. Károlyi, J. Pach, G. Tóth, P. Valtr: Ramsey-Type Results for Geometric Graphs. II , Discrete and Computational Geometry 20 (1998), 375-388. Also in: Proceedings of the 13th Annual ACM Symposium on Computational Geometry 1997, 94-103.
J. Pach, J. Solymosi, G. Tóth: Unavoidable configurations in complete topological graphs , Discrete and Computational Geometry 30 (2003), 311-320. Also in: Lecture Notes in Computer Science 1984 Springer-Verlag, 2001, 328-337.

Abstract: Given n points in the plane they determine n choose 2 distances between them. But these distances are highly dependent, usually 2n-3 of them determines the rest. Distance geometry's goal in general is to gain information on which sets of distances can be realized by a set of points. Many questions from discrete geometry fit into this area. (Chromatic number of the plane, Harborth conjecture, integral point sets...) I will introduce the basic questions and results from these topics and then I will present a selection of nice open problems.

Bibliogaphy: List of problems

Abstract: We present algorithms for the \((1+\epsilon)\)-approximate version of the closest vector problem for certain norms. The currently fastest algorithm (Dadush and Kun 2016) for general norms has running time \(2^{O(n)} (1/\epsilon)^n\). We improve this substantially for convex bodies whose modulus of smoothness, a quantity expressing how well tangent hyperplanes approximate the boundary, is well bounded. This is the case for unit balls of \(\ell_p\) spaces. Joint work with Moritz Venzin.

Bibliography:
Márton Naszódi, Moritz Venzin: Covering convex bodies and the Closest Vector Problem

Abstract: Neumann-Lara and Urrutia posed the following question: for an integer n, what is the maximal number such that for any set S of n points in the plane we can always find two points p and q in S such that all circles passing through them enclose that many points. We examine some variants of this problem and show that for all sets we can find two points such that all circles passing through them enclose at most \(\left\lfloor 2n-3\over 3\right\rfloor\) points. We also show that for any 2-coloured point set with n red and n blue points, we can find two points of different colours such that every circle passing through them encloses at least \(n\left(1-{1\over\sqrt{2}}\right)-o(n)\) points from the set. The proofs use higher order Voronoi diagrams.

Bibliography:
Mercè Claverol, Clemens Huemer, Alejandra Martínez-Moraian: On circles enclosing many points

Abstract: In 2018, Aubrey de Grey proved that (the graph of the unit distances on) the plane is not 4-colourable, improving the lower bound for the Hadwiger-Nelson problem. His solution used computer assistance, so a Polymath Project was launched to find a simpler proof for the bound and possibly other related results. One of the ideas was to randomize a hypothetical 4-colouring of the plane and then give estimates to the probabilities for certain distances being monochromatic. We will summarize recent results in and around this project.

Abstract: We study Hamiltonicity for some of the most general variants of Delaunay and Gabriel graphs.Let S be a point set in the plane. The k-order Delaunay graph of S, denoted k-DGC(S), has vertex set S and edge pq provided that there exists some homothet of C with p and q on its boundary and containing at most k points of S different from p and q. The k-order Gabriel graphk-GGC(S) is defined analogously, except for the fact that the homothets considered are restricted to be smallest homothets of C with p and q on its boundary. We provide upper bounds on the minimum value of k for which k-GGC(S) is Hamiltonian.

Bibliography:
Prosenjit Bose, Pilar Cano, Maria Saumell, and Rodrigo I.Silveira: Hamiltonicity for convex shape Delaunay and Gabriel graphs

Abstract: Given a finite family of bottomless rectangles in the plane, let \(m^*(k)\) be the least integer so that there is a \(k\)-coloring of the rectangles with the property that any point contained in \(m^*(k)\) rectangles is covered by all \(k\) colors. We construct algorithms to \(k\)-color certain configurations with \(m^*(k)\) linear, and give an improved lower bound for \(m^*(k)\) for general families.

Abstract: We consider the following packing problem in Euclidean space: given a set of ball-like (i.e., fat) objects, find the largest subset of pairwise non-intersecting objects among them. We briefly discuss some related separator theorems and algorithms. It turns out that one can give progressively faster algorithms the more fat the underlying objects are. Then we turn to lower bounds to explain why object fatness is so crucial. We show how certain wiring constructions in grids can be used for gaining lower bounds for packing problems with fat objects. We present the so-called Cube Wiring Theorem: using an elementary construction, we show that any graph on m edges is a minor of the k x k x k grid, where \(k=O(m^{1/2}\)). Finally, we show how Cube Wiring extends to blown-up grids (replacing each grid point by a clique), and use this extension to get a lower bound for the packing of "skinny" axis-parallel boxes. The talk is based on joint work with M. de Berg, H.L. Bodlaender, D. Marx and T.C. van der Zanden.

Bibliography:
M. de Berg, H.L. Bodlaender, S. Kisfaludi-Bak, D. Marx and T.C. van der Zanden: A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs , arXiv.

Let \(A\) and \(B\) be finite sets and consider a partition of the \emph{discrete box} \(A \times B\) into \emph{sub-boxes} of the form \(A' \times B'\) where \(A' \subset A\) and \(B' \subset B\). We say that such a partition has the \((k,\ell)\)-piercing property for positive integers \(k\) and \(\ell\) if every \emph{line} of the form \(\{a\} \times B\) intersects at least \(k\) sub-boxes and every line of the form \(A \times \{b\}\) intersects at least \(\ell\) sub-boxes. We show that a partition of \(A \times B\) that has the \((k, \ell)\)-piercing property must consist of at least \((k-1)+(\ell-1)+\left\lceil 2\sqrt{(k-1)(\ell-1)} \right\rceil\) sub-boxes. This bound is nearly sharp (up to one additive unit) for every \(k\) and \(\ell\). As a corollary we get that the same bound holds for the minimum number of vertices of a graph whose edges can be colored red and blue such that every vertex is part of a red \(k\)-clique and a blue \(\ell\)-clique. Joint work with Rom Pinchasi.

Bibliography:
Eyal Ackerman and Rom Pinchasi, On Partitions of Two-Dimensional Discrete Boxes , arXiv.

Abstract: A graph H is planar unavoidable if there is a planar graph G such that any red/blue coloring of the edges of G contains a monochromatic copy of H. We prove that the cycle on 4 vertices and any path are planar unavoidable, and discuss related questions.

Bibliography:
Maria Axenovich, Carsten Thomassen, Ursula Schade, Torsten Ueckerdt: Planar Ramsey graphs , arXiv.

Abstract: We study several problems concerning convex polygons whose vertices lie in a Cartesian product (for short, grid) of two sets of \(n\) real numbers. We prove that every such grid contains a convex polygon with \(\Omega(\log n)\) vertices and that this bound is tight up to a constant factor. We generalize this result to \(d\) dimensions (for a fixed \(d\)), and obtain a tight lower bound of \(\Omega(\log^{d-1}n)\) for the maximum number of points in convex position in a \(d\)-dimensional grid. We also present exponential upper and lower bounds on the maximum number of convex polygons in planar grids.These bounds are tight up to polynomial factors. (Joint work with Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, and Sander Verdonschot.)

Bibliography:
Jean-Lou De Carufel, Adrian Dumitrescu (CS), Wouter Meulemans, Tim Ophelders, Claire Pennarun (ALGCO), Csaba Toth (CPSC), Sander Verdonschot: Convex Polygons in Cartesian Products , arXiv

Bibliography:
Gábor Damásdi, Leonardo Martínez-Sandoval, Dániel T. Nagy, Zoltán Lóránt Nagy, Triangle areas determined by arrangements of planar lines , arXiv.

Bibliography:
J. Pach and J. Törőcsik, Some geometric applications of Dilworth’s theorem , DCG 12(1):1-7, 1994.
Géza Tóth, Note on Geometric Graphs , JCT A 89(1):126-132, 2000.

Abstract: To complement Nabil's minicourse, I'll prove a \(1/\epsilon \log(1/\epsilon)\) type lower bound for the size of WEAK epsilon-nets for planar convex sets. The talk will be self-contained.

Bibliography:
B. Bukh, J. Matousek, and G. Nivasch, Lower bounds for weak epsilon-nets and stair-convexity , Israel J. Math. 182, 199–228, 2011.

Abstract: An r-segment hypergraph H is a hypergraph whose edges consist of r consecutive integer points on line segments in R^2. In this paper, we bound the chromatic number χ(H) and covering number τ(H) of hypergraphs in this family, uncovering several interesting geometric properties in the process. We conjecture that for r ≥ 3, the covering number τ(H) is at most (r − 1)ν(H), where ν(H) denotes the matching number of H. We prove our conjecture in the case where ν(H) = 1, and provide improved (in fact, optimal) bounds on τ(H) for r ≤ 5. We also provide sharp bounds on the chromatic number χ(H) in terms of r, and use them to prove two fractional versions of our conjecture.

Bibliogaphy:
Deborah Oliveros, Christopher O'Neill, Shira Zerbib: The geometry and combinatorics of discrete line segment hypergraphs , arXiv.

Abstract: We start from a natural coloring problem: colour some points in the plane with c colours, in a way that any fixed (top right and bottom left corners are points of the set) axis-parallel rectangle, which contains at least d points, contains a point of every colour. I will prove that for any c, d integers, there exist a point set P of the plane, so that any c-colouring of the elements of P, there is a fixed axis-parallel rectangle, which contains exactly d points, all the same colour. Moreover, the d points inside the rectangle lie in a monotonically increasing order.

Abstract: Let P be a set of n points in the plane in general position. The vertices of the intersection graph of P are the pairs of P and two vertices are connected if the corresponding straight line segments intersect. We show some results about how the (compatible) exchange graph of P determines the intersection graph of P. The vertices of the exchange graph of P are the planar spanning trees on P and two vertices are connected if the corresponding trees differ in exactly two edges. In the compatible exchange graph we further require that these two edges are also non-crossing.

Bibliogaphy:
M. Oropeza, Cs. D. Tóth: Reconstruction of the Crossing Type of a Point Set from the Compatible Exchange Graph of Noncrossing Spanning Trees

Abstract: Consider \(n\) points in \(R^d\) and a positive integer \(m \geq 2\). If \(n \geq (m-1)(d+1)+1\), the points can always be partitioned into \(m\) subsets whose convex hulls contain a common point. This is the celebrated theorem of Tverberg, which has been the topic of many generalizations and variations since it was first proved in 1966. We formalize new versions of Tverberg's theorem where the coordinates of the points are integer. We show that the Tverberg number of \(Z^2\) is \(4m-3\). We also show new upper bounds for the Tverberg numbers of \(Z^3\) and \(Z^j \times R^k\).

Bibliogaphy:
Jesús A. De Loera, Thomas Hogan, Frédéric Meunier, Nabil Mustafa: Integer and Mixed Integer Tverberg Numbers , arXiv.

Abstract: Let G be a finite set of points in the plane. A line M is a (k,k)-line if M is determined by G, and there are at least k points of G in each of the two open half-planes bounded by M. Let f(k,k) denote the maximum size of a set G in the plane, which is not contained in a line and does not determine a (k,k)-line. We show that \(f(k,k)<=2k+O(\log\log k)\).

Bibliogaphy:
Rom Pinchasi: Lines With Many Points On Both Sides , Discrete and Computational Geometry 30: 415-435, 2003.

Abstract: We study Erdős-Szekeres-type problems for so-called \(k\)-convex point sets, a recently introduced notion that naturally extends the concept of convex position. A finite set \(S\) of points in the plane is \)k\)-convex if \(S\) is a vertex set of a simple polygon that is intersected by every line in at most \(k\) connected components. We address several open problems about \(k\)-convex point sets. In particular, we extend the famous Erdős-Szekeres Theorem by showing that, for every fixed \(k \in \mathbb{N}\), every set of \(n\) points in the plane in general position (with no three collinear points) contains a \(k\)-convex subset of size at least \(\Omega(\log^k{n})\). We also show that there are arbitrarily large \(3\)-convex sets of \(n\) points in the plane in general position with no (\(1\)-)convex subset of size larger than \(c \log{n}\) for some constant \(c\). This gives a solution to a problem posed by Aichholzer et al. This is joint work with Sujoy Bhore, Leonardo Martínez-Sandoval, and Pavel Valtr.

Abstract: A finite set X in some Euclidean space is called Ramsey if for any k a monochromatic copy of X appears in any k-colouring of a sufficiently high dimensional Euclidean space. A long-standing conjecture claims that X is Ramsey if and only if it can be embedded into the surface of a sphere. It is known that any Ramsey set is indeed spehrical, but all our examples for Ramsey sets so far also satisfy the stronger condition of transitivity. Therefore we propose the alternative conjecture that X is Ramsey if and only if it is transitive. We show that this new conjecture is different from the old one and that it reduces to a purely combinatorial statement.

Bibliogaphy:
Imre Leader, Paul A. Russell, Mark Walters: Transitive Sets in Euclidean Ramsey Theory , J. Comb. Theory Ser. A 119, 382-396 (2012).

Abstract: We study the problem of how to breakup many point sets in Rd into smaller parts using a few splitting (shared) hyperplanes. This problem is related to the classical Ham-Sandwich Theorem. We provide a logarithmic approximation to the optimal solution using the greedy algorithm for submodular optimization.

Bibliogaphy:
Sariel Har-Peled, Mitchell Jones: Few Cuts Meet Many Point Sets , arXiv.

Abstract: For any n and k, we show that any n point set has \(O(nk^{1/3})\) k-sets.

Bibliogaphy:
T. K. Dey, Improved bounds for planar k-sets and related problems , Discrete and Computational Geometry 19: 373–382, 1998.

Abstract: For any n and k, we construct an n point set with \(\Omega(n2^\sqrt{\log k})\) k-sets.

Bibliogaphy:
Géza Tóth: Point sets with many k-sets , Discrete and Computational Geometry 26:187-194, 2001.

Abstract: I'll present a surprising connection between the maximum number of sets separable from an n point set by lines, and the maximum number of possible turns an x-monotone path can make in an arrangement of n lines. I'll follow this 10 year-old paper, but it's worth mentioning that most results have been independently rediscovered in this summer's Emlektabla workshop.

Bibliography:
Rom Pinchasi, Günter Rote: On the maximum size of an anti-chain of linearly separable sets and convex pseudo-discs , Israel Journal of Mathematics, 172(1), 337–348 (2009).

Bibliogaphy:
Rajiv Raman, Saurabh Ray: Planar Support for Non-piercing Regions and Applications , ESA 2018, 14 pages.

Abstract: We present a recent claimed family of finite unit-distance graphs in the plane that are not 4-colourable, thereby improving the lower bound of the Hadwiger-Nelson problem. After this, we will discuss possible simplifications of the problem in a research Jam session.

Bibliogaphy:
Aubrey D.N.J. de Grey: The chromatic number of the plane is at least 5.

Abstract: A rollercoaster is a sequence of real numbers for which every maximal contiguous monotonic subsequence has length at least three. We will show that every sequence of n distinct real numbers contains a rollercoaster of length at least [(n+1)/2] for n>7, and a linear time algorithm for computing such a rollercoaster. We will also show an O(n log n) algorithm for finding a longest increasing subsequence and a maximal length rollercoaster. The other topic of the lecture will be caterpillars which are trees such that deleting the leaves gives a path, called the spine. A top-view caterpillar is one of degree 4 such that the two leaves adjacent to each vertex lie on opposite sides of the spine. The results on rollercoasters helps finding a planar drawing of every n-node top-view caterpillar on every set of (25/3)n points in the plane, such that each edge is an orthogonal path with one bend.

Bibliogaphy:
Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, Jeffrey Shallit: Rollercoasters and Caterpillars.

Abstract: A conflict-free k-coloring of a graph G = (V,E) assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among v and v's neighbors. Such colorings have applications in wireless networking, robotics, and geometry, and are well studied in graph theory. Here we study the conflict-free coloring of geometric intersection graphs. We demonstrate that the intersection graph of n geometric objects without fatness properties and size restrictions may have conflict-free chromatic number in Ω(logn/loglogn) and in Ω(√ log n) for disks or squares of different sizes; it is known for general graphs that the worst case is in Θ(log^2 n). For unit-disk intersection graphs, we prove that it is NP-complete to decide the existence of a conflict-free coloring with one color; we also show that six colors always suffice, using an algorithm that colors unit disk graphs of restricted height with two colors. We conjecture that four colors are sufficient, which we prove for unit squares instead of unit disks. For interval graphs, we establish a tight worst-case bound of two.

Bibliogaphy:
Sándor P. Fekete, Phillip Keldenich: Conflict-Free Coloring of Intersection Graphs , ISAAC 2017: 31:1-31:12.

Abstract: An ordered graph H is a graph with a linear ordering on its vertex set. The corresponding Turán problem, first studied by Pach and Tardos, asks for the maximum number \(ex_{<}(n,H)\) of edges in an ordered graph on n vertices that does not contain H as an ordered subgraph. It is known that \(ex_{<}(n,H)> n^{1+ε}\) for some positive \(\epsilon=\epsilon(H)\) unless H is a forest that has a bipartition \(V_1\cup V_2\) such that \(V_1\) totally precedes \(V_2\) in the ordering. Making progress towards a conjecture of Pach and Tardos, we prove that \(ex_{<}(n,H)=n^ {1+o(1)}\) holds for all such forests that are "degenerate" in a certain sense. This class includes every forest for which an \(n^{1+o(1)}\) upper bound was previously known, as well as new examples. Our proof is based on a density-increment argument.

Bibliogaphy:
Dániel Korándi, Gábor Tardos, István Tomon and Craig Weidert: On the Turán number of ordered forests , Electronic Notes in Discrete Mathematics, 61, 773-779 (2017).

Abstract: Say that a family of sets satisfies the (p,q)r property if for any p members of the family, at least r of the {p choose q} q-tuples intersect. The Alon-Kleitman (p,q) theorem says that if a family of d-dimensional convex sets has the (p,q)1 property for some q>=d+1, then there are HDd(p,q) points that meet all members of the family. Earlier this theorem was known as the Hadwiger-Debrunner (p,q) conjecture; Hadwiger and Debrunner could only prove the (much easier) case of q>p(d-1)/d+1 (and q>=d+1), in which case HDd(p,q)<=p-q+1 holds. Montejano and Soberon showed that the same upper bound holds for families satisfying the (p,q)r property for r>{p choose q} - {p-d+1 choose q-d+1}, i.e., HDd(p,q)r<=p-q+1. We show that this inequality also holds for much smaller r's as well, already for r>p^{-q/2d} {p \choose q}. The proof uses bootstrapping, a recent upper bound on HDd(p,q) and Kalai’s Upper Bound Theorem for convex sets.

Bibliogaphy:
Chaya Keller, Shakhar Smorodinsky: On piercing numbers of families satisfying the (p,q)r property , Computational Geometry, 2018, in press.

Abstract: Every convex n-gon is a projection of a polytope with o(n) facets.

Bibliogaphy:
Yaroslav Shitov: Sublinear extensions of polygons

Abstract: Mass partition theorems have been extensively studied in recent decades. Conical partitions have been mainly considered in the planar case, but some higher dimensional results have been obtained by Vrecica and Živaljevic, and Makeev. The proof of mass partition theorems usually follows the configuration space/test map procedure or some degree theoretic method, both of which heavily rely on topological results. This is especially true for results in higher dimensions, where our combinatorial tools are limited. We show a completely combinatorial proof for the discrete version of a theorem of Vrecica and Živaljevic concerning conical partitions.

Abstract: We prove that the intersection hypergraph of a family of n pseudo-disks with respect to another family of pseudo-disks admits a proper coloring with 4 colors and a conflict-free coloring with O(logn) colors. Along the way we prove that the respective Delaunay-graph is planar. We also prove that the intersection hypergraph of a family of n regions with linear union complexity with respect to a family of pseudo-disks admits a proper coloring with constant many colors and a conflict-free coloring with O(logn) colors. Our results serve as a common generalization and strengthening of many earlier results, including ones about proper and conflict-free coloring points with respect to pseudo-disks, coloring regions of linear union complexity with respect to points and coloring disks with respect to disks.

Bibliography:
Balázs Keszegh: Coloring intersection hypergraphs of pseudo-disks

Abstract: Let P be a set of n points in the plane. A topological hyper-graph G on the set of points of P is a collection of simple closed curves in the plane that avoid the points of P. Each of these curves is called an edge of G, and the points of P are called the vertices of G. We provide bounds on the number of edges of topological hyper-graphs in terms of the number of their vertices under various restrictions assuming the set of edges is a family of pseudo-circles.

Bibliogaphy:
Sarit Buzaglo, Rom Pinchasi, Günter Rote: Topological Hypergraphs , in: Pach J. (eds) Thirty Essays on Geometric Graph Theory. Springer, New York, NY, pp 71-81, 2013.

Abstract: Let us call a colouring of a set of points in R^d conflict-free for some family Q (for example Q can be the set of all disks in R^d) if for every S∈Q there is a colour that is used exactly once inside S. We are discussing algorithms which give a colouring for point sets on R when the points are added one by one, and all of them should be coloured immediately upon insertion in such a way that the colouring remains conflict-free with respect to the intervals of R all the time. The goal is to minimize the number of colours used.

Bibliogaphy:
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Jiří Matoušek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, and Emo Welzl: Online Conflict-Free Coloring for Intervals , SIAM J. Comput., 36(5), 1342-1359 (2006).

Abstract: The celebrated Szemerédi-Trotter Theorem provides a good upper bound on the incidences of a given planar point set P and line set L in terms of |P| and |L|. We present a new proof due to Matousek which is based on a polynomial lemma, which enable us to construct bivariate low-degree polynomials whose nullset partition arbitrary point set into small classes.

Abstract: I will talk about the following result of Axenovich and Ueckerdt: let X be a finite set of points of the plane, S be a compact subset of the plane and k>=2. Let H(X,S,k) be that k-uniform hypergraph on X, whose edges are those k-subsets of X, that can be captured by a homothetic copy of S (i.e. has the form X \cap S', for some homothetic copy S' of S). We give an upper bound on the cardinality of the edges of this hypergraph.

Bibliogaphy:
M. Axenovich, T Ueckerdt: Density of range capturing hypergraphs , Journal of Computational Geometry 7 (2016).

Abstract: I will present several Helly type theorems, and generalizations of these. Helly's theorem deals with a family of convex sets in R^d where every d+1 have non-empty intersection, and concludes non-empty intersection for the whole family. We will consider what happens if we ask for intersections with large volume, or intersections with large inscribed ellipsoids. We will also discuss the colorful versions of these theorems.

Abstract: The (orientable) \(Z_2\)-genus of a graph G is the minimum g such that G has a drawing on the surface of (orientable) genus g, in which every pair of non-adjacent edges cross an even number of times. We find a graph of orientable genus 5 and orientable \(Z_2\)-genus 4, which disproves a conjecture of Schaefer and Stefankovic (2013) predicting that the orientable genus and \(Z_2\)-genus are the same for every graph. We also discuss their relaxed version of the conjecture predicting that there exists a function f such that an (orientable) genus of every graph with \(Z_2\)-genus g is at most f(g). In particular, we prove that the (orientable) genus of every graph in the family consisting of Kuratowski minors, i.e., copies of \(K_5\) or \(K_{3,3}\) glued on 0,1, or 2 vertice and \(K_{3,k}\)'s; and projective grids, is upper bounded by a function of its \(Z_2\)-genus. This in turn implies that the statement of the relaxed conjecture follows from an unpublished result claimed by Robertson and Seymour characterizing graphs that are not embeddable on a given surface. The talk will be self-contained, and area related definitions will be given during the talk. Therefore no previous knowledge of the theory of graph embeddings on surfaces is required. This is a joint work with Jan Kynčl.

Bibliography:
Radoslav Fulek, Jan Kynčl: Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4

Abstract: Let P be a set of n points in the plane and C a family of simple closed curves avoiding P. Assume that the intersection of any two discs bounded by curves of C is connected and that every two curves intersect at most k times. We consider a family F that consists of the point sets surrounded by curves of C, and give bounds for the number of l-size subsets and the VC-dimension of F.

Bibliography:
Sarit Buzaglo, Ron Holzman, Rom Pinchasi: On k-intersecting curves and related problems , SoCG '08: 79-84, 2008.

Abstract: For a graph G, consider an arrangement of its vertices in the plane along with some polygonal obstacles in such a way that two vertices can see each other if and only if they are adjacent in the graph. Let obs(G) denote the minimum achievable number of obstacles. We give an upper bound of O(n log n) in general and O(n) for graphs with bounded chromatic number.

Bibliography:
Martin Balko, Josef Cibulka, Pavel Valtr: Drawing graphs using a small number of obstacles , Graph Drawing 2015: 360-372. Springer, 2015.

Abstract: A graph is a string graph if it is the intersection graph of strings (curves) in the plane. The complexity of a string graph G is the minimum number of crossings in a string representation of G. We give an exponential upper bound on the complexity of a string graph of m edges. We also give a construction of a string graph of exponential complexity.

Bibliogaphy:
Jan Kratochvíl and Jiří Matoušek: String graphs requiring exponential representations , Journal of Combinatorial Theory, Series B 53.1 (1991): 1-4.
Marcus Schaefer and Daniel Stefankovic: Decidability of string graphs , Proceedings of the thirty-third annual ACM symposium on Theory of computing. ACM, 2001.

Abstract: We show that there is an absolute constant c ≤ 156 such that in every finite family F of pseudo-discs in the plane one can find a member D ∈ F such that among all of the pseudo-discs in F intersecting D there are at most c pairwise disjoint sets.

Bibliography:
Rom Pinchasi: A Finite Family of Pseudodiscs Must Include a “Small” Pseudodisc , SIAM J. Discrete Math., 28(4), 1930–1934 (2014).