
Many important problems in combinatorics and other related areas can be
phrased in the language of independent sets in hypergraphs. Recently Balogh,
Morris and Samotij, and independently Saxton and Thomason developed very
general container theorems for independent sets in hypergraphs; both of which
have seen numerous applications to a wide range of problems. In this paper we
use the container method to give relatively short and elementary proofs of a
number of results concerning Ramsey (and Tur\'an) properties of (hyper)graphs
and the integers. In particular:
(i) We generalise the random Ramsey theorem of R\"odl and Ruci\'nski by
providing a resilience analogue. Our result unifies and generalises several
fundamental results in the area including the random version of Tur\'an's
theorem due to Conlon and Gowers and Schacht.
(ii) The above result also resolves a general subcase of the asymmetric
random Ramsey conjecture of Kohayakawa and Kreuter.
(iii) All of the above results in fact hold for uniform hypergraphs.
(iv) For a (hyper)graph $H$, we determine, up to an error term in the
exponent, the number of $n$vertex (hyper)graphs $G$ that have the Ramsey
property with respect to $H$ (that is, whenever $G$ is $r$coloured, there is a
monochromatic copy of $H$ in $G$).
(v) We strengthen the random Rado theorem of Friedgut, R\"odl and Schacht by
proving a resilience version of the result.
(vi) For partition regular matrices $A$ we determine, up to an error term in
the exponent, the number of subsets of $\{1,\dots,n\}$ for which there exists
an $r$colouring which contains no monochromatic solutions to $Ax=0$.
Along the way a number of open problems are posed.

A perfect $H$tiling in a graph $G$ is a collection of vertexdisjoint copies
of a graph $H$ in $G$ that together cover all the vertices in $G$. In this
paper we investigate perfect $H$tilings in a random graph model introduced by
Bohman, Frieze and Martin in which one starts with a dense graph and then adds
$m$ random edges to it. Specifically, for any fixed graph $H$, we determine the
number of random edges required to add to an arbitrary graph of linear minimum
degree in order to ensure the resulting graph contains a perfect $H$tiling
with high probability. Our proof utilises Szemer\'edi's Regularity lemma as
well as a special case of a result of Koml\'os concerning almost perfect
$H$tilings in dense graphs.

Cameron and Erd\H{o}s asked whether the number of \emph{maximal} sumfree
sets in $\{1, \dots , n\}$ is much smaller than the number of sumfree sets. In
the same paper they gave a lower bound of $2^{\lfloor n/4 \rfloor }$ for the
number of maximal sumfree sets. Here, we prove the following: For each $1\leq
i \leq 4$, there is a constant $C_i$ such that, given any $n\equiv i \mod 4$,
$\{1, \dots , n\}$ contains $(C_i+o(1)) 2^{n/4}$ maximal sumfree sets. Our
proof makes use of container and removal lemmas of Green, a structural result
of Deshouillers, Freiman, S\'os and Temkin and a recent bound on the number of
subsets of integers with small sumset by Green and Morris. We also discuss
related results and open problems on the number of maximal sumfree subsets of
abelian groups.

We apply the graph container method to prove a number of counting results for
the Boolean lattice $\mathcal P(n)$. In particular, we: (i) Give a partial
answer to a question of Sapozhenko estimating the number of $t$ error
correcting codes in $\mathcal P(n)$, and we also give an upper bound on the
number of transportation codes; (ii) Provide an alternative proof of Kleitman's
theorem on the number of antichains in $\mathcal P(n)$ and give a twocoloured
analogue; (iii) Give an asymptotic formula for the number of $(p,q)$tilted
Sperner families in $\mathcal P(n)$; (iv) Prove a random version of Katona's
$t$intersection theorem.
In each case, to apply the container method, we first prove corresponding
supersaturation results. We also give a construction which disproves two
conjectures of Ilinca and Kahn on maximal independent sets and antichains in
the Boolean lattice. A number of open questions are also given.

Given a linear equation $\mathcal{L}$, a set $A \subseteq [n]$ is
$\mathcal{L}$free if $A$ does not contain any `nontrivial' solutions to
$\mathcal{L}$. We determine the precise size of the largest $\mathcal{L}$free
subset of $[n]$ for several general classes of linear equations $\mathcal{L}$
of the form $px+qy=rz$ for fixed $p,q,r \in \mathbb N$ where $p \geq q \geq r$.
Further, for all such linear equations $\mathcal{L}$, we give an upper bound on
the number of maximal $\mathcal{L}$free subsets of $[n]$. In the case when
$p=q\geq 2$ and $r=1$ this bound is exact up to an error term in the exponent.
We make use of container and removal lemmas of Green to prove this result.
Our results also extend to various linear equations with more than three
variables.

Folkman's Theorem asserts that for each $k \in \mathbb{N}$, there exists a
natural number $n = F(k)$ such that whenever the elements of $[n]$ are
twocoloured, there exists a set $A \subset [n]$ of size $k$ with the property
that all the sums of the form $\sum_{x \in B} x$, where $B$ is a nonempty
subset of $A$, are contained in $[n]$ and have the same colour. In 1989,
Erd\H{o}s and Spencer showed that $F(k) \ge 2^{ck^2/ \log k}$, where $c >0$ is
an absolute constant; here, we improve this bound significantly by showing that
$F(k) \ge 2^{2^{k1}/k}$ for all $k\in \mathbb{N}$.

Given a linear equation $\mathcal{L}$, a set $A$ of integers is
$\mathcal{L}$free if $A$ does not contain any `nontrivial' solutions to
$\mathcal{L}$. This notion incorporates many central topics in combinatorial
number theory such as sumfree and progressionfree sets. In this paper we
initiate the study of (parameterised) complexity questions involving
$\mathcal{L}$free sets of integers. The main questions we consider involve
deciding whether a finite set of integers $A$ has an $\mathcal{L}$free subset
of a given size, and counting all such $\mathcal{L}$free subsets. We also
raise a number of open problems.

A famous conjecture of P\'osa from 1962 asserts that every graph on $n$
vertices and with minimum degree at least $2n/3$ contains the square of a
Hamilton cycle. The conjecture was proven for large graphs in 1996 by Koml\'os,
S\'ark\"ozy and Szemer\'edi. In this paper we prove a degree sequence version
of P\'osa's conjecture: Given any $\eta >0$, every graph $G$ of sufficiently
large order $n$ contains the square of a Hamilton cycle if its degree sequence
$d_1\leq \dots \leq d_n$ satisfies $d_i \geq (1/3+\eta)n+i$ for all $i \leq
n/3$. The degree sequence condition here is asymptotically best possible. Our
approach uses a hybrid of the RegularityBlowup method and the
ConnectingAbsorbing method.

Given a linear equation $\mathcal{L}$, a set $A \subseteq [n]$ is
$\mathcal{L}$free if $A$ does not contain any `nontrivial' solutions to
$\mathcal{L}$. In this paper we consider the following three general questions:
(i) What is the size of the largest $\mathcal{L}$free subset of $[n]$?
(ii) How many $\mathcal{L}$free subsets of $[n]$ are there?
(iii) How many maximal $\mathcal{L}$free subsets of $[n]$ are there?
We completely resolve (i) in the case when $\mathcal{L}$ is the equation
$px+qy=z$ for fixed $p,q\in \mathbb N$ where $p\geq 2$. Further, up to a
multiplicative constant, we answer (ii) for a wide class of such equations
$\mathcal{L}$, thereby refining a special case of a result of Green. We also
give various bounds on the number of maximal $\mathcal{L}$free subsets of
$[n]$ for threevariable homogeneous linear equations $\mathcal{L}$. For this,
we make use of container and removal lemmas of Green.

Given two $k$graphs $H$ and $F$, a perfect $F$packing in $H$ is a
collection of vertexdisjoint copies of $F$ in $H$ which together cover all the
vertices in $H$. In the case when $F$ is a single edge, a perfect $F$packing
is simply a perfect matching. For a given fixed $F$, it is often the case that
the decision problem whether an $n$vertex $k$graph $H$ contains a perfect
$F$packing is NPcomplete. Indeed, if $k \geq 3$, the corresponding problem
for perfect matchings is NPcomplete whilst if $k=2$ the problem is NPcomplete
in the case when $F$ has a component consisting of at least $3$ vertices.
In this paper we give a general tool which can be used to determine classes
of (hyper)graphs for which the corresponding decision problem for perfect
$F$packings is polynomial time solvable. We then give three applications of
this tool: (i) Given $1\leq \ell \leq k1$, we give a minimum $\ell$degree
condition for which it is polynomial time solvable to determine whether a
$k$graph satisfying this condition has a perfect matching; (ii) Given any
graph $F$ we give a minimum degree condition for which it is polynomial time
solvable to determine whether a graph satisfying this condition has a perfect
$F$packing; (iii) We also prove a similar result for perfect $K$packings in
$k$graphs where $K$ is a $k$partite $k$graph.
For a range of values of $\ell,k$ (i) resolves a conjecture of Keevash, Knox
and Mycroft whilst (ii) answers a question of Yuster in the negative. In many
cases our results are best possible in the sense that lowering the minimum
degree condition means that the corresponding decision problem becomes
NPcomplete.

The HajnalSzemer\'edi theorem states that for any integer $r \ge 1$ and any
multiple $n$ of $r$, if $G$ is a graph on $n$ vertices and $\delta(G) \ge (1 
1/r)n$, then $G$ can be partitioned into $n/r$ vertexdisjoint copies of the
complete graph on $r$ vertices. We prove a very general analogue of this result
for directed graphs: for any integer $r \ge 4$ and any sufficiently large
multiple $n$ of $r$, if $G$ is a directed graph on $n$ vertices and every
vertex is incident to at least $2(1  1/r)n  1$ directed edges, then $G$ can
be partitioned into $n/r$ vertexdisjoint subgraphs of size $r$ each of which
contain every tournament on $r$ vertices. A related Tur\'antype result is also
proven.

We say that a graph $G$ has a perfect $H$packing if there exists a set of
vertexdisjoint copies of $H$ which cover all the vertices in $G$. The seminal
HajnalSzemer\'edi theorem characterises the minimum degree that ensures a
graph $G$ contains a perfect $K_r$packing. Balogh, Kostochka and Treglown
proposed a degree sequence version of the HajnalSzemer\'edi theorem which, if
true, gives a strengthening of the HajnalSzemer\'edi theorem. In this paper
we prove this conjecture asymptotically. Another fundamental result in the area
is the AlonYuster theorem which gives a minimum degree condition that ensures
a graph contains a perfect $H$packing for an \emph{arbitrary} graph $H$. We
give a widereaching generalisation of this result by answering another
conjecture of Balogh, Kostochka and Treglown on the degree sequence of a graph
that forces a perfect $H$packing. We also prove a degree sequence result
concerning perfect transitive tournament packings in directed graphs. The
proofs blend together the regularity and absorbing methods.

We determine the \emph{exact} minimum $\ell$degree threshold for perfect
matchings in $k$uniform hypergraphs when the corresponding threshold for
perfect fractional matchings is significantly less than $\frac{1}{2}
\binom{n}{k \ell}$. This extends our previous results that determine the
minimum $\ell$degree thresholds for perfect matchings in $k$uniform
hypergraphs for all $\ell\ge k/2$ and provides two new (exact) thresholds:
$(k,\ell)=(5,2)$ and $(7,3)$.

Given hypergraphs $F$ and $H$, an $F$factor in $H$ is a set of
vertexdisjoint copies of $F$ which cover all the vertices in $H$. Let $K^ _4$
denote the $3$uniform hypergraph with $4$ vertices and $3$ edges. We show that
for sufficiently large $n\in 4 \mathbb N$, every $3$uniform hypergraph $H$ on
$n$ vertices with minimum codegree at least $n/21$ contains a $K^ _4$factor.
Our bound on the minimum codegree here is bestpossible. It resolves a
conjecture of Lo and Markstr\"om for large hypergraphs, who earlier proved an
asymptotically exact version of this result. Our proof makes use of the
absorbing method as well as a result of Keevash and Mycroft concerning almost
perfect matchings in hypergraphs.

We say that a (di)graph $G$ has a perfect $H$packing if there exists a set
of vertexdisjoint copies of $H$ which cover all the vertices in $G$. The
seminal HajnalSzemer\'edi theorem characterises the minimum degree that
ensures a graph $G$ contains a perfect $K_r$packing. In this paper we prove
the following analogue for directed graphs: Suppose that $T$ is a tournament on
$r$ vertices and $G$ is a digraph of sufficiently large order $n$ where $r$
divides $n$. If $G$ has minimum in and outdegree at least $ (11/r)n$ then $G$
contains a perfect $T$packing. In the case when $T$ is a cyclic triangle, this
result verifies a recent conjecture of Czygrinow, Kierstead and Molla (for
large digraphs). Furthermore, in the case when $T$ is transitive we conjecture
that it suffices for every vertex in $G$ to have sufficiently large indegree or
outdegree. We prove this conjecture for transitive triangles and asymptotically
for all $r \geq 3$. Our approach makes use of a result of Keevash and Mycroft
concerning almost perfect matchings in hypergraphs as well as the Directed
Graph Removal lemma.

In a sequence of four papers, we prove the following results (via a unified
approach) for all sufficiently large $n$:
(i) [1factorization conjecture] Suppose that $n$ is even and $D \geq 2\lceil
n/4\rceil 1$. Then every $D$regular graph $G$ on $n$ vertices has a
decomposition into perfect matchings. Equivalently, $\chi'(G)=D$.
(ii) [Hamilton decomposition conjecture] Suppose that $D \ge \lfloor n/2
\rfloor $. Then every $D$regular graph $G$ on $n$ vertices has a decomposition
into Hamilton cycles and at most one perfect matching.
(iii) [Optimal packings of Hamilton cycles] Suppose that $G$ is a graph on
$n$ vertices with minimum degree $\delta\ge n/2$. Then $G$ contains at least
${\rm reg}_{\rm even}(n,\delta)/2 \ge (n2)/8$ edgedisjoint Hamilton cycles.
Here ${\rm reg}_{\rm even}(n,\delta)$ denotes the degree of the largest
evenregular spanning subgraph one can guarantee in a graph on $n$ vertices
with minimum degree $\delta$.
According to Dirac, (i) was first raised in the 1950s. (ii) and the special
case $\delta= \lceil n/2 \rceil$ of (iii) answer questions of NashWilliams
from 1970. All of the above bounds are best possible. In the current paper, we
prove the above results for the case when $G$ is close to a complete balanced
bipartite graph.

In a sequence of four papers, we prove the following results (via a unified
approach) for all sufficiently large $n$:
(i) [1factorization conjecture] Suppose that $n$ is even and $D\geq 2\lceil
n/4\rceil 1$. Then every $D$regular graph $G$ on $n$ vertices has a
decomposition into perfect matchings. Equivalently, $\chi'(G)=D$.
(ii) [Hamilton decomposition conjecture] Suppose that $D \ge \lfloor n/2
\rfloor $. Then every $D$regular graph $G$ on $n$ vertices has a decomposition
into Hamilton cycles and at most one perfect matching.
(iii) We prove an optimal result on the number of edgedisjoint Hamilton
cycles in a graph of given minimum degree.
According to Dirac, (i) was first raised in the 1950s. (ii) and (iii) answer
questions of NashWilliams from 1970. The above bounds are best possible. In
the current paper, we show the following: suppose that $G$ is close to a
complete balanced bipartite graph or to the union of two cliques of equal size.
If we are given a suitable set of path systems which cover a set of
`exceptional' vertices and edges of $G$, then we can extend these path systems
into an approximate decomposition of $G$ into Hamilton cycles (or perfect
matchings if appropriate).

In this paper we prove the following results (via a unified approach) for all
sufficiently large $n$:
(i) [$1$factorization conjecture] Suppose that $n$ is even and $D\geq
2\lceil n/4\rceil 1$. Then every $D$regular graph $G$ on $n$ vertices has a
decomposition into perfect matchings. Equivalently, $\chi'(G)=D$.
(ii) [Hamilton decomposition conjecture] Suppose that $D \ge \lfloor n/2
\rfloor $. Then every $D$regular graph $G$ on $n$ vertices has a decomposition
into Hamilton cycles and at most one perfect matching.
(iii) [Optimal packings of Hamilton cycles] Suppose that $G$ is a graph on
$n$ vertices with minimum degree $\delta\ge n/2$. Then $G$ contains at least
${\rm reg}_{\rm even}(n,\delta)/2 \ge (n2)/8$ edgedisjoint Hamilton cycles.
Here $\text{reg}_{\text{even}}(n,\delta)$ denotes the degree of the largest
evenregular spanning subgraph one can guarantee in a graph on $n$ vertices
with minimum degree $\delta$.
(i) was first explicitly stated by Chetwynd and Hilton. (ii) and the special
case $\delta= \lceil n/2 \rceil$ of (iii) answer questions of NashWilliams
from 1970. All of the above bounds are best possible.

Let $\mathcal{P}(n)$ denote the power set of $[n]$, ordered by inclusion, and
let $\mathcal{P}(n,p)$ be obtained from $\mathcal{P}(n)$ by selecting elements
from $\mathcal{P}(n)$ independently at random with probability $p$. A classical
result of Sperner asserts that every antichain in $\mathcal{P}(n)$ has size at
most that of the middle layer, $\binom{n}{\lfloor n/2 \rfloor}$. In this note
we prove an analogous result for $\mathcal{P} (n,p)$: If $pn \rightarrow
\infty$ then, with high probability, the size of the largest antichain in
$\mathcal{P}(n,p)$ is at most $(1+o(1)) p \binom{n}{\lfloor n/2 \rfloor}$. This
solves a conjecture of Osthus who proved the result in the case when $pn/\log n
\rightarrow \infty$. Our condition on $p$ is bestpossible. In fact, we prove a
more general result giving an upper bound on the size of the largest antichain
for a wider range of values of $p$.

Cameron and Erd\H{o}s raised the question of how many maximal sumfree sets
there are in $\{1, \dots , n\}$, giving a lower bound of $2^{\lfloor n/4
\rfloor }$. In this paper we prove that there are in fact at most
$2^{(1/4+o(1))n}$ maximal sumfree sets in $\{1, \dots , n\}$. Our proof makes
use of container and removal lemmas of Green as well as a result of
Deshouillers, Freiman, S\'os and Temkin on the structure of sumfree sets.

We say that a graph G has a perfect Hpacking if there exists a set of
vertexdisjoint copies of H which cover all the vertices in G. We consider
various problems concerning perfect Hpackings: Given positive integers n, r,
D, we characterise the edge density threshold that ensures a perfect
K_rpacking in any graph G on n vertices and with minimum degree at least D. We
also give two conjectures concerning degree sequence conditions which force a
graph to contain a perfect Hpacking. Other related embedding problems are also
considered. Indeed, we give a structural result concerning K_rfree graphs that
satisfy a certain degree sequence condition.

We determine the minimum vertex degree that ensures a perfect matching in a
3uniform hypergraph. More precisely, suppose that H is a sufficiently large
3uniform hypergraph whose order n is divisible by 3. If the minimum vertex
degree of H is greater than \binom{n1}{2}\binom{2n/3}{2}, then H contains a
perfect matching. This bound is tight and answers a question of Han, Person and
Schacht. More generally, we show that H contains a matching of size d\le n/3 if
its minimum vertex degree is greater than \binom{n1}{2}\binom{nd}{2}, which
is also best possible. This extends a result of Bollobas, Daykin and Erdos.

Given positive integers k and r where 4 divides k and k/2 \leq r \leq k1, we
give a minimum rdegree condition that ensures a perfect matching in a
kuniform hypergraph. This condition is best possible and improves on work of
Pikhurko who gave an asymptotically exact result. Our approach makes use of the
absorbing method, as well as the hypergraph removal lemma and a structural
result of Keevash and Sudakov relating to the Turan number of the expanded
triangle.

Given positive integers k\geq 3 and r where k/2 \leq r \leq k1, we give a
minimum rdegree condition that ensures a perfect matching in a kuniform
hypergraph. This condition is best possible and improves on work of Pikhurko
who gave an asymptotically exact result. Our approach makes use of the
absorbing method, and builds on work in 'Exact minimum degree thresholds for
perfect matchings in uniform hypergraphs', where we proved the result for k
divisible by 4.

Boettcher, Schacht and Taraz gave a condition on the minimum degree of a
graph G on n vertices that ensures G contains every rchromatic graph H on n
vertices of bounded degree and of bandwidth o(n), thereby proving a conjecture
of Bollobas and Komlos. We strengthen this result in the case when H is
bipartite. Indeed, we give an essentially bestpossible condition on the degree
sequence of a graph G on n vertices that forces G to contain every bipartite
graph H on n vertices of bounded degree and of bandwidth o(n). This also
implies an Oretype result. In fact, we prove a much stronger result where the
condition on G is relaxed to a certain robust expansion property. Our result
also confirms the bipartite case of a conjecture of Balogh, Kostochka and
Treglown concerning the degree sequence of a graph which forces a perfect
Hpacking.