Dimension 4 is the first dimension in which exotic smooth manifold pairs appear — manifolds which are topologically the same but for which there is no smooth deformation of one into the other. On the other hand, smooth and PL manifolds (manifolds which can be described discretely) do coincide in dimension 4. Despite this, there has been comparatively little work done towards gaining an understanding of smooth 4-manifolds from the discrete and algorithmic perspective. The aim of this talk will be to give a gentle introduction to some of the tools, techniques, and ideas, which inform a computational approach to 4-manifold topology.

In the talk, I'll first describe a more general context of Sárközy-type problems and interesting directions in which they can be pursued. Then, I'll focus on the specific case of bounding the size of sets A s. t. A - A + 1 contains no prime. After describing the progress on the problem for integers, I'll pass on to considering an analogous question for function fields and (after a general introduction to function fields) I'll speak about my recent result in this area.

It is a classical result that a random permutation of $n$ elements has, on average, about $\log n$ cycles. We generalise this fact to all directed $d$-regular graphs on $n$ vertices by showing that, on average, a random cycle-factor of such a graph has $\mathcal{O}((n\log d)/d)$ cycles. This is tight up to the constant factor and improves the best previous bound of the form $\mathcal{O}({n/\sqrt{\log d}})$ due to Vishnoi. It also yields randomised polynomial-time algorithms for finding such a cycle-factor and for finding a tour of length $(1+\mathcal{O}((\log d)/d)) \cdot n$ if the graph is connected. The latter result makes progress on a restriction of the Traveling Salesman Problem to regular graphs, a problem studied by Vishnoi and by Feige, Ravi, and Singh. Our proof uses the language of entropy to exploit the fact that the upper and lower bounds on the number of perfect matchings in regular bipartite graphs are extremely close.

This talk is based on joint work with Micha Christoph, Nemanja Draganić, António Girão, Eoin Hurley, and Alp Müyesser.

For a tree $T$ whose bipartition classes have sizes $t_1 \ge t_2$, two simple constructions shows that the Ramsey number of $T$ is at least $\max\{t_1+2t_2,2t_1\}-1$. In 1974, Burr conjectured that equality holds for every tree. It turns out that Burr’s conjecture is false for certain trees called the double stars, though all of the known counterexamples have large maximum degrees. In 2002, Haxell, Łuczak, and Tingley showed that Burr’s conjecture is approximately true if one imposes a maximum degree condition.

We show that Burr’s conjecture holds for all trees with up to small linear maximum degrees. That is, there exists $c>0$ such that for every $n$-vertex tree $T$ with maximum degree at most $cn$ and bipartition class sizes $t_1\ge t_2$, its Ramsey number $R(T)$ is exactly $\max\{t_1+2t_2,2t_1\}-1$. We also generalise this result to determine the exact asymmetric Ramsey number $R(T,S)$ of two trees $T$ and $S$ under certain additional conditions, and construct examples showing that these conditions are necessary. 

This talk is based on joint work with Richard Montgomery and Matías Pavez-Signé.