Discrete Mathematics

I will discuss several recent results on the Turán density of long cycle-like hypergraphs. These results (due to Kamčev–Letzter–Pokrovskiy, Balogh–Luo, and myself) all follow a similar framework, and I will outline a general strategy to prove Turán-type results for tight cycles in larger uniformities or for other "cycle-like" hypergraphs.

One key ingredient in this framework, which I hope to prove in full, is a hypergraph analogue of the statement that a graph has no odd closed walks if and only if it is bipartite. More precisely, for various classes C of "cycle-like" r-uniform hypergraphs — including, for any k, the family of tight cycles of length k modulo r — we equiivalently characterize C-hom-free hypergraphs as those admitting a certain type of coloring of (r-1)-tuples of vertices. This provides a common generalization of results due to Kamčev–Letzter–Pokrovskiy and Balogh–Luo.

For any $r\geq 2$, an $r$-uniform hypergraph $\mathcal{H}$, and integer $n$, the \emph{Tur\'{a}n number} for $\mathcal{H}$ is the maximum number of hyperedges in any $r$-uniform hypergraph on $n$ vertices containing no copy of $\mathcal{H}$. While the Tur\'{a}n numbers of graphs are well-understood and exact Tur\'{a}n numbers are known for some classes of graphs, few exact results are known for the cases $r \geq 3$. I will present a construction, using quadratic residues, for an infinite family of hypergraphs having no copy of the $4$-uniform hypergraph on $5$ vertices with $3$ hyperedges, with the maximum number of hyperedges subject to this condition. I will also describe a connection between this construction and a `switching' operation on tournaments, with applications to finding new bounds on Tur\'{a}n numbers for other small hypergraphs.

I will describe recent joint work with Jeroen Sijsling, Drew Sutherland, John Voight and Dan Yasaki on genus 2 curves over Q. Our work has three primary goals: (1) produce an extensive table of genus 2 curves and their associated invariants; (2) explain the various Sato-Tate groups that arise in terms of functoriality; (3) prove at least one example of modularity for each nongeneric Sato-Tate group. Goal (1) was achieved in arXiv:1602.03715, with the data accessible inthe LMFDB, while goals (2) and (3) are in progress.

Central to Alan Turing's posthumous reputation is his work with British codebreaking during the Second World War. This relationship is not well understood, largely because it stands on the intersection of two technical fields, mathematics and cryptology, the second of which also has been shrouded by secrecy. This lecture will assess this relationship from an historical cryptological perspective. It treats the mathematization and mechanization of cryptology between 1920-50 as international phenomena. It assesses Turing's role in one important phase of this process, British work at Bletchley Park in developing cryptanalytical machines for use against Enigma in 1940-41. It focuses on also his interest in and work with cryptographic machines between 1942-46, and concludes that work with them served as a seed bed for the development of his thinking about computers.

Turing 2012 - Calgary

This talk is part of a series celebrating the Alan Turing Centenary in Calgary. The following mathtube videos are part of this series

1. Alan Turing and the Decision Problem, Richard Zach.
2. Turing's Real Machine, Michael R. Williams.
3. Alan Turing and Enigma, John R. Ferris.

Many scientific questions are considered solved to the best possible degree when we have a method for computing a solution. This is especially true in mathematics and those areas of science in which phenomena can be described mathematically: one only has to think of the methods of symbolic algebra in order to solve equations, or laws of physics which allow one to calculate unknown quantities from known measurements. The crowning achievement of mathematics would thus be a systematic way to compute the solution to any mathematical problem. The hope that this was possible was perhaps first articulated by the 18th century mathematician-philosopher G. W. Leibniz. Advances in the foundations of mathematics in the early 20th century made it possible in the 1920s to first formulate the question of whether there is such a systematic way to find a solution to every mathematical problem. This became known as the decision problem, and it was considered a major open problem in the 1920s and 1930s. Alan Turing solved it in his first, groundbreaking paper "On computable numbers" (1936). In order to show that there cannot be a systematic computational procedure that solves every mathematical question, Turing had to provide a convincing analysis of what a computational procedure is. His abstract, mathematical model of computability is that of a Turing Machine. He showed that no Turing machine, and hence no computational procedure at all, could solve the Entscheidungsproblem.

Turing 2012 - Calgary

This talk is part of a series celebrating the Alan Turing Centenary in Calgary. The following mathtube videos are also part of this series

1. Alan Turing and the Decision Problem, Richard Zach.
2. Turing's Real Machine, Michael R. Williams.
3. Alan Turing and Enigma, John R. Ferris.