Thu, 16 Feb 2023

14:00 - 15:00
Lecture Room 3

Accuracy controlled schemes for the eigenvalue problem of the neutron transport equation

Olga Mula
(TU Eindhoven)
Abstract

The neutron transport equation is a linear Boltzmann-type PDE that models radiative transfer processes, and fission nuclear reactions. The computation of the largest eigenvalue of this Boltzmann operator is crucial in nuclear safety studies but it has classically been formulated only at a discretized level, so the predictive capabilities of such computations are fairly limited. In this talk, I will give an overview of the modeling for this equation, as well as recent analysis that leads to an infinite dimensional formulation of the eigenvalue problem. We leverage this point of view to build a numerical scheme that comes with a rigorous, a posteriori estimation of the error between the exact, infinite-dimensional solution, and the computed one.

Local dominance unveils clusters in networks
Shang, F Chen, B Expert, P Lü, L Yang, A Stanley, H Lambiotte, R Evans, T Li, R (30 Sep 2022)
Tue, 29 Nov 2022

14:00 - 15:00
L5

Distances in colourings of the plane

James Davies
(Cambridge University)
Abstract

We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd (integral) distance from each other. We will also discuss some further results with Rose McCarty and Michal Pilipczuk concerning prime and polynomial distances.

Tue, 22 Nov 2022

17:00 - 18:00
Virtual

Percolation on finite transitive graphs

Philip Easo
(Caltech)
Further Information

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

Abstract

Tom Hutchcroft and I have been working to develop a general theory of percolation on arbitrary finite transitive graphs. This extends from percolation on local approximations to infinite graphs, such as a sequence of tori, to percolation on the complete graphs - the Erdős-Rényi model. I will summarise our progress on the basic questions: When is there a phase transition for the emergence of a giant cluster? When is the giant cluster unique? How does this relate to percolation on infinite graphs? I will then sketch our proof that for finite transitive graphs with uniformly bounded vertex degrees, the supercritical giant cluster is unique, verifying a conjecture of Benjamini from 2001.

Tue, 22 Nov 2022

15:30 - 16:30
Virtual

Hypergraph Matchings Avoiding Forbidden Submatchings

Michelle Delcourt
(Toronto Metropolitan University)
Further Information

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

Abstract

In 1973, Erdős conjectured the existence of high girth $(n,3,2)$-Steiner systems. Recently, Glock, Kühn, Lo, and Osthus and independently Bohman and Warnke proved the approximate version of Erdős' conjecture. Just this year, Kwan, Sah, Sawhney, and Simkin proved Erdős' conjecture. As for Steiner systems with more general parameters, Glock, Kühn, Lo, and Osthus conjectured the existence of high girth $(n,q,r)$-Steiner systems. We prove the approximate version of their conjecture. This result follows from our general main results which concern finding perfect or almost perfect matchings in a hypergraph $G$ avoiding a given set of submatchings (which we view as a hypergraph $H$ where $V(H)=E(G)$). Our first main result is a common generalization of the classical theorems of Pippenger (for finding an almost perfect matching) and Ajtai, Komlós, Pintz, Spencer, and Szemerédi (for finding an independent set in girth five hypergraphs). More generally, we prove this for coloring and even list coloring, and also generalize this further to when $H$ is a hypergraph with small codegrees (for which high girth designs is a specific instance). A number of applications in various areas follow from our main results including: Latin squares, high dimensional permutations, and rainbow matchings. This is joint work with Luke Postle.

Tue, 15 Nov 2022

14:00 - 15:00
L5

Unavoidable order-size pairs in graphs and hypergraphs

Maria Axenovich
(KIT)
Abstract

A graph has a pair $(m,f)$ if it has an induced subgraph on $m$ vertices and $f$ edges. We write $(n,e)\rightarrow (m,f)$  if any graph on $n$ vertices and $e$ edges has a pair $(m,f)$.  Let  $$S(n,m,f)=\{e: ~(n,e)\rightarrow (m,f)\} ~{\rm and}$$     $$\sigma(m,f) =   \limsup_{n\rightarrow \infty}\frac{ |S(n,m,f)|}{\binom{n}{2}}.$$ These notions were first introduced and investigated by Erdős, Füredi, Rothschild, and Sós. They found five pairs $(m,f)$ with  $\sigma(m,f)=1$ and showed that for all other pairs $\sigma(m,f)\leq 2/3$.  We extend these results in two directions.

First, in a joint work with Weber, we show that not only $\sigma(m,f)$ can be zero, but also $S(n,m,f)$  could be empty for some pairs $(m,f)$ and any sufficiently large $n$. We call such pairs $(m,f)$ absolutely avoidable.

Second, we consider a natural analogue $\sigma_r(m,f)$ of $\sigma(m,f)$ in the setting of $r$-uniform hypergraphs.  Weber showed that for any $r\geq 3$ and  $m>r$,  $\sigma_r(m,f)=0$ for most values of $f$.  Surprisingly, it was not immediately clear whether there are nontrivial pairs $(m,f)$,  $(f\neq 0$, $f\neq \binom{m}{r}$,  $r\geq 3$),  for which $\sigma_r(m,f)>0$. In a joint work with Balogh, Clemen, and Weber we show that $\sigma_3(6,10)>0$ and conjecture that in the $3$-uniform case $(6,10)$ is the only such pair.

Tue, 08 Nov 2022

14:00 - 15:00
L5

On the Ryser-Buraldi-Stein conjecture

Richard Montgomery
(University of Warwick)
Abstract

A Latin square of order n is an n by n grid filled with n different symbols so that every symbol occurs exactly once in each row and each column, while a transversal in a Latin square is a collection of cells which share no row, column or symbol. The Ryser-Brualdi-Stein conjecture states that every Latin square of order n should have a transversal with n-1 elements, and one with n elements if n is odd. In 2020, Keevash, Pokrovskiy, Sudakov and Yepremyan improved the long-standing best known bounds on this conjecture by showing that a transversal with n-O(log n/loglog n) elements exists in any Latin square of order n. In this talk, I will discuss how to show, for large n, that a transversal with n-1 elements always exists.

Tue, 25 Oct 2022

17:00 - 18:00
Virtual

A tale of two balloons

Yinon Spinka
(UBC)
Further Information

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

Abstract

From each point of a Poisson point process start growing a balloon at rate 1. When two balloons touch, they pop and disappear. Will balloons reach the origin infinitely often or not? We answer this question for various underlying spaces. En route we find a new(ish) 0-1 law, and generalize bounds on independent sets that are factors of IID on trees. Joint work with Omer Angel and Gourab Ray.

Tue, 25 Oct 2022

15:30 - 16:30
Virtual

Average degree and girth

Rose McCarty
(Princeton University)
Further Information

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

Abstract

In 1983 Thomassen conjectured that every graph of sufficiently large average degree has a subgraph of large girth and large average degree. While this conjecture remains open, recent evidence suggests that something stronger might be true; perhaps the subgraph can be made induced when a clique and biclique are forbidden. We overview our proof for removing 4-cycles from $K_{t,t}$-free bipartite graphs. Moreover, we discuss consequences to tau-boundedness, which is an analog of chi-boundedness.

Tue, 18 Oct 2022

14:00 - 15:00
L5

Improved bounds for 1-independent percolation on $\mathbb{Z}^n$

Paul Balister & Michael Savery
(Oxford University)
Abstract

A 1-independent bond percolation model on a graph $G$ is a probability distribution on the spanning subgraphs of $G$ in which, for all vertex-disjoint sets of edges $S_1$ and $S_2$, the states (i.e. present or not present) of the edges in $S_1$ are independent of the states of the edges in $S_2$. Such models typically arise in renormalisation arguments applied to independent percolation models, or percolation models with finite range dependencies. A 1-independent model is said to percolate if the random subgraph has an infinite component with positive probability. In 2012 Balister and Bollobás defined $p_{\textrm{max}}(G)$ to be the supremum of those $p$ for which there exists a 1-independent bond percolation model on $G$ in which each edge is present in the random subgraph with probability at least $p$ but which does not percolate. A fundamental and challenging problem in this area is to determine, or give good bounds on, the value of $p_{\textrm{max}}(G)$ when $G$ is the lattice graph $\mathbb{Z}^2$. Since $p_{\textrm{max}}(\mathbb{Z}^n)\leq p_{\textrm{max}}(\mathbb{Z}^{n-1})$, it is also of interest to establish the value of $\lim_{n\to\infty}p_{\textrm{max}}(\mathbb{Z}^n)$.

In this talk we will present a significantly improved upper bound for this limit as well as improved upper and lower bounds for $p_{\textrm{max}}(\mathbb{Z}^2)$. We will also show that with high confidence we have $p_{\textrm{max}}(\mathbb{Z}^n)<p_{\textrm{max}}(\mathbb{Z}^2)$ for large $n$ and discuss some open problems concerning 1-independent models on other graphs.

This is joint work with Tom Johnston and Alex Scott.

Subscribe to