L6

One of many overlaps between logic and topology is duality: Stone duality links Boolean algebras with zero-dimensional compact Hausdorff spaces, and gives a useful topological way of describing certain phenomena in first order logic; and there are generalisations that allow one to study infinitary logics also. We will look at a couple of ways in which this duality theory is useful.'

Given vectors $V = (v_i: i \in [n]) \in R^D$, we define the $V$-intersection of $A,B \subset [n]$ to be the vector $\sum_{i \in A \cap B} v_i$. In this talk, I will discuss a new, essentially optimal, supersaturation theorem for $V$-intersections, which can be roughly stated as saying that any large family of sets contains many pairs $(A,B)$ with $V$-intersection $w$, for a wide range of $V$ and $w$. A famous theorem of Frankl and Rödl corresponds to the case $D=1$ and all $v_i=1$ of our theorem. The case $D=2$ and $v_i=(1,i)$ solves a conjecture of Kalai.

Joint work with Peter Keevash.

The Turán number of an $r$-graph $G$, denoted by $ex(n,G)$, is the maximum number of edges in an $G$-free $r$-graph on $n$ vertices. The Turán density  of an $r$-graph $G$, denoted by $\pi(G)$, is the limit as $n$ tends to infinity of the maximum edge density of an $G$-free $r$-graph on $n$ vertices.

During this talk I will discuss a method, which we call  local stability method, that allows one to obtain exact Turán numbers from Turán density results. This method can be thought of as an extension of the classical stability method by  generically utilising the Lagrangian function. Using it, we obtained new hypergraph Turán numbers. In particular, we did so for a hypergraph called generalized triangle, for uniformities 5 and 6, which solved a conjecture of Frankl and Füredi from 1980's.

This is joint work with Sergey Norin.

After mentioning, by way of motivation (mine at least), some diophantine questions concerning
sets definable in the restricted analytic, exponential field $\R_{an, exp}$, I discuss the
problem of extending a given $\R_{an, exp}$-definable function $f:(a, \infty) \to \R$ to
a holomorphic function $\hat f : \{z \in \C : Re(z) > b \} \to \C$ (for some $b > a$).
In particular, I give a necessary and sufficient condition on $f$ for such an $\hat f$ to exist and be
$\R_{an, exp}$-definable.
 

The Graham-Pollak theorem states that to decompose the complete graph $K_n$ into complete bipartite subgraphs we need at least $n-1$ of them. What
happens for hypergraphs? In other words, suppose that we wish to decompose the complete $r$-graph on $n$ vertices into complete $r$-partite $r$-graphs; how many do we need?

In this talk we will report on recent progress on this problem. This is joint work with Luka Milicevic and Ta Sheng Tan.

It follows from the ellipsoid method and results of Grotschel, Lovasz and Schrijver that one can find an optimal colouring of a perfect graph in polynomial time. But no ''combinatorial'' algorithm to do this is known.

Here we give a combinatorial algorithm to do this in an n-vertex perfect graph in time O(n^{k+1}^2) where k is the clique number; so polynomial-time for fixed k. The algorithm depends on another result, a polynomial-time algorithm to find a ''balanced skew partition'' in a perfect graph if there is one.

Joint work with Maria Chudnovsky, Aurelie Lagoutte, and Sophie Spirkl.

For a graph $G$, the $k$-colour Ramsey number $R_k(G)$ is the least integer $N$ such that every $k$-colouring of the edges of the complete graph $K_N$ contains a monochromatic copy of $G$. Let $C_n$ denote the cycle on $n$ vertices. We show that for fixed $k\geq2$ and $n$ odd and sufficiently large,
$$
R_k(C_n)=2^{k-1}(n-1)+1.
$$
This resolves a conjecture of Bondy and Erdős for large $n$. The proof is analytic in nature, the first step of which is to use the regularity method to relate this problem in Ramsey theory to one in nonlinear optimisation.  This allows us to prove a stability-type generalisation of the above and establish a correspondence between extremal $k$-colourings for this problem and perfect matchings in the $k$-dimensional hypercube $Q_k$.

In joint work with Olof Sisask, we establish new quantitative bounds for Roth's theorem on arithmetic progressions, showing that a set of integers with no three-term arithmetic progressions must have density O(1/(log N)^{1+c}) for some absolute constant c>0. This is the integer analogue of a result of Bateman and Katz for the model setting of vector spaces over a finite field, and the proof follows a similar structure.