Bibliography:
Elizaveta Streltsova, Uli Wagner:
Sublevels in arrangements and the spherical arc crossing number of complete graphs, arXiv
Bibliography:
Rahul Gangopadhyay, Alexander Polyanskii, Wei Rao:
New Helly-type results for discrete boxes: Quantitative colorful and $(p,q)$-variants, arXiv
Bibliography:
Håvard Bakke Bjerkevik, Linda Kleist, Torsten Ueckerdt, Birgit Vogtenhuber:
Flipping Non-Crossing Spanning Trees, arXiv
Bibliography:
Natan Rubin:
On Lines Crossing Pairwise Intersecting Convex Sets in Three Dimensions
Abstract: We show that if $\mathcal{K}$ is a family of $n$ pairwise intersecting convex sets in $\mathbb{R}^3$, then there is a line crossing $\Theta(n)$ elements of $\mathcal{K}$.
Abstract: We consider the faces in pseudoline arrangements in which the pseudolines are colored with two colors. Björner, Las Vergnas, Sturmfels, White, and Ziegler conjecture the existence of a two-colored triangle in such arrangements. We consider variants of this problem. We show that in any non-trivial two-coloring of a pseudoline arrangement there exists a two-colored triangle or quadrangle. We also investigate the existence of a bichromatic triangle assuming certain structures on the coloring.
Previously, several authors investigated the chromatic number and independence number of hypergraphs whose vertices correspond to the pseudolines of an arrangement and the hyperedges correspond to the faces of the arrangement. We show that the maximum of the independence numbers of such hypergraphs is $\lceil \frac{2}{3}n-1\rceil$. We also prove that if we only consider the triangular faces then this maximum becomes $n-\Theta(\log n)$.
Joint work with Yan Alves Radtke and Robert Lauff
Bibliography:
János Pach, Orit E. Raz, József Solymosi:
Erdős's unit distance problem and rigidity, arXiv
Bibliography:
Noga Alon, Rom Pinchasi:
Distinct Directions and Distinct Distances in $\mathbb{R}^d$, arXiv
Bibliography:
José M. Díaz-Bañez, Ruy Fabila-Monroy, Jorge Urrutia:
A Note on Empty Balanced Tetrahedra in Two colored Point sets in $\mathbb{R}^3$, Computational Geometry, Volume 96 (2021) (arXiv)
Ting-Wei Chao, Zichao Dong, Zhuo Wu:
Empty red-red-blue triangles, arXiv
Bibliography:
Zichao Dong, Zijian Xu:
Large grid subsets without many cospherical points, arXiv
Bibliography:
Therese Biedl, Erin Chambers, Irina Kostitsyna, Günter Rote:
Sweeping $x$-monotone pseudolines, arXiv
Bibliography:
Romain Bourneuf, Pierre Charbit, Stéphan Thomassé:
A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number, arXiv
Abstract: Three lines are concurrent if they intersect at a single point. In this paper I prove that if $F$ is a bounded family of compact connected sets in the plane, such that every three sets in $F$ can be pierced by a single line, then there exists three concurrent lines in the plane such that the union of the three lines intersect every member of $F$. This had previously only been proven for lines that are not required to be concurrent by McGinnis and Zerbib.
Abstract: Arrangements of curves have long played a central role in discrete and computational geometry. In particular, the study of pseudocircles—simple closed curves in the plane or on the sphere that pairwise intersect exactly twice—offers a powerful generalization of both arrangements of straight lines and arrangements of true circles. This topic was pioneered by Branko Grünbaum in the 1970s, who posed fundamental questions about the combinatorial structure of such arrangements: How many $k$-gonal faces (in particular, triangles and digons) can appear? Which arrangements can actually be realized by proper circles? And how do classical incidence theorems extend to this broader setting? I will talk about the recent progress made on the number of digons and triangles in pairwise intersecting arrangements.
Abstract: An ordered graph is a graph together with a total ordering of its vertices. Let $H$ be an ordered $k$-uniform hypergraph. We say that $H$ contains a monotone path of length $n$ if there is an ordered sequence of vertices of length $n+k-1$ for which $H$ contains every $k$-tuple (i.e. edge) of consecutive vertices in the sequence. Let $N_k(q,n)$ be the smallest integer $N$ so that every $q$-coloring of the edges of the complete $k$-uniform hypergraph on $N$ vertices contains a monochromatic monotone path of length $n$. The problem of bounding $N_k(q,n)$ was studied by Fox, Pach, Sudakov and Suk; however, it goes back (implicitly) to the seminal 1935 paper of Erdős and Szekeres. In this talk, I present a construction by Moshkovitz and Shapira that improves the bound of Fox et al.; furthermore, I investigate how $N_k(q,n)$ changes if the coloring is restricted to stricter properties, and I present a construction by Balko addressing this case.
Bibliography:
Barnabás Janzer, Oliver Janzer, Abhishek Methuku, Gábor Tardos:
Tight bounds for intersection-reverse sequences, edge-ordered graphs and applications, arXiv
Bibliography:
Stefan Steinerberger:
Many antipodes implies many neighbors, arXiv
Bibliography:
Cosmin Pohoata, Kevin Yang, Shengtong Zhang:
Colorful Helly via induced matchings, arXiv
Bibliography:
Johanna Ockenfels, Yoshio Okamoto, Patrick Schnider:
Chasing puppies on orthogonal straight-line plane graphs, arXiv
Bibliography:
David Eppstein:
Non-Euclidean Erdős-Anning Theorems, arXiv
Bibliography:
James Davies, Yelena Yuditsky:
Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity, arXiv
Bibliography:
Aaron Büngener, Michael Kaufmann:
Improving the Crossing Lemma by Characterizing Dense 2-Planar and 3-Planar Graphs, arXiv
Abstract: I present a result of Holmsen and Patáková about fractional Helly numbers of separable convexity spaces, which generalizes a result of Bárány and Matoušek about the fractional Helly number of convex lattice sets.
Bibliography:
Andreas F. Holmsen, Zuzana Patáková:
The fractional Helly number for separable convexity spaces, arXiv
Bibliography: Eric Myzelev: Characterization of Colorings Obtained by a Method of Szlam, arXiv
Bibliography: Debsoumya Chakraborti, Minho Cho, Jinha Kim, Minki Kim: Colorful fractional Helly theorem via weak saturation, arXiv
Bibliography: Terence Tao: Planar point sets with forbidden 4-point patterns and few distinct distances, arXiv
Bibliography: Helena Bergold, Joachim Orthaber, Manfred Scheucher, Felix Schröder: Holes in Convex and Simple Drawings, arXiv
Bibliography: Suryendu Dalal, Rahul Gangopadhyay, Rajiv Raman, Saurabh Ray: Sweeping Arrangements of Non-Piercing Curves in Plane, arXiv
Bibliography: Seunghun Lee, Eran Nevo: On colorings of hypergraphs embeddable in $\mathbb{R}^d$, arXiv
Bibliography: Josef Greilhuber, Carl Schildkraut, Jonathan Tidor: More unit distances in arbitrary norms, arXiv
Bibliography: Isabel McGuigan, Katherine Pan: Bipartite and Euclidean Gallai-Ramsey Theory, arXiv
Bibliography: Maria-Romina Ivan, Imre Leader, Mark Walters: Block Sizes in the Block Sets Conjecture, arXiv
Bibliography: József Balogh, Anton Bernshteyn, Michelle Delcourt, Asaf Ferber, Huy Tuan Pham: Sunflowers in set systems with small VC-dimension, arXiv
Bibliography: Helena Bergold, Stefan Felsner, Meghana M. Reddy, Joachim Orthaber, Manfred Scheucher: Plane Hamiltonian Cycles in Convex Drawings, arXiv
Bibliography:
Minho Cho, Andreas F. Holmsen, Jinha Kim, Minki Kim:
Strong Erdős-Hajnal properties in chordal graphs, arXiv
Bibliography:
Jacob Fox, Janos Pach, Andrew Suk:
A structure theorem for pseudo-segments and its applications, arXiv
Bibliography:
Andreas F. Holmsen:
Helly type problems in convexity spaces, arXiv
Bibliography:
József Balogh, Ethan Patrick White:
Grid-drawings of graphs in three-dimensions, arXiv
Abstract: Lovász proved that any hypergraph containing no two hyperedges with intersection size one admits a proper 2-coloring. This result has several generalizations. One possible generalization of this result is that if we do not require for every pair of hyperedges to have an empty intersection or intersection with size at least two. Directed hypergraphs are hypergraphs in which the vertex set of each hyperedge is partitioned into two parts, a head and a tail. B. Keszegh and D. Pálvölgyi have the following conjecture. Let $H$ be a directed hypergraph such that in every hyperedge the number of head-vertices is less than the number of tail-vertices. Assume that for every pair of hyperedges $E_{1},E_{2}\in E(H)$, if $E_{1}\cap E_{2}=\{v\}$, then $v$ is a head-vertex in at least one of the hyperedges. Then $H$ admits a proper 2-coloring. B. Keszegh showed that the conjecture is true in the special case of 3-uniform hypergraphs. A directed 3-uniform hypergraph such that in every hyperedge the number of head-vertices is one and the number of tail-vertices is two is called $2\rightarrow 1$ hypergraph. In this talk I will prove that the conjecture is also true if every hyperedge has at most one head-vertex and I will talk about other sufficient conditions for $2\rightarrow 1$ hypergraphs to be proper $k$-colorable.
Bibliography:
Jan Kynčl, Jan Soukup:
Extending simple monotone drawings, arXiv
Bibliography:
Matija Bucić, James Davies:
Explicit unit distance graphs with exponential chromatic number and arbitrary girth, arXiv
Bibliography:
David Ellis, Maria-Romina Ivan, Imre Leader:
Turán Densities for Daisies and Hypercubes, arXiv
Bibliography:
Gabriel Currier, Kenneth Moore, Chi Hoi Yip:
Any two-coloring of the plane contains monochromatic 3-term arithmetic progressions, arXiv
Jakob Führer, Géza Tóth:
Progressions in Euclidean Ramsey theory, arXiv
Bibliography:
Petr Hliněný:
Note on $k$-Planar and Min-$k$-Planar Drawings of Graphs, arXiv
Bibliography:
Gerardo L. Maldonado, Miguel Raggi Pérez, Edgardo Roldán-Pensado:
On prescribing total orders for bipartite sets of distances in euclidean plane, arXiv
Bibliography:
Víctor Hugo Almendra-Hernández, Leonardo Martínez-Sandoval:
On prescribing total orders and preorders to pairwise distances of points in Euclidean space, Computational Geometry, Volume 107 (2022) (arXiv)
Bibliography:
Patrick Schnider, Simon Weber:
On the Complexity of Recognizing Nerves of Convex Sets, arXiv
Bibliography:
Helena Bergold, Stefan Felsner, Manfred Scheucher, Felix Schröder, Raphael Steiner:
Topological Drawings meet Classical Theorems from Convex Geometry, arXiv
Bibliography:
David G. Larman, Claude Ambrose Rogers:
The realization of distances within sets in Euclidean space, Mathematika Volume 19 Issue 1 (1972)
Kenneth John Falconer:
The realization of distances in measurable subsets covering $\mathbb{R}^n$, Journal of Combinatorial Theory, Series A Volume 31 Issue 2 (1981)
Bibliography:
Patrizio Angelini, Michael A. Bekos, Franz J. Brandenburg, Giordano Da Lozzo, Giuseppe Di Battista, Walter Didimo, Michael Hoffmann, Giuseppe Liotta, Fabrizio Montecchiani, Ignaz Rutter, Csaba D. Tóth:
Simple $k$-planar graphs are simple $(k+1)$-quasiplanar, Journal of Combinatorial Theory, Series B, Volume 142 (2020)
Bibliography:
Boris Bukh, R. Amzi Jeffs:
Distances between realizations of order types, arXiv
Bibliography:
Jakub Černý:
A simple proof for open cups and caps, European Journal of Combinatorics, Volume 29 Issue 1 (2008)
Bibliography:
Ting-Wei Chao, Hung-Hsun Hans Yu:
Kruskal--Katona-Type Problems via Entropy Method, arXiv
Bibliography:
Karim Adiprasito, Imre Bárány, Nabil H. Mustafa, Tamás Terpai:
Theorems of Carathéodory, Helly, and Tverberg without dimension, arXiv
Bibliography:
Jun Wang, Fei Xue, Chuanming Zong:
Borsuk's Problem in Metric Spaces, arXiv
Bibliography:
Igor Araujo, Simón Piga, Andrew Treglown, Zimu Xiang:
Tiling edge-ordered graphs with monotone paths and other structures, arXiv
Bibliography:
Nikita Chernega, Alexandr Polyanskii, Rinat Sadykov:
Disjoint edges in geometric graphs, Graphs and Combinatorics volume 38, Article number: 162 (2022) (preprint)
Bibliography:
Daniel McGinnis:
A necessary and sufficient condition for (2d−2)-transversals in $\mathbb{R}^{2d}$, arXiv
Shira Zerbib:
Bounds on piercing and line-piercing numbers in families of convex sets in the plane, arXiv
Bibliography:
Maria Axenovich, John Goldwasser, Bernard Lidický, Ryan R. Martin, David Offner, John Talbot, Michael Young:
Polychromatic Colorings on the Integers, arXiv
Abstract: One consequence of Marcus & Tardos's proof of the Furedi-Hajnal/Stanley-Wilf conjecture is that any n-permutation avoiding a specific k-permutation can be sorted with $O_k(n)$ comparisons. However, no algorithms are known to sort such sequences in $O_k(n)$ time. Chalermsook et al. (2014) and Kozma and Saranurak (2019) proved that two specific sorting algorithms run in $O(n 2^{\alpha{O(k)} n})$ time. This time bound reflects a general upper bound on the extremal function of a "light" 0-1 matrix, i.e., one containing exactly one 1 in each column. In this talk I'll prove that sorting takes $n2^{(1+o(1))\alpha}$ time. The light patterns of Chalermsook et al./Kozma-Saranurak are of the form P x HAT, where P is a permutation matrix, "x" is the Kronecker product, and HAT is the 2x3 "hat" pattern with three 1s. This is essentially the tightest possible bound. We also prove that there is a pattern of this form with extremal function $n2^{\alpha(n)}$. Joint work with Parinya Chalermsook and Sorrachai Yingchareonthawornchai
Bibliography:
Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky:
Conflict-Free Colouring of Subsets, arXiv
Abstract: Arya, Fonseca and Mount give a method that yields the approximation of a convex body in $\mathbb{R}^d$ by a polytope with few vertices.
Bibliography:
Sunil Arya, Guilherme Dias da Fonseca, David Mount:
Economical Convex Coverings and Applications, arXiv
Bibliography:
Eduardo Rivera-Campo, Jorge Urrutia:
Convex polygons and separation of convex sets, arXiv
Bibliography:
Matt Gibson-Lopez, Serge Zamarripa:
Optimal Bounds for Weak Consistent Digital Rays in 2D, arXiv
Abstract: I will present a Chaya Keller - Micha A. Perles paper titled "An $(\aleph_0, k+2)$-theorem for $k$-transversals". Their main result is about families of convex sets in $d$-space, where every convex set contains a ball of radius $r$ and contained in a ball of radius $R$. It says that if among every $\aleph_0$ elements, some $k+2$ can be pierced by a $k$-dimensional affine subspace, then the whole family can be pierced by finitely many $k$-dimensional affine subspaces.
Bibliography:
Chaya Keller - Micha A. Perles:
An $(\aleph_0, k+2)$-theorem for $k$-transversals, SoCG 2022
Bibliography:
Csaba Biró, Jenő Lehel, Géza Tóth:
Helly-type theorems for the ordering of the vertices of a hypergraph, arXiv
Bibliography:
Jineon Baek:
On the Erdős-Tuza-Valtr Conjecture, arXiv
Bibliography:
Oded Schramm:
Illumination of sets of constant width, Mathematika 35, 180–189 (1988)
Bibliography:
Florian Frick, R. Amzi Jeffs:
Colorful Words and d-Tverberg Complexes, arXiv
Bibliography:
David Conlon, Yu-Han Wu:
More on lines in Euclidean Ramsey theory, arXiv
Bibliography:
Michael Elkin:
An improved construction of progression-free sets, Israel Journal of Mathematics 184, 93 (2011)
Bibliography:
István Tomon:
Lower bounds for piercing and coloring boxes, arXiv
Bibliography:
Henry L. Fleischmann, Sergei V. Konyagin, Steven J. Miller, Eyvindur A. Palsson, Ethan Pesikoff, Charles Wolf:
Distinct Angles in General Position, arXiv
Bibliography:
Nati Linial, Idan Orzech: Bounds on Unique-Neighbor Codes, arXiv
Bibliography:
Eric Naslund:
Monochromatic Equilateral Triangles in the Unit Distance Graph, arXiv
Abstract: Let \(X\) be a finite point set in \(\mathbb{R}^d\). We introduce the peeling process as follows: in each step, we take our current set (starting with \(X\)), and we remove the vertices of its convex hull from it. How many steps are needed to delete the entire set \(X\)? This is called the layer number of \(X\). Previous studies about layer numbers include determining the layer number of random point sets, and the planar square grid. In this talk, we will study evenly distributed families of sets contained in the unit ball. We determine the sharp lower bound for their layer numbers, and also give an upper bound together with an asymptotically almost matching construction. Joint work with Peter Nielsen and Caledonia Wilson.
Abstract: What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even. If both m and n are odd, the best known construction has \(mn−(m+n)+3\) intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only \(mn−(m+\lceil\frac{n}{6}\rceil)\), for \(m\ge n\). We prove a new upper bound of \(mn−(m+n)+C\) for some constant \(C\), which is optimal apart from the value of \(C\). Joint work with Eyal Ackerman and Günter Rote.
Abstract: We prove that the volume of central hyperplane sections of a unit cube in \(\mathbb{R}^n\) orthogonal to a diameter of the cube is a strictly monotonically increasing function of the dimension for sufficiently large n. Our argument uses the integral formula of Ball for the volume of central sections of the cube, and Laplace's method to estimate the asymptotic behaviour of Ball's integral. This is joint work with Bernardo Gonzales Merino (Murcia, Spain).
At least how long does a permutation have to be if it is to contain all patterns of length \(k\)? At least how long does a word over the alphabet \(\{1,2,\cdots ,n\}\) have to be if it is to contain all permutations as a subsequence. As a factor? These questions are easy to formulate, but surprisingly difficult to answer, even at the level of bounds. It is quite possible that for some of these questions, the best answers will come from constructions of geometric nature. No previous knowledge of the combinatorics of permutations or pattern avoidance will be assumed.
Abstract: The crossing number of a graph \(G\), \(cr(G)\), is the smallest number of edge crossings over all drawings of the graph in the plane. For any \(k\geq 1\), the \(k\)-planar crossing number of \(G\) is defined as the minimum of \(cr(G_1)+cr(G_2)+...+cr(G_k)\), where the edges of \(G\) are partitioned into the graphs \(G_1,G_2,...,G_k\). What is the smallest positive number \(\alpha_k\), such that \(cr_k(G)\leq \alpha_k cr(G)\) holds for every graph \(G\)? Czabarka, Sýkora, Sz, and Vrťo [1] showed \(\alpha_2\leq 3/8\), which is still the best result for \(k=2\). Pach, Sz, Tóth and Tóth [2] estimated \(\alpha_k\) within a multiplicative factor of 2. Now we show that \(\alpha_k=1/k^2 +o(1)\) as \(k\rightarrow\infty\), and furthermore, if we restrict the problem to bipartite graphs, it is {\it exactly} \(1/k^2\). The upper bounds come from randomized algorithms that make use the of the existence of RBIBDs, while the lower bounds utilize the existence of the midrange crossing constant of Pach, Spencer and Tóth [3]. For the lower bound in the bipartite case, we had to extend the existence of the midrange crossing constant from the class of all graphs to other graph classes, including the class of bipartite graphs. Likely there are infinitely many different crossing constants for graph classes. We gave a simple proof to the \(8 \over 9\pi^2\) upper bound on the (ordinary) midrange crossing constant of Pach and Tóth [4] and Pach, Radoičić, Tardos and Tóth [5] using spherical geometry. This is joint work with John Asplund, Éva Czabarka, Gregory Clark, Garner Cochran, Arran Hamm, Josiah Reiswig, Inne Singgih, Gwen Spencer, Libby Taylor and Zhiyu Wang, originating from a Mathematics Research Communities program.
Bibliogaphy:
[1]
Éva Czabarka, Ondřej Sýkora, László Székely and Imrich Vrťo: Biplanar Crossing Numbers II: comparing crossing numbers and biplanar crossing numbers using the probabilistic method, Random Structures and Algorithms 33 (2008), 480--496., pdf
[2]
János Pach, László Székely, Csaba D. Tóth, Géza Tóth: Note on k-planar crossing numbers, Computational Geometry: Theory and Applications 68 (2018), 2--6., pdf
[3]
János Pach, Joel Spencer, Géza Tóth: New bounds on crossing numbers, Discrete and Computational Geometry (2000), 623--624., pdf
[4]
János Pach, Géza Tóth: Graphs drawn with few crossings per edge, Combinatorica 17, 345--354., pdf
[5]
János Pach, Radoš Radoičić, Gábor Tardos, Géza Tóth: Improving the Crossing Lemma by finding more crossings in sparse graphs, Discrete and Computational Geometry 36 (2006), 527--552., pdf
Abstract: We generalize the weak version of the Tverberg theorem to convexity spaces (for which I show some interesting examples). This solves asymptotically an old problem by Calder, Eckhoff and Jamison, improving the earlier quadratic bound by Bukh. The proof is based on a really interesting result of Holmsen and Lee from last year.
Bibliogaphy:
Dömötör Pálvölgyi: Radon numbers grow linearly, arXiv
Abstract: The largest volume ellipsoid contained in a convex body in \(R^d\) is a central object in convex geometry. We study how it can be extended to the space of log-concave functions. As it is ongoing work, we kindly expect the audience to ask questions that we do not have an answer to, yet. Joint work with Grigory Ivanov.
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
Labor day
2019 April 24Abstract: 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.
Spring Break
2019 April 10Abstract: 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.
Bolyai ülés break
2019 March 27Abstract: 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.
Dagstuhl break
2019 February 20Abstract: 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.
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.
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).