Seminars and Colloquia by Series

Counting integer partitions with the method of maximum entropy

Series
Combinatorics Seminar
Time
Friday, October 30, 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

Series
Combinatorics Seminar
Time
Friday, October 23, 2020 - 15: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.

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

A Higher-Dimensional Sandpile Map (note the unusual time/day)

Series
Combinatorics Seminar
Time
Wednesday, September 30, 2020 - 15:30 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Alex McdonoughBrown University

Traditionally, the sandpile group is defined on a graph and the Matrix-Tree Theorem says that this group's size is equal to the number of spanning trees. An extension of the Matrix-Tree Theorem gives a relationship between the sandpile group and bases of an arithmetic matroid. I provide a family of combinatorially meaningful maps between these two sets.  This generalizes a bijection given by Backman, Baker, and Yuen and extends work by Duval, Klivans, and Martin.

Please note the unusual time/day.

Spatial mixing and the Swendsen-Wang dynamics

Series
Combinatorics Seminar
Time
Friday, September 18, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Antonio Blanca Pennsylvania State University

The Swendsen-Wang dynamics is a popular algorithm for sampling from the Gibbs distribution for the ferromagnetic Ising and Potts models. The dynamics is a global Markov chain that is conjectured to converge quickly to equilibrium even at low temperatures, where the correlations in the system are strong and local chains converge slowly. In this talk, we present new results concerning the speed of convergence of the Swendsen-Wang dynamics under spatial mixing (i.e., decay of correlations) conditions. In particular, we provide tight results for three distinct geometries: the integer d-dimensional integer lattice graph Z^d, regular trees, and random d-regular graphs. Our approaches crucially exploit the underlying geometry in different ways in each case.

The chromatic number of a random lift of K_d

Series
Combinatorics Seminar
Time
Friday, September 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
Xavier Pérez GiménezUniversity of Nebraska-Lincoln

An n-lift of a graph G is a graph from which there is an n-to-1 covering map onto G. Amit, Linial, and Matousek (2002) raised the question of whether the chromatic number of a random n-lift of K_5 is concentrated on a single value. We consider a more general problem, and show that for fixed d ≥ 3 the chromatic number of a random lift of K_d is (asymptotically almost surely) either k or k+1, where k is the smallest integer satisfying d < 2k log k. Moreover, we show that, for roughly half of the values of d, the chromatic number is concentrated on k. The argument for the upper-bound on the chromatic number uses the small subgraph conditioning method, and it can be extended to random n-lifts of G, for any fixed d-regular graph G. (This is joint work with JD Nir.)

On the Helfgott-Lindenstrauss conjecture for linear groups

Series
Combinatorics Seminar
Time
Friday, September 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
Brendan MurphyUniversity of Bristol

Freiman's theorem characterizes finite subsets of abelian groups that behave "approximately" like subgroups: any such set is (roughly) a sum of arithmetic progressions and a finite subgroup. Quantifying Freiman's theorem is an important area of additive combinatorics; in particular, proving a "polynomial" Freiman theorem would be extremely useful.

The "Helfgott-Lindenstrauss conjecture" describes the structure of finite subsets of non-abelian groups that behave approximately like subgroups: any such set is (roughly) a finite extension of a nilpotent group. Breuillard, Green, and Tao proved a qualitative version of this conjecture. In general, a "polynomial" version of the HL conjecture cannot hold, but we prove that a polynomial version of the HL conjecture is true for linear groups of bounded rank.

In this talk, we will see how the "sum-product phenomenon" and its generalizations play a crucial role in the proof of this result. The amount of group theory needed is minimal.

Exponentially Many Hypergraph Colourings

Series
Combinatorics Seminar
Time
Friday, August 28, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/???? (Replace ???? with the password sent via email)
Speaker
Lutz WarnkeGeorgia Institute of Technology

We shall discuss a recent paper of Wanless and Wood (arXiv:2008.00775), which proves a Lovász Local Lemma type result using inductive counting arguments.
For example, in the context of hypergraph colorings, under LLL-type assumptions their result typically gives exponentially many colorings (usually more than the textbook proof of LLL would give).
We will present a probabilistic proof of the Wanless-Wood result, and discuss some applications to k-SAT, Ramsey number lower bounds, and traversals, as time permits.

Pages