Combinatorial Theory Seminar

Please note that the list below only shows forthcoming events, which may not include regular events that have not yet been entered for the forthcoming term. Please see the past events page for a list of all seminar series that the department has on offer.

Past events in this series
Tomorrow
14:30
Dongyeap Kang
Abstract

The extremal number ${\rm ex}(n,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $r \in [0,2]$ is realisable if there exists a graph $F$ with ${\rm ex}(n , F) = \Theta(n^r)$. Several decades ago, Erdős and Simonovits conjectured that every rational number in $[1,2]$ is realisable. Despite decades of effort, the only known realisable numbers are $0,1, \frac{7}{5}, 2$, and the numbers of the form $1+\frac{1}{m}$, $2-\frac{1}{m}$, $2-\frac{2}{m}$ for integers $m \geq 1$. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers $1$ and $2$.

We discuss some progress on the conjecture of Erdős and Simonovits. First, we show that $2 - \frac{a}{b}$ is realisable for any integers $a,b \geq 1$ with $b>a$ and $b \equiv \pm 1 ~({\rm mod}\:a)$. This includes all previously known ones, and gives infinitely many limit points $2-\frac{1}{m}$ in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.

This is joint work with Jaehoon Kim and Hong Liu.

  • Combinatorial Theory Seminar
27 November 2018
14:30
Imre Leader
Abstract

We will examine how the various notions of partition regularity change as we change the ambient space. A typical question would be as follows. We say that the system of equations $Ax=b$, where $A$ is an integer matrix and $b$ is a (non-zero) integer vector, is partition regular if whenever the integers are finitely coloured there is a monochromatic vector $x$ with $Ax=b$. Rado proved that the system $Ax=b$ is partition regular if and only if it has a constant solution. What happens if the integers are replaced by the rationals, or the reals, or a more general ring? 


No previous knowledge of partition regularity is assumed. This is based on joint work with Paul Russell and joint work with Ben Barber, Neil Hindman and Dona Strauss.

  • Combinatorial Theory Seminar
Add to My Calendar