Tue, 26 Jan 2021

A solution to Erdős and Hajnal's odd cycle problem

Richard Montgomery
Further Information

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


I will discuss how to construct cycles of many different lengths in graphs, in particular answering the following two problems on odd and even cycles. Erdős and Hajnal asked in 1981 whether the sum of the reciprocals of the odd cycle lengths in a graph diverges as the chromatic number increases, while, in 1984, Erdős asked whether there is a constant $C$ such that every graph with average degree at least $C$ contains a cycle whose length is a power of 2.

Wed, 20 Feb 2019

‘Expansivity and shadowing’

Chris Good

Abstract:   Let $f$ be a continuous surjection from the compact metric space $X$ to itself. 


We say that the dynamical system $(X,f)$ has shadowing if for every $\epsilon>0$ there is a $\delta>0$ such that every $\delta$-pseudo orbit is $\epsilon$-shadowed.  Here a sequence $(x_n)$ is a $\delta$-pseudo orbit provided the distance from $f(x_n)$ to $x_{n+1}$ is less than $\delta$ and $(x_n)$ is $\epsilon$-shadowed if there is a point $z$ such that the distance from $x_n$ to $f^n(z)$ is less than $\epsilon$.  


If $f$ is a homeomorphism, $(X,f)$ is said to be expansive if there is some $c>0$, such that if the distance from $f^n(x)$ and $f^n(y)$ is less than $c$ for all $n\in \mathbb Z$, then $x=y$.


In his proof that a homeomorphism that is expansive and has shadowing is stable, Walters shows that in an expansive system with shadowing, a pseudo orbit is shadowed by exactly one point.  It turns out that the converse is also true: if the system has unique shadowing (in the above sense), then it is expansive.


In this talk, which is joint work with Joel Mitchell and Joe Thomas, we explore this notion of unique shadowing.

Tue, 05 Feb 2019

Towards a generic representation theory

David Craven

In combinatorics, the 'nicest' way to prove that two sets have the same size is to find a bijection between them, giving more structure to the seeming numerical coincidences. In representation theory, many of the outstanding conjectures seem to imply that the characteristic p of the ground field can be allowed to vary, and we can relate different groups and different primes, to say that they have 'the same' representation theory. In this talk I will try to make precise what we could mean by this

Tue, 12 Jun 2018

Random graph coloring and the cavity method

Will Perkins

The last remaining open problem from Erdős and Rényi's original paper on random graphs is the following: for q at least 3, what is the largest d so that the random graph G(n,d/n) is q-colorable with high probability?  A lot of interesting work in probabilistic combinatorics has gone into proving better and better bounds on this q-coloring threshold, but the full answer remains elusive.  However, a non-rigorous method from the statistical physics of glasses - the cavity method - gives a precise prediction for the threshold.  I will give an introduction to the cavity method, with random graph coloring as the running example, and describe recent progress in making parts of the method rigorous, emphasizing the role played by tools from extremal combinatorics.  Based on joint work with Amin Coja-Oghlan, Florent Krzakala, and Lenka Zdeborová.

Tue, 13 Jun 2017

On the number of distinct vertex sets covered by cycles

Jaehoon Kim

Komlós conjectured in 1981 that among all graphs with minimum degree at least $d$, the complete graph $K_{d+1}$ minimises the number of Hamiltonian subsets, where a subset of vertices is Hamiltonian if it contains a spanning cycle. We prove this conjecture when $d$ is sufficiently large.  In fact we prove a stronger result: for large $d$, any graph $G$ with average degree at least $d$ contains almost twice as many Hamiltonian subsets as $K_{d+1}$, unless $G$ is isomorphic to $K_{d+1}$ or a certain other graph which we specify. This is joint work with Hong Liu, Maryam Sharifzadeh and Katherine Staden.

Wed, 27 Apr 2016

A counterexample to the Ho-Zhao problem

Achim Jung

It is quite easy to see that the sobrification of a
topological space is a dcpo with respect to its specialisation order
and that the topology is contained in the Scott topology wrt this
order. It is also known that many classes of dcpo's are sober when
considered as topological spaces via their Scott topology. In 1982,
Peter Johnstone showed that, however, not every dcpo has this
property in a delightful short note entitled "Scott is not always

Weng Kin Ho and Dongsheng Zhao observed in the early 2000s that the
Scott topology of the sobrification of a dcpo is typically different
from the Scott topology of the original dcpo, and they wondered
whether there is a way to recover the original dcpo from its
sobrification. They showed that for large classes of dcpos this is
possible but were not able to establish it for all of them. The
question became known as the Ho-Zhao Problem. In a recent
collaboration, Ho, Xiaoyong Xi, and I were able to construct a

In this talk I want to present the positive results that we have about
the Ho-Zhao problem as well as our counterexample. 

Subscribe to Birmingham