BBC+G Seminar (Budapest Big Combinatorics and Geometry Seminar)

Until the end of 2023, the BBC + G Seminar (Big Budapest Combinatorics + Geometry Seminar) is one of the main seminars of the Special Semester on Discrete Geometry and Convexity at the Erdos Center. Most of the lectures will be on Thursday afternoon (16:15 or 14:15), in the Big Hall of Rényi Institute, and - unless the speaker disagrees - will be recorded. The recordings will be available for the participants on the website:

https://video.renyi.hu/group-2/BBC-G-Seminar/10

Some lectures will be hybrid, that is, they can be followed on zoom. In this case, this will be indicated in the schedule (see below), and the login information is:

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

September 13, 2023, Wednesday 16:00(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 $q_0$ 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.

September 21, 2023, Thursday 14:15(CET), joint with the Combinatorics Seminar.

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 28, 2023, Thursday, 14:15(CET), joint with the Combinatorics Seminar.

Csaba Tóth: Reconfiguration of Polygonal Subdivisions via Recombination EXCEPTIONALLY AT KUTYAS TEREM (DOG ROOM, 3rd floor)

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.

October 5, 2023, Thursday 16:15(CET).

Adrian Dumitrescu:  Which Problem to solve and how to solve it? -- Let the algorithm decide everything!

We revisit the algorithmic problem of finding a triangle in a graph <Triangle Detection>,
and examine its relation to other problems such as <3Sum> and <Independent set>.
We discuss several new algorithms:

(I) An algorithm which given a graph G=(V,E) performs one of the
following tasks in O(m+n) (i.e., linear) time:
(i) compute a Omega(1/sqrt{n})-approximation of <Maximum Independent Set> in G or
(ii) find a triangle in G.

(II) The above result suggests the following broader research direction:
if it is difficult to find (A) or (B) separately, can one find one of the two efficiently?
This motivates the <dual pair> concept we introduce.
We discuss and provide several instances of dual-pair approximation.

(III) We give improved arboricity-sensitive running times for counting and/or detection
of copies of K_l, for small l at least 4.
Our new algorithms are faster than all previous algorithms in certain
high-range arboricity intervals for every l at least 7.

Part of this, like (III) above, is based on joint work with
Andrzej Lingas (Lund University, Sweden)

October 26, 2023, Thursday 16:15(CET).

Piotr Micek: Planarity and dimension

The dimension of a partially ordered set $P$ (poset for short) is the minimum positive integer $d$ such that $P$ is isomorphic to a subposet of $R^d$ with the natural product order. Dimension is arguably the most widely studied measure of complexity of posets and standard examples in posets are the canonical structure forcing dimension to be large. In many ways, dimension for posets is analogous to chromatic number for graphs with standard examples in posets playing the role of cliques in graphs. However, planar graphs have chromatic number at most four, while posets with planar diagrams may have arbitrarily large dimension. The key feature of all known constructions is that large dimension is forced by a large standard example. Since the early 1980s, the question of whether every poset of large dimension and a planar diagram contains a large standard example has been a critical challenge in posets theory with very little progress over the years. More recently, the analogous question has been considered for the broader class of posets with planar cover graphs. We answer both questions in the affirmative by proving that for every poset $P$: (1) if $P$ has a planar diagram, then $dim(P) <= 128 se(P) + 512$, and (2) if $P$ has a planar cover graph, then $dim(P) = O( se^8(P) )$, where $dim(P)$ stands for the dimension of $P$ and $se(P)$ stands for the maximum order of a standard example in $P$. Joint work with Heather Blake, Jędrzej Hodor, Michał Seweryn and
William T. Trotter.

November 9, 2023, Thursday 14:15(CET)

 Friedrich Eisenbrand: TBD