Past Combinatorial Theory Seminar

30 November 2021
14:00
Candy Bowtell
Abstract

The $n$-queens problem asks how many ways there are to place $n$ queens on an $n \times 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 \equiv 1,5 \mod 6$. Much more recently Luria showed that $T(n)\leq ((1+o(1))ne^{-3})^n$ and conjectured equality when $n \equiv 1,5 \mod 6$. We prove this conjecture, prior to which no non-trivial lower bounds were known to hold for all (sufficiently large) $n \equiv 1,5 \mod 6$. We also show that $Q(n)\geq((1+o(1))ne^{-3})^n$ for all $n \in \mathbb{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.

  • Combinatorial Theory Seminar
23 November 2021
14:00
Mariana Olvera-Cravioto
Abstract

We study a family of evolving directed random graphs that includes the directed preferential model and the directed uniform attachment model. The directed preferential model is of particular interest since it is known to produce scale-free graphs with regularly varying in-degree distribution. We start by describing the local weak limits for our family of random graphs in terms of randomly stopped continuous-time branching processes, and then use these limits to establish the asymptotic behavior of the corresponding PageRank distribution. We show that the limiting PageRank distribution decays as a power-law in both models, which is surprising for the uniform attachment model where the in-degree distribution has exponential tails. And even for the preferential attachment model, where the power-law hypothesis suggests that PageRank should follow a power-law, our result shows that the two tail indexes are different, with the PageRank distribution having a heavier tail than the in-degree distribution.

  • Combinatorial Theory Seminar
16 November 2021
14:00
Matthew Jenssen
Abstract

Let $A$ be drawn uniformly at random from the set of all $n \times n$ symmetric matrices with entries in $\{-1,1\}$. We show that $A$ is singular with probability at most $e^{-cn}$ for some absolute constant $c>0$, thereby resolving a well-known conjecture. This is joint work with Marcelo Campos, Marcus Michelen and Julian Sahasrabudhe.
 

  • Combinatorial Theory Seminar
2 November 2021
14:00
Yifan Jing
Abstract

Henstock and Macbeath asked in 1953 whether the Brunn-Minkowski inequality can be generalized to nonabelian locally compact groups; questions in the same line were also asked by Hrushovski, McCrudden, and Tao. We obtain here such an inequality and prove that it is sharp for helix-free locally compact groups, which includes real linear algebraic groups, Nash groups, semisimple Lie groups with finite center, solvable Lie groups, etc. If time allows I will also discuss some applications of this result. (Joint with Chieu-Minh Tran and Ruixiang Zhang)

  • Combinatorial Theory Seminar
26 October 2021
14:00
Ashwin Sah

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details. Joint with the Random Matrix Theory Seminar.

Abstract

We introduce a new method for studying stochastic processes in random graphs controlled by degree information, involving combining enumeration techniques with an abstract second moment argument. We use it to constructively resolve a conjecture of Füredi from 1988: with high probability, the random graph G(n,1/2) admits a friendly bisection of its vertex set, i.e., a partition of its vertex set into two parts whose sizes differ by at most one in which n-o(n) vertices have at least as many neighbours in their own part as across. This work is joint with Asaf Ferber, Matthew Kwan, Bhargav Narayanan, and Mehtaab Sawhney.

  • Combinatorial Theory Seminar
19 October 2021
14:00
Peter Van Hintum
Abstract

I'll consider recent results concerning the stability of the classic Brunn-Minkowski inequality. In particular, I will focus on the linear stability for homothetic sets. Resolving a conjecture of Figalli and Jerison, we showed there are constants $C,d>0$ depending only on $n$ such that for every subset $A$ of $\mathbb{R}^n$ of positive measure, if $|(A+A)/2 - A| \leq d |A|$, then $|co(A) - A| \leq C |(A+A)/2 - A|$ where $co(A)$ is the convex hull of $A$. The talk is based on joint work with Hunter Spink and Marius Tiba.

  • Combinatorial Theory Seminar
12 October 2021
14:00
Sumit Mukherjee

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details. Joint with the Random Matrix Theory Seminar.

Abstract

Suppose there are $n$ students in a class. But assume that not everybody is friends with everyone else, and there is a graph which determines the friendship structure. What is the chance that there are two friends in this class, both with birthdays on October 12? More generally, given a simple labelled graph $G_n$ on $n$ vertices, color each vertex with one of $c=c_n$ colors chosen uniformly at random, independent from other vertices. We study the question: what is the number of monochromatic edges of color 1?

As it turns out, the limiting distribution has three parts, the first and second of which are quadratic and linear functions of a homogeneous Poisson point process, and the third component is an independent Poisson. In fact, we show that any distribution limit must belong to the closure of this class of random variables. As an application, we characterize exactly when the limiting distribution is a Poisson random variable.

This talk is based on joint work with Bhaswar Bhattacharya and Somabha Mukherjee.

  • Combinatorial Theory Seminar
1 June 2021
15:30
Gérard Ben Arous

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details. Joint with the Random Matrix Theory Seminar.

Abstract

This is joint work with Paul Bourgade and Benjamin McKenna (Courant Institute, NYU).
The elastic manifold is a paradigmatic representative of the class of disordered elastic systems. These models describe random surfaces with rugged shapes resulting from a competition between random spatial impurities (preferring disordered configurations), on the one hand, and elastic self-interactions (preferring ordered configurations), on the other. The elastic manifold model is interesting because it displays a depinning phase transition and has a long history as a testing ground for new approaches in statistical physics of disordered media, for example for fixed dimension by Fisher (1986) using functional renormalization group methods, and in the high-dimensional limit by Mézard and Parisi (1992) using the replica method.
We study the topology of the energy landscape of this model in the Mézard-Parisi setting, and compute the (annealed) topological complexity both of total critical points and of local minima. Our main result confirms the recent formulas by Fyodorov and Le Doussal (2020) and allows to identify the boundary between simple and glassy phases. The core argument relies on the analysis of the asymptotic behavior of large random determinants in the exponential scale.

  • Combinatorial Theory Seminar
1 June 2021
14:30
Konstantin Tikhomirov

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details. Joint with the Random Matrix Theory Seminar.

Abstract

Consider an $n$ by $n$ random matrix $A$ with i.i.d entries. In this talk, we discuss some results on the magnitude of the smallest singular value of $A$, and, in particular, the problem of estimating the singularity probability when the entries of $A$ are discrete.

  • Combinatorial Theory Seminar

Pages