Discrete Analysis Seminar

The simple random walk on the \(n\)-dimensional hypercube mixes to the uniform distribution once every coordinate is touched at least once, which happens in \(O(n \log n)\) time. However, analyzing mixing times of random walks for sampling from distributions on the hypercube even with mild correlations across coordinates is a lot trickier. In recent years, techniques based on high-dimensional expansion have been successful in analyzing such random walks in the context of sampling bases in a matroid, independent sets and colorings in graphs, and the Gibbs distributions of various Ising models. We will discuss this paper of Chen and Eldan, which presents a clean generalization of the high-dimensional expansion framework, and establishes "local-to-global" theorems for objects beyond simplicial complexes. In particular, we will go over their framework, a proof of their local-to-global theorem, and some examples.

This is a continuation of last week's talk.

The condition number \(\kappa(M) = \|M\|\|M^{-1}\|\) of a matrix \(M\) is important in numerical linear algebra. Under mild assumptions, Tao and Vu proved that \(\kappa(M)\) can be regularized (i.e., made to be only polynomially large) by adding a random sparse matrix. I will go over their proof.

This is a continuation of last week's talk.

Quantum ergodicity states that eigenfunctions for a regular graph are delocalized in that the average of any vertex function under the probability distribution from an eigenfunction is typically near the function's uniform average. It was initially proved by Anantharaman and Le Masson, and Anantharaman later gave three additional proofs. We will discuss one of those subsequent proofs.

If a directed hypercube satisfies the property that every subface has a unique sink (a node with only incoming edges), then it is called a unique sink orientation (USO). Given a USO, being able to find the global sink efficiently would imply efficient algorithms for many problems in optimization, linear programming and the theory of games. While there are no known polynomial-time classical algorithms for this problem, Bacon showed that there is an efficient quantum algorithm if one is able to solve a self-contained discrete math problem. After a brief overview of quantum algorithms and the structure of USOs, we will go over the missing piece and the implied quantum algorithm.

A well-known result in spectral graph theory is Cheeger's inequality, which gives bounds on the conductance of a graph in terms of the first non-trivial eigenvalue of the normalized Laplacian. To prove the upper bound of Cheeger's inequality, we consider spectral partitions, a partition of the vertices based on the first non-trivial eigenvector. Kwok et. al. improve on Cheeger's inequality by showing such spectral partitions satisfy an upper bound dependent on higher order spectral gaps. Kwok et. al. provide two proofs of their theorem; we will give a brief overview of Cheeger's inequality, then discuss the first proof in detail and the general idea of the second.

The Erdős-Rényi model of random graphs exhibits a phase transition in which a giant component emerges. At criticality, there are many big (but not giant) components. The sizes of these components can be described, in the limit, by a random process which at first seems entirely unrelated: the sequence of excursions of a reflected drifting brownian motion. We will explore this connection and provide some intuition for the proof.

This time, we will go through the details of the proof.

No, obviously. But making an analogy between graphs and manifolds turns out to be surprisingly fruitful. In particular, we can define a few notions of “curvature” of a graph that posses some of the nice qualities of the curvature of a Riemannian manifold. We will discuss the relationship between the curvature of a graph and various combinatorial properties, like it's diameter mixing time, cutoff, and expansion.