It is easy to see that if a tournament (a complete oriented graph) has a directed cycle then it has a directed 3-cycle. We investigate the analogous question for 3-tournaments, and more generally for oriented 3-graphs.
The Erdős–Ko–Rado theorem is a central result in extremal set theory which tells us how large uniform intersecting families can be. In this talk, I shall discuss some recent results concerning the 'stability' of this result. One possible formulation of the Erdős–Ko–Rado theorem is the following: if $n \ge 2r$, then the size of the largest independent set of the Kneser graph $K(n,r)$ is $\binom{n-1}{r-1}$, where $K(n,r)$ is the graph on the family of $r$-element subsets of $\{1,\dots,n\}$ in which two sets are adjacent if and only if they are disjoint. The following will be the question of interest. Delete the edges of the Kneser graph with some probability, independently of each other: is the independence number of this random graph equal to the independence number of the Kneser graph itself? I shall discuss an affirmative answer to this question in a few different regimes. Joint work with Bollobás and Raigorodskii, and Balogh and Bollobás.
This is an exciting time to study quantum algorithms. As the technological challenges of building a quantum computer continue to be met there is still much to learn about the power of quantum computing. Understanding which problems a quantum computer could solve faster than a classical device and which problems remain hard is particularly relevant to cryptography. We would like to design schemes that are secure against an adversary with a quantum computer. I'll give an overview of the quantum computing that is accessible to a general audience and use a recently declassified project called "soliloquy" as a case study for the development (and breaking) of post-quantum cryptography.
The prime number race is the competition between different coprime residue classes mod $q$ to contain the most primes, up to a point $x$ . Rubinstein and Sarnak showed, assuming two $L$-function conjectures, that as $x$ varies the problem is equivalent to a problem about orderings of certain random variables, having weak correlations coming from number theory. In particular, as $q \rightarrow \infty$ the number of primes in any fixed set of $r$ coprime classes will achieve any given ordering for $\sim 1/r!$ values of $x$. In this talk I will try to explain what happens when $r$ is allowed to grow as a function of $q$. It turns out that one still sees uniformity of orderings in many situations, but not always. The proofs involve various probabilistic ideas, and also some harmonic analysis related to the circle method. This is joint work with Youness Lamzouri.
Suppose that we have a tile $T$ in say $\mathbb{Z}^2$, meaning a finite subset of $\mathbb{Z}^2$. It may or may not be the case that $T$ tiles $\mathbb{Z}^2$, in the sense that $\mathbb{Z}^2$ can be partitioned into copies of $T$. But is there always some higher dimension $\mathbb{Z}^d$ that can be tiled with copies of $T$? We prove that this is the case: for any tile in $\mathbb{Z}^2$ (or in $\mathbb{Z}^n$, any $n$) there is a $d$ such that $\mathbb{Z}^d$ can be tiled with copies of it. This proves a conjecture of Chalcraft.
In the Erdös-Rényi random graph process, starting from an empty graph, in each step a new random edge is added to the evolving graph. One of its most interesting features is the `percolation phase transition': as the ratio of the number of edges to vertices increases past a certain critical density, the global structure changes radically, from only small components to a single giant component plus small ones.
In this talk we consider Achlioptas processes, which have become a key example for random graph processes with dependencies between the edges.
Starting from an empty graph these proceed as follows: in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. We discuss why, for a large class of rules, the percolation phase transition is qualitatively comparable to the classical Erdös-Rényi process.
Based on joint work with Oliver Riordan.
The celebrated strong cosmic censorship conjecture in general relativity in particular suggests that the Cauchy horizon in the interior of the Kerr black hole is unstable and small perturbations would give rise to singularities. We present a recent result proving that the Cauchy horizon is stable in the sense that spacetime arising from data close to that of Kerr has a continuous metric up to the Cauchy horizon. We discuss its implications on the nature of the potential singularity in the interior of the black hole. This is joint work with Mihalis Dafermos.