Gyárfás conjectured in 1985 that if $G$ is a graph with no induced cycle of odd length at least 5, then the chromatic number of $G$ is bounded by a function of its clique number. We prove this conjecture. Joint work with Paul Seymour.
More than twenty years ago Erdős conjectured that a triangle-free graph $G$ of chromatic number $k$ contains cycles of at least $k^{2−o(1)}$ different lengths. In this talk we prove this conjecture in a stronger form, showing that every such $G$ contains cycles of $ck^2\log k$ consecutive lengths, which is tight. Our approach can be also used to give new bounds on the number of different cycle lengths for other monotone classes of $k$-chromatic graphs, i.e., clique-free graphs and graphs without odd cycles.
Joint work with A. Kostochka and J. Verstraete.
We study the properties of finite graphs in which the ball of radius $r$ around each vertex induces a graph isomorphic to some fixed graph $F$. (Such a graph is said to be $r$-locally-$F$.) This is a natural extension of the study of regular graphs, and of the study of graphs of constant link. We focus on the case where $F$ is $\mathbb{L}^d$, the $d$-dimensional integer lattice. We obtain a characterisation of all the finite graphs in which the ball of radius $3$ around each vertex is isomorphic to the ball of radius $3$ in $\mathbb{L}^d$, for each integer $d$. These graphs have a very rigidly proscribed global structure, much more so than that of $(2d)$-regular graphs. (They can be viewed as quotient lattices in certain 'flat orbifolds'.) Our results are best possible in the sense that '3' cannot be replaced with '2'. Our proofs use a mixture of techniques and results from combinatorics, algebraic topology and group theory. We will also discuss some results and open problems on the properties of a random n-vertex graph which is $r$-locally-$F$. This is all joint work with Itai Benjamini (Weizmann Institute of Science).
No doubt you have found yourself screaming at the stupidity of characters in a horror movie. You would never have walked into that room alone, you would always make sure your weapon was loaded and you would certainly always ensure a monster was dead before returning to the corpse!
But what are the real rules that you should live by if the dead should begin to rise? Dr Thomas Woolley and coauthors from the Mathematical Institute, University of Oxford believe they have come up with the answer:
In this talk, I will describe how to use the partial hodograph-Legendre transformation to show the analyticity of the free boundary in the elliptic thin obstacle problem. In particular, I will discuss the invertibility of this transformation and show that the resulting fully nonlinear PDE has a subelliptic structure. This is based on a joint work with Herbert Koch and Arshak Petrosyan.
