Zoom Link

The mathematics of origami, or paper folding, raises rich questions in combinatorics and computational geometry, particularly related to flat-foldability: given a crease pattern, represented as a planar graph, and an assignment of mountains and valleys to the creases, can the configuration fold flat? Perhaps surprisingly, this decision problem for “global” flat-foldability is NP-hard in general. In contrast, “local" flat-foldability (folding flat in a small ball around each vertex) can be characterized by a few simple combinatorial conditions.

In this talk, we’ll present a new probabilistic perspective on flat-foldable origami. We consider the uniform distribution on locally flat-foldable crease patterns and a natural Markov chain called the face-flip chain which approximately samples from this distribution. We prove that this chain mixes rapidly for several natural families of origami tessellations---the square twist, the square grid, and the Miura-ori---as well as for the single-vertex crease pattern. We also show that on the square grid, a random locally flat-foldable configuration is exponentially unlikely to be globally flat-foldable. Joint work with Tom Hull and Marcus Michelen.

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

I will introduce the two ideas central to the method of graph containers, pioneered by works of Kleitman--Winston and Sapozhenko. Graph containers are a kind of tool for contour arguments --- for "beating the union bound," so to speak --- finding use in probabilistic combinatorics and statistical physics. We will take as a guiding example Sapozhenko's asymptotic enumeration of the independent sets of the hypercube. Time permitting, I'll discuss some recent variations of the method and some open problems.

Alternating sign matrices are certain {0,1,-1}-matrices known to be equinumerous with plane partitions in the totally symmetric self-complementary symmetry class (TSSCPP), but no meaningful bijection is known. In joint work with Daoji Huang, we give such a bijection in the reduced, 1432-avoiding case, using the bijection of Gao and Huang between reduced bumpless pipe dreams and reduced pipe dreams. In joint work with Mathilde Bouvel and Rebecca Smith, we discuss the related notion of key-avoidance in alternating sign matrices. In joint work with Vincent Holmlund, we transform TSSCPPs to {0,1,-1}-matrices we call magog matrices, and investigate their enumerative and geometric properties.

Zoom Link

Models of preference and ranking aim to capture patterns of ordered structure arising across diverse contexts—from voting and recommendation systems to genetics and sports competitions, yet they often rely on fixed, pre-specified notions of distance between rankings. In practice, however, rankings differ in context-specific ways, suggesting that it is natural to let the data itself guide the choice of distance.  Motivated by this, we study the Mallows model, in which permutations $\pi$ are sampled proportional to $\exp(-\beta d(\pi, \sigma))$, parameterized by a central ranking $\sigma$ and a dispersion parameter $\beta$, where distance function $d$ can be learned from data. 

We analyze a general class of distance metrics based on $L_\alpha$ norms, defined as $d_\alpha(\pi, \sigma) = \sum_{i=1}^n |\pi(i) - \sigma(i)|^\alpha$. For any $\alpha \geq 1$ and $\beta > 0$, we develop a Polynomial-Time Approximation Scheme (PTAS) that achieves two main objectives: (i) approximating the partition function $Z_n(\beta, \alpha)$ within a multiplicative factor of $1 \pm \epsilon$, and (ii) efficiently generating samples that are $\epsilon$-close (in total variation distance) to the true distribution. Leveraging these approximations, we propose a computationally efficient Maximum Likelihood Estimation (MLE) algorithm capable of jointly inferring the central ranking, the dispersion parameter, and the optimal distance metric. We validate our methods empirically on datasets from American College Football and Basketball, demonstrating both theoretical rigor and practical effectiveness.

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