Seminars and Colloquia by Series

The differential equation method in Banach spaces and the n-queens problem

Series
Combinatorics Seminar
Time
Friday, January 29, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke
Speaker
Michael Simkin

The differential equation method is a powerful tool used to study the evolution of random combinatorial processes. By showing that the process is likely to follow the trajectory of an ODE, one can study the deterministic ODE rather than the random process directly. We extend this method to ODEs in infinite-dimensional Banach spaces.
We apply this tool to the classical n-queens problem: Let Q(n) be the number of placements of n non-attacking chess queens on an n x n board. Consider the following random process: Begin with an empty board. For as long as possible choose, uniformly at random, a space with no queens in its row, column, or either diagonal, and place on it a queen. We associate the process with an abstract ODE. By analyzing the ODE we conclude that the process almost succeeds in placing n queens on the board. Furthermore, we can obtain a complete n-queens placement by making only a few changes to the board. By counting the number of choices available at each step we conclude that Q(n) \geq (n/C)^n, for a constant C>0 associated with the ODE. This is optimal up to the value of C.

Based on joint work with Zur Luria.

Prime gaps, probabilistic models and the Hardy-Littlewood conjectures

Series
Combinatorics Seminar
Time
Friday, January 22, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Kevin FordThe University of Illinois at Urbana-Champaign

Motivated by a new probabilistic interpretation of the Hardy-Littlewood k-tuples conjectures, we introduce a new probabilistic model of the primes and make a new conjecture about the largest gaps between the primes below x.  Our bound depends on a property of the interval sieve which is not well understood.  We also show that any sequence of integers which satisfies a sufficiently uniform version of the Hardy-Littlewood conjectures must have large gaps of a specific size.  This work is joint with Bill Banks and Terry Tao.

Large deviations of the greedy independent set algorithm on sparse random graphs

Series
Combinatorics Seminar
Time
Friday, January 15, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Brett KolesnikUniversity of California, Berkeley

We study the greedy independent set algorithm on sparse Erdős-Rényi random graphs G(n,c/n). This range of p is of interest due to the threshold at c=e, beyond which it appears that greedy algorithms are affected by a sudden change in the independent set landscape. A large deviation principle was recently established by Bermolen et al. (2020), however, the proof and rate function are somewhat involved. Upper bounds for the rate function were obtained earlier by Pittel (1982). By discrete calculus, we identify the optimal trajectory realizing a given large deviation and obtain the rate function in a simple closed form. In particular, we show that Pittel's bounds are sharp. The proof is brief and elementary. We think the methods presented here will be useful in analyzing the tail behavior of other random growth and exploration processes.

Based on https://arxiv.org/abs/2011.04613

Flip processes on finite graphs and dynamical systems they induce on graphons

Series
Combinatorics Seminar
Time
Friday, December 11, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Jan HladkyCzech Academy of Sciences

We introduce a class of random graph processes, which we call flip processes. Each such process is given by a rule which is just a function $\mathcal{R}:\mathcal{H}_k\rightarrow \mathcal{H}_k$ from all labelled $k$-vertex graphs into itself ($k$ is fixed). Now, the process starts with a given $n$-vertex graph $G_0$. In each step, the graph $G_i$ is obtained by sampling $k$ random vertices $v_1,\ldots,v_k$ of $G_{i-1}$ and replacing the induced graph $G_{i-1}[v_1,\ldots,v_k]$ by $\mathcal{R}(G_{i-1}[v_1,\ldots,v_k])$. This class contains several previously studied processes including the Erdos-Renyi random graph process and the random triangle removal.

Given a flip processes with a rule $\mathcal{R}$ we construct time-indexed trajectories $\Phi:\mathcal{W}\times [0,\infty)\rightarrow\mathcal{W}$ in the space of graphons. We prove that with high probability, starting with a large finite graph $G_0$ which is close to a graphon $W_0$, the flip process will follow the trajectory $(\Phi(W_0,t))_{t=0}^\infty$ (with appropriate rescaling of the time).

These graphon trajectories are then studied from the perspective of dynamical systems. We prove that two trajectories cannot form a confluence, give an example of a process with an oscilatory trajectory, and study stability and instability of fixed points.

Joint work with Frederik Garbe, Matas Sileikis and Fiona Skerman.

Universality of Random Permutations

Series
Combinatorics Seminar
Time
Friday, December 4, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Xiaoyu HeStanford University

It is a classical fact that for any c > 0, a random permutation of length n = (1+c)k^2/4 typically contains a monotone subsequence of length k. As a far-reaching generalization, Alon conjectured that for this same n, a typical n-permutation is k-universal, meaning that it simultaneously contains every k-pattern. He also gave a simple proof for the fact that if n is increased to Ck^2 log k, then a typical n-permutation is k-universal. Our main result is that the same statement holds for n = Ck^2 log log k, getting almost all of the way to Alon's conjecture.

In this talk we give an overview of the structure-vs-randomness paradigm which is a key ingredient in the proof, and a sketch of the other main ideas. Based on joint work with Matthew Kwan.

Counting integer partitions with the method of maximum entropy

Series
Combinatorics Seminar
Time
Friday, November 6, 2020 - 15:05 for 1 hour (actually 50 minutes)
Location
Bluejeans link: https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Gwen McKinleyUniversity of California, San Diego, CA

We give an asymptotic formula for the number of partitions of an integer n where the sums of the kth powers of the parts are also fixed, for some collection of values k. To obtain this result, we reframe the counting problem as an optimization problem, and find the probability distribution on the set of all integer partitions with maximum entropy among those that satisfy our restrictions in expectation (in essence, this is an application of Jaynes' principle of maximum entropy). This approach leads to an approximate version of our formula as the solution to a relatively straightforward optimization problem over real-valued functions. To establish more precise asymptotics, we prove a local central limit theorem using an equidistribution result of Green and Tao.

A large portion of the talk will be devoted to outlining how our method can be used to re-derive a classical result of Hardy and Ramanujan, with an emphasis on the intuitions behind the method, and limited technical detail. This is joint work with Marcus Michelen and Will Perkins.

Oriented Matroids from Triangulations of Products of Simplices (note the unusual time: 4pm)

Series
Combinatorics Seminar
Time
Friday, October 23, 2020 - 16:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Chi Ho YuenBrown University

We introduce a construction of oriented matroids from any triangulation of a product of two simplices, extending the regular case which follows from signed tropicalization. For this, we use the structure of such a triangulation in terms of polyhedral matching fields. The oriented matroid is composed of compatible chirotopes on the cells in a matroid subdivision of the hypersimplex, which might be of independent interest. We will also describe the extension to matroids over hyperfields and sketch some connections with optimization. This is joint work with Marcel Celaya and Georg Loho; Marcel Celaya will be giving a talk on the topological aspect of the work at the algebra seminar next week.

Please note the unusual time: 4pm

Higher-order fluctuations in dense random graph models (note the unusual time/day)

Series
Combinatorics Seminar
Time
Thursday, October 22, 2020 - 17:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Adrian RoellinNational University of Singapore

Dense graph limit theory is essentially a first-order limit theory analogous to the classical Law of Large Numbers. Is there a corresponding central limit theorem? We believe so. Using the language of Gaussian Hilbert Spaces and the comprehensive theory of generalised U-statistics developed by Svante Janson in the 90s, we identify a collection of Gaussian measures (aka white noise processes) that describes the fluctuations of all orders of magnitude for a broad family of random graphs. We complement the theory with error bounds using a new variant of Stein’s method for multivariate normal approximation, which allows us to also generalise Janson’s theory in some important aspects. This is joint work with Gursharn Kaur.

Please note the unusual time/day.

Toppleable Permutations, Ursell Functions and Excedances

Series
Combinatorics Seminar
Time
Friday, October 16, 2020 - 10:00 for 1 hour (actually 50 minutes)
Location
Bluejeans link: https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Arvind AyyerIndian Institute of Science, Bengaluru, India


 Recall that an excedance of a permutation $\pi$ is any position $i$
 such that $\pi_i > i$. Inspired by the work of Hopkins, McConville and
 Propp (arXiv:1612.06816) on sorting using toppling, we say that
 a permutation is toppleable if it gets sorted by a certain sequence of
 toppling moves. For the most part of the talk, we will explain the
 main ideas in showing that the number of toppleable permutations on n
 letters is the same as those for which excedances happen exactly at
 $\{1,\dots, \lfloor (n-1)/2 \rfloor\}$. Time permitting, we will give
 some ideas showing that this is also the number of acyclic
 orientations with unique sink (also known as the Ursell function) of the
 complete bipartite graph $K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor + 1}$.


 This is joint work with D. Hathcock (CMU) and P. Tetali (Georgia Tech).

Discrepancy Minimization via a Self-Balancing Walk

Series
Combinatorics Seminar
Time
Friday, October 9, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Yang P. LiuStanford University

We study discrepancy minimization for vectors in R^n under various settings. The main result is the analysis of a new simple random process in multiple dimensions through a comparison argument. As corollaries, we obtain bounds which are tight up to logarithmic factors for several problems in online vector balancing posed by Bansal, Jiang, Singla, and Sinha (STOC 2020), as well as linear time algorithms for logarithmic bounds for the Komlós conjecture.

Based on joint work with Alweiss and Sawhney, see https://arxiv.org/abs/2006.14009

Pages