Starting September 2020, this is the joint Budapest Big Combinatorics + Geometry (BBC+G) Seminar of the Geometry Seminar of the Rényi Institute, the GeoScape Research Group and the Lendület Combinatorial Geometry (CoGe) Research Group.

The talks are typically on Friday 2-4 pm, but this can change depending on the time zone of the speaker.

Zoom link for the online lectures: https://zoom.us/j/96029300722 and the password is the first 6 terms from the Fibonacci sequence starting with 11.

The talks are typically on Friday 2-4 pm, but this can change depending on the time zone of the speaker.

Zoom link for the online lectures: https://zoom.us/j/96029300722 and the password is the first 6 terms from the Fibonacci sequence starting with 11.

Recordings of past online talks of the BBC+G Seminar can be watched at the BBC+G video archive.

27-28 May, 2022

2022 Szeged Workshop on Convexity

May 20, 2022, 2 pm (CET)

__
Károly Bezdek: On the separable Tammes problem
__

May 13, 2022, 2 pm (CET)

__
Balázs Keszegh: The number of tangencies between two families of curves
__

May 6, 2022, 2 pm (CET)

__
István Miklós: Fast transformations of Latin squares, half-regular factorizations and edge colorings of bipartite graphs in small steps
__

April 29, 2022, 2 pm (CET)

__
Artem Zvavitch (Kent State University): Volume product and Mahler conjecture for convex bodies
__

April 22, 2022, 3 pm (CET)

__
Manfred Scheucher: Erdős-Szekeres-type problems in the real projective plane
__

April 8, 2022, 2 pm (CET)

__
Xavier Goaoc: No weak epsilon nets for lines and convex sets in space
__

April 1, 2022, 2 pm (CET)

__
Vsevolod Voronov: On the chromatic number of 2-dimensional spheres
__

March 25, 2022, 2 pm (CET)

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

March 18, 2022, 2 pm (CET)

__
Márió Szegedy: Budgeted Steiner Networks: Three Terminals with Equal Path Weights
__

March 11, 2022, 2 pm (CET)

__
Nicolas Bousquet: Fast transformations between colorings
__

March 4, 2022, 2 pm (CET)

__
Imre Bárány: Orientation preserving maps of the n by n grid
__

February 25, 2022, 2 pm (CET)

__
Sophie Spirkl: A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
__

February 18, 2022, 2 pm (CET)

__
Márton Naszódi: Löwner's problem for log-concave functions and beyond __

February 11, 2022, 2 pm (CET)

__
Alexandr Polyanskii: Polynomial plank covering problem
__

2022 Szeged Workshop on Convexity

May 20, 2022, 2 pm (CET)

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

May 13, 2022, 2 pm (CET)

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

Bibliography:

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

May 6, 2022, 2 pm (CET)

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

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

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

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

Bibliography:

Jacobson, M.T., Matthews, P. (1996) Generating uniformly distributed random Latin squares. *Journal of Combinatorial Designs* **4(6)**:404-437.

Aksen, M. Miklós, I., Zhou, K. (2017) Half-regular factorizations of the complete bipartite graph. *Discrete Applied Mathematics* **230**:21-33.

Hong, L. Miklós, I. (2021) A Markov chain on the solution space of edge-colorings of bipartite graphs. https://arxiv.org/abs/2103.11990

April 29, 2022, 2 pm (CET)

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

Bibliography:

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

April 22, 2022, 3 pm (CET)

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

Bibliography:

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

April 8, 2022, 2 pm (CET)

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

Bibliography:

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

April 1, 2022, 2 pm (CET)

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

Bibliography:

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

March 25, 2022, 2 pm (CET)

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

Bibliography:

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

March 18, 2022, 2 pm (CET)

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

Bibliography:

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

March 11, 2022, 2 pm (CET)

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

Bibliography:

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

March 4, 2022, 2 pm (CET)

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

February 25, 2022, 2 pm (CET)

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

Bibliography:

Alvaro Carbonero, Patrick Hompe, Benjamin Moore, Sophie Spirkl:
A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
, arXiv

Marcin Briański, James Davies, Bartosz Walczak:
Separating polynomial χ-boundedness from χ-boundedness
, arXiv

February 18, 2022, 2 pm (CET)

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

February 11, 2022, 2 pm (CET)

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

December 17, 2021, 2 pm (CET)

Lecture dedicated to the memory of Aladár Heppes:

Gábor Fejes Tóth: Remembering Aladár Heppes

December 10, 2021, 2 pm (CET)

Lecture dedicated to the memory of Béla Uhrin:

__
David Conlon: Difference sets in higher dimensions
__

December 3, 2021, 2 pm (CET)
__
Gergely Ambrus: Piercing the chessboard
__

November 26, 2021, 2 pm (CET)
__
Oscar Ortega Moreno: The complex plank problem and Fejes Toth's zone conjecture, revisited.
__

November 19, 2021, 2 pm (CET)
__
Attila Pór: Universal order type of lines/$k$-flats in $R^d$
__

November 12, 2021, 2 pm (CET)
__
Imre Bárány: Pairwise intersecting convex sets and cylinders in $R^3$
__

November 5, 2021, 2 pm (CET)
__
János Barát: Saturated k-plane graphs and k-planar drawings with special emphasis on k=2
__

October 15, 2021, 2 pm (CET)
__
András Bezdek: On colored variants of some two-player games
__

October 8, 2021, 2 pm (CET)
__
Zsolt Lángi: An isoperimetric problem for three-dimensional parallelohedra
__

October 1, 2021

Szeged Geometry Day 2021

September 24, 2021, 2 pm (CET)
__
Dömötör Pálvölgyi: 666-uniform Unit Disk Hypergraphs are 3-colorable
__

September 17, 2021, 2 pm (CET)
__
Alexandr Polyanskii: Colorful Tverberg revisited
__

Lecture dedicated to the memory of Aladár Heppes:

Gábor Fejes Tóth: Remembering Aladár Heppes

December 10, 2021, 2 pm (CET)

Lecture dedicated to the memory of Béla Uhrin:

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

December 3, 2021, 2 pm (CET)

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

November 26, 2021, 2 pm (CET)

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

November 19, 2021, 2 pm (CET)

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

November 12, 2021, 2 pm (CET)

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

November 5, 2021, 2 pm (CET)

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

October 15, 2021, 2 pm (CET)

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

October 8, 2021, 2 pm (CET)

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

October 1, 2021

Szeged Geometry Day 2021

September 24, 2021, 2 pm (CET)

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

Bibliography:

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

September 17, 2021, 2 pm (CET)

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

June 11, 2021, 2 pm (CET)
__
András Bezdek: Separating circles with polygonal tilings
__

June 8, 2021, 1 pm (CET)

Part of the Round the World Relay in Combinatorics:

__
László Lovász: Orthogonal representations and graph limits
__

May 21, 2021, 4 pm (CET)
__
Károly Bezdek: More on contact numbers of unit sphere packings
__

May 14, 2021, 2 pm (CET)
__
Balázs Keszegh: On tangencies among planar curves
__

May 7, 2021, 2 pm (CET)
__
Chaya Keller: On multicolor Ramsey numbers and subset-coloring of hypergraphs
__

April 30, 2021, 2 pm (CET)
__
Imre Bárány: Erdős-Szekeres theorem for k-flats
__

April 16, 2021, 2 pm (CET)
__
Endre Csóka: Upper bounds for the necklace folding problems
__

April 9, 2021

EuroCG 2021

April 2, 2021, 2 pm (CET)
__
Madhu Sudan (Harvard): (Deterministic) Communication Amid Uncertainty
__

March 26, 2021, 2 pm (CET)
__
Pablo Soberón: Quantitative Helly theorems
__

March 19, 2021, 2 pm (CET)
__
Ramon van Handel: Some unusual extremal problems in convexity and combinatorics
__

March 12, 2021

Workshop on Euclidean Ramsey Theory

March 5, 2021, 4 pm (CET)
__
James Davies: Circle graphs are quadratically chi-bounded
__

February 26, 2021, 2 pm (CET)
__
Wolfgang Mulzer: Long Alternating Paths Exist
__

February 19, 2021, 2 pm (CET)
__
Barak Weiss (Tel Aviv University): New bounds on the covering density of lattices
__

February 12, 2021, 2 pm (CET)
__
Sergey Avvakumov: A subexponential size ${\mathbb R}P^n$
__

February 5, 2021, 2 pm (CET)
__
Natan Rubin: Stronger bounds for weak Epsilon-Nets
__

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

June 8, 2021, 1 pm (CET)

Part of the Round the World Relay in Combinatorics:

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

May 21, 2021, 4 pm (CET)

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

May 14, 2021, 2 pm (CET)

Abstract: We prove that there are $O(n)$ tangencies among any set of $n$ red and blue planar curves in which every pair of curves intersects at most once and no two curves of the same color intersect. If every pair of curves may intersect more than once, then it is known that the number of tangencies could be super-linear. However, we show that a linear upper bound still holds if we replace tangencies by pairwise disjoint connecting curves that all intersect a certain face of the arrangement of red and blue curves. The latter result has an application for the following problem studied by Keller, Rok and Smorodinsky [Disc. Comput. Geom. (2020)] in the context of conflict-free coloring of string graphs: what is the minimum number of colors that is always sufficient to color the members of any family of $n$ grounded L-shapes such that among the L-shapes intersected by any L-shape there is one with a unique color? They showed that $O(\log^3 n)$ colors are always sufficient and that $\Omega(\log n)$ colors are sometimes necessary. We improve their upper bound to $O(\log^2 n)$. Joint work with Eyal Ackerman and Dömötör Pálvölgyi.

May 7, 2021, 2 pm (CET)

Abstract: The multicolor hypergraph Ramsey number $R_k(s,r)$ is the minimal n, such that in any k-coloring of all r-element subsets of [n], there is a subset of size s, all whose r-subsets are monochromatic. We present a new "stepping-up lemma" for $R_k(s,r)$: If $R_k(s,r)>n$, then $R_{k+3}(s+1,r+1)>2^n$. Using the lemma, we improve some known lower bounds on multicolor hypergraph Ramsey numbers. Furthermore, given a hypergraph $H=(V,E)$, we consider the Ramsey-like problem of coloring all r-subsets of $V$ such that no hyperedge of size >r is monochromatic. We provide upper and lower bounds on the number of colors necessary in terms of the chromatic number $\chi(H)$. In particular, we show that this number is $O(log^{(r-1)} (r \chi(H)) + r)$, where $log^{(m)}$ denotes m-fold logarithm. Joint work with Bruno Jartoux, Shakhar Smorodinsky, and Yelena Yuditsky.

April 30, 2021, 2 pm (CET)

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

April 16, 2021, 2 pm (CET)

Abstract: A necklace can be considered as a cyclic list of n red and n blue beads in an arbitrary order, and the goal is to fold it into two and find a large cross-free matching of pairs of beads of different colors. We give a counterexample for a conjecture about the necklace folding problem, also known as the separated matching problem. The conjecture (given independently by three sets of authors) states that $\mu = 2/3$ , where µ is the ratio of the ‘covered’ beads to the total number of beads. We refute this conjecture by giving a construction which proves that $\mu \le 2 − \sqrt 2 < 0.5858$. Our construction also applies to the homogeneous model: when we are matching beads of the same color. Moreover, we also consider the problem where the two color classes do not necessarily have the same size. Joint work with Zoltán L. Blázsik, Zoltán Király, Dániel Lenger.

April 9, 2021

EuroCG 2021

April 2, 2021, 2 pm (CET)

Abstract: Most natural communication among humans is characterized by a lack of perfect understanding among the communicating players. Arguably this lack of perfect understanding plays a significant role in the development of human languages, which tend to have bendable rules, ambiguous dictionaries, and seemingly needless redundancies. In this series of works we explore one mathematical question that arises from such communication amid uncertainty. We consider a case of a sender of information attempting to compress information before sending it to the receiver, in a setting where the sender and receiver have moderate, but not perfect, agreement on the distribution from which the message is chosen. In case of perfect agreement, a scheme like Huffman coding would compress the information down to its entropy. What happens with imperfect agreement? We will show some randomized and deterministic schemes that achieve some non-trivial compression. We will mention some intriguing open problems in the deterministic setting (which we believe to be harder and possibly more insightful in this setting). Based on joint works with Elad Haramaty (Technion), Brendan Juba (MIT/Harvard), Adam Kalai (MSR), and Sanjeev Khanna (U.Penn.)

March 26, 2021, 2 pm (CET)

Abstract: Given a family of convex sets in R^d, how do we know that their intersection has a large volume or a large diameter? A large family of results in combinatorial geometry, called Helly-type theorems, characterize families of convex sets whose intersections are not empty. During this talk we will describe how some bootstrapping arguments allow us to extend classic results to describe when the intersection of a family of convex sets in R^d is quantifiably large. The work presented in this talk was done in collaboration with Travis Dillon, Jack Messina, Sherry Sarkar, and Alexander Xue.

March 19, 2021, 2 pm (CET)

Abstract: It is a basic fact of convexity that the volume of convex bodies is a polynomial, whose coefficients (the mixed volumes) contain many familiar geometric parameters as special cases. A deep result of convex geometry, the Alexandrov-Fenchel inequality, states that these coefficients are log-concave. This result proves to have striking connections with other areas of mathematics: for example, the appearance of log-concave sequences in many combinatorial problems may be understood as a consequence of the Alexandrov-Fenchel inequality and its algebraic analogues. There is a long-standing problem surrounding the Alexandrov-Fenchel inequality that has remained open since the original works of Minkowski (1903) and Alexandrov (1937): in what cases is equality attained? In convexity, this question corresponds to the solution of certain unusual isoperimetric problems, whose extremal bodies turn out to be numerous and strikingly bizarre. In combinatorics, an answer to this question would provide nontrivial information on the type of log-concave sequences that can arise in combinatorial applications. In recent work with Y. Shenfeld, we succeeded to settle the equality cases completely in the setting of convex polytopes. I will aim to describe this result, and to illustrate its potential combinatorial implications through a question of Stanley on the combinatorics of partially ordered sets.

March 12, 2021

Workshop on Euclidean Ramsey Theory

March 5, 2021, 4 pm (CET)

Abstract: We prove that the chromatic number of a circle graph with clique number $\omega$ is at most $7 \omega^2$. Joint work with Rose McCarty.

February 26, 2021, 2 pm (CET)

Abstract: Let P be a set of 2n points in convex position, such that n points are colored red and n points are colored blue. A non-crossing alternating path on P of length l is a sequence $p_1, ..., p_l$ of l points from P so that (i) all points are pairwise distinct; (ii) any two consecutive points $p_i, p_{i+1}$ have different colors; and (iii) any two segments $p_i p_{i+1}$ and $p_j p_{j+1}$ have disjoint relative interiors, for $i \ne j$. We show that there is an absolute constant eps > 0, independent of n and of the coloring, such that P always admits a non-crossing alternating path of length at least $(1 + \epsilon)n$. The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least $(1 + \epsilon)n$ points of P. This is a properly colored matching whose segments are pairwise disjoint and intersected by a common line. For both versions, this is the first improvement of the easily obtained lower bound of n by an additive term linear in n. The best known published upper bounds are asymptotically of order $4n/3 + o(n)$. Based on joint work with Pavel Valtr.

February 19, 2021, 2 pm (CET)

Abstract: We obtain new upper bounds on the minimal density of lattice coverings of $R^n$ by dilates of a convex body $K$. We also obtain bounds on the probability (with respect to the natural Haar-Siegel measure on the space of lattices) that a randomly chosen lattice $L$ satisfies $L+K=R^n$. As a step in the proof, we utilize and strengthen results on the discrete Kakeya problem. Joint work with Or Ordentlich and Oded Regev.

February 12, 2021, 2 pm (CET)

Abstract: A practical way to encode a manifold is to triangulate it. Among all possible triangulations it makes sense to look for the minimal one, which for the purpose of this talk means using the least number of vertices. Consider now a family of manifolds such as $S^n$, ${\mathbb R}P^n$, $SO_n$, etc. A natural question is how the size of the minimal triangulation depends on $n$? Surprisingly, except for the trivial case of $S^n$, our best lower and upper bounds are very far apart. For ${\mathbb R}P^n$ the current best lower and upper bounds are around $n^2$ and $\phi^n$, respectively, where $\phi$ is the golden ratio. In this talk I will present the first triangulation of ${\mathbb R}P^n$ with a subexponential, $\sqrt{n}^\sqrt{n}$, number of vertices. I will also state several open problems related to the topic. This is a joint work with Karim Adiprasito and Roman Karasev.

February 5, 2021, 2 pm (CET)

Abstract: Given a finite point set $P$ in $R^d$, and $\epsilon>0$ we say that a point set $N$ in $R^d$ is a weak $\epsilon$-net if it pierces every convex set $K$ with $|K\cap P|\geq \epsilon |P|$. Let $d\geq 3$. We show that for any finite point set in $R^d$, and any $\epsilon>0$, there exists a weak $\epsilon$-net of cardinality $O(1/\epsilon^{d-1/2+\delta})$, where $\delta>0$ is an arbitrary small constant. This is the first improvement of the bound of $O^*(1/\epsilon^d)$ that was obtained in 1994 by Chazelle, Edelsbrunner, Grini, Guibas, Sharir, and Welzl for general point sets in dimension $d\geq 3$.

2020 December 18, 2 pm (CET)
__
Pavel Valtr (Charles University, Prague): On the expected number of holes in random point sets
__

2020 December 11

ICNTDM 2020 (Ramanujan conference)

2020 December 4, 10 am (CET)
__
David Wood (Monash University): Universal Graph Product Structures
__

2020 November 27, 2 pm (CET)
__
Oscar Ortega Moreno (TU Wien): An optimal plank theorem
__

2020 November 20, 2 pm (CET)
__
Jacques Verstraete (UCSD): Extremal problems for geometric hypergraphs
__

2020 November 13, 2 pm (CET)
__
Andrey Kupavskii (MIPT + other): Binary scalar products
__

2020 November 6, 2 pm (CET)
__
Zsolt Lángi (BME, Budapest): A solution to some problems of Conway and Guy on monostable polyhedra
__

2020 October 30, 2 pm (CET)
__
Márton Naszódi (MTA-ELTE CoGe, Budapest): Computing the Covering Radius with an Application to the Lonely Runner Conjecture
__

2020 October 23

National Holiday

2020 October 16, 2 pm (CET)
__
Micha Sharir (Tel Aviv University): Eliminating depth cycles and its relatives
__

2020 October 9, 2 pm (CET)
__
Péter Ágoston (MTA-ELTE CoGe, Budapest): A lower bound on the number of colours needed to nicely colour a sphere
__

2020 October 2, 2 pm (CET)
__
Andreas Holmsen (KAIST): Extensions of the (p,q) theorem
__

2020 September 25, 2 pm (CET)
__
Gábor Damásdi (MTA-ELTE CoGe, Budapest): Odd wheels are not odd-distance graphs
__

2020 September 18, 2 pm (CET)
__
Claude Tardif (Queen's University and Royal Military College of Canada): The chromatic number of the product of 15-chromatic graphs can be 14
__

2020 September 11, 10 am (CET)
__
Xuding Zhu (Zhejiang Normal University, Jinhua): Hedetniemi's conjecture and the Poljak-Rödl function
__

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.

2020 December 11

ICNTDM 2020 (Ramanujan conference)

2020 December 4, 10 am (CET)

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.

2020 November 27, 2 pm (CET)

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.

2020 November 20, 2 pm (CET)

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.

2020 November 13, 2 pm (CET)

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.

2020 November 6, 2 pm (CET)

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.

2020 October 30, 2 pm (CET)

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.

2020 October 23

National Holiday

2020 October 16, 2 pm (CET)

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.

2020 October 9, 2 pm (CET)

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.

2020 October 2, 2 pm (CET)

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.

2020 September 25, 2 pm (CET)

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.

2020 September 18, 2 pm (CET)

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.

2020 September 11, 10 am (CET)

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.

starting from 2020 March 24

During the rest of the semester we have merged our seminar with the Geometry Seminar of the Rényi Institute, which is online Fridays from 2 pm. See the talks there.

2020 March 17

Spring break

2020 March 10
__
Géza Tóth: Crossing numbers, drawings
__

2020 March 3
__
Narmada Varadarajan: Nearly linear monotone paths in edge-ordered graphs
__

2020 February 25
__
Dömötör Pálvölgyi: Hasse diagrams with large chromatic number
__

2020 February 18
__
Sameer Desai: Uniformity of Point Samples in Metric Spaces Using Gap Ratio
__

During the rest of the semester we have merged our seminar with the Geometry Seminar of the Rényi Institute, which is online Fridays from 2 pm. See the talks there.

2020 March 17

Spring break

2020 March 10

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

2020 March 3

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.

2020 February 25

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.

2020 February 18

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.

2019 December 4

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.

2019 November 27

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.

2019 November 20

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.

2019 November 13

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.

2019 November 6

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.

2019 October 30

Fall break

2019 October 23

National holiday

2019 October 16

Gábor Tardos at Academy

2019 October 9

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.

2019 October 2

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

2019 September 25

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

2019 September 18

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

2019 May 15
__
Péter Ágoston: Unit distance graphs, (1,d)-graphs and their application in the Hadwiger-Nelson problem and related problems
__

2019 May 8
__
Balázs Keszegh: Hamiltonicity for convex shape Delaunay and Gabriel graphs
__

2019 May 1
__
Narmada Varadarajan: Polychromatic colorings of bottomless rectangles
__

2019 April 17
__
Sándor Kisfaludi-Bak (TU Eindhoven): How does object fatness impact the complexity of packing in Euclidean space?
__

__
Eyal Ackerman (Haifa): On Partitions of Two-Dimensional Discrete Boxes
__

2019 April 3
__
Dömötör Pálvölgyi: Planar Ramsey graphs
__

2019 March 20
__
Csaba D. Tóth (CSUN): Convex Polygons in Cartesian Products
__

2019 March 13
__
Gábor Damásdi: Triangle areas determined by arrangements of planar lines
__

2019 March 6
__
Géza Tóth: Geometric graphs without many disjoint edges
__

2019 February 27

__
Dömötör Pálvölgyi: Lower bounds for weak epsilon-nets and stair-convexity
__

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.

2019 May 8

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

2019 May 1

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.

2019 April 17

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.

2019 April 3

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.

2019 March 20

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

2019 March 13

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.

2019 March 6

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.

2019 February 27

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.

2018 December 11

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.

2018 December 4

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.

2018 November 27

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.

2018 November 20

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.

2018 November 13

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.

2018 November 6

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.

2018 October 30

Fall break

2018 October 23

National Holiday

2018 October 16

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

2018 October 9

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.

2018 October 2

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.

2018 September 25

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.

2018 September 18

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

2018 May 8
__
Balázs Keszegh: New results about coloring intersection hypergraphs
__

2018 May 1

Holiday

2018 April 24

Cancelled because of Dani Nagy's defense in Északi Tömb 0.100A from 14:30

2018 April 17

More thinking together about unit-distance graphs

2018 April 10
__
Tamás Hubai: The chromatic number of the plane is at least 5
__

2018 April 3

Spring break

2018 March 27
__
Péter Ágoston: Rollercoasters and Caterpillars
__

2018 March 20
__
Dániel Lenger: Conflict-Free Coloring of Intersection Graphs
__

2018 March 13
__
Dániel Korándi (EPFL): On the Turán number of ordered forests
__

2018 March 6
__
Dömötör Pálvölgyi: Hadwiger-Debrunner (p,q)r property
__

2018 February 27
__
Tamás Hubai: Sublinear extensions of polygons
__

2018 February 20
__
Gábor Damásdi (HUJI): Conical partitions of point sets
__

Bibliogaphy:

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

2018 May 1

Holiday

2018 April 24

Cancelled because of Dani Nagy's defense in Északi Tömb 0.100A from 14:30

2018 April 17

More thinking together about unit-distance graphs

2018 April 10

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.

2018 April 3

Spring break

2018 March 27

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.

2018 March 20

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.

2018 March 13

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

2018 March 6

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.

2018 February 27

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

Bibliogaphy:

Yaroslav Shitov: Sublinear extensions of polygons

2018 February 20

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.

2017 December 12
__
Balázs Keszegh: Coloring intersection hypergraphs of pseudo-disks
__

2017 December 5
__
András Csépai: Topological Hyper-Graphs
__

2017 November 28
__
Péter Ágoston: Online Conflict-Free Colouring for Intervals
__

2017 November 21
__
Zoltán Nagy: A proof of the Szemerédi-Trotter theorem by using polynomials
__

2017 November 14
__
Máté Vizer: Density of range capturing hypergraphs
__

2017 November 7

Fall break

2017 October 31

Fall break

2017 October 24
__
Gábor Damásdi (HUJI): Helly-type theorems
__

2017 October 17
__
Radoslav Fulek (IST Austria): The orientable genus and orientable \(Z_2\)-genus are not the same
__

2017 October 10
__
Viktória Földvári: On k-intersecting curves and related problems
__

2017 October 3
__
Tamás Hubai: Obstacle representation of graphs
__

2017 September 26
__
Géza Tóth: Complexity of string graphs
__

2017 September 19
__
Dömötör Pálvölgyi: About small pseudo-disks
__

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

2017 December 5

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.

2017 November 28

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

2017 November 21

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.

2017 November 14

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

2017 November 7

Fall break

2017 October 31

Fall break

2017 October 24

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.

2017 October 17

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

2017 October 10

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.

2017 October 3

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.

2017 September 26

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.

2017 September 19

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