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:00 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 12, 2023, Thursday 16:00 (CET).

Márton Naszódi: Higher rank antipodality

Motivated by general probability theory, we say that the set $X$ in $\mathbb{R}^d$ is antipodal of rank $k$, if for any $k+1$ elements $q_1,\ldots q_{k+1}\in X$, there is an affine map from $\mathrm{conv} X$ to the $k$-dimensional simplex $\Delta_k$ that maps $q_1,\ldots q_{k+1}$ onto the $k+1$ vertices of $\Delta_k$. For $k=1$, it coincides with the well-studied notion of (pairwise) antipodality introduced by Klee.
We consider the following natural generalization of Klee's problem on antipodal sets: What is the maximum size of an antipodal set of rank $k$ in $\mathbb{R}^d$? We present a geometric characterization of antipodal sets of rank $k$ and adapting the argument of Danzer and Grünbaum originally developed for the $k=1$ case, we prove an upper bound which is exponential in the dimension. We point out that this problem can be
connected to a classical question in computer science on finding perfect hashes, and it provides a lower bound on the maximum size, which is also exponential in the dimension.
Joint work with Zsombor Szilágyi and Mihály Weiner.

October 19, 2023, Thursday 16:00(CET).

Konrad Swanepoel: Contact graphs of totally separable packings

A packing of translates of a convex body is called separable if any two translates can be separated by a hyperplane that does not intersect the interior of any translate of the packing.  This notion was introduced by Gábor Fejes Tóth and László Fejes Tóth in 1973, and studied mostly by considering the density of such packings.  More recently, Károly Bezdek and others considered the combinatorial properties of the contact graphs of totally separable packings.  In a contact graph of a packing, the vertices are the translates, and two vertices are joined when the two translates touch. We will discuss the maximum degree (Hadwiger number), minimum degree, and total number of edges (contact number) of these graphs. In particular, we completely settle the problem of determining the maximum number of edges of a contact graph of $n$ translates of a convex disc in the plane, for each convex disc. This is joint work with Márton Naszódi.

October 26, 2023, Thursday 16:00(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 2, 2023, Thursday 12.15 (CET) - jointly with the Extremal Set Theory seminar

Andrey Kupavskii (MIPT, Moscow): Spread approximations and forbidden subconfigurations 

In this talk, we discuss a general method to approach a certain class of Turán-type problems, which complements the existing Delta-system method and junta approximation method. We refer to it as the ‘spread approximations method’. The method is based on the notion of r-spread families and builds on the recent breakthrough result of Alweiss, Lovett, Wu and Zhang for the Erdos–Rado Sunflower Conjecture. We will present some of its applications to questions for families of different classes of objects: sets, permutations, partitions, complexes.

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

Friedrich Eisenbrand: Pseudopolynomial time algorithms for integer programming - jointly with the Combinatorics Seminar

November 30, 2023, Thursday 14.15(CET)

Gyula Károlyi:  Old and new applications of the Combinatorial Nullstellensatz in geometry

Abstract: In previous talks at this seminar Zoltán Lóránt Nagy and Péter Maga discussed applications of the Combinatorial Nullstellensatz in graph theory and additive combinatorics. Here we mostly focus on applications in finite and discrete convex geometry. An almost cover of a discrete set of points is a collection of hyperplanes that cover all points except one. After showing the short proofs of some classical results, such as Jamison's theorem and the Alon-Füredi theorem, I will present some new results obtained with Gábor Hegedűs. Beacuse of its relevance, at some point I may make a short detour to additive combinatorics as well. I will also propose some open problems in the hope that some people visiting the Erdős Center will find them appealing.

November 30, 2023, Thursday 16.00(CET)

Balázs Keszegh:  On the number of tangencies among 1-intersecting x-monotone curves

Abstract: Let $\mathcal{C}$ be a set of curves in the plane such that no three curves in $\mathcal{C}$ intersect at a single point and every pair of curves in $\mathcal{C}$ intersect at exactly one point which is either a crossing or a touching point. Janos Pach conjectured that the number of pairs of curves in $\mathcal{C}$ that touch each other is $O(|\mathcal{C}|)$. We prove this conjecture for $x$-monotone curves. Joint work with Eyal Ackerman.

December 7, 2023, Thursday 16.00(CET)

Ji Zeng: On cliques in three-dimensional dense point-line arrangements

Abstract: As a variant of the celebrated Szemerédi--Trotter theorem, Guth and Katz proved that $m$ points and $n$ lines in $\mathbb{R}^3$ with at most $\sqrt{n}$ lines in a common plane must determine at most $O(m^{1/2}n^{3/4})$ incidences for $n^{1/2}\leq m\leq n^{3/2}$. This upper bound is asymptotically tight and has an important application in Erdős distinct distances problem. We characterize the extremal constructions towards the Guth--Katz bound by proving that such a large dense point-line arrangement must contain a $k$-clique in general position provided $m \ll n$. This is an analog of a result by Solymosi for extremal Szemerédi--Trotter constructions in the plane. Joint work with with Andrew Suk.