Combinatorics, Physics and Probability Seminar

03/29/2022 9:00 am - 10:00 am

During the 2021–22 academic year, the CMSA will be hosting a seminar on Combinatorics, Physics and Probability, organized by Matteo Parisi and Michael Simkin. This seminar will take place on Tuesdays at 9:00 am – 10:00 am (Boston time). The meetings will take place virtually on Zoom. To learn how to attend, please fill out this form, or contact the organizers Matteo (mparisi@cmsa.fas.harvard.edu) and Michael (msimkin@cmsa.fas.harvard.edu).

The schedule below will be updated as talks are confirmed.

Spring 2022

Date Speaker Title/Abstract
1/25/2022
*note special time 9:00–10:00 AM ET
Jacob Bourjaily (Penn State University, Eberly College of Science Title: Adventures in Perturbation Theory

Abstract: Recent years have seen tremendous advances in our understanding of perturbative quantum field theory—fueled largely by discoveries (and eventual explanations and exploitation) of shocking simplicity in the mathematical form of the predictions made for experiment. Among the most important frontiers in this progress is the understanding of loop amplitudes—their mathematical form, underlying geometric structure, and how best to manifest the physical properties of finite observables in general quantum field theories. This work is motivated in part by the desire to simplify the difficult work of doing Feynman integrals. I review some of the examples of this progress, and describe some ongoing efforts to recast perturbation theory in terms that expose as much simplicity (and as much physics) as possible.

2/3/2022 Ran Tessler
(Weizmann Institute of Science)
Title: The Amplituhedron BCFW Triangulation

Abstract:  The (tree) amplituhedron was introduced in 2013 by Arkani-Hamed and Trnka in their study of N=4 SYM scattering amplitudes. A central conjecture in the field was to prove that the m=4 amplituhedron is triangulated by the images of certain positroid cells, called the BCFW cells. In this talk I will describe a resolution of this conjecture. The seminar is based on a recent joint work with Chaim Even-Zohar and Tsviqa Lakrec.

2/8/2022 Anna Seigal (Harvard) Title: Invariant theory for maximum likelihood estimation

Abstract:  I will talk about work to uncover connections between invariant theory and maximum likelihood estimation. I will describe how norm minimization over a torus orbit is equivalent to maximum likelihood estimation in log-linear models. We will see the role played by polytopes and discuss connections to scaling algorithms. Based on joint work with Carlos Améndola, Kathlén Kohn, and Philipp Reichenbach.

2/15/2022 Igor Balla, Hebrew University of Jerusalem Title: Equiangular lines and regular graphs

Abstract: In 1973, Lemmens and Seidel asked to determine N_alpha(r), the maximum number of equiangular lines in R^r with common angle arccos(alpha). Recently, this problem has been almost completely settled when r is exponentially large relative to 1/alpha, with the approach both relying on Ramsey’s theorem, as well as being limited by it. In this talk, we will show how orthogonal projections of matrices with respect to the Frobenius inner product can be used to overcome this limitation, thereby obtaining significantly improved upper bounds on N_alpha(r) when r is polynomial in 1/alpha. In particular, our results imply that N_alpha(r) = Theta(r) for alpha >= Omega(1 / r^1/5).

Our projection method generalizes to complex equiangular lines in C^r, which may be of independent interest in quantum theory. Applying this method also allows us to obtain
the first universal bound on the maximum number of complex equiangular lines in C^r with common Hermitian angle arccos(alpha), an extension of the Alon-Boppana theorem to dense regular graphs, which is tight for strongly regular graphs corresponding to r(r+1)/2 equiangular lines in R^r, an improvement to Welch’s bound in coding theory.

Fall 2021

Date Speaker Title/Abstract
9/21/2021 Nima Arkani-Hamed
IAS (Institute for Advanced Study), School of Natural Sciences
Title: Surfacehedra and the Binary Positive Geometry of Particle and “String” Amplitudes
9/28/2021 Melissa Sherman-Bennett
University of Michigan, Department of Mathematics
Title: The hypersimplex and the m=2 amplituhedron

Abstract: I’ll discuss a curious correspondence between the m=2 amplituhedron, a 2k-dimensional subset of Gr(k, k+2), and the hypersimplex, an (n-1)-dimensional polytope in R^n. The amplituhedron and hypersimplex are both images of the totally nonnegative Grassmannian under some map (the amplituhedron map and the moment map, respectively), but are different dimensions and live in very different ambient spaces. I’ll talk about joint work with Matteo Parisi and Lauren Williams in which we give a bijection between decompositions of the amplituhedron and decompositions of the hypersimplex (originally conjectured by Lukowski–Parisi–Williams). Along the way, we prove the sign-flip description of the m=2 amplituhedron conjectured by Arkani-Hamed–Thomas–Trnka and give a new decomposition of the m=2 amplituhedron into Eulerian-number-many chambers (inspired by an analogous hypersimplex decomposition).

10/5/2021 Daniel Cizma, Hebrew University Title: Geodesic Geometry on Graphs

Abstract: In a graph G = (V, E) we consider a system of paths S so that for every two vertices u,v in V there is a unique uv path in S connecting them. The path system is said to be consistent if it is closed under taking subpaths, i.e. if P is a path in S then any subpath of P is also in S. Every positive weight function w: E–>R^+ gives rise to a consistent path system in G by taking the paths in S to be geodesics w.r.t. w. In this case, we say w induces S. We say a graph G is metrizable if every consistent path system in G is induced by some such w.

We’ll discuss the concept of graph metrizability, and, in particular, we’ll see that while metrizability is a rare property, there exists infinitely many 2-connected metrizable graphs.

Joint work with Nati Linial.

10/12/2021 Lisa Sauermann, MIT Title: On counting algebraically defined graphs

Abstract: For many classes of graphs that arise naturally in discrete geometry (for example intersection graphs of segments or disks in the plane), the edges of these graphs can be defined algebraically using the signs of a finite list of fixed polynomials. We investigate the number of n-vertex graphs in such an algebraically defined class of graphs. Warren’s theorem (a variant of a theorem of Milnor and Thom) implies upper bounds for the number of n-vertex graphs in such graph classes, but all the previously known lower bounds were obtained from ad hoc constructions for very specific classes. We prove a general theorem giving a lower bound for this number (under some reasonable assumptions on the fixed list of polynomials), and this lower bound essentially matches the upper bound from Warren’s theorem.

10/19/2021 Pavel Galashin
UCLA, Department of Mathematics
Title: Ising model, total positivity, and criticality

Abstract: The Ising model, introduced in 1920, is one of the most well-studied models in statistical mechanics. It is known to undergo a phase transition at critical temperature, and has attracted considerable interest over the last two decades due to special properties of its scaling limit at criticality.
The totally nonnegative Grassmannian is a subset of the real Grassmannian introduced by Postnikov in 2006. It arises naturally in Lusztig’s theory of total positivity and canonical bases, and is closely related to cluster algebras and scattering amplitudes.
I will give some background on the above objects and then explain a precise relationship between the planar Ising model and the totally nonnegative Grassmannian, obtained in our recent work with P. Pylyavskyy. Building on this connection, I will give a new boundary correlation formula for the critical Ising model.

10/26/2021 Candida Bowtell, University of Oxford Title: The n-queens problem

Abstract: The n-queens problem asks how many ways there are to place n queens on an n x n chessboard so that no two queens can attack one another, and the toroidal n-queens problem asks the same question where the board is considered on the surface of a torus. Let Q(n) denote the number of n-queens configurations on the classical board and T(n) the number of toroidal n-queens configurations. The toroidal problem was first studied in 1918 by Pólya who showed that T(n)>0 if and only if n is not divisible by 2 or 3. Much more recently Luria showed that T(n) is at most ((1+o(1))ne^{-3})^n and conjectured equality when n is not divisible by 2 or 3. We prove this conjecture, prior to which no non-trivial lower bounds were known to hold for all (sufficiently large) n not divisible by 2 or 3. We also show that Q(n) is at least ((1+o(1))ne^{-3})^n for all natural numbers n which was independently proved by Luria and Simkin and, combined with our toroidal result, completely settles a conjecture of Rivin, Vardi and Zimmerman regarding both Q(n) and T(n).

In this talk we’ll discuss our methods used to prove these results. A crucial element of this is translating the problem to one of counting matchings in a 4-partite 4-uniform hypergraph. Our strategy combines a random greedy algorithm to count `almost’ configurations with a complex absorbing strategy that uses ideas from the methods of randomised algebraic construction and iterative absorption.

This is joint work with Peter Keevash.

11/9/2021 Steven Karp
Universite du Quebec a Montreal, LaCIM (Laboratoire de combinatoire et d’informatique mathématique)
Title: Gradient flows on totally nonnegative flag varieties

Abstract: One can view a partial flag variety in C^n as an adjoint orbit inside the Lie algebra of n x n skew-Hermitian matrices. We use the orbit context to study the totally nonnegative part of a partial flag variety from an algebraic, geometric, and dynamical perspective. We classify gradient flows on adjoint orbits in various metrics which are compatible with total positivity. As applications, we show how the classical Toda flow fits into this framework, and prove that a new family of amplituhedra are homeomorphic to closed balls. This is joint work with Anthony Bloch.
11/16/2021
*note special time 12:30–1:30 ET*
Yinon Spinka (University of British Columbia) Title: A tale of two balloons

Abstract: From each point of a Poisson point process start growing a balloon at rate 1. When two balloons touch, they pop and disappear. Will balloons reach the origin infinitely often or not? We answer this question for various underlying spaces. En route we find a new(ish) 0-1 law, and generalize bounds on independent sets that are factors of IID on trees.
Joint work with Omer Angel and Gourab Ray.

11/23/2021 Lutz Warnke (UC San Diego) Title: Prague dimension of random graphs

Abstract: The Prague dimension of graphs was introduced by Nesetril, Pultr and Rodl in the 1970s: as a combinatorial measure of complexity, it is closely related to clique edges coverings and partitions. Proving a conjecture of Furedi and Kantor, we show that the Prague dimension of the binomial random graph is typically of order n/(log n) for constant edge-probabilities. The main new proof ingredient is a Pippenger-Spencer type edge-coloring result for random hypergraphs with large uniformities, i.e., edges of size O(log n).

11/30/2021 Karel Devriendt (University of Oxford) Title: Resistance curvature – a new discrete curvature on graphs

Abstract: The last few decades have seen a surge of interest in building towards a theory of discrete curvature that attempts to translate the key properties of curvature in differential geometry to the setting of discrete objects and spaces. In the case of graphs there have been several successful proposals, for instance by Lin-Lu-Yau, Forman and Ollivier, that replicate important curvature theorems and have inspired applications in a variety of practical settings.
In this talk, I will introduce a new notion of discrete curvature on graphs, which we call the resistance curvature, and discuss some of its basic properties. The resistance curvature is defined based on the concept of effective resistance which is a metric between the vertices of a graph and has many other properties such as a close relation to random spanning trees. The rich theory of these effective resistances allows to study the resistance curvature in great detail; I will for instance show that “Lin-Lu-Yau >= resistance >= Forman curvature” in a specific sense, show strong evidence that the resistance curvature converges to zero in expectation for Euclidean random graphs, and give a connectivity theorem for positively curved graphs. The resistance curvature also has a naturally associated discrete Ricci flow which is a gradient flow and has a closed-form solution in the case of vertex-transitive and path graphs.
Finally, if time permits I will draw a connection with the geometry of hyperacute simplices, following the work of Miroslav Fiedler.
This work was done in collaboration with Renaud Lambiotte.

12/7/2021 Matthew Jenssen (University of Birmingham) Title: The singularity probability of random symmetric matrices

Abstract: Let M_n be drawn uniformly from all n by n symmetric matrices with entries in {-1,1}. In this talk I’ll consider the following basic question: what is the probability that M_n is singular? I’ll discuss recent joint work with Marcelo Campos, Marcus Michelen and Julian Sahasrabudhe where we show that this probability is exponentially small. I hope to make the talk accessible to a fairly general audience.

12/14/2021 Stefan Glock (ETH Zurich) Title: The longest induced path in a sparse random graph

Abstract: A long-standing problem in random graph theory has been to determine asymptotically the length of a longest induced path in sparse random graphs. Independent work of Luczak and Suen from the 90s showed the existence of an induced path of roughly half the optimal size, which seems to be a barrier for certain natural approaches. Recently, in joint work with Draganic and Krivelevich, we solved this problem. In the talk, I will discuss the history of the problem and give an overview of the proof.

12/21/2021
01/25/2022 Jacob Bourjaily
Penn State University, Department of Physics