© 2001-2017 Московский физико-технический институт
(государственный университет)
Лекция профессора П. Тетали
Состоится 2 лекции:
22 июня, Актовый зал ЛК, 17:05 — 18:30 — 1-я лекция.
23 июня, Актовый зал ЛК, 18:30 — 20:00 — 2-я лекция.
Анонсы:
Lecture 1: Discrete Curvature and Applications
Inspired by exciting developments in optimal transport and Riemannian geometry, several independent groups have formulated notions of (Ricci) curvature in discrete spaces. I will mention briefly some of these approaches, results, examples and open problems.
An interesting by-product is the result (obtained jointly with Klartag, Kozma, and Ralli) that the Cheeger inequality — relating the spectral gap to the edge-isoperimetric constant — is tight for the class of abelian Cayley graphs.
Lecture 2: Catalan Shuffles
Catalan numbers arise in many enumerative contexts as the counting sequence of combinatorial structures. In this work, we consider natural Markov chains on some of the realizations of the Catalan sequence, and derive estimates on the mixing time of the corresponding Markov chains.
While our main result is an O(n^2 log n) bound on the mixing time for the random transposition chain on the so-called Dyck paths, we raise several open questions, including the optimality of the above bound.
The novelty in our proof is in establishing a certain negative correlation property among random bases of the Catalan matroid, for which the Dyck paths form the bases.
This is joint work with Damir Yeliussizov (Kazakhstan) and Emma Cohen (Georgia Tech).
