BBC+G Seminar

Organizers: János Pach, Dömötör Pálvölgyi, Géza Tóth

Starting September 2020, this is the joint Budapest Big Combinatorics + Geometry (BBC+G) Seminar of the Geometry Seminar of the Rényi Institute, the ERC Geometric Combinatorics 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: and the password is the first 6 terms from the Fibonacci sequence starting with 11.

2020 Fall Semester - online

2020 December 18, 2 pm (CET)
Andrey Kupavskii (MIPT + other): TBA

Abstract: TBA

2020 December 11
ICNTDM 2020 (Ramanujan conference)

2020 December 4, 10 am (CET)
David Wood (Monash University): TBA

Abstract: TBA

2020 November 27

Abstract: TBA

2020 November 20, 2 pm (CET)
Jacques Verstraete (UCSD): TBA

Abstract: TBA

2020 November 13, 2 pm (CET)
Pavel Valtr (Charles University, Prague): TBA

Abstract: TBA

2020 November 6, 2 pm (CET)
Zsolt Lángi (BME, Budapest): TBA

Abstract: TBA

2020 October 30, 2 pm (CET)
Márton Naszódi (MTA-ELTE CoGe, Budapest): TBA

Abstract: TBA

2020 October 23
National Holiday

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

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)
Péter Ágoston (MTA-ELTE CoGe, Budapest): A lower bound on the number of colours needed to nicely colour a sphere

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)
Andreas Holmsen (KAIST): Extensions of the (p,q) theorem

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)
Gábor Damásdi (MTA-ELTE CoGe, Budapest): Odd wheels are not odd-distance graphs

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)
Claude Tardif (Queen's University and Royal Military College of Canada): The chromatic number of the product of 15-chromatic graphs can be 14

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)
Xuding Zhu (Zhejiang Normal University, Jinhua): Hedetniemi's conjecture and the Poljak-Rödl function

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.