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

Budapest Big Combinatorics + Geometry (BBC+G) Seminar is the main seminar in whose organization our group takes active part.

It was initiated in 2020 as the joint seminar of the Geometry Seminar of the Rényi Institute, the GeoScape Research Group and the Combinatorial Geometry (CoGe) Research Group. See also the official BBC+G Seminar Homepage hosted since 2023 Fall by the Rényi Institute/Erdős Center.
Zoom link for the online lectures: 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.

2023 Fall Semester - every Thursday usually at 16:00 in the Main Lecture Hall of the Rényi Institute

September 28, 2023, 2.15pm (CET)
Csaba Tóth: Reconfiguration of Polygonal Subdivisions via Recombination

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

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

September 21, 2023, 2.15pm (CET)
James Davies: Reuniting $\chi$-boundedness with polynomial $\chi$-boundedness

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

September 13, 2023, 4pm (CET)
Günter Rote: Lattice paths with states, and counting geometric objects via production matrices

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