Seminar time: Thursdays 10:20-11:15am.
September 10, 2020: Open
Title: Open
Abstract: Open
September 17, 2020: Igor Pak (UCLA), Unusual time: 2-2:55pm
Title: Counting contingency tables
Abstract: Contingency tables are nonnegative integer matrices with fixed row and column sums. They were introduced in statistics and are now used widely throughout combinatorics and applications — from graphical enumeration to Young tableaux and flow polytopes. Both counting and random generation of contingency tables remains difficult, with many open questions. I will give a broad survey of classical and recent results on the subject, emphasising recent theoretical challenges.
October 1, 2020: Peter Winkler
Title: Permutation Pattern Densities
Abstract: The “pattern density” of a permutation pi in a permutation sigma
is the fraction of subsequences of sigma (written in one-line form) that
are ordered like pi. For example, the density of the pattern “12” in sigma
is the number of pairs i < j with sigma(i) < sigma(j), divided by n choose 2.
What does a typical permutation look like that has one or more
pattern densities fixed? To help answer this we employ limit objects
called “permutons,” together with a variational principle that identifies
the permuton that best represents a given class of permutations.
Joint work with Rick Kenyon, Dan Kral’ and Charles Radin, and
(later) with Chris Coscia and Martin Tassy.
October 8, 2020: Caroline Terry
Title: Speeds of hereditary properties and mutual algebricity
Abstract: A hereditary graph property is a class of finite graphs closed under isomorphism and induced subgraphs. Given a hereditary graph property H, the speed of H is the function which sends an integer n to the number of distinct elements in H with underlying set {1,…,n}. Not just any function can occur as the speed of hereditary graph property. Specifically, there are discrete “jumps” in the possible speeds. Study of these jumps began with work of Scheinerman and Zito in the 90’s, and culminated in a series of papers from the 2000’s by Balogh, Bollob\'{a}s, and Weinreich, in which essentially all possible speeds of a hereditary graph property were characterized. In contrast to this, many aspects of this problem in the hypergraph setting remained unknown. In this talk we present new hypergraph analogues of many of the jumps from the graph setting, specifically those involving the polynomial, exponential, and factorial speeds. The jumps in the factorial range turned out to have surprising connections to the model theoretic notion of mutual algebricity, which we also discuss. This is joint work with Chris Laskowski.
October 15, 2020: Kristina Wicke
Title: On the Colless balance index for rooted binary trees
Abstract: Measures of tree balance play an important role in the analysis of phylogenetic trees. One of the oldest and most popular indices in this regard is the Colless index for rooted binary trees.
In this talk, we focus on its combinatorial properties, in particular, its minimum value and the trees that achieve it. We derive both recursive and closed expressions for this minimum value and highlight a surprising connection between the minimum Colless index and the fractal Blancmange curve. We then fully characterize the trees that achieve this minimum value and introduce a recurrence to count them. After focusing on two extremal classes of trees with minimum Colless index (the maximally balanced trees and the greedy from the bottom trees), we conclude by showing that all trees with minimum Colless index also have minimum Sackin index, another popular balance index (joint work with Tomás M. Coronado, Mareike Fischer, Lina Herbst and Francesc Rosselló).
October 22, 2020: Rob Morris (IMPA)
Title: Flat Littlewood Polynomials Exist
Abstract:
A polynomial $P(z) = \sum_{k=0}^n \eps_k z^k$ is a Littlewood polynomial if $\eps_k \in \{-1,1\}$ for all $k$. Littlewood proved many beautiful theorems about these polynomials over his long life, and in his 1968 monograph he stated several influential conjectures about them. One of the most famous of these was inspired by a question of Erd\H{o}s, who asked in 1957 whether there exist “flat” Littlewood polynomials of degree $n$, that is, such that
$$\delta\sqrt{n} \le |P(z)| \le \Delta\sqrt{n}$$
for all $z \in \mathbb{C}$ with $|z|=1$, for some absolute constants $\Delta > \delta > 0$. In this talk we will describe a proof that flat Littlewood polynomials of degree $n$ exist for all $n \ge 2$. The proof is entirely combinatorial, and uses probabilistic ideas from discrepancy theory.
Joint work with Paul Balister, Béla Bollobás, Julian Sahasrabudhe and Marius Tiba.
October 29, 2020: Sean Eberhard (Cambridge, UK)
Title: The characteristic polynomial of a random matrix
Abstract: Consider an n x n matrix M with independent random +-1 entries. The probability that M is singular is well-studied, and is known to be exponentially small (Kahn–Komlos–Szemeredi). In this talk we make the stronger claim that the characteristic polynomial phi of M is irreducible, and that the Galois group Gal(phi) is at least the alternating group, with high probability. The proof depends on both the extended Riemann hypothesis and the classification of finite simple groups (but if the entries are instead drawn uniformly from {1, …, 210} then we can drop both dependencies). The method is related to recent work of Bary-Soroker–Kozma and Breuillard–Varju in the context of random polynomials, and to work of Maples and Nguyen–Paquette on random matrices mod p.
November 5, 2020: Perla Sousi (Cambridge)
Title: The uniform spanning tree in 4 dimensions
Abstract: A uniform spanning tree of Z^4 can be thought of as the ‘’uniform measure’’ on trees of Z^4. The past of 0 in the uniform spanning tree is the finite component that is disconnected from infinity when 0 is deleted from the tree. We establish the logarithmic corrections to the probabilities that the past contains a path of length n, that it has volume at least n and that it reaches the boundary of the box of side length n around 0. Dimension 4 is the upper critical dimension for this model in the sense that in higher dimensions it exhibits “mean-field” critical behaviour. An important part of our proof is the study of the Newtonian capacity of a loop erased random walk in 4 dimensions. This is joint work with Tom Hutchcroft.
November 12, 2020: Vishesh Jain (Simons Institute for the Theory of Computing)
Title: Singularity of discrete random matrices
Abstract: Let $\xi$ be a discrete random variable, and let $M_n$ be an $n\times n$ random matrix whose entries are independent copies of $\xi$. It has been conjectured that the dominant reason for the singularity of $M_n$ is the event that a row or column of $M_n$ is zero, or that two rows or columns of $M_n$ coincide (up to a sign). In this talk, I will discuss recent progress towards the resolution of this conjecture.
Joint work with Ashwin Sah (MIT) and Mehtaab Sawhney (MIT).
November 19, 2020: Andrew Vander Werf
Title: Random geometric graphs on high–dimensional spheres
Abstract: The random geometric graph model on the unit $d$–sphere, denoted by $\mathcal{G}(n,p,d)$, is defined by independently sampling $n$ points $X_1,…,X_n$ from the uniform distribution on $S^{d-1}$ and placing an edge between any two vertices which are within a fixed distance from each other; $p$ here is the probability that any two of these vertices are close enough to have an edge between them. In this talk we employ techniques from Fourier analysis to give a detailed asymptotic comparison of the probability that a given graph $G$ is contained in $\mathcal{G}(n,p,d)$ to the probability that the same $G$ is contained in the Erd\H{o}s–R\'{e}nyi random graph $\mathcal{G}(n,p)$ as $d\to\infty$ with $n$ and $p$ in a certain range. This is joint work with Elliot Paquette.
November 26, 2020: Thanksgiving
December 3, 2020: Jason Fulman (USC). Unusual time: 11:30-12:25.
Title: Derangements and random matrices over finite fields
Abstract: An element of the symmetric group on n symbols is called a derangement if it has no fixed points, and a classical result in combinatorics and probability is that for n > 1, the proportion of derangements is at least 1/3. A vast generalization was conjectured by Boston and Shalev, stating that for any transitive action of a finite simple group G on a set X of size greater than 1, the proportion of derangements is bounded away from 0 by an absolute constant. This was proved by Fulman and Guralnick, and in this talk we describe how random matrices over finite fields were essential to the proof. We also discuss motivations for the study of derangements.