Zoom Link

Fundamentals of statistical mechanics explain that systems in thermal equilibrium spend a greater fraction of their time in states with apparent order because these states have lower energy. This explanation is remarkable, and powerful, because energy is a "local" property of states. While non-equilibrium systems can similarly exhibit order, there can be no property of states analogous to energy that generally explains why it emerges. However, recent experiments suggest that a local property called “rattling” predicts which states are favored, at least for a broad class of non-equilibrium systems.

In this seminar, I will present a simple Markov chain theory of rattling that explains when and why it works. This theory motivates new questions concerning the complexity of the relationship between a Markov chain's transition rates and its stationary distribution. The underlying principle is that, although the stationary distribution is generally a complicated function of the transition rates, in many cases it is closely approximated by a simple function of the exit rates alone. As one example, I will present recent work which establishes this picture for Markov chains with i.i.d. random directed rates, which are generally non-reversible, under certain tail conditions on the rate distribution. (This talk features joint work with Dana Randall and Frank den Hollander.)

Zoom Link

Given a digraph $D$, we say that a set of vertices $Q\subseteq V(D)$ is a quasi-kernel if $Q$ is an independent set and if every vertex of $D$ can be reached from $Q$ by a path of length at most 2.  The Small Quasi-kernel Conjecture of P.L.\ Erd\H{o}s and Sz\'ekely from 1976 states that every $n$-vertex source-free digraph $D$ contains a quasi-kernel of size at most $\frac{1}{2}n$.  Despite being posed nearly 50 years ago, very little is known about this conjecture, with the only non-trivial upper bound of $n-\frac{1}{4}\sqrt{n\log n}$ being proven recently by ourself.  We discuss this result together with a number of other related results and open problems around the Small Quasi-kernel Conjecture.

The theory of combinatorial limits is a rapidly developing area of mathematics, which provides analytic tools to study large combinatorial objects (e.g., graphs representing social networks). These analytic methods have led to new ways to cope with notoriously difficult extremal combinatorics questions and established new links between analysis, combinatorics, ergodic theory, group theory, probability theory and statistics. The theory was also the subject of the 2021 Abel Prize lecture of Lovász entitled "Continuous limits of finite structures".

The course will present basic concepts of the theory of combinatorial limits related to various combinatorial objects such as graphs, permutations, and hypergraphs, and discuss analytic representations of their limits. We will discuss how the theory of combinatorial limits is related to regularity decompositions and how its analytic tools can be applied to various problems in computer science and mathematics, in particular, in extremal combinatorics where Razborov's flag algebra method has led to advances on long-standing open problems (with solutions of the Erdős-Rademacher Problem and the Erdős Pentagon Problem being among the first results obtained using the method). We will demonstrate how the flag algebra arguments can be applied both directly and in a computer-assisted way, including non-asymptotic settings, e.g., to compute particular Ramsey numbers.

Zoom Link

A central tool in additive combinatorics is the "polynomial method," a family of powerful techniques for studying the existence and size of sets satisfying given properties by encoding them in terms of the zeros of certain polynomials, which can then be analyzed from an algebraic perspective.

In this talk, we introduce some iconic classical and modern versions of the polynomial method—including the Combinatorial Nullstellensatz, the Croot-Lev-Pach method, and Dvir's method of multiplicities—from the unified perspective of a new framework based on what we call "shift operators." We show how to take advantage of the many useful properties of these operators to rederive the core results of these existing versions of the polynomial method. We also touch on some novel directions in which these new tools may be fruitfully applied.

Zoom Link

A temporal random geometric graph is a random geometric graph in which all edges are endowed with a uniformly random time-stamp, representing the time of interaction between vertices. In such graphs, paths with increasing time stamps indicate the propagation of information. We determine a threshold for the existence of monotone increasing paths between all pairs of vertices in temporal random geometric graphs. The results reveal that temporal connectivity appears at a significantly larger edge density than simple connectivity of the underlying random geometric graph. This is in contrast with Erdős-Rényi random graphs in which the thresholds for temporal connectivity and simple connectivity are of the same order of magnitude. Our results hold for a family of "soft" random geometric graphs as well as the standard random geometric graph. 

Cluster algebras are certain combinatorially defined algebras that have been shown to relate to a myriad of areas in math and physics. One can define a cluster algebra structure on orientable surfaces where the generators correspond to certain curves on the surface and the relations are given by skein relations. In this talk, we will focus on an extension of this construction to non-orientable surfaces. We will discuss various joint work developing non-orientable analogues of many results from cluster theory. Time permitting, we will define a partitioned quiver associated to the surface, give expansion formulae for the generators, give an algebraic interpretation of the mapping class group and state some enumerative results about these algebras. This will be based on various joint works: one project with Véronique Bazier-Matte and our students: Fenghuan He, Ruiyan Huang, Hanyi Luo; another with Cody Gilbert and McCleary Philbin; and lastly, work in progress with James Hughes.

Zoom Link

Consider the random bipartite Erdos-Renyi graph $\gG(n, m, p)$, where each edge with one vertex in $V_{1}=[n]$ and the other vertex in $V_{2}=[m]$ is connected with probability $p$ with $n \geq m$. For the centered and normalized adjacency matrix $A$, it is well known that the empirical spectral measure of $A$ will converge to the Marchenko-Pastur (MP) distribution. Dumitriu and Zhu proved that almost surely there are no outliers outside the compact support of the MP law when $np = \omega(\log(n))$. In this talk, we consider the critical sparsity regime with $np =O(\log(n))$, where we denote $p = b\log(n)/\sqrt{mn}$, $\kappa = n/m$ for some positive constants $b$ and $\kappa$. We quantitatively characterize the emergence of outlier singular values. When $b > b_{\star}$, there is no outlier outside the bulk; when $b^{\star}< b < b_{\star}$, outlier singular values only appear outside the right edge of the MP law; when $b < b^{\star}$, outliers appear on both sides. Meanwhile, the locations of those outliers are precisely characterized by some function depending on the largest and smallest degrees of the sampled random graph. The thresholds $b^{\star}$ and $b_{\star}$ purely depend on $\kappa$. This is a joint work with Ioana Dumitriu, Haixiao Wang, and Yizhe Zhu.

The theory of combinatorial limits is a rapidly developing area of mathematics, which provides analytic tools to study large combinatorial objects (e.g., graphs representing social networks). These analytic methods have led to new ways to cope with notoriously difficult extremal combinatorics questions and established new links between analysis, combinatorics, ergodic theory, group theory, probability theory and statistics. The theory was also the subject of the 2021 Abel Prize lecture of Lovász entitled "Continuous limits of finite structures".

The course will present basic concepts of the theory of combinatorial limits related to various combinatorial objects such as graphs, permutations, and hypergraphs, and discuss analytic representations of their limits. We will discuss how the theory of combinatorial limits is related to regularity decompositions and how its analytic tools can be applied to various problems in computer science and mathematics, in particular, in extremal combinatorics where Razborov's flag algebra method has led to advances on long-standing open problems (with solutions of the Erdős-Rademacher Problem and the Erdős Pentagon Problem being among the first results obtained using the method). We will demonstrate how the flag algebra arguments can be applied both directly and in a computer-assisted way, including non-asymptotic settings, e.g., to compute particular Ramsey numbers.

The theory of combinatorial limits is a rapidly developing area of mathematics, which provides analytic tools to study large combinatorial objects (e.g., graphs representing social networks). These analytic methods have led to new ways to cope with notoriously difficult extremal combinatorics questions and established new links between analysis, combinatorics, ergodic theory, group theory, probability theory and statistics. The theory was also the subject of the 2021 Abel Prize lecture of Lovász entitled "Continuous limits of finite structures".

The course will present basic concepts of the theory of combinatorial limits related to various combinatorial objects such as graphs, permutations, and hypergraphs, and discuss analytic representations of their limits. We will discuss how the theory of combinatorial limits is related to regularity decompositions and how its analytic tools can be applied to various problems in computer science and mathematics, in particular, in extremal combinatorics where Razborov's flag algebra method has led to advances on long-standing open problems (with solutions of the Erdős-Rademacher Problem and the Erdős Pentagon Problem being among the first results obtained using the method). We will demonstrate how the flag algebra arguments can be applied both directly and in a computer-assisted way, including non-asymptotic settings, e.g., to compute particular Ramsey numbers.

The theory of combinatorial limits is a rapidly developing area of mathematics, which provides analytic tools to study large combinatorial objects (e.g., graphs representing social networks). These analytic methods have led to new ways to cope with notoriously difficult extremal combinatorics questions and established new links between analysis, combinatorics, ergodic theory, group theory, probability theory and statistics. The theory was also the subject of the 2021 Abel Prize lecture of Lovász entitled "Continuous limits of finite structures".

The course will present basic concepts of the theory of combinatorial limits related to various combinatorial objects such as graphs, permutations, and hypergraphs, and discuss analytic representations of their limits. We will discuss how the theory of combinatorial limits is related to regularity decompositions and how its analytic tools can be applied to various problems in computer science and mathematics, in particular, in extremal combinatorics where Razborov's flag algebra method has led to advances on long-standing open problems (with solutions of the Erdős-Rademacher Problem and the Erdős Pentagon Problem being among the first results obtained using the method). We will demonstrate how the flag algebra arguments can be applied both directly and in a computer-assisted way, including non-asymptotic settings, e.g., to compute particular Ramsey numbers.

Zoom Link

The theory of combinatorial limits is a rapidly developing area of mathematics, which provides analytic tools to study large combinatorial objects (e.g., graphs representing social networks). These analytic methods have led to new ways to cope with notoriously difficult extremal combinatorics questions and established new links between analysis, combinatorics, ergodic theory, group theory, probability theory and statistics. The theory was also the subject of the 2021 Abel Prize lecture of Lovász entitled "Continuous limits of finite structures".

The course will present basic concepts of the theory of combinatorial limits related to various combinatorial objects such as graphs, permutations, and hypergraphs, and discuss analytic representations of their limits. We will discuss how the theory of combinatorial limits is related to regularity decompositions and how its analytic tools can be applied to various problems in computer science and mathematics, in particular, in extremal combinatorics where Razborov's flag algebra method has led to advances on long-standing open problems (with solutions of the Erdős-Rademacher Problem and the Erdős Pentagon Problem being among the first results obtained using the method). We will demonstrate how the flag algebra arguments can be applied both directly and in a computer-assisted way, including non-asymptotic settings, e.g., to compute particular Ramsey numbers.

Zoom Link

Zoom Link

The theory of combinatorial limits is a rapidly developing area of mathematics, which provides analytic tools to study large combinatorial objects (e.g., graphs representing social networks). These analytic methods have led to new ways to cope with notoriously difficult extremal combinatorics questions and established new links between analysis, combinatorics, ergodic theory, group theory, probability theory and statistics. The theory was also the subject of the 2021 Abel Prize lecture of Lovász entitled "Continuous limits of finite structures".

The course will present basic concepts of the theory of combinatorial limits related to various combinatorial objects such as graphs, permutations, and hypergraphs, and discuss analytic representations of their limits. We will discuss how the theory of combinatorial limits is related to regularity decompositions and how its analytic tools can be applied to various problems in computer science and mathematics, in particular, in extremal combinatorics where Razborov's flag algebra method has led to advances on long-standing open problems (with solutions of the Erdős-Rademacher Problem and the Erdős Pentagon Problem being among the first results obtained using the method). We will demonstrate how the flag algebra arguments can be applied both directly and in a computer-assisted way, including non-asymptotic settings, e.g., to compute particular Ramsey numbers.

Zoom Link

Zoom Link

Zoom Link

The theory of combinatorial limits is a rapidly developing area of mathematics, which provides analytic tools to study large combinatorial objects (e.g., graphs representing social networks). These analytic methods have led to new ways to cope with notoriously difficult extremal combinatorics questions and established new links between analysis, combinatorics, ergodic theory, group theory, probability theory and statistics. The theory was also the subject of the 2021 Abel Prize lecture of Lovász entitled "Continuous limits of finite structures".

The course will present basic concepts of the theory of combinatorial limits related to various combinatorial objects such as graphs, permutations, and hypergraphs, and discuss analytic representations of their limits. We will discuss how the theory of combinatorial limits is related to regularity decompositions and how its analytic tools can be applied to various problems in computer science and mathematics, in particular, in extremal combinatorics where Razborov's flag algebra method has led to advances on long-standing open problems (with solutions of the Erdős-Rademacher Problem and the Erdős Pentagon Problem being among the first results obtained using the method). We will demonstrate how the flag algebra arguments can be applied both directly and in a computer-assisted way, including non-asymptotic settings, e.g., to compute particular Ramsey numbers.

Zoom Link

The theory of combinatorial limits is a rapidly developing area of mathematics, which provides analytic tools to study large combinatorial objects (e.g., graphs representing social networks). These analytic methods have led to new ways to cope with notoriously difficult extremal combinatorics questions and established new links between analysis, combinatorics, ergodic theory, group theory, probability theory and statistics. The theory was also the subject of the 2021 Abel Prize lecture of Lovász entitled "Continuous limits of finite structures".

The course will present basic concepts of the theory of combinatorial limits related to various combinatorial objects such as graphs, permutations, and hypergraphs, and discuss analytic representations of their limits. We will discuss how the theory of combinatorial limits is related to regularity decompositions and how its analytic tools can be applied to various problems in computer science and mathematics, in particular, in extremal combinatorics where Razborov's flag algebra method has led to advances on long-standing open problems (with solutions of the Erdős-Rademacher Problem and the Erdős Pentagon Problem being among the first results obtained using the method). We will demonstrate how the flag algebra arguments can be applied both directly and in a computer-assisted way, including non-asymptotic settings, e.g., to compute particular Ramsey numbers.

Zoom Link

Zoom Link

Zoom Link

Zoom Link