Tamas Katay (Renyi)
Title: The new Borel LLL of Bernshteyn and Yu II
Time: Wednesday, 21.05.2025, 14:00.
Place: ELTE, D3-211.
Abstract: We will discuss the new proof of the Borel Lovasz Local Lemma by Bernshteyn and Yu.
Mate Geng (ELTE)
Title: The new Borel LLL of Bernshteyn and Yu
Time: Wednesday, 14.05.2025, 14:00.
Place: ELTE, D3-211.
Abstract: We will discuss the new proof of the Borel Lovasz Local Lemma by Bernshteyn and Yu.
Gabor Kun (Renyi and ELTE)
Title: Dichotomy for orderings?
Time: Wednesday, 30.04.2025, 14:00.
Place: ELTE, D3-211.
Abstract: The class NP can be defined by the means of Monadic Second-Order logic going back to Fagin and Feder-Vardi, and also by forbidden expanded substructures (cf. lifts and shadows of Kun and Nešetřil). Consequently, for such problems there is no dichotomy, unlike for CSP's. We prove that ordering problems for graphs defined by finitely many forbidden ordered subgraphs still capture the class NP. In particular, we refute a conjecture of Hell, Mohar and Rafiey that dichotomy holds for this class. On the positive side, we confirm the conjecture of Duffus, Ginn and Rödl that ordering problems defined by one single biconnected ordered graph are NP-complete but for the ordered complete graph. An interesting feature appeared and was noticed several times. For finite sets of biconnected patterns (which may be colored structures or ordered structures) complexity dichotomy holds. A principal tool for obtaining this result is known as the Sparse Incomparability Lemma, a classical result in the theory of homomorphisms of graphs and structures. We prove it here in the setting of ordered graphs as a Temporal Sparse Incomparability Lemma for orderings. Interestingly, our proof involves the Lovász Local Lemma.
Petr Naryshkin (Renyi)
Title: Borel asymptotic dimension for several commuting bounded-to-one
maps.
Time: Wednesday, 23.04.2025, 14:00.
Place: ELTE, D3-211.
Abstract: We prove that several commuting bounded-to-one maps induce a
graph with finite Borel asymptotic dimension. If time permits, we
discuss how this is related to higher rank lattices.
Clark Lyons (Renyi and ELTE)
Title: Borel Families of Games
Time: Wednesday, 26.03.2025, 14:00.
Place: ELTE, D3-211.
Abstract: Just as Borel sets A\subseteq\mathbb{N}^\mathbb{N} can be considered as payoff sets in Gale-Stewart games, Borel sets A\subseteq\mathbb{N}^\mathbb{N}\times X for a Polish space X can be considered as Borel families of games. In such a family of games, the Borel game over each x\in X is determined. But how complicated is the set of x such that player II wins? Can we show that this set always measurable? This can be demonstrated with an unfolding argument, and also through the theory of universally Baire sets.
Anett Kocsis (ELTE)
Title: Universal graphs under homomorphism
Time: Wednesday, 05.03.2025, 14:00.
Place: ELTE, D3-211.
Abstract: We say that a Borel graph $H$ is universal (among some family $\mathcal{G}$ of Borel graphs) if for every $G\in \mathcal{G}$ there is a homomorphism from $G$ to $H$. We prove that the shift graph is universal among Borel graphs generated by a countable-to-one function. We will also see that the graph $G_0$ is not universal among hyperfinite ones. This is joint work with Zoltán Vidnyánszky.
Máté Pálfy (ELTE)
Title: The KPT correspondence
Time: Wednesday, 19.02.2025, 14:00.
Place: ELTE, D3-211.
Abstract: In this talk we will discuss Forte Shinko's proof of the Kechris-Pestov-Todorcevic correspondence. The correspondence says roughly that for a non-archimedean group G the group itself is extremely amenable if and only if it satisfies a Ramsey-like property.
Bertalan Bodor (TU Wien)
Title: Introduction to the world of constraint satisfaction problems
Time: Wednesday, 12.02.2025, 14:00.
Place: ELTE, D3-211.
Abstract: The Constraint Satisfaction Problem, or CSP for short, over a relational structure B (called the template structure) is the decision problem where we are given a finite structure A with the same signature as B and we need to decide whether there exists a homomorphism from A to B. Many well-known computation problems can be described as CSPs in a natural way. Examples are linear equations over finite fields, n-colorability for undirected graphs, and various SAT problems. Using concepts and techniques from universal algebra, Bulatov and Zhuk proved independently that CSPs with finite template satisfy a complexity dichotomy: they are in P or NP-complete. In my talk I will give a brief introduction to some of these techniques and results, and I will also talk about some of the known generalizations and open questions for infinite template structures.
Márton Borbényi (ELTE)
Title: Cycle matroid of a graphing
Time: Wednesday, 04.12.2024, 14:00.
Place: ELTE, D3-211.
Abstract: Lovász defined the cycle matroid of a graphing, generalising the notion from discrete graphs to the measurable setting. We studied different properties of this object, like convergence or duality. In the talk we will mostly talk about independent sets, Choguet integration, Wired Maximal Spanning Forest, extreme points of the base-polytope (all these notions will be defined). We also talk about the measured version of exchange property, and give a new proof of submodularity. This talk will be quite disjoint from the one I gave on Kutszem.
Joint work Kristóf Bérczi, László Lovász, László Márton Tóth.
Petr Naryshkin (Renyi)
Title: Asymptotic dimension
Time: Wednesday, 13-20-27.11.2024, 14:00.
Place: ELTE, D3-211.
Abstract: The problem of characterizing hyperfiniteness has been one of the
central questions in the study of countable Borel equivalence relations.
A few years ago, a breakthrough occurred with the introduction of Borel
asymptotic dimension. This notion allowed the authors to recover all of
the prior results with a simpler proof as well as obtain several new
ones. In this lecture series, we will first develop the basic theory of
Borel asymptotic dimension, then describe how it relates to
hyperfiniteness, and, finally, show how it can be applied in relevant
examples.
Balázs Bursics (ELTE)
Title: Hyperfiniteness on topological Ramsey spaces
Time: Wednesday, 6.11.2024, 14:00.
Place: ELTE, D3-211.
Abstract: A classical result of Mathias and Soare states that every countable Borel equivalence relation on [N]^N is hyperfinite on a pure Ellentuck cube, that is, [A]^N for some A \in [N]^N.
I will present a short combinatorial proof of this statement using the Galvin-Prikry
theorem. Generalizing the main idea of the proof yields an analogous statement for topological Ramsey spaces, the generalizations of the Ellentuck space [N]^N: every countable Borel equivalence relation on a topological Ramsey space is hyperfinite on a Ramsey-positive set.
This is joint work with Zoltán Vidnyánszky.
Konrad Wrobel (Jagiellonian University, Kraków)
Title: Ergodic subgraphs and mcp treeings of Aut(T_p,q)
Time: Wednesday, 6.11.2024, 15:30.
Place: ELTE, D3-211/4-713.
Abstract: Hjorth first demonstrated that the measure equivalence classes of free groups are characterized by treeability in the measure preserving setting.
We generalize this result to the measure class preserving setting, via studying directed treeings with prescribed in degree, out degree and Radon-Nikodym cocycle values. We are thus able to show all nonunimodular groups of the form Aut(T_p,q) are pairwise measure equivalent. This work finds a use even in the unimodular setting to finish the measure equivalence classification of Baumslag-Solitar groups.
A key ingredient of the proof is a refinement of an ergodic subgraph lemma of Tserunyan to retain additional information regarding the so-called Krieger flow which I will describe.
This is joint work with Damien Gaboriau, Antoine Poulin, Anush Tserunyan, and Robin Tucker-Drob.
András Imolay (ELTE) and Boglárka Gehér (ELTE)
Title: An Introduction to Matroid Theory and Submodular Functions on Borel Spaces
Time: Wednesday, 9-16.10.2024, 16:00.
Place: ELTE, D3-211.
Abstract: Recently, Lovász initiated a project aimed at developing the theory of matroid limits, among other things, through their submodular rank functions. Lovász introduced the concept of minorizing measures of submodular set functions on a standard Borel space, which generalizes the matroid independence polytope and makes it a promising candidate for the limit object of matroids.
In my talk, I will present the key concepts of finite matroid theory, with a particular focus on those that extend to the realm of submodular functions on a standard Borel space, exploring the similarities and differences between the finite and infinite cases.
Next week, Bogi Gehér will continue with more details, discussing recent advances and outlining open research questions for future work.
Clark Lyons (Renyi Institute and ELTE)
Title: Separating Descriptive Complexity Classes on Grids
Time: Wednesday, 2.10.2024, 14:00.
Place: ELTE, D4-713.
Abstract: In upcoming joint work with Berlow, Bernshteyn, and Weilacher, we exhibit a locally checkable labeling problem (LCL) on grids which, for any free action of $\mathbb{Z}^2$ on a Polish space $X$ and any Borel probability measure $\mu$ on $X$, admits a $\mu$-measurable solution but does not always admit a Borel solution. This LCL also does not admit a finitary factor of IID solution even though it admits a factor of IID solution. It also provides an example of an LCL which admits computable solutions on computable grids, but does not always admit Baire measurable solutions. The new method used for constructing $\mu$-measurable solutions on grids is "rectangular toast".
Greg Terlov (Renyi Institute and University of North Carolina)
Title: Nonamenable subforests of multi-ended quasi-pmp graphs
Time: Wednesday, 18.09.2024, 14:00.
Place: ELTE, D4-713.
Abstract: In the last thirty years, amenability of probability measure preserving (pmp) Borel actions of countable groups has been well understood, largely due to the theory of cost available for pmp countable Borel equivalence relations. On the other hand, very little is known in the quasi-pmp (measure-class preserving) setting, where cost does not yield desirable results. Moreover, since nonamenable groups, such as F_2, can have free amenable quasi-pmp actions, the behavior in this setting has been regarded as particularly mysterious. In this talk, I will present a construction of a nonamenable subforest of multi-ended quasi-pmp Borel graphs. This, together with a result of Tserunyan and Tucker-Drob, witnesses nonamenablility of quasi-pmp actions, whose orbit equivalence relations admit such graphings. The main technique is a weighted cycle-cutting algorithm, which yields a weight-maximal spanning forest. We also introduce a random version of this forest, which generalizes the Free Minimal Spanning Forest, to capture nonunimodularity in the context of percolation theory. This is a joint work with Ruiyuan Chen and Anush Tserunyan.
Alessandro Codenotti (University of Bologna)
Title: Universal minimal flows of groups of homeomorphisms
Time: Wednesday, 28.08.2024, 14:00.
Place: Renyi, Tondo Room.
Abstract: Every topological group G has an associated universal minimal flow M(G): a compact space on which G acts continuously and minimally and such that every other continuous minimal action of G on a compact space is a factor of the action on M(G). In other words, the action of G on M(G) is the "most complicated" among all continuous minimal G-actions and understanding M(G) for various groups of interest, which are usually Polish, has been a major avenue of research in topological dynamics for the past 30 years. A natural dividing line that emerged is between groups with a metrizable universal minimal flows and those whose universal minimal is not, since there is little hope of understanding M(G) in the latter case. In this talk we will begin with a quick survey of the historical developments regarding the (non)metrizability of universal minimal flows, focussing on groups of the form Homeo(X) for a compact metric space X, and we will then present recent results obtained in joint work with Gianluca Basso and Andrea Vaccaro for the case in which X is a Peano continuum.
Josh Frisch (UCSD)
Title: Automorphism groups of subshifts of low complexity
Time: Thursday, 04.07.2024, 10:30.
Place: Renyi, Tondo Room.
Abstract: A subshift is a symbolic dynamical system system defined by giving a family of forbidden words. In this talk I will discuss a forthcoming result, joint with Forte Shinko, where we show that subshifts with low complexity have surprisingly simple automorphism groups.
Forte Shinko (UC Berkeley)
Title: Equivalence relations classifiable by Polish abelian groups
Time: Thursday, 04.07.2024, 14:00.
Place: Renyi, Tondo Room.
Abstract: A conjecture of Hjorth states that the only countable Borel equivalence relations reducible to orbit equivalence relations of Polish abelian group actions are the hyperfinite ones. This conjecture was recently refuted by Allison, where he showed that every treeable countable Borel equivalence relation reduces to such an orbit equivalence relation. We show that this holds for more general equivalence relations, including all countable Borel equivalence relations. This is joint with Josh Frisch.
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.
ZV
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.
ZV
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.
ZV
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.
2023-24/1.
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