Borel Combinatorics Seminar

Jan Grebik (UCLA and Masaryk University)

Title: Translational tilings of the plane by a polygonal set

Time: Wednesday, 03.07.2024, 16:00.
Place: Renyi, Tondo Room.
Abstract: Bhattacharya proved that the problem of whether a given finite set F tiles \mathbb{Z}^2 by translations is decidable. He obtained this result by proving that the periodic tiling conjecture (PTC) holds in \mathbb{Z}^2. The analogous question in \mathbb{R}^2 is open even for polygonal sets. Here, the most general result is by Kenyon, who proved that PTC holds for topological disks. In an ongoing work with de Dios Pont, Greenfeld and Madrid, we obtain a structure result about translational tilings by polygonal sets with rational slopes by connecting the ideas from the discrete and continuous case. In the talk I will discuss the main differences between tilings in \mathbb{Z}^2 and \mathbb{R}^2 as well as the main ideas on how to apply the structure theory of Greenfeld and Tao in the continuous setting.

Claudio Agostini (TU Wien)

Title: On Ramsey monoids

Time: Thursday, 16.05.2024, 16:15.
Place: ELTE, D3-306.
Abstract: Many theorems in combinatorics share a very similar structure: ``Let $M$ be monoid acting by endomorphism on a partial semigroup $S$. For each finite coloring of $S$, there are ``nice'' monochromatic subsets $N\subseteq S$''. Notable examples include Carlson’s theorem on variable words, Gowers’ $\mathrm{FIN}_k$ theorem, and Furstenberg-Katznelson's Ramsey Theorem.
In 2019, Solecki isolated the common underlying structure of these theorems into a formal statement, and then, he proved a number of results, showing that the possibility to obtain such a statement depends on the algebraic structure of the monoid and on the existence of certain idempotents in a suitable compact right topological semigroup.
In this talk, I will introduce these different notions and explain the known relations between them and with other algebraic classes of monoids.

Gabor Elek (University of Lancaster)

Title: Uniform Borel Amenability

Time: Thursday, 01.05.2024, 16:15.
Place: ELTE, D3-306.
Abstract: According to the classical result of Ornstein and Weiss, if a countable amenable group has a Borel action on the standard Borel set, then for all quasi-invariant measure mu the associated equivalence relation is mu-hyperfinite. A little bit later Connes-Feldman-Weiss extended this result for arbitrary "amenable actions". In the talk I will introduce uniform Borel amenability. and show how to strengthen the results of Ornstein-Weiss and Connes-Feldman-Weiss in the uniform Borel amenable case. Note that Borel actions of countable amenable groups are uniformly Borel amenable. I will explain all the necessary notions. This is joint work with Adam Timar.

Gabor Kun

Title: Matchings and Equidecompositions

Time: Thursday, 11-18-25.04.2024, 16:15.
Place: ELTE, D3-306.
Abstract: I will talk about measurable equidecompositions, perfect matchings, toasts etc.


Title: Borel Lovasz Local Lemma

Time: Thursday, 04.04.2024, 16:15.
Place: ELTE, D3-306.
Abstract: I will continue the Borel version of the Local Lemma.


Title: Borel Lovasz Local Lemma

Time: Thursday, 21.03.2024, 16:15.
Place: ELTE, D3-306.
Abstract: I will talk about the Borel version of the Local Lemma.

Gabor Kun

Title: Property testing

Time: Thursday, 07.03.2024, 16:15.
Place: ELTE, D3-306.
Abstract: I will talk about hyperfinite sequences of graphs and property testing. This is part of the Measurable Combinatorics 2 course.


Title: An invitation to Borel Polymorphisms

Time: Thursday, 29.02.2024, 16:15.
Place: ELTE, D3-306.
Abstract: I will discuss in some detail why is it hard to solve Borel systems of linear equations over finite fields and the relationship of these results to Borel polymorphisms.

Matt Bowen (Oxford)

Title: Monochromatic products and sums

Time: Thursday, 22.02.2024, 16:00.
Place: ELTE, D3-306.
Abstract: We show that any 2-coloring of the naturals and any finite coloring of the rationals contains many monochromatic sets of the form {x, y, xy, x+y}. This is partially based on joint work with Marcin Sabok.

Petr Naryshkin (Munster)

Title: Borel asymptotic dimension and hyperbolic groups

Time: Thursday, 15.02.2024, 16:00.
Place: ELTE
Abstract: We will give a brief overview of the hyperfiniteness question for orbit equivalence relations and define the Borel asymptotic dimension. We will provide an easy proof of the theorem of Marquis and Sabok, which states that the actions of hyperbolic groups of their Gromov boundaries are hyperfinite. If time permits, we will also explain how the same holds for free topologically amenable actions of free groups. The talk is based on joint works with Andrea Vaccaro.

Clark Lyons (UCLA/Berkeley)

Title: Baire Measurable Matchings in Non-amenable Graphs

Time: 08.02.2024, 16:00.
Place: Renyi Institute, Tondo Room
Abstract: Tutte's theorem provides a necessary and sufficient condition for a finite graph to have a perfect matching. In this talk I will present joint work with Kastner showing that if a locally finite Borel graph satisfies a strengthened form of Tutte's condition, then it has a perfect matching which is Baire measurable. As a consequence, the Schreier graph of a free action of a non-amenable group on a Polish space admits a Baire measurable perfect matching. This is analogous to the result of Csoka and Lippner on factor of IID perfect matchings for non-amenable Cayley graphs.

Felix Weilacher (CMU)

Title: Computable vs. Descriptive Combinatorics of Local Problems

Time: 07.02.2024, 14:00.
Place: Renyi Institute, Tondo Room
Abstract: We consider "local" combinatorial problems on graphs. I.e, problems in which we seek a global labelling of vertices, edges, etc. satisfying some set of local constraints. Typical examples include proper coloring and perfect matching. We are moreover interested in finding solutions which are in some sense "constructive" or "definable". We will focus on two specializations of this: finding Baire measurable solutions for Borel graphs on Polish spaces, and finding computable solutions for computable graphs on the natural numbers. Recent investigations have uncovered a large number of similarities between these two settings, but there are interesting questions about how deep the relationship really is. We will attempt to survey some recent positive and negative results in this direction. Includes joint work with Qian, Bowen, and Conley.


09.13. ZV: On a theorem of Bourgain-Fremlin-Talagrand
09.20. ZV: On a theorem of Bourgain-Fremlin-Talagrand
09.27. ZV: On a theorem of Bourgain-Fremlin-Talagrand
10.04. Anett Kocsis: On a note of Weilacher
10.11. Anett Kocsis: On a note of Weilacher
10.18. Balázs Bursics: Borel boundedness
10.25. Balázs Bursics: Borel boundedness
11.08. Máté Pálfy: Cost
11.15. Máté Pálfy: Cost
11.22. Máté Pálfy: Cost
11.28. Donát Pigler: Martin's Conjecture
12.06. Julia Millhouse (Vienna): A minimal counterexample to a uniform strengthening of Ramsey's Theorem
12.13. Donát Pigler: Martin's Conjecture
12.20. Jonathan Schilhan (Leeds): A geometric condition for Dependent Choice