McGill

Descriptive Dynamics and Combinatorics

Seminar

Organizers: Marcin Sabok & Anush Tserunyan

Time: Friday at 14:30 ET (50 minutes + ε)

Place: Zoom meeting https://mcgill.zoom.us/j/87587975637, password: Bo▩▩▩ (the last name of the mathematician whose σ-algebra is generated by open sets)


Upcoming talk

The seminar is on pause and will resume in September.


Past talks

2021 Aug 6 Speaker: Dakota Ihli (University of Illinois Urbana-Champaign)
Title: The group of absolutely continuous homeomorphisms of [0,1] is topologically 2-generated
Abstract

Akhmedov and Cohen recently showed that the homeomorphism group of the interval is generically 2-generated ¶mdash; that is, the generic pair of elements generate a dense subgroup. In this talk we outline the proof of this result, and we show how it may be altered to show the same result for the group of absolutely continuous homeomorphisms of the interval.

Notes
2021 Jul 20 Speaker: Marcin Sabok (McGill University)
Title: On one-ended spanning subforests and treeability of groups, part 8
Abstract

In this part, we finish covering Section 3 of the paper of Conley, Gaboriau, Marks and Tucker-Drob. We will discuss the proof of the fact that any Borel planar graph is measure treeable.

Notes
2021 Jul 9 Speaker: Marcin Sabok (McGill University)
Title: On one-ended spanning subforests and treeability of groups, part 7
Abstract

In this part, we cover the first part of Section 3 of the paper of Conley, Gaboriau, Marks and Tucker-Drob. We will discuss the proof of the fact that any Borel planar graph is measure treeable.

Notes
2021 Jul 2 Speaker: Anush Tserunyan (McGill University)
Title: On one-ended spanning subforests and treeability of groups, part 6: local-global bridges, 2-ended graphs, and
the 1% lemma
Abstract

We will begin the talk by explicitly stating and explaining the local-global bridge lemmas in the pmp setting that were used in various constructions, e.g. to go from nowhere µ-hyperfiniteness to exponential growth. We then discuss properties of 2-ended graphs, maximal hyperfinite connected subrelations, and prove the 1% lemma — a conservation property for µ-nonhyperfiniteness.

Notes
2021 Jun 25 Speaker: Anush Tserunyan (McGill University)
Title: On one-ended spanning subforests and treeability of groups, part 5: the 99% lemma and
the Kaimanovich–Elek theorem
Abstract

We begin by presenting µ-hyperfiniteness of locally finite graphs as almost finiteness (the 99% lemma) and use this to prove a characterization of µ-hyperfiniteness in terms of the isoperimetric constant (the Kaimanovich–Elek theorem).

Notes
2021 Jun 18 Speaker: Anush Tserunyan (McGill University)
Title: On one-ended spanning subforests and treeability of groups, part 4: combining the hyperfinite and superquadratic
growth cases
Abstract

Assuming a characterization of µ-hyperfiniteness in terms of the isoperimetric constant (Kaimanovich–Elek theorem), we explain how nowhere µ-hyperfiniteness implies the existence of a Borel a.e. one-ended spanning subforest.

Notes
2021 Jun 11 Speaker: Jenna Zomback (University of Illinois Urbana-Champaign)
Title: On one-ended spanning subforests and treeability of groups, part 3: one-ended subforests in pmp graphs of
superquadratic growth
Abstract

In the third talk on this paper, we continue to investigate which graphs have a.e. spanning subforests. We prove that any pmp graph of superquadratic growth has an a.e. spanning subforest by demonstrating a sufficient condition for having such a subforest.

Notes and recording
2021 Jun 4 Speaker: Matthew Bowen (McGill University)
Title: On one-ended spanning subforests and treeability of groups, part 2: one-ended subforests in hyperfinite graphs
Abstract

We give a brief introduction to the use of one-ended spanning trees and forests in descriptive graph combinatorics and characterize which hyperfinite locally finite Borel graphs admit a.e. one-ended spanning subforests.

Annotated slides and recording
2021 May 28 Speaker: Ruiyuan (Ronnie) Chen (University of Illinois Urbana-Champaign)
Title: On one-ended spanning subforests and treeability of groups, part 1: introduction
Annotated slides
2021 May 20 Speaker: Nishant Chandgotia (TIFR Bangalore)
Title: About Borel and almost Borel embeddings for d actions
Abstract

Krieger's generator theorem says that all free ergodic measure preserving ℤ actions (under natural entropy constraints) can be modelled by a full shift. Following results by Anush Tserunyan and answering a question by Benjamin Weiss, in a sequence of two papers Mike Hochman noticed that this theorem can be strengthened: He showed that all free homeomorphisms of a Polish space (under entropy constraints) can be Borel embedded into the full shift. In this talk we will discuss some results along this line from a recent paper with Tom Meyerovitch and ongoing work with Spencer Unger.

Slides
2021 Apr 28 Speaker: Sohail Farhangi (Ohio State University)
Title: Connections between van der Corput's Difference Theorem and the Ergodic Hierarchy of Mixing
Abstract

We will begin with an overview of the classical van der Corput Difference Theorem and some of its Hilbertian variants that are useful in Ergodic Theory, including the variant that is used in the proof of Szemeredi's Theorem. We will then briefly review the ergodic hierarchy of mixing and point out the similarities to the existing variants of van der Corput's Theorem. Afterwards, we will state generalizations of the existing variants of van der Corput's Difference Theorem in Hilbert spaces that demonstrate connections to weak mixing, mild mixing, strong mixing, and Bernoulli (this last connection is more delicate than the rest). We will also be able to state a new Hilbertian variant of van der Corput's Difference Theorem corresponding to ergodicity. If time permits, we will state mixing van der Corput Difference Theorems in the context of uniform distribution.

Slides
2021 Apr 21 Speaker: Antoine Poulin (McGill University)
Title: On metrizability of universal minimal flows of homeomorphism groups of manifolds, part 2
Abstract

In these two talks, we will discuss a result by Gutman, Tsankov, and Zucker, where non-metrizability of the universal minimal flow of the homeomorphism groups of high dimensional manifolds is established. The proof uses ingenious technology in the form of the space of maximal connected chains, as well as geometric property inherited from the charts.

Notes
2021 Apr 14 Speaker: Antoine Poulin (McGill University)
Title: On metrizability of universal minimal flows of homeomorphism groups of manifolds, part 1
Abstract

In these two talks, we will discuss a result by Gutman, Tsankov, and Zucker, where non-metrizability of the universal minimal flow of the homeomorphism groups of high dimensional manifolds is established. The proof uses ingenious technology in the form of the space of maximal connected chains, as well as geometric property inherited from the charts.

Notes
2021 Apr 7 Joint with McGill Geometric Group Theory Seminar
Speaker: Joshua Frisch (Caltech)
Title: The ICC property in Random Walks and Dynamics
Abstract

A topological dynamical system (i..e a group acting by homeomorphisms on a compact Hausdorff space) is said to be proximal if for any two points p and q we can simultaneously "push them together" (rigorously, there is a net gn such that limgn(p) = limgn(q)). In his paper introducing the concept of proximality, Glasner noted that whenever ℤ acts proximally, that action will have a fixed point. He termed groups with this fixed point property “strongly amenable”.
  The Poisson Boundary of a random walk on a group is a measure space that corresponds to the space of different asymptotic trajectories that the random walk might take. Given a group G and a probability measure μ on G the Poisson boundary is trivial (i.e. has no non-trivial events) if and only if G supports a bounded mu-harmonic function. A group is Called Choquet Deny if its Poisson Boundary is trivial for every μ.
  In this talk I will discuss work giving an explicit classification of which groups are Choquet Deny, which groups are strongly amenable, and what these mysteriously equivalent classes of groups have to do with the ICC property. I will also discuss why strongly amenable groups can be viewed as strengthening amenability in at least three distinct ways thus proving the name is extremely well deserved.
  This is joint work with Yair Hartman, Omer Tamuz, and Pooya Vahidi Ferdowsi.

2021 Mar 31 Speaker: Sławomir Solecki (Cornell University)
Title: Random continuum and iterated Brownian motion
Abstract

We describe a probabilistic model involving iterated Brownian motion for constructing a random chainable continuum. We show that this random continuum is indecomposable. We use our probabilistic model to define a Wiener-type measure on the space of all chainable continua. This is joint work with Viktor Kiss.

Slides
2021 Mar 24 Speaker: Anton Bernshteyn (Georgia Tech)
Title: Probabilistic tools in continuous combinatorics
Abstract

In this talk I will describe probabilistic tools that can be used to construct continuous solutions to combinatorial problems on zero-dimensional spaces. I will also discuss some applications of these tools. In particular, I will outline an equivalence between certain problems in two seemingly disparate subjects: continuous combinatorics and distributed computing.

Slides
2021 Mar 17 Speaker: Prakash Panangaden (McGill University)
Title: The Logical Characterization of Probabilistic Bisimulation
Abstract

Probabilistic bisimulation is an equivalence relation on the states of a Labelled Markov Process that captures behavioural equivalence. It was introduced by Larsen and Skou in the late 1980s following the definition of bisimulation for nondeterministic transition systems in the 1970s by Park and Milner. I and my coworkers extended the theory to systems with continuous state spaces. In particular we showed that one can characterize bisimulation by a modal logic, which, surprisingly, was much simpler than the logic previously used to characterize probabilistic bisimulation on discrete state spaces. We were able to do this by using ideas from descriptive set theory specifically the concept of smooth equivalence relation and the unique structure theorem for analytic spaces. Later we extended these results to cover simulation as well. Still later this work was extended to MDPs and to metric analogues of bisimulation. I will give an expository talk assuming the audience knows all the relevant measure theory and descriptive set theory but not the computer science concepts like bisimulation. I will use a tablet to give a “chalkboard” talk rather than slides. This is joint work with Josée Desharnais, Abbas Edalat and then later with Josée Desharnais, Radha Jagadeesan and Vineet Gupta and finally with Florence Clerc, Nathanael Fijalkow and Bartek Klin.

2021 Mar 10 Speaker: Shrey Sanadhya (University of Iowa)
Title: Generalized Bratteli Vershik model for substitution on infinite alphabets
Abstract

We consider substitutions on countably infinite alphabets as Borel dynamical system and build their Bratteli-Vershik models. We prove two versions of Rokhlin’s lemma for such substitution dynamical systems. Using the Bratteli-Vershik model we give an explicit formula for a shift-invariant measure (finite and infinite) and provide a criterion for this measure to be ergodic. This is joint work with Sergii Bezuglyi and Palle Jorgensen.

Annotated slides
2021 Mar 3 Speaker: Matthiew Bowen (McGill University)
Title: Descriptive graph combinatorics and the Kechris-Solecki-Todorcevic dichotomy, part 2
Abstract

In this series of two talks, we will give a brief introduction to the field of descriptive graph combinatorics and present a new proof of the Kechris-Solecki-Todorcevic (KST) dichotomy discovered independently by Anton Bernshteyn and Ben Miller. During the first talk we will discuss some key examples and results from this field, including the KST dichotomy and its applications. In the second talk we will go over Anton and Ben's proof in detail.

2021 Feb 24 Speaker: Matthiew Bowen (McGill University)
Title: Descriptive graph combinatorics and the Kechris-Solecki-Todorcevic dichotomy, part 1
Abstract

In this series of two talks, we will give a brief introduction to the field of descriptive graph combinatorics and present a new proof of the Kechris-Solecki-Todorcevic (KST) dichotomy discovered independently by Anton Bernshteyn and Ben Miller. During the first talk we will discuss some key examples and results from this field, including the KST dichotomy and its applications. In the second talk we will go over Anton and Ben's proof in detail.

2021 Feb 17 Speaker: Michael Wolman (Caltech)
Title: Probabilistic Programming Semantics for Name Generation, part 3: the proof
Abstract

In this series of talks we present a probabilistic model for name generation. Specifically, we interpret the nu-calculus, a simply-typed lambda-calculus with name generation, in the category of quasi-Borel spaces, an extension of the category of standard Borel spaces supporting both measure theory and higher-order programming. We prove that this model is fully abstract at first-order types. This is joint work with Marcin Sabok, Sam Staton and Dario Stein.
 In part 3 of this series, we present the proof of full abstraction of the nu-calculus in the category of quasi-Borel spaces. It will be a nice mix of programming language theory and descriptive set theory. On the programming language side, we will use logical relations to construct a normal form for the nu-calculus eliminating private names. On the descriptive set theory side, we will use a pmp action and a pair of Borel-inseparable sets to prove that passing to the normal form is valid in QBS.

2021 Feb 3 Speaker: Michael Wolman (Caltech)
Title: Probabilistic Programming Semantics for Name Generation, part 2
Abstract

In this series of talks we present a probabilistic model for name generation. Specifically, we interpret the nu-calculus, a simply-typed lambda-calculus with name generation, in the category of quasi-Borel spaces, an extension of the category of standard Borel spaces supporting both measure theory and higher-order programming. We prove that this model is fully abstract at first-order types. This is joint work with Marcin Sabok, Sam Staton and Dario Stein.

2021 Jan 26 Speaker: Michael Wolman (Caltech)
Title: Probabilistic Programming Semantics for Name Generation, part 1
Abstract

In this series of talks we present a probabilistic model for name generation. Specifically, we interpret the nu-calculus, a simply-typed lambda-calculus with name generation, in the category of quasi-Borel spaces, an extension of the category of standard Borel spaces supporting both measure theory and higher-order programming. We prove that this model is fully abstract at first-order types. This is joint work with Marcin Sabok, Sam Staton and Dario Stein.