Past Combinatorial Theory Seminar

24 November 2020
15:30
Gwenaël Joret

Further Information: 

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

Abstract

This talk will focus on the following two related problems:
    (1) What is the minimum number of edges in a graph containing all $n$-vertex planar graphs as subgraphs? A simple construction of Babai, Erdos, Chung, Graham, and Spencer (1982) has $O(n^{3/2})$ edges, which is the best known upper bound.
    (2) What is the minimum number of *vertices* in a graph containing all $n$-vertex planar graphs as *induced* subgraphs? Here steady progress has been achieved over the years, culminating in a $O(n^{4/3})$ bound due to Bonamy, Gavoille, and Pilipczuk (2019).
    As it turns out, a bound of $n^{1+o(1)}$ can be achieved for each of these two problems. The two constructions are somewhat different but are based on a common technique. In this talk I will first give a gentle introduction to the area and then sketch these constructions. The talk is based on joint works with Vida Dujmović, Louis Esperet, Cyril Gavoille, Piotr Micek, and Pat Morin.

  • Combinatorial Theory Seminar
24 November 2020
14:00
Alexander Holroyd

Further Information: 

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

Abstract

What is fairness, and to what extent is it practically achievable? I'll talk about a simple mathematical model under which one might hope to understand such questions. Red and blue points occur as independent homogeneous Poisson processes of equal intensity in Euclidean space, and we try to match them to each other. We would like to minimize the sum of a some function (say, a power, $\gamma$) of the distances between matched pairs. This does not make sense, because the sum is infinite, so instead we satisfy ourselves with minimizing *locally*. If the points are interpreted as agents who would like to be matched as close as possible, the parameter $\gamma$ encodes a measure of fairness - large $\gamma$ means that we try to avoid occasional very bad outcomes (long edges), even if that means inconvenience to others - small $\gamma$ means everyone is in it for themselves.
    In dimension 1 we have a reasonably complete picture, with a phase transition at $\gamma=1$. For $\gamma<1$ there is a unique minimal matching, while for $\gamma>1$ there are multiple matchings but no stationary solution. In higher dimensions, even existence is not clear in all cases.

  • Combinatorial Theory Seminar
17 November 2020
15:30
Ron Rosenthal

Further Information: 

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

Abstract

A spanning tree of $G$ is a subgraph of $G$ with the same vertex set as $G$ that is a tree. In 1981, McKay proved an asymptotic result regarding the number of spanning trees in random $k$-regular graphs, showing that the number of spanning trees $\kappa_1(G_n)$ in a random $k$-regular graph on $n$ vertices satisfies $\lim_{n \to \infty} (\kappa_1(G_n))^{1/n} = c_{1,k}$ in probability, where $c_{1,k} = (k-1)^{k-1} (k^2-2k)^{-(k-2)/2}$.

In this talk we will discuss a high-dimensional of the matching model for simplicial complexes, known as random Steiner complexes. In particular, we will prove a high-dimensional counterpart of McKay's result and discuss the local limit of such random complexes. 
Based on a joint work with Lior Tenenbaum. 

  • Combinatorial Theory Seminar
17 November 2020
14:00
Yuval Peled

Further Information: 

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

Abstract

We study the minimum total weight of a disk triangulation using any number of vertices out of $\{1,..,n\}$ where the boundary is fixed and the $n \choose 3$ triangles have independent rate-1 exponential weights. We show that, with high probability, the minimum weight is equal to $(c+o(1))n-1/2\log n$ for an explicit constant $c$. Further, we prove that, with high probability, the minimum weights of a homological filling and a homotopical filling of the cycle $(123)$ are both attained by the minimum weight disk triangulation. We will discuss a related open problem concerning simple-connectivity of random simplicial complexes, where a similar phenomenon is conjectured to hold. Based on joint works with Itai Benjamini, Eyal Lubetzky, and Zur Luria.

  • Combinatorial Theory Seminar
10 November 2020
15:30
Tom Hutchcroft

Further Information: 

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

Abstract

In long-range percolation on $\mathbb{Z}^d$, each potential edge $\{x,y\}$ is included independently at random with probability roughly $\beta\|x-y\|-d-\alpha$, where $\alpha > 0$ controls how long-range the model is and $\beta > 0$ is an intensity parameter. The smaller $\alpha$ is, the easier it is for very long edges to appear. We are normally interested in fixing $\alpha$ and studying the phase transition that occurs as $\beta$ is increased and an infinite cluster emerges. Perhaps surprisingly, the phase transition for long-range percolation is much better understood than that of nearest neighbour percolation, at least when $\alpha$ is small: It is a theorem of Noam Berger that if $\alpha < d$ then the phase transition is continuous, meaning that there are no infinite clusters at the critical value of $\beta$. (Proving the analogous result for nearest neighbour percolation is a notorious open problem!) In my talk I will describe a new, quantitative proof of Berger's theorem that yields power-law upper bounds on the distribution of the cluster of the origin at criticality.
    As a part of this proof, I will describe a new universal inequality stating that on any graph, the maximum size of a percolation cluster is of the same order as its median with high probability. This inequality can also be used to give streamlined new proofs of various classical results on e.g. Erdős-Rényi random graphs, which I will hopefully have time to talk a little bit about also.

  • Combinatorial Theory Seminar
10 November 2020
14:00
Vincent Beffara

Further Information: 

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

Abstract

I will present work in progress with D. Gayet and F. Pouran (Grenoble) to establish Russo-Seymour-Welsh (RSW) estimates for 2d statistical mechanics models that do not satisfy the FKG inequality. RSW states that critical percolation has no characteristic length, in the sense that large rectangles are crossed by an open path with a probability that is bounded below by a function of their shape, but uniformly in their size; this ensures the polynomial decay of many relevant quantities and opens the way to deeper understanding of the critical features of the model. All the standard proofs of RSW rely on the FKG inequality, i.e. on the positive correlation between increasing events; we establish the stability of RSW under small perturbations that do not preserve FKG, which extends it for instance to the high-temperature anti-ferromagnetic Ising model.

  • Combinatorial Theory Seminar
3 November 2020
15:30
Shoham Letzter

Further Information: 

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

Abstract

A connected matching is a matching contained in a connected component. A well-known method due to Łuczak reduces problems about monochromatic paths and cycles in complete graphs to problems about monochromatic matchings in almost complete graphs. We show that these can be further reduced to problems about monochromatic connected matchings in complete graphs.
    
I will describe Łuczak's reduction, introduce the new reduction, and mention potential applications of the improved method.

  • Combinatorial Theory Seminar
3 November 2020
14:00
Julian Sahasrabudhe

Further Information: 

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

Abstract

Let $X$ be a random variable, taking values in $\{1,…,n\}$, with standard deviation $\sigma$ and let $f_X$ be its probability generating function. Pemantle conjectured that if $\sigma$ is large and $f_X$ has no roots close to 1 in the complex plane then $X$ must approximate a normal distribution. In this talk, I will discuss a complete resolution of Pemantle's conjecture. As an application, we resolve a conjecture of Ghosh, Liggett and Pemantle by proving a multivariate central limit theorem for, so called, strong Rayleigh distributions. I will also discuss how these sorts of results shed light on random variables that arise naturally in combinatorial settings. This talk is based on joint work with Marcus Michelen.

  • Combinatorial Theory Seminar
27 October 2020
15:30
Luke Postle

Further Information: 

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

Abstract

In 1943, Hadwiger conjectured that every graph with no Kt minor is $(t-1)$-colorable for every $t\geq 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t(\log t)^{1/2})$ and hence is $O(t(\log t)^{1/2)}$-colorable. Recently, Norin, Song and I showed that every graph with no $K_t$ minor is $O(t(\log t)^\beta)$-colorable for every $\beta > 1/4$, making the first improvement on the order of magnitude of the $O(t(\log t)^{1/2})$ bound. Here we show that every graph with no $K_t$ minor is $O(t (\log t)^\beta)$-colorable for every $\beta > 0$; more specifically, they are $O(t (\log \log t)^6)$-colorable.

  • Combinatorial Theory Seminar
27 October 2020
14:00
Igor Kortchemski

Further Information: 

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

Abstract

We will be interested in the structure of random typical minimal factorizations of the n-cycle into transpositions, which are factorizations of $(1,\ldots,n)$ as a product of $n-1$ transpositions. We shall establish a phase transition when a certain amount of transpositions have been read one after the other. One of the main tools is a limit theorem for two-type Bienaymé-Galton-Watson trees conditioned on having given numbers of vertices of both types, which is of independent interest. This is joint work with Valentin Féray.

  • Combinatorial Theory Seminar

Pages