\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.3}{22(4)}{2015}

\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\newcommand\B{\mathcal{B}}
\newcommand\es{\varnothing}
\newcommand\IA{\mathcal{I}(\A)}
\newcommand\IAm{\mathcal{I}_m(\A)}
\newcommand\ksets{\binom{[n]}{k}}
\newcommand\E{\mathbb{E}}
\newcommand\Q{\mathcal{Q}}
\newcommand\F{\mathcal{F}}
\newcommand\tr{\textrm}
\newcommand\ex{\tr{ex}}
\newcommand\mc{\mathcal}
\newcommand\qn{\mc{Q}_n}
\newcommand\prf{\emph{Proof: }}
\newcommand\qed{$\hfill\Box$}
\newcommand\pic{\lambda}
\newcommand\supp{\tr{supp}}
\usepackage{amsmath,amssymb,enumitem}

\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{question}[thm]{Question}
\newtheorem{con}[thm]{Conjecture}


\title{\bf An exact Tur\'an result for tripartite 3-graphs}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Adam Sanitt\\
\small Department of Mathematics\\[-0.8ex]
\small University College London\\[-0.8ex]
\small WC1E 6BT, United Kingdom\\
\small\tt adam@sanitt.com\\
\and John Talbot\\
\small Department of Mathematics\\[-0.8ex]
\small University College London\\[-0.8ex]
\small WC1E 6BT, United Kingdom\\
\small\tt j.talbot@ucl.ac.uk
}



\date{\dateline{Apr 22, 2015}{Sep 21, 2015}{Oct 16, 2015}\\}

\begin{document}

\maketitle


\begin{abstract}
Mantel's theorem says that among all triangle-free graphs of a given order the balanced complete bipartite graph is the unique graph of maximum size. We prove an analogue of this result for 3-graphs.   Let $K_4^-=\{123,124,134\}$, $F_6=\{123,124,345,156\}$ and $\mathcal{F}=\{K_4^-,F_6\}$: for $n\neq 5$ the unique $\mathcal{F}$-free 3-graph of order $n$ and maximum size is the balanced complete tripartite 3-graph $S_3(n)$ (for $n=5$ it is $C_5^{(3)}=\{123,234,345,145,125\}$). This extends an old result of Bollob\'as that $S_3(n) $ is the unique 3-graph of maximum size with no copy of $K_4^-=\{123,124,134\}$ or $F_5=\{123,124,345\}$. 
\end{abstract}


\section{Introduction}
If $r\geq 2$ then an \emph{$r$-graph} $G$ is a pair $G=(V(G),E(G))$, where $E(G)$ is a collection of $r$-sets from $V(G)$. The elements of $V(G)$ are called \emph{vertices} and the $r$-sets in $E(G)$ are called \emph{edges}. The number of vertices is the \emph{order} of $G$, while the number of edges, denoted by $e(G)$, is the \emph{size} of $G$.


Given a family of $r$-graphs $\F$, an $r$-graph $G$ is \emph{$\F$-free} if it does not contain a subgraph isomorphic to any member of $\F$. For an integer $n\geq r$ we define the \emph{Tur\'an number of $\F$} to be 
\[
\ex(n,\F)=\max\{e(G):G\tr{ an $\F$-free $r$-graph of order $n$}\}.\]
The related asymptotic \emph{Tur\'an density} is the following limit
(an averaging argument due to Katona, Nemetz and Simonovits \cite{KNS}
shows that it always exists)
\[
\pi\left(\mathcal{F}\right)=\lim_{n\rightarrow\infty}\frac{\textrm{ex}\left(n,\mathcal{F}\right)}{\binom{n}{r}}.
\]


The problem of determining the Tur\'an density is essentially solved
for all 2-graphs by the Erd\H os--Stone--Simonovits Theorem.
\begin{thm}[Erd\H os and Stone \cite{ESt}, Erd\H os and Simonovits \cite{ESi}]
Let $\mathcal{F}$ be a family of 2-graphs. If $t=\min\left\{ \chi(F)\,:\, F\in\mathcal{F}\right\} \geq2$,
then
\[
\pi\left(\mathcal{F}\right)=\frac{t-2}{t-1}.
\]
\end{thm}
It follows that the set of all\emph{ }Tur\'an densities for 2-graphs
is $\{0,1/2,2/3,3/4,\ldots\}$.

There is no analogous result for $r\geq3$ and most progress has been
made through determining the Tur\'an densities of individual graphs
or families of graphs. A central problem, originally posed by Tur\'an,
is to determine $\ex(n,K_{4}^{(3)})$, where $K_{4}^{(3)}=\{123,124,134,234\}$ is
the complete 3-graph of order 4. This is a natural extension of
determining the Tur\'an number of the triangle for 2-graphs, a question
answered by Mantel's theorem \cite{M}. Tur\'an gave a construction that he conjectured to be optimal that has density
$5/9$ but this question remains unanswered despite a great deal of
work. The current best upper bound for $\pi(K_4^{(3)})$ is $0.561666$, given by Razborov \cite{R4}.

A related problem due to Katona is given by considering cancellative hypergraphs. A hypergraph $H$ is \emph{cancellative} if for any distinct edges $a,b\in H$, there is no edge $c\in H$ such that $a\triangle b\subseteq c$ (where $\triangle$ denotes the symmetric
difference). For 2-graphs, this is equivalent to forbidding all triangles.
For a 3-graph, it is equivalent to forbidding the two non-isomorphic
configurations $K_{4}^{-}=\{123,124,134\}$ and $F_{5}=\{123,124,345\}$.


An $r$-graph $G$ is \emph{$k$-partite} if there is a partition of its vertices into $k$ classes so that all edges of $G$ contain at most one vertex from each class. It is \emph{complete $k$-partite} if there is a partition into $k$ classes such that all edges meeting each class at most once are present. If the partition of the vertices of a complete $k$-partite graph is into classes that are as equal as possible in size then we say that $G$ is \emph{balanced}.

Let $S_3(n)$ be the complete balanced tripartite 3-graph of order $n$.
\begin{thm}[Bollob\'as \cite{B}]\label{bol:thm}
For $n\geq 3$, $S_3(n)$ is the unique cancellative 3-graph of order $n$ and maximum size.
\end{thm}
This result was refined by Frankl and F\"uredi \cite{FF} and
Keevash and Mubayi \cite{KM}, who proved that $S_3(n)$ is
the unique $F_5$-free 3-graph of order $n$ and maximum size, for
 $n$ sufficiently large.
%for $n\geq33$.%; that is, $\textrm{ex}\left(n,F_{5}\right)=s_3(n)$ for $n\geq33$.

The \emph{blow-up} of an $r$-graph $H$ is the $r$-graph $H(t)$ obtained from $H$ by
replacing each vertex $a\in V(H)$ with a set of $t$ vertices $V_{a}$
in $H(t)$ and inserting a complete $r$-partite $r$-graph between any $r$ vertex classes corresponding to an edge in $H$. The following result is an invaluable
tool in determining the Tur\'an density of an $r$-graph that is contained in the blow-ups of other $r$-graphs:
\begin{thm}[Brown and Simonovits \cite{BS}, \cite{BT}]
\label{thm:blowup}If $F$ is a $k$-graph that is contained in a blow-up of every member of a family of $k$-graphs $\mathcal{G}$, then $\pi\left(F\right)=\pi\left(F\cup\mathcal{G}\right)$.
\end{thm}
Since $F_5$ is contained in $K_4^-(2)$, Theorems \ref{bol:thm} and \ref{thm:blowup} imply that $\pi(F_5)=2/9$.

A natural question to ask is which $3$-graphs (that are not subgraphs of blow-ups of $F_5$) also have Tur\'an density $2/9$? Baber and Talbot \cite{BT} considered the 3-graph $F_{6}=\{123,124,345,156\}$,
which is not contained in any blow-up of $F_{5}$. Using Razborov's
flag algebra framework \cite{RF}, they gave a computational
proof that $\pi\left(F_{6}\right)=2/9$. In this paper,
we obtain a new (non-computer) proof of this result. In fact we go further and determine the exact Tur\'an number of $\F=\{F_6,K_4^-\}$. %implies that $\pi\left(F_{6}\right)=\pi(\mathcal{F})$, where $\mathcal{F}=\left\{ K_{4}^{-},F_{6}\right\} $.
%Accordingly, we work throughout with the family $\mathcal{F}$. 
%We will first prove the Tur\'an number for $\mathcal{F}$:
\begin{thm}\label{main:thm}If $n\geq3$
then the unique $\mathcal{F}$-free 3-graph with $\textrm{ex}(n,\mathcal{F})$
edges and $n$ vertices is $S_3(n)$ unless $n=5$ in which case
it is $C_{5}^{(3)}=\{123,234,345,145,125\}$. \end{thm}
As $F_{6}$ is contained in $K_{4}^{-}(2)$, we have the following corollary to Theorem \ref{main:thm}.
\begin{cor}\label{thm:f6turan}$\pi\left(F_{6}\right)=2/9$.\end{cor}


%Let $S_3(n)$ be the complete balanced 3-partite 3-graph of order $n$. Define $K_4^-=\{123,124,134\}$, $F_6=\{123, 124, 345, 156\}$, $C_5^{(3)}=\{123,124,125,345\}$ and set $\F=\{K_4^-,F_6\}$. 
%Our main result determines the exact Tur\'an number of $\F=\{F_6,K_4^-\}$. %implies that $\pi\left(F_{6}\right)=\pi(\mathcal{F})$, where $\mathcal{F}=\left\{ K_{4}^{-},F_{6}\right\} $.
%\begin{thm}\label{main:thm}
%If $n\geq 3$ then the unique $\F$-free 3-graph with $\ex(n,\F)$ edges and $n$ vertices is $S_3(n)$ unless $n=5$ in which case it is $C_5^{(3)}$. 
%\end{thm}



%The \emph{blow-up} of a $k$-graph $H$ is the $k$-graph $H(t)$ obtained from $H$ by
%replacing each vertex $a\in V(H)$ with a set of $t$ vertices $V_{a}$
%in $H(t)$ and inserting a complete $k$-partite $k$-graph between any $k$ vertex classes corresponding to an edge in $H$. The following result is an invaluable
%tool in determining the Tur\'an density of a $k$-graph that is contained in the blow-ups of other $k$-graphs:
%\begin{thm}[Brown and Simonovits \cite{BS}, \cite{BT}]
%\label{thm:blowup}If $F$ is a $k$-graph that is contained in a blow-up of every member of a family of $k$-graphs $\mathcal{G}$, then $\pi\left(F\right)=\pi\left(F\cup\mathcal{G}\right)$.
%\end{thm}
%Baber and Talbot considered the 3-graph $F_{6}=\{123,124,125,345,156\}$,
%which is not contained in a blow-up of $F_{5}$. Using Razborov's
%flag algebra framework \cite{RF}, they gave a computational
%proof that $\pi\left(F_{6}\right)=2/9$. In this paper,
%we obtain a new (non-computer) proof of this result. 


%As $F_{6}$ is contained in blow-ups of $K_{4}^{-}$, Theorem \ref{thm:blowup} then yields $\pi(F_6)$.
%\begin{cor}\label{thm:f6turan}$\pi\left(F_{6}\right)=2/9$.\end{cor}

%We also obtain a corresponding stability result. 
%\begin{thm}\label{thm:stabilityfsix}For any $\epsilon>0$ there
%exist $\delta>0$ and $n_{0}$ such that the following holds: if
%$H$ is an $\mathcal{F}$-free 3-graph of order $n\geq n_{0}$ with
%at least $\left(1-\delta\right)s_3(n)$ edges, then there is a partition
%of the vertex set of $H$ as $V(H)=U_{1}\cup U_{2}\cup U_{3}$ so
%that all but at most $\epsilon n^{3}$ edges of $H$ have one vertex
%in each $U_{i}$.\end{thm}


\section{Tur\'an number}
\emph{Proof of Theorem \ref{main:thm}:} The underlying proof structure is the same as that employed by Keevash and Mubayi \cite{KM} in their proof of Bollob\'as's theorem (Theorem \ref{bol:thm}). 

We use induction on $n$. Note that the result holds trivially for $n=3,4$. For $n=5$ it is straightforward to check that the only $\F$-free 3-graphs with 4 edges are $S_3(5)$, $\{123,124,125,345\}$ and $\{123,234,345,451\}$. Of these the first two are edge maximal while the third can be extended by a single edge to give $C_5^{(3)}$. Thus we may suppose that $n\geq 6$ and the theorem is true for $n-3$. 


For $k\geq 2$ let $T_k(n)$ be the $k$-partite Tur\'an graph of order $n$: this is the complete balanced $k$-partite graph. We denote the number of edges in $S_3(n)$ and $T_k(n)$ by $s_3(n)$ and $t_k(n)$ respectively. 
Let $G$ be $\F$-free with $n\geq 6 $ vertices and $\ex(n,\F)$ edges. Since $S_3(n)$ is $\F$-free we have $e(G)\geq s_3(n)$.

The inductive step proceeds as follows: select a special edge $abc\in E(G)$ (precisely how we choose this edge will be explained in Lemma \ref{key:lem} below). For $0\leq i \leq 3$ let $f_i$ be the number of edges in $G$ meeting $abc$ in exactly $i$ vertices. By our inductive hypothesis we have
\begin{equation}\label{ind1:eq}
e(G)=f_0+f_1+f_2+f_3\leq\ex(n-3,\F)+f_1+f_2+1.\end{equation}
Note that unless $n-3=5$ our inductive hypothesis says that $\ex(n-3,\F)=s_3(n-3)$ with equality iff $G-\{a,b,c\}=S_3(n-3)$. For the moment we will assume that $n\neq 8$ and so we have the following bound 
\begin{equation}\label{s3:eq}
e(G)\leq s_3(n-3)+f_1+f_2+1,
\end{equation}
with equality iff $G-\{a,b,c\}=S_3(n-3)$.

Let $V^-=V(G)-\{a,b,c\}$. For each pair $xy\in \{ab,ac,bc\}$ define $\Gamma_{xy}=\{z\in V^-:xyz\in E(G)\}$ and let $\Gamma_{abc}=\Gamma_{ab}\cup \Gamma_{ac}\cup\Gamma_{bc}$ be the \emph{link-neighbourhood} of $abc$. Note that since $G$ is $K_4^-$-free this is a disjoint union, so \[
f_2=|\Gamma_{ab}|+|\Gamma_{ac}|+|\Gamma_{bc}|=|\Gamma_{abc}|.\] 

For  $x\in \{a,b,c\}$ define $L(x)$ to be the \emph{link-graph of $x$}, so $V(L(x))=V^-$ and $E(L(x))=\{yz\subset V^-:xyz\in E(G)\}$. The \emph{link-graph of the edge $abc$} is  the edge labelled graph $L_{abc}$ with vertex set $V^-$ and edge set $L(a)\cup L(b) \cup L(c)$. The label of an edge $yz\in E(L_{abc})$ is $l(yz)=\{x\in \{a,b,c\}:xyz\in E(G)\}$. The \emph{weight} of an edge $yz\in L_{abc}$ is $|l(yz)|$ and the weight of $L_{abc}$ is $w(L_{abc})=\sum_{yz\in L_{abc}}|l(yz)|$. Note that  $f_1=w(L_{abc})$. To ease our presentation we will express the label of an edge as, for example, $ab$ rather than $\{a,b\}$.


By a subgraph of $L_{abc}$ we mean an ordinary subgraph of the underlying graph where the labels of edges are non-empty subsets of the labels of the edges in $L_{abc}$. For example if $xy\in E(L_{abc})$ has $l(xy)=ab$ then in any subgraph of $L_{abc}$ containing the edge $xy$ it must have label $a,b$ or $ab$.


%A copy of $K_4$ in $L_{abc}$ is rainbow if its edges are labelled $a,a,b,b,c,c$ and no two edges with the same label meet (i.e. iff all the triangles it contains are rainbow). 
A triangle in $L_{abc}$ is said to be \emph{rainbow} iff all its edges have weight one and are labelled $a,b,c$. Given an edge labelled subgraph $H$ of $L_{abc}$ and an (unlabelled) graph $G$ we say that $H$ is a \emph{rainbow} $G$ if all of the edges in $H$ have weight 1 and all the triangles in $H$ are rainbow.

The following lemma provides our choice of edge $abc$.
\begin{lemma}\label{key:lem}If $G$ is an $\F$-free 3-graph with $n\geq 6$ vertices and $\ex(n,\F)$ edges then there is an edge $abc\in E(G)$ such that
\[
f_1+f_2=w(L_{abc})+|\Gamma_{abc}|\leq t_3(n-3)+n-3,
\]
with equality iff $L_{abc}$ is a rainbow $T_3(n-3)$ and $\Gamma_{abc}=V^-$.
\end{lemma}

Underlying all our analysis are some simple facts regarding $\mc{F}$-free 3-graphs that are contained in Lemmas \ref{ax:lem} and \ref{struct1:lem}.
\begin{lemma}\label{ax:lem} If $G$ is $\F$-free and $abc\in E(G)$ then the following configurations cannot appear as subgraphs of $L_{abc}$. Moreover any configuration that can be obtained from one described below by applying a permutation to the labels $\{a,b,c\}$ must also be absent.
\begin{enumerate}[leftmargin=1.5cm]
\item[($F_6$-1)] The triangle $xy,xz,yz$ with $l(xy)=l(xz)=a$ and $l(yz)=b$.
\item[($F_6$-2)] The pair of edges $xy,xz$ with $l(xy)=ab$ and $l(xz)=c$.
\item[($F_6$-3)] A vertex $x\in \Gamma_{ab}$ and edges $xy,yz$ with labels $l(xy)=c$ and $l(yz)=a$.
\item[($F_6$-4)] A vertex $x\in \Gamma_{ab}$ and edges $xy,yz,zw$ with labels $l(xy)=l(zw)=a$ and $l(yz)=b$.
\item[($F_6$-5)] Vertices $x\in \Gamma_{ac},y\in \Gamma_{bc},z\in \Gamma_{ab}$ and the edge $xy$ with label $l(xy)=b$.
\item[($K_4^-$-1)] The triangle $xy,xz,yz$ with $l(xy)=l(xz)=l(yz)=a$.
\item[($K_4^-$-2)] The vertex $x\in \Gamma_{ab}$ and edge $xy$ with label $l(xy)=ab$.
\item[($K_4^-$-3)] The vertices $x,y\in \Gamma_{ab}$ and edge $xy$ with label $l(xy)=a$.
\end{enumerate}
\end{lemma}
\begin{lemma}\label{struct1:lem}If $G$ is $\F$-free and  $abc\in E(G)$ then the link-graph and link-neighbourhood satisfy:
\begin{enumerate}%[leftmargin=1cm]
\item[(i)] The only triangles in $L_{abc}$ are rainbow.
\item[(ii)] The only $K_4$s in $L_{abc}$ are rainbow.  
\item[(iii)] $L_{abc}$ is $K_5$-free.
\item[(iv)] If $xy\in E(L_{abc})$ has $l(xy)=abc$ then $x$ and $y$ meet no other edges in $L_{abc}$ and $x,y \not\in \Gamma_{abc}$.
\item[(v)] If $V_{abc}^4=\{x\in V^-:\tr{there is a $K_4$ containing $x$}\}$ 
then $\Gamma_{abc}\cap V_{abc}^4=\varnothing$.
\item[(vi)] There are no edges in $L_{abc}$ between $\Gamma_{abc}$ and $V_{abc}^4$.
\item[(vii)] If $x\in V_{abc}^4$ then $|l(xy)|\leq 1$ for all $y\in V^-$.
\item[(viii)] If $x\in \Gamma_{ac}$, $y\in \Gamma_{bc}$ and $l(xy)=ab$, then $\Gamma_{bc}=\varnothing$. Moreover, if $xz\in E(L_{abc})$ with $z\neq y$ then $z\not\in \Gamma_{abc}$ and $l(xz)=a$, while if $yz\in E(L_{abc})$ with $z\neq x$ then $z\not\in \Gamma_{abc}$ and $l(yz)=b$.
\item[(ix)] If $xy,xz\in E(L_{abc})$, $l(xy)=ab$ and $z\in \Gamma_{abc}$ then $|l(xz)|\leq 1$.
\end{enumerate}
\end{lemma} 

We also require the following identities, that are easy to verify. 
\begin{lemma}\label{id:lem}
If $n\geq k \geq 3$ then
\begin{itemize}
\item[(i)] $s_3(n)=s_3(n-3)+t_3(n-3)+n-2$.
\item[(ii)]$t_3(n)=t_3(n-3)+2n-3$.
\item[(iii)]$t_3(n)=t_3(n-2)+n-1+\lfloor n/3\rfloor$.
\item[(iv)]$t_k(n)=t_k(n-1)+n-\lceil n/k\rceil.$
\end{itemize}
\end{lemma}
Let $abc\in E(G)$ be a fixed edge given by Lemma \ref{key:lem}.

By assumption $e(G)\geq s_3(n)$ so Lemma \ref{id:lem}  (i) and Lemma \ref{key:lem} together with the bound on $e(G)$ given by (\ref{s3:eq}) imply that $e(G)=s_3(n)$ and hence $G-\{a,b,c\}=S_3(n-3)$, $L_{abc}$ is a rainbow $T_3(n-3)$ and $\Gamma_{abc}=V^-$. 
To complete the proof we need to show that $G=S_3(n)$. First note that since $L_{abc}$ is a rainbow $T_3(n-3)$ and $\Gamma_{abc}=V^-$, Lemma \ref{struct1:lem} (i) and Lemma \ref{ax:lem}($F_6$-3) imply that no vertex in $\Gamma_{ab}$ is in an edge with label $c$ and similarly for $\Gamma_{ac},\Gamma_{bc}$. Hence $L_{abc}$ is the complete tripartite graph with vertex classes $\Gamma_{ab}$, $\Gamma_{ac}$ and $\Gamma_{bc}$ and the edges between any two parts are labelled with the common label of the parts (e.g.~all edges from $\Gamma_{ab}$ to $\Gamma_{ac}$ receive label $a$). So $L_{abc}$ is precisely the link graph of an edge $abc\in S_3(n)$.


In order to deduce that $G=S_3(n)$ we need to show that $G-\{a,b,c\}=S_3(n-3)$ has the same tripartition as $L_{abc}$. This is straightforward: any edge $xyz\in E(G-\{a,b,c\})$ not respecting the tripartition of $L_{abc}$ meets one of the parts at least twice. But if $x,y,z \in \Gamma_{ab}$ then $|\Gamma_{ac}|\geq 2$ so let $u\in \Gamma_{ac}$. Setting $a=1,b=2,x=3,y=4,z=5,u=6$ gives a copy of $F_6$.  If $x,y\in \Gamma_{ab}$ and $z\in \Gamma_{ac}$ then $a=1,x=3,y=4,z=2$ gives a copy of $K_4^-$.

Hence $G=S_3(n)$ and the proof is complete in the case $n\neq 8$.

For $n=8$ we note that if $G-\{a,b,c\}$ is $F_5$-free then Theorem \ref{bol:thm} implies that the result follows as above, so we may assume that $G-\{a,b,c\}$ contains a copy of $F_5$. In this case it is sufficent to show that $e(G)\leq 17 <18 =s_3(8)$.

If $V(G-\{a,b,c\})=\{s,t,u,v,w\}$ then we may suppose that $stu, stv,uvw, abc \in G$. Since $G$ is $K_4^-$-free it does not contain $suv$ or $tuv$. Moreover it contains at most 3 edges from $\{u,v,w\}^{(2)}\times\{a,b,c\}$ and at most 5 edges from $\{s,t,u,v,w\}\times \{a,b,c\}^{(2)}$. Since $G$ is $F_6$-free it contains no edges from $\{s,t\}\times \{w\}\times\{a,b,c\}$. 

The only potential edges we have yet to consider are those in  $\{st,su,tu,sv,tv\}\times\{w,a,b,c\}$. Since $G$ is $K_4^-$-free it contains at most 2 edges from $std,sud,tud,svd,tvd$, for any $d\in \{w,a,b,c\}$. Moreover, since $G$ is $F_6$-free, if it contains 2 such edges for a fixed $d$ then it can contain at most 3 such edges in total for the other choices of $d$. Hence at most 5 such edges are present.

Thus in total $e(G)\leq 4+ 3 +5 +5=17$, as required.
\qed


In order to prove Lemma \ref{key:lem} we first need an edge with large link-neighbourhood.
\begin{lemma}\label{edge:lem}If $G$ is $K_4^-$-free 3-graph of order $n$ with $s_3(n)$ edges, then there is an edge $abc\in E(G)$ with $|\Gamma_{abc}|\geq n-\lfloor n/3\rfloor-3$.
\end{lemma}
\emph{Proof of Lemma \ref{edge:lem}:} 
Let $G$ be $K_4^-$-free with $n$ vertices and $s_3(n)$ edges. For $x,y\in V(G)$ let $d_{xy}=|\{x:xyz\in E(G)\}$. If $uvw\in E(G)$ then $\Gamma_{uvw}=\Gamma_{uv}\cup\Gamma_{uw}\cup \Gamma_{vw}$ is a union of pairwise disjoint sets and $|\Gamma_{uvw}|=d_{uv}+d_{uw}+d_{vw}-3$. Thus if the lemma fails to hold then for every edge $uvw\in E(G)$ we have $d_{uv}+d_{uw}+d_{vw}\leq n-\lfloor n/3\rfloor -1$. Note that since $\sum_{xy\in \binom{V}{2}}d_{xy}=3e(G)$, convexity implies that
\[
e(G)(n-\left\lfloor \frac{n}{3}\right\rfloor -1)\geq\sum_{uvw\in E(G)}d_{uv}+d_{uw}+d_{vw}=\sum_{xy\in \binom{V}{2}}d_{xy}^2\geq \frac{9e^2(G)}{\binom{n}{2}}.\]
Thus
\[
e(G)\leq \frac{1}{18}n(n-1)(n-\lfloor n/3\rfloor -1).\]
But it is easy to check that this is less than $s_3(n)$. \qed





Our next objective is to describe various properties of the link-graph $L_{abc}$ and link-neighbourhood $\Gamma_{abc}$. 


Lemma \ref{struct1:lem} (v) allows us to partition the vertices of $L_{abc}$ as $V^-=\Gamma_{abc}\cup V_{abc}^4\cup R_{abc}$, where $V_{abc}^4=\{x\in V^-:\tr{there is a $K_4$ containing $x$}\}$ and $R_{abc}=V^--(\Gamma_{abc}\cup V_{abc}^4)$. To prove Lemma \ref{key:lem} we require the following result to deal with the part of $L_{abc}$ not meeting any copies of $K_4$.
\begin{lemma}\label{work:lem} Let $H$ be a subgraph of $L_{abc}$ with $s\geq 3$ vertices satisfying $V(H)\cap V_{abc}^4=\varnothing$. If $H_\Gamma=V(H)\cap \Gamma_{abc}$ and $|H_\Gamma|\geq s-\lfloor s/3\rfloor -1$ then \[
w(H)+|H_\Gamma|\leq t_3(s)+s,\] with equality iff $H_\Gamma=V(H)$ and $H$ is a rainbow $T_3(s)$.
\end{lemma}
\emph{Proof of Lemma \ref{key:lem}:} Let $G$ be $\F$-free with $n\geq 6$ vertices and $\ex(n,\F)$ edges. By Lemma \ref{edge:lem} we can choose  an edge $abc\in E(G)$ such that $|\Gamma_{abc}|\geq n-\lfloor n/3 \rfloor -3$. Let $V^-=\Gamma_{abc}\cup R_{abc}\cup V_{abc}^4$ be the partition of $V^-$ given by Lemma \ref{struct1:lem} (v). If $s=|V^-|$, $j=|\Gamma_{abc}|$, $k=|R_{abc}|$ and $l=|V_{abc}^4|$ then $n-3=s=j+k+l$ and $j\geq s-\lfloor s/3\rfloor-1\geq j+k-\lfloor(j+k)/3\rfloor-1$. We can apply Lemma \ref{work:lem} to $H=L_{abc}[\Gamma_{abc}\cup R_{abc}]$, to deduce that \[
w(L_{abc}[\Gamma_{abc}\cup R_{abc}])+|\Gamma_{abc}|\leq t_3(j+k)+j+k,\] with equality iff $R_{abc}=\varnothing$ and $L_{abc}[\Gamma_{abc}]$ is a rainbow $T_3(j+k)$. Now if $L_{abc}$ is $K_4$-free then $V_{abc}^4=\varnothing$ and the proof is complete, so suppose there is a $K_4$ in $L_{abc}$. In this case $4\leq |V_{abc}^4|\leq n-3-|\Gamma_{abc}|\leq \lfloor n/3\rfloor$, so $n\geq 12$.

We now need to consider the edges in $L_{abc}$ meeting $V_{abc}^4$. By Lemma \ref{struct1:lem} (iii) we know that $L_{abc}$ is $K_5$-free, while Lemma \ref{struct1:lem} (vii) says that $V_{abc}^4$ meets no edges of weight 2 or 3, so by Tur\'an's theorem $w(L_{abc}[V_{abc}^4])\leq t_4(l)$. 

Lemma \ref{struct1:lem} (vi) implies that there are no edges from $\Gamma_{abc}$ to $V_{abc}^4$ so the total weight of edges between $\Gamma_{abc}\cup R_{abc}$ and $V_{abc}^4$ is at most $kl$.  Thus
\[
w(L_{abc})+|\Gamma_{abc}|\leq t_3(j+k)+j+k+t_4(l)+kl.\] Finally Lemma \ref{k4:lem} with $s=n-3$ implies that
\[
w(L_{abc})+|\Gamma_{abc}|\leq t_3(n-3)+n-3,\] with equality iff $R_{abc}=V_{abc}^4=\varnothing$ and $L_{abc}$ is a rainbow $T_3(n-3)$ as required. \qed
\begin{lemma}\label{k4:lem}If $j,k,l\geq 0$ are integers satisfying $j+k+l=s\geq 5$ and $j\geq s-\lfloor s/3\rfloor -1$ then
\begin{equation}\label{k4:eq}
t_3(j+k)+t_4(l)+j+k+kl\leq t_3(s)+s,\end{equation}
with equality iff $l=0$.
\end{lemma}
\emph{Proof of Lemma \ref{k4:lem}:}
If $l=0$ then the result clearly holds, so suppose that $l\geq 1$, $j+k+l=s\geq 5$ and $j\geq s-\lfloor s/3 \rfloor -1$. Let $f(j,k,l)$ be the LHS of (\ref{k4:eq}).  We need to check that $\Delta(j,k,l)=f(j,k+1,l-1)-f(j,k,l)>0$. Since if this holds then we have
\[
f(j,k,l)<f(j,k+1,l-1)<\cdots<f(j,k+l,0)=t_3(s)+s.\]
Using Lemma \ref{id:lem} (iv) we have
\begin{eqnarray*}
\Delta(j,k,l)&=&j-\lceil (j+k+1)/3\rceil +\lceil l/4\rceil+1\\
& = & j+\lceil l/4\rceil-\lfloor (j+k)/3\rfloor.
\end{eqnarray*}
So it is sufficient to check that $j+l/4>(j+k)/3$. This follows easily from $j\geq s-\lfloor s/3\rfloor -1$,  $k\leq \lfloor s/3\rfloor +1$, $l\geq 1$ and $s\geq 5$.\qed

\emph{Proof of Lemma \ref{work:lem}:}
We prove this by induction on $s\geq 3$. 
The result holds for $s=3,4$ (see the end of this proof for the tedious details) so suppose that $s\geq 5$ and the result holds for $s-2$.

Let $H$ be a subgraph of $L_{abc}$ with $s\geq 5$ vertices satisfying $V(H)\cap V_{abc}^4=\varnothing$. Let $H_\Gamma=V(H)\cap \Gamma_{abc}$ and suppose that $|H_\Gamma|\geq s-\lfloor s/3\rfloor -1$. 

Note that if $H$ contains no edges of weight 2 or 3 then the result follows directly from Tur\'an's theorem and Lemma \ref{struct1:lem} (i), so we may suppose there are edges of weight 2 or 3. With this assumption it is sufficient  to show that 
\[
w(H)+|H_\Gamma|\leq t_3(s)+s-1.\]
By Lemma \ref{id:lem} (iii) this is equivalent to showing that the following inequality holds:
\begin{equation}\label{ind:eq}
w(H)+|H_\Gamma|\leq t_3(s-2)+2s-2+\lfloor s/3 \rfloor
\end{equation} 
\textbf{Case (i):} There exists an edge of weight 3, $l(xy)=abc$.

Lemma \ref{struct1:lem} (iv) implies that $x,y\not\in H_{\Gamma}$ and $x,y$ meet no other edges in $H$, so we can apply the inductive hypothesis to $H'=H-\{x,y\}$ to obtain
\[
w(H)+|H_\Gamma|\leq w(H')+|H'_\Gamma|+3\leq t_3(s-2)+s-2+3.\]
Hence (\ref{ind:eq}) holds as required. So we may suppose that $H$ contains no edges of weight 3.

\textbf{Case (ii):} The only edges of weight 2 are contained in $H_\Gamma$

Let $xy\in E(H)$ have weight 2, say $l(xy)=ab$.
Now Lemma \ref{ax:lem} $(K_4^-$-$2)$ implies that $x,y\not\in \Gamma_{ab}$, while Lemma \ref{ax:lem} $(K_4^-$-$3)$ implies that $x,y$ cannot both belong to $\Gamma_{ac}$ or $\Gamma_{bc}$ so we may suppose that $x\in \Gamma_{ac}$ and $y\in \Gamma_{bc}$. Lemma \ref{struct1:lem} (viii) implies that $x,y$ have no more neighbours in $H_\Gamma$. If $H_\Gamma=V(H)$ then we can apply the inductive hypothesis to $H'=H-\{x,y\}$ to obtain
\[
w(H)+|H_\Gamma|\leq t_3(s-2)+s-2+2+2,\] in which case (\ref{ind:eq}) holds, so suppose $V(H)\neq H_\Gamma$. 

Let $z\in V(H)-H_\Gamma$ be a neighbour of $x$ in $H$ if one exists otherwise let $z$ be any vertex in $V(H)-H_\Gamma$. By our assumption that all edges of weight 2 are contained in $H_\Gamma$, $z$ meets no edges of weight 2. Moreover, by Lemma \ref{struct1:lem} (viii), all edges containing $x$ (except $xy$) have label $b$, so $x$ is not in any triangles in $H$. Hence $x$ and $z$ have no common neighbours in $H$ and so the total weight of edges meeting $\{x,z\}$ is at most $2+1+s-3$ (if $xz$ is an edge) and at most $2+s-2$ otherwise. Applying our inductive hypothesis to $H'=H-\{x,z\}$ we have
\[
w(H)+|H_\Gamma|\leq t_3(s-2)+s-2+1+s,\] and (\ref{ind:eq}) holds.

\textbf{Case (iii):} There is an edge of weight 2 meeting $V(H)-H_\Gamma$.

So suppose that $xy\in E(H)$, $l(xy)=ab$ and $y\not\in H_\Gamma$. Lemma \ref{struct1:lem} (ix) implies that for any $z\in H_\Gamma$ we have $|l(xz)|$, $|l(yz)|\leq 1$. Let $\gamma_{xy}=|\{x,y\}\cap H_\Gamma|\leq 1$. Thus, since $xy$ is not in any triangles, the total weight of edges meeting $\{x,y\}$ is at most \[
2+s-2+|V(H)-H_\Gamma|-(2-\gamma_{xy}).\]
Applying the inductive hypothesis to $H'=H-\{x,y\}$ we have
\[
w(H)+|H_\Gamma|\leq t_3(s-2)+s-2+s+s-|H_\Gamma|-2+2\gamma_{xy},\] with equality holding only if $|H'_\Gamma|=s-2$.
Now $|H_\Gamma|\geq s-\lfloor s/3\rfloor -1$ implies that
\begin{equation}\label{strict:eq}
w(H)+|H_\Gamma|\leq t_3(s-2)+2s-3+\lfloor s/3\rfloor +2\gamma_{xy},\end{equation}
 with equality only if $|H'_\Gamma|=s-2$ and $|H_\Gamma|=s-\lfloor s/3\rfloor -1$. If $\gamma_{xy}=0$ then (\ref{ind:eq}) holds as required, so suppose $\gamma_{xy}=1$. In this case (\ref{ind:eq}) holds, unless (\ref{strict:eq}) holds with equality. But if (\ref{strict:eq}) is an equality then $|H_\Gamma|=|H'_\Gamma|+1=s-1$, while $|H_\Gamma|=s-\lfloor s/3\rfloor -1$, which is impossible for $s\geq 3$.  

We finally need to verify the cases $s=3,4$. It is again sufficient to prove that if $H$ contains edges of weight 2 or 3 then $w(H)+|H_\Gamma|\leq t_3(s)+s-1$, thus we need to show that $w(H)+|H_\Gamma|$ is at most $5$ if $s=3$ and at most $8$ if $s=4$.

We note that argument in Case (i) above implies that if $H$ contains an edge of weight 3 then $|H_\Gamma|\leq s-2$ and $w(H)\leq 3+3\binom{s-2}{2}$, so if $s=3$ then $w(H)+|H_\Gamma|\leq 4$ and if $s=4 $ then  $w(H)+|H_\Gamma|\leq 8$ so the result holds. So we may suppose there are no edges of weight 3.

Now let $xy$ be an edge of weight $2$. Using the fact that $xy$ is not in any triangles and Lemma \ref{struct1:lem} (viii) and (ix) we find that for $s=3$ we have $w(H)+|H_\Gamma|\leq 2+3-|H_\Gamma|$, while for $s=4$ we have $w(H)+|H_\Gamma|\leq 2+ 6-|H_\Gamma|$, so the result holds. 
\qed

Finally we need to establish our two stuctural lemmas.

\emph{Proof of Lemma \ref{ax:lem}:} In each case we describe a labelling of the vertices of the given configuration to show that if it is present then $G$ is not $\F$-free.
\begin{enumerate}[leftmargin=1.5cm]
\item[($F_6$-1)] $a=1$, $b=5$, $c=6$, $x=2$, $y=3$, $z=4$.%The triangle $xy,xz,yz$ with $l(xy)=l(xz)=a$ and $l(yz)=b$.
\item[($F_6$-2)] $a=3$, $b=4$, $c=5$, $x=1$, $y=2$, $z=6.$%The pair of edges $xy$, $xz$ with $l(xy)=ab$ and $l(xz)=c$.
\item[($F_6$-3)] $a=1$, $b=2$, $c=3$, $x=4$, $y=5$, $z=6$.%A vertex $x\in \Gamma_{ab}$ and edges $xy$, $yz$ with labels $l(xy)=c$ and $l(yz)=a$.
\item[($F_6$-4)] $a=1$, $b=3$, $x=2$, $y=4$, $z=5$, $w=6$.%A vertex $x\in \Gamma_{ab}$ and edges $xy$, $yz$, $zw$ with labels $l(xy)=l(xw)=a$ and $l(yz)=b$.
\item[($F_6$-5)] $a=5$, $b=1$, $c=3$, $x=4$, $y=2$, $z=6$.%Vertices $x\in \Gamma_{ab}$, $y\in \Gamma_{bc}$, $z\in \Gamma_{ac}$ and the edge $xy$ with label $l(xy)=c$.
\item[($K_4^-$-1)] $a=1$, $x=2$, $y=3$, $z=4$.%The triangle $xy$, $xz$, $yz$ with $l(xy)=l(xz)=l(yz)=a$.
\item[($K_4^-$-2)] $a=3$, $b=4$, $x=1$, $y=2$.%The vertex $x\in \Gamma_{ab}$ and edge $xy$ with label $l(xy)=ab$.
\item[($K_4^-$-3)] $a=1$, $b=2$, $x=3$, $y=4$. \qed%The vertices $x,y\in \Gamma_{ab}$ and edge $xy$ with label $l(xy)=a$.
\end{enumerate}
\emph{Proof of Lemma \ref{struct1:lem}:}
We will make repeated use of Lemma \ref{ax:lem}.

(i) This follows immediately from $(F_6$-$1)$ and $(K_4^-$-$1)$.

(ii) This follows immediately from (i): if $uvwx$ is a copy of $K_4$ then we may suppose $l(uv)=a,l(uw)=b,l(vw)=c$, thus $l(ux)=c$ (otherwise (i) would be violated) continuing we see that $uvwx$ must be rainbow.

(iii) This follows immediately from (ii): if $xyzuv$ is a copy of $K_5$ then by (ii) we may suppose that $l(xy),l(xz),l(xu),l(xv)$ are all distinct single labels from $\{a,b,c\}$ but this is impossible since there are only 3 labels in total.

(iv) This follows immediately from  $(F_6$-$2)$ and $(K_4^-$-$2)$.

(v) If $x$ is in a $K_4$ then by (ii) it lies in edges with labels $a,b,c$, so $(F_6$-$3)$ implies that $x\not\in \Gamma_{abc}$.

(vi) If $x\in \Gamma_{abc}$, say $x\in \Gamma_{ab}$, and $y\in V_{abc}^4$ with $xy\in E(L_{abc})$ then $(F_6$-$3)$ implies that $l(xy)\neq c$, while $(F_6$-$4)$ implies that $l(xy)\neq a,b$ (since there are $t,u,v,w$ such that $l(yt)=b,l(tu)=a$ and $l(yv)=a,l(vw)=b$). 

(vii) This follows immediately from the fact that all $v\in V_{abc}^4$ meet edges with labels $a,b,c$ and $(F_6$-$2)$.

(viii) ($F_6$-5) implies that $\Gamma_{bc}=\varnothing$. If $xz\in E(L_{abc})$ then 
($F_6$-3) implies that $l(xz)=a$. Now $(K_4$-3) implies that $z\not\in \Gamma_{ac}$ while $(F_6$-3) implies that $z\not\in \Gamma_{bc}$. Hence $z\not\in \Gamma_{abc}$. Similarly if $yz\in E(L_{abc})$ then $l(yz)=b$ and $z\not\in \Gamma_{abc}$.

(ix) If $x\in\Gamma_{abc}$ or $y\in\Gamma_{abc}$ then this follows directly from (viii) so suppose that $x,y\not\in \Gamma_{abc}$, $l(xy)=ab$ and $|l(xz)|=2$. In this case, $(F_6$-2) implies that $l(xz)=ab$ so $(K_4$-2) implies that $z\in \Gamma_{ac}\cup\Gamma_{bc}$. But then $(F_6$-3) is violated. Hence $|l(xz)|\leq 1$. \qed










\section{Conclusion}
Many Tur\'an-type results have associated ``stability'' versions, and we were able to obtain such a result. For reasons of length we state it without proof.
\begin{thm}\label{thm:stabilityfsix}For any $\epsilon>0$ there
exist $\delta>0$ and $n_{0}$ such that the following holds: if
$H$ is an $\mathcal{F}$-free 3-graph of order $n\geq n_{0}$ with
at least $\left(1-\delta\right)s_3(n)$ edges, then there is a partition
of the vertex set of $H$ as $V(H)=U_{1}\cup U_{2}\cup U_{3}$ so
that all but at most $\epsilon n^{3}$ edges of $H$ have one vertex
in each $U_{i}$.\end{thm}

\subsection*{Acknowledgements}
We wish to thank a referee for their careful reading of this paper and their helpful comments.

\begin{thebibliography}{99}
\bibitem{BS} W. G. Brown and M. Simonovits, \emph{Digraph extremal problems, hypergraph extremal functions, and the densities of graph structures}, Discrete Math. {\bf 48}, 147--162 (1984).
\bibitem{BT} R. Baber and J. Talbot, \emph{New Tur\'an densities for 3-graphs}, Electron. J. Combin. {\bf 19 (2)}, \#P22 (2012). 
\bibitem{B} B. Bollob\'as, \emph{Three-graphs without two triples whose symmetric difference is contained in a third}, Discrete Math. {\bf 8}, 21--24, (1974).
\bibitem{ESi} P. Erd\H os and M. Simonovits, \emph{A limit theorem in graph theory}, Studia Sci. Math. Hung. Acad. {\bf 1}, 51--57, (1966).
\bibitem{ESt} P. Erd\H os and A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. {\bf 52}, 1087--1091, (1946).
\bibitem{FF} P. Frankl and Z. F\"uredi, \emph{A new generalization of the Erd\H os--Ko--Rado theorem}, Combinatorica {\bf 3}, 341--349, (1983).
\bibitem{KNS} G. Katona, T. Nemetz and M. Simonovits, \emph{On a problem of Tur\'an in the theory of graphs}, Mat. Lapok {\bf 15}, 228--238, (1964).
\bibitem{KM} P. Keevash and D. Mubayi, \emph{Stability theorems for cancellative hypergraphs}, J. Combin. Theory Ser. B {\bf 92}, 163--175 (2004).
\bibitem{M} V. W. Mantel, \emph{Problem 28}, Wiskundige Opgaven {\bf 10}, 60--61 (1907). 
\bibitem{RF} A. A. Razborov, \emph{Flag Algebras}, J. Symb. Logic, {\bf 72}, (4) 1239--1282, (2007).
\bibitem{R4} A. A. Razborov, \emph{On $3$-hypergraphs with forbidden $4$-vertex configurations}, SIAM J. Disc. Math. {\bf 24}, (3) 946--963 (2010).
\bibitem{T2} P. Tur\'an, On an extremal problem in graph theory, Mat. Fiz. Lapok {\bf 48}, 436-452 (1941) [in Hungarian].
\end{thebibliography}




\end{document}





\begin{thebibliography}{9}
\bibitem{RBcube} R. Baber, \emph{Tur\'an densities of hypercubes,} \arxiv{1201.3587} [math.CO]
\bibitem{BS} W. G. Brown and M. Simonovits, \emph{Digraph extremal problems, hypergraph extremal functions, and the densities of graph structures}, Disc. Math. {\bf 48} 147--162 (1984).
\bibitem{CF} D. de Caen and Z. F\"uredi, \emph{The maximum size of 3-uniform hypergraphs not containing a Fano Plane}, J. Combin. Theory Ser. B. {\bf 78} 274--276, (2000).
\bibitem{CG} F. Chung and R. Graham, \emph{Erd\H os on graphs: his legacy of unsolved problems}, A.K. Peters, (1999).
\bibitem{E} P. Erd\H os, \emph{On some extremal problems on $r$-graphs}, Disc. Math. {\bf 1} 1--6, (1971).
\bibitem{ESi} P. Erd\H os and M. Simonovits, \emph{A limit theorem in graph theory}, Studia Sci. Math. Hung. Acad. {\bf 1} 51--57, (1966).
\bibitem{ESt} P. Erd\H os and A.H. Stone, \emph{On the structure of linear graphs}, Bull. Am. Math. Soc. {\bf 52} 1087--1091, (1946).
\bibitem{EV} V. Falgas-Ravry and E. R. Vaughan, \emph{On applications of Razborov's flag algebra calculus to extremal 3-graph theory} 	arXiv:1110.1623v1 [math.CO]
\bibitem{FdF} D. G. Fon-Der-Flass, \emph{A method for constructing $(3,4)$-graphs}, Math. Zeitschrift {\bf 44} 546--550, (1988).
\bibitem{FF} P. Frankl and Z. F\"uredi, \emph{A new generalization of the Erd\H os--Ko--Rado theorem}, Combinatorica {\bf 3} 341--349, (1983).
%\bibitem{FPRT} P. Frankl, Y. Peng, V. R\"odl and J. Talbot \emph{A note on the jumping constant conjecture of Erd\H os}, J. Combin. Theory Ser. B, {\bf 97}(2) 204--216, (2007).
%\bibitem{FR} P. Frankl and V. R\"odl, \emph{Hypergraphs do not jump}, Combinatorica, {\bf 4} 149--159, (1984).
\bibitem{sdpa} K. Fujisawa, M. Kojima, K. Nakata, and M. Yamashita. \emph{SDPA (semidefinite programming algorithm) users manual - version 6.00.} Technical Report B--308, Tokyo Institute of Technology, (1995).
 \url{http://sourceforge.net/projects/sdpa/files/sdpa-gmp/}
\bibitem{FPS} Z. F\"uredi, O. Pikhurko and M. Simonovits, \emph{On triple systems with independent neighbourhoods}, Combin. Probab. Comput. {\bf 14} 795--813, (2005).
\bibitem{KNS} G. Katona, T. Nemetz and M. Simonovits, \emph{On a problem of Tur\'an in the theory of graphs}, Mat. Lapok {\bf 15}, 228--238, (1964).
\bibitem{KM} P. Keevash and D. Mubayi, \emph{Stability theorems for cancellative hypergraphs}, J. Combin. Theory Ser. B {\bf 92} 163--175 (2004).
\bibitem{K} A. Kostochka, \emph{A class of constructions for Tur\'an's $(3,4)$ problem} Combinatorica {\bf 2} 187--192 (1982).
\bibitem{Mu} D. Mubayi, \emph{A hypergraph extension of Tur\'an's theorem}, J. Combin. Theory Ser. B {\bf 96} 122--134 (2006).
\bibitem{MR} D. Mubayi and V. R\"odl, \emph{On the Tur\'an number of triple systems}, J. Combin. Theory Ser. A {\bf 100} 136--152 (2002).
\bibitem{Pi} O. Pikhurko, \emph{Exact computation of the hypergraph Tur\'an function for expanded complete 2-graphs}, accepted by J. Combin. Theory Ser. B, publication suspended indefinitely see \url{http://www.math.cmu.edu/\~pikhurko/Copyright.html} 
\bibitem{PP} O. Pikhurko, \emph{On Possible Turan Densities}, submitted (2011).
\bibitem{Pexact} O. Pikhurko, \emph{The Minimum Size of $3$-Graphs without a $4$-Set Spanning No or Exactly Three Edges}, Europ. J. Comb., {\bf 23} 1142--1155 (2011).
\bibitem{RF} A. A. Razborov, \emph{Flag Algebras}, Journal of Symbolic Logic, {\bf 72} (4) 1239--1282, (2007).
\bibitem{R4} A. A. Razborov, \emph{On $3$-hypergraphs with forbidden $4$-vertex configurations},in  SIAM J. Disc. Math. {\bf 24}, (3) 946--963 (2010).
\bibitem{RS} V. R\"odl and M. Schacht, \emph{Generalizations of the Removal Lemma}, Combinatorica {\bf 29}  467--501 (2009).
\end{thebibliography}


\end{document}


\section{Stability Lemmas}
The stability result will follow from these lemmas:

\begin{lemma}\label{lem:nok4s}Let $H$ be
a $\mathcal{F}$-free 3-graph of order $n+7$ such that each vertex
in $H$ has degree at least $\left(1-10\epsilon\delta'\right)\left(n^{2}/9\right)$,
where $\epsilon\delta'\leq1/280$. Let $E=\{abc\}$ be any edge in
$H$. Then the link graph of $E$ does not contain a copy of $K_{4}$.\end{lemma}

\begin{lemma}\label{lem:stability2edges}Let
$H$ be an $\mathcal{F}$-free 3-graph of order $n$ such that every
vertex in $H$ has degree $\left(1-10\epsilon\delta'\right)\left(n^{2}/9\right)$,
where $\epsilon\delta'<1/619520$, that contains an edge $abc$ with
total double neighbourhoods at least $\left(1-\delta\right)\left(2n/3\right)$.
Then the link graph of $abc$ has at most $16\epsilon\delta'$ vertices
incident with an edge of weight 2.\end{lemma}




Now we prove the lemmas concerning the structure of link graphs to
be used in the stability proof. 

%\ffourfree*
\prf
Assume that the link graph of $E$ does contain a copy of $K_{4}$
with vertices $p,$ $q$, $r$ and $s$ and edges $\{apq,ars,bpr,bqs,cps,cqr\}$.
Let $L$ be the link graph of $\{a,b,c,p,q,r,s\}=Q$; that is, $V(L)=V(G)-Q$
and $E(L)=\{xy\,:\,\exists z\in V(G)-Q\textrm{ and }xyz\in E(G)\}$.
By the given assumptions, $L$ contains at least $\left(1-10\epsilon\delta'\right)7\frac{2}{9}\frac{n^{2}}{2}-{7 \choose 2}n-{7 \choose 3}=\left(1-10\epsilon\delta'\right)\frac{7n^{2}}{9}-21n-35$
edges and is a multigraph containing edges of multiplicity up to 7.

We note the following facts about the subgraph $Q$:
\begin{enumerate}
\item Every vertex is incident with exactly three edges.
\item Every pair of vertices is included in exactly one edge.
\item No two edges are entirely disjoint.
\end{enumerate}
We note the following facts about $L$:
\begin{enumerate}
\item $L$ contains no monochromatic or two-colour triangles (because every
pair of colours is part of an edge).
\item To every pair of colours, there corresponds a third colour, such that
a pair of vertices connected by edges with that pair of colours is
not incident with the third colour -- again, this follows from every
pair of colours being part of an edge.
\item There are exactly three pairs of colours corresponding to each colour,
which satisfy the conditions of 2 above: this follows from each vertex
being incident with three different edges within $Q$.
\end{enumerate}
Next, we are able to characterise edges of weight 3:
\begin{prop}
\label{lem:3edge}Let $\alpha\beta$ be an edge in $L$ containing
colours $xyz$. If $xyz$ is an edge in $H$ then $\alpha$ and $\beta$
are incident only with edges of weight 1 (excluding the edge $\alpha\beta$).
If $xyz$ is not an edge then $\alpha$ and $\beta$ are incident
only with colours $xyz$ and exactly one other, that together form
the complement to an edge in $X$.\end{prop}
\prf
For $xyz\in E(H)$, each pair from $xyz$ excludes the third of those
colours, so $\alpha$ and $\beta$ are not incident with any of $xyz$,
other than in the edge $\alpha\beta$. But each pair outside $xyz$
excludes one of these colours, or else there would be two disjoint
edges in $X$, so $\alpha$ and $\beta$ are not incident with any
edges of weight 2 outside $xyz$. For $xyz\notin E(H)$, each pair
from $xyz$ excludes a different colour, or else there would be two
edges that overlap in two colours, and none of these colours are $x$,
$y$ or $z$, as $xyz$ is not an edge, so this leaves only one available
colour outside $xyz$. This fourth colour together with $xyz$ cannot
contain an edge, or else one of $xyz$ would be excluded, so it must
consist of the complement to an edge.
\qed
These properties enable us to classify certain small structures that
appear in $L$:
\begin{prop}
$L$ does not contain any triangles of total weight 7 or greater and
the only triangles of weight 6 contain 3 edges of weight 2 and are
disjoint from a particular colour.\end{prop}
\prf
In any triangle, all edges are different colours, or else there would
be a two-colour triangle. Accordingly, there can be no triangle of
weight more than 7. Also, any edge of weight two is not incident with
at least one other colour, so at least one colour must be excluded
from any triangle with edges of multiple weight, which contradicts
any triangle of weight 7. Next, considering triangles of weight 6,
there are two possibilities: 2-2-2 and 3-2-1. But any edge of weight
$3$ is either an edge, in which case it is incident only with edges
of weight 1, or it is not an edge, in which case it is not incident
with edges of weight 2 consisting wholly of colours different from
those in the edge; in both cases this follows from Lemma \ref{lem:3edge}.
This leaves triangles of the form 2-2-2, where each pair excludes
the same colour. There are seven possibilities, one corresponding
to each colour (for instance, $ab-ps-qr$ for $c$), and that colour
is not incident with any vertex of the triangle.\qed
\begin{cor}
The sets of vertices incident with a particular triangle of weight
6 are disjoint.\end{cor}

An edge is \emph{degenerate }if it contains colours that form an edge
in $Q$ (that is, it is of weight greater than 4 or if it is of weight
4 but is not one of the following colours: $abps$, $abqr$, $acpr$,
$acqs$, $bcpq,$$bcrs$); and \emph{non-degenerate }is defined accordingly
(that is, a non-degenerate edge of weight 4 contains colours that
are the complement of an edge in $X$).
\begin{prop}
\label{prop:degenerate}A vertex incident with a non-degenerate edge
of weight 4 is not incident with any colours other than those forming
part of that edge and a vertex incident with a degenerate edge is
incident only with edges of weight 1 (excluding the degenerate edge),
so that there are at most $\frac{n}{2}$ degenerate edges in $L$.\end{prop}
\prf
A degenerate edge contains colours that constitute an edge in $Q$,
so by Lemma \ref{lem:3edge} is incident only with edges of weight
1. Also by Lemma \ref{lem:3edge} any 4 colours that do not contain
an edge form the complement to an edge and are incident exactly with
those colours.

To calculate the total density of degenerate edges in $L$, take a
maximal matching of degenerate edges in $L$. As degenerate edges
are only incident with edges of weight 1, no two degenerate edges
are incident, and so this matching includes all degenerate edges.
Accordingly, there are a maximum of $\frac{n}{2}$ degenerate
edges.\qed
\begin{cor}
The sets of vertices incident with a particular type of non-degenerate
edge of weight 4 are disjoint.
\end{cor}
Let $dn$ be the number of degenerate edges in $L$ of maximum size
$7n/2$. We temporarily remove these edges from $L$. We now set out
certain densities that apply to different sets of vertices within
$L$.
\begin{prop}
\label{prop:fourdensity}The maximum density of any set $K$ of vertices
of order $k$ in $L$ is $k^{2}$.\end{prop}
\prf
If $k=2$, the maximum number of edges is $2^{2}=4$. We proceed by
induction. Let $m(x)$ be the maximum number of edges in $K$, where
$K$ is of order $x$. Take an edge in $K$ of maximum multiplicity.
There are a maximum of four edges between the pair of vertices forming
this edge and any other edge (one edge of weight four or two edges
of weight two). So, given that $m(k-2)\leq(k-2)^{2}$ 
\begin{eqnarray*}
m(k) & \leq & 4(k-2)+4+(k-2)^{2}\\
 & = & k^{2}
\end{eqnarray*}
\qed
\begin{prop}
\label{prop:remdensity}The maximum density of any set $K$ of vertices
of order $k$ in $L$ that does not contain an edge of weight 4 or
more or a triangle of weight 6 is $(3/4)k^{2}$\end{prop}
\prf
If $k=2$, the maximum number of edges is $3=(3/4)2^{2}$. We proceed
by induction. Let $m(x)$ be the maximum number of edges in $K$,
where $K$ is of order $x$. Take an edge in $K$ of maximum multiplicity.
There are a maximum of three edges between the pair of vertices forming
this edge and any other edge (one edge of weight three or two edges
of weight one and two). So, given that $m(k-2)\leq\frac{3}{2}(k-2)^{2}$
\begin{eqnarray*}
m(k) & \leq & 3(k-3)+3+\frac{3}{2}(k-2)^{2}\\
 & = & \frac{3}{4}k^{2}
\end{eqnarray*}
\qed
\begin{prop}
\label{prop:triangledensity}The maximum number of edges between any
2-2-2 triangle and any other vertex is 6; the maximum number of edges
between any 2-2-2 triangle and any other vertex incident with the
colour not part of that triangle is 3.\end{prop}
\prf
We have already seen that a degenerate edge cannot be incident with
an edge of weight 2. We have also seen that there are no 3-2-1 triangles,
so if there is an edge of weight 3 (or a non-degenerate edge of weight
4) between the other vertex and any vertex in the triangle, there
are no other edges between that vertex and the triangle. Therefore,
the maximum that can be achieved is three edges of weight 2.

Consider now the case where the other vertex is incident with the
colour missing from the triangle: we take the triangle $ab-ps-qr$
and a vertex incident with $c$; the other cases are similar. Any
edge of weight 4 between the vertex and the triangle must include
$c$, as the other vertex is incident with $c$, but the triangle
is not incident with $c$. Similarly, any edge of weight 3 between
the vertex and the triangle cannot include any of the pairs $ab$,
$ps$ or $qr,$ so it must consist of one colour from each edge: say,
for instance $apr$, but this then excludes $q$, $s$ and $b$, so
that it cannot be incident with the triangle. Finally, consider an
edge of weight 2. It cannot contain any of the pairs forming edges
of the triangle, as these are not incident with $c$. Take, for instance
the vertex incident with $ab$ and $ps$. There are then two cases.
The pair could take one colour from each of these pairs. But then
there would be no edge between either of the other two vertices of
the triangle and the other vertex, or else there would be a two-colour
triangle, so there would be a total of two edges between the triangle
and the vertex. Or the pair could consist of one colour from the opposite
edge and one colour from the incident pairs: say $qs$. But each of
these pairs excludes one of the colours incident with the $ab-ps$
vertex, and so is not allowed. The maximum is achieved if we allow
edges of weight 1 between each vertex of the triangle and the other
vertex.\qed
\begin{prop}
\label{prop:edgedensity}Let $xy$ be a non-degenerate edge of weight
4. The maximum number of edges between $xy$ and any other vertex
is 4. The maximum number of edges between $xy$ and any vertex incident
with at least one colour not in that edge is 2.\end{prop}
\prf
Let $z$ be the other vertex. Assume the colour of $xy$ is $abps$:
the other cases are similar. As $xyz$ only contains these four colours
and as $xy$ contains all four colours, $xyz$ is triangle free, so
the greatest number of edges between $xy$ and $z$ is achieved by
an edge of weight 4 from $x$ or $y$ to $z$.

Now take the case where $z$ is incident with a colour other than
$abps$. Note that by Lemma \ref{lem:3edge} any triple of these colours
excludes all other colours. Therefore, the maximum multiplicity of
an edge between $xy$ and $z$ is 2. As $xyz$ is triangle free, the
greatest number of edges between $xy$ and $z$ is achieved by an
edge of weight 2 from $x$ or $y$ to $z$.\qed
\begin{prop}
\label{prop:twothirds}Each colour is incident with at least $(2/3)\left(1-5\epsilon\delta'\right)$
of the vertices of $L$.\end{prop}
\prf
Let $C_{x}$ be defined as the set of vertices incident with colour
$x$ in $L$. Note that the subgraph of colour $x$ is triangle-free.
So, by Mantel's Theorem,
\begin{eqnarray*}
\frac{c_{x}^{2}}{4} & \geq & \left(1-10\epsilon\delta'\right)\frac{n^{2}}{9}\\
c_{x}^{} & \geq & \left(1-10\epsilon\delta'\right)^{\frac{1}{2}}\frac{2n}{3}\\
 & \geq & \left(1-5\epsilon\delta'\right)\frac{2n}{3}
\end{eqnarray*}
\qed

Let $M_{x}$ be a subset of the vertices of $L$ defined as follows:
$M_{x}$ is the union of a maximal matching of edges of weight 4 that
are not incident with colour $x$ and a maximal matching of 2-2-2
triangles that are not incident with colour $x$.

We form the partition of $L$ consisting of $M_{a},M_{b}\ldots M_{s}$
and $R$: all the remaining vertices. In particular, choose a matching
of edges of weight 4 and 2-2-2 triangles that are not incident with
colour $a$. Then, from the remaining vertices, choose a matching
of edges of weight 4 and 2-2-2 triangles that are not incident with
colour $b$, and so on. So, for instance, a matching of edges $pqrs$
would be inside $M_{a}$. 

For $x\in Q$, let $D_{x}$ be the set of vertices disjoint from colour
$x$. Let $\left|C_{x}\right|=\left(2/3-\delta_{x}\right)n$ and so
$\left|D_{x}\right|=\left(1/3+\delta_{x}\right)n$, where $\delta_{x}$
is less than $(2/3)5\epsilon\delta'=(10/3)\epsilon\delta'$, as guaranteed
by Proposition \ref{prop:twothirds} (note that $\delta_{x}$ is also
permitted to be negative). Let $\left|D_{x}\cap M_{y}\right|=d_{x,y}$
and $\left|C_{x}\cap M_{y}\right|=c_{x,y}$. We derive an expression
for the upper bound of the total number of edges in $L$ and show
that this upper bound is always less than our lower bound of $(7/9)\left(1-5\epsilon\delta'\right)$. 

We form the upper bound of the number of edges in $L$ by calculating
an upper bound for the number of edges in each subset of $L$ and
between each pair of subsets in $L$. The maximum density of $R$
is $\frac{3}{4}$, by Proposition \ref{prop:remdensity}, and the
maximum density of each $M_{x}$ is $1$, by Proposition \ref{prop:fourdensity},
so this gives terms of $\frac{3}{4}\left[\left(1-\sum_{x\in Q}m_{x}\right)n\right]^{2}$
and $\left(m_{x}n\right)^{2}$ for each $x\in Q$ for all the densities
of subsets of $L$. We then calculate the density of edges between
each $M_{x}$ and the rest of $L$. 

For each $M_{x}$, consider first the set of vertices incident with
colour $x$, other than those forming part of any $M_{y}$. We label
this subset temporarily $C$ and note that it contains $\left((2/3)-\delta_{x}-\sum_{y\neq x\in Q}c_{x,y}\right)n$
vertices. Let the subset of $M_{x}$ consisting of matched pairs of
edges of weight 4 be labelled $M_{x,P}$ and the subset consisting
of matched triangles of total weight 6 be labelled $M_{x,T}$. By
Propositions \ref{prop:triangledensity} and \ref{prop:edgedensity},
each matched pair in $M_{x,P}$ sends at most one edge of weight 2
to any vertex in $C$, giving a maximum of $2(m_{x,P}n/2)cn=m_{x,P}cn^{2}$
edges between those two subsets and each matched triangle in $M_{x}$
sends at most three edges of weight 1 to any vertex in $C$ giving
a maximum of $3(m_{x,T}n/3)cn=m_{x,T}cn^{2}$. The overall maximum
is therefore $m_{x}cn^{2}$.

For each $M_{x}$, consider next the set of vertices not incident
with colour $x$, other than those forming $M_{x}$ or any part of
$M_{y}$. We label this subset temporarily $D$ and note that it contains
$\left((1/3)+\delta_{x}-m_{x}-\sum_{y\neq x\in Q}d_{x,y}\right)n$
vertices. By similar reasoning to above, the maximum number of vertices
between $M_{x}$ and $D$ is $4(m_{x,P}n/2)dn+6(m_{x,T}n/3)dn=2m_{x}tn^{2}$.

Next, we consider the maximum number of edges between $M_{x}$ and
each $M_{y}$. Using similar reasoning to above, we can fix a maximum
of $m_{x}c_{x,y}n^{2}$ edges between $M_{x}$ and the subset of each
$M_{y}$ that is incident with $x$ and a maximum of $2m_{x}d_{x,y}n^{2}$
edges between $M_{x}$ and the subset of each $M_{y}$ that is not
incident with $x$. Note that, as we are summing over all $M_{x}$
below, we introduce a factor $1/2$ to avoid double counting.

Finally, we add the $dn$ degenerate edges.

Accordingly, the total number of edges in $L$ is at most:
\[
e(L)\leq n^{2}\left[\frac{3}{4}\left(1-\sum_{x\in Q}m_{x}\right)^{2}+\sum_{x\in Q}\left\{ m_{x}^{2}+m_{x}\left(\frac{2}{3}-\delta_{x}-\sum_{y\neq x\in Q}c_{x,y}\right)+2m_{x}\left(\frac{1}{3}+\delta_{x}-m_{x}-\sum_{y\neq x\in Q}d_{x,y}\right)+\frac{1}{2}\sum_{y\neq x\in Q}\left\{ m_{x}c_{x,y}+2m_{x}d_{x,y}\right\} \right\} +\frac{d}{n}\right]
\]


We can express the lower bound for the number of edges in $L$ using
the same partition of vertex sets:
\begin{eqnarray*}
e(L) & \geq & \frac{7}{9}\left(1-5\epsilon\delta'\right)n^{2}-21n-35=\frac{3}{4}n^{2}+\left[\frac{1}{36}-\frac{35}{9}\epsilon\delta'\right]n^{2}-21n-35
\end{eqnarray*}


\[
=n^{2}\left[\frac{3}{4}\left(1-\sum_{x\in Q}m_{x}\right)^{2}+\sum_{x\in Q}\left\{ \frac{3}{4}m_{x}^{2}+\frac{3}{2}m_{x}\left(\frac{2}{3}-\delta_{x}-\sum_{y\neq x\in Q}c_{x,y}\right)+\frac{3}{2}m_{x}\left(\frac{1}{3}+\delta-m_{x}-\sum_{y\neq x\in Q}d_{x,y}\right)+\frac{1}{2}\sum_{y\neq x\in Q}\left\{ \frac{3}{2}m_{x}c_{x,y}+\frac{3}{2}m_{x}d_{x,y}\right\} \right\} +\left[\frac{1}{36}-\frac{35}{9}\epsilon\delta'\right]-\frac{21}{n}-\frac{35}{n^{2}}\right]
\]


Combining these inequalities gives:

\[
0\leq n^{2}\left[\sum_{x\in Q}\left\{ \frac{1}{4}m_{x}^{2}-\frac{1}{2}m_{x}\left(\frac{2}{3}-\delta_{x}-\sum_{y\neq x\in Q}c_{x,y}\right)+\frac{1}{2}m_{x}\left(\frac{1}{3}+\delta_{x}-m_{x}-\sum_{y\neq x\in Q}d_{x,y}\right)+\frac{1}{2}\sum_{y\neq x\in Q}\left\{ -\frac{1}{2}m_{x}c_{x,y}+\frac{1}{2}m_{x}d_{x,y}\right\} \right\} -\left[\frac{1}{36}-\frac{35}{9}\epsilon\delta'\right]+\frac{d+21}{n}+\frac{35}{n^{2}}\right]
\]


\[
=n^{2}\left[\sum_{x\in Q}\left\{ \frac{1}{4}m_{x}^{2}-\frac{1}{3}m_{x}+\frac{1}{2}m_{x}\delta_{x}+\frac{1}{2}m_{x}\sum_{y\neq x\in Q}c_{x,y}+\frac{1}{6}m_{x}+\frac{1}{2}m_{x}\delta_{x}-\frac{1}{2}m_{x}^{2}-\frac{1}{2}m_{x}\sum_{y\neq x\in Q}d_{x,y}-\frac{1}{4}m_{x}\sum_{y\neq x\in Q}c_{x,y}+\frac{1}{4}m_{x}\sum_{y\neq x\in Q}d_{x,y}\right\} -\left[\frac{1}{36}-\frac{35}{9}\epsilon\delta'\right]+\frac{d+21}{n}+\frac{35}{n^{2}}\right]
\]


\[
=n^{2}\left[\sum_{x\in Q}\left\{ -\frac{1}{4}m_{x}^{2}-\frac{1}{6}m_{x}+m_{x}\delta_{x}+\frac{1}{4}m_{x}\sum_{y\neq x\in Q}c_{x,y}-\frac{1}{4}m_{x}\sum_{y\neq x\in Q}d_{x,y}\right\} -\left[\frac{1}{36}-\frac{35}{9}\epsilon\delta'\right]+\frac{d+21}{n}+\frac{35}{n^{2}}\right]
\]
\begin{eqnarray*}
 & \leq & n^{2}\left[\sum_{x\in Q}\left\{ -\frac{1}{4}m_{x}^{2}-\frac{1}{6}m_{x}+\frac{1}{4}m_{x}\left(\frac{2}{3}-\frac{10}{3}\epsilon\delta'\right)+m_{x}\frac{10}{3}\epsilon\delta'\right\} -\left[\frac{1}{36}-\frac{35}{9}\epsilon\delta'\right]+\frac{49}{2n}+\frac{35}{n^{2}}\right]\\
 & < & n^{2}\left[\sum_{x\in Q}\left\{ -\frac{1}{4}m_{x}^{2}\right\} -\frac{1}{36}+\frac{115}{18}\epsilon\delta'+\frac{49}{2n}+\frac{35}{n^{2}}\right]\\
 & < & 0
\end{eqnarray*}
where we have used the fact that, for each $x$, $\sum_{y\in Q}c_{x,y}\leq\left(2/3-\delta_{x}\right)$,
$\delta_{x}\leq(10/3)\epsilon\delta'$ and $\epsilon\delta'<1/230$
and taken $n$ as sufficiently large.

This contradiction establishes the lemma.
\qed
Next we establish some preliminary stability results for link neighbourhoods
that will be used in the next stability lemma.
\begin{prop}
\label{lem:doublesize}Let $H$ be an $\mathcal{F}$-free 3-graph
of order $n$ with at least $\left(1-\delta\right)\frac{2}{9}\binom{n}{3}$
edges. Then there is at least one edge with link neighbourhood of
size at least $\left(1-\delta\right)\frac{2}{3}n$.\end{prop}
\prf
Note that, by Lemma \ref{ax:lem}($K_{4}^{-}$-3), no vertex appears
with multiplicity more than one in $\Gamma_{e}$.

We employ the following equality:
\[
\sum_{abc\in E(G)}\left(\left|\Gamma_{ab}\right|+\left|\Gamma_{ac}\right|+\left|\Gamma_{bc}\right|\right)=\sum_{xy\in\binom{V(H)}{2}}\left|\Gamma_{xy}\right|(\left|\Gamma_{xy}\right|-1)
\]


The left hand side measures the total size of all double neighbourhoods
of all edges in $H$. The right hand side, for each pair of vertices
that is part of an edge, provides the contribution of $\Gamma_{xy}-1$
to the double neighbourhood of that edge from each of the other edges
of which it is a part.

We then have
\[
\sum_{\{abc\}\in E(G)}\left(\left|\Gamma_{ab}\right|+\left|\Gamma_{ac}\right|+\left|\Gamma_{bc}\right|\right)\leq\sum_{abc\in E(G)}\max\left(\left|\Gamma_{ab}\right|+\left|\Gamma_{ac}\right|+\left|\Gamma_{bc}\right|\right)=\left|E(G)\right|\max\left(\left|\Gamma_{ab}\right|+\left|\Gamma_{ac}\right|+\left|\Gamma_{bc}\right|\right)
\]
and
\begin{eqnarray*}
\sum_{xy\in\binom{V(H)}{2}}\left|\Gamma_{xy}\right|(\left|\Gamma_{xy}\right|-1) & \geq & \frac{1}{\binom{V(H)}{2}}\left(\sum_{xy\in\binom{V(H)}{2}}\Gamma_{xy}\right)^{2}-\sum_{xy\in\binom{V(H)}{2}}\Gamma_{xy}\\
 & = & \frac{1}{\binom{\left|V(H)\right|}{2}}9\left|E(G)\right|^{2}-3E(G)
\end{eqnarray*}
(where the total number of neighbourhoods of every pair counts each
edge three times) and putting these together gives
\begin{eqnarray*}
\max\left(\left|\Gamma_{ab}\right|+\left|\Gamma_{ac}\right|+\left|\Gamma_{bc}\right|\right) & \geq & \frac{2}{n(n-1)}9\frac{n(n-1)(n-2)}{6}\frac{2}{9}\left(1-\delta\right)-3\\
 & = & \frac{2}{3}(n-2)(1-\delta)-3\\
 & = & (1-\delta)\frac{2}{3}n-\left[\frac{13}{3}-\frac{4}{3}\delta\right]
\end{eqnarray*}
\qed
\begin{prop}
\label{lem:doublemax}Let $H$ be an $\mathcal{F}$-free 3-graph of
order $n+3$ that contains an edge $abc$ with total link neighbourhoods
at least $\left(1-\delta\right)2n/3$. Then the link graph $L_{abc}$
contains fewer than $\left(1+2\delta\right)^{2}n^{2}/36$ edges of
weight 2.\end{prop}
\prf
Let $P=\{ab,ac,bc\}$, let $D=\cup_{p\in P}\Gamma_{p}$ and let $R=L-D$,
so that by assumption we have $\left|D\right|>\left(1-\delta\right)2n/3$.
Note that, by Lemma \ref{ax:lem}($K_{4}^{-}$-3), each $\Gamma_{xy}$
is disjoint.

Without loss of generality, take any vertex $x$ in $\Gamma_{ab}$
and assume that $x$ is incident with an edge of weight 2 in $L$:
$xy$. Note that $y\notin\Gamma_{ab}$ and that $xy$ is not coloured
$ab$: in either case we have a copy of $K_{4}^{-}$. So assume, again
without loss of generality, that $xy$ is coloured $ac$.

Neither $x$ nor $y$ is incident with $b$, or else $\{xya,xyb,abc,xbq\}$
for example, would be a copy of $F_{6}$. Also, $y$ is not incident
with $a$ (apart from the edge $xy$), or else $\{abc,abx,cxy,ayq\}$
for example, would be a copy of $F_{6}$. Therefore, $y$ is not incident
with any edge of weight 2 other than $xy$. By symmetrical reasoning,
if $y\in\Gamma_{bc}$ (note that it is not possible for $y$ to be
contained in $\Gamma_{ac}$), then $x$ is not incident with any edge
of weight 2 other than $xy$.

Accordingly, there are two cases: if $xy$ is contained entirely in
the double neighbourhoods of $abc$, then neither $x$ nor $y$ is
incident with any other edge of weight 2; if $y$ is not contained
in any double neighbourhoods, that is, $y\in R$, then $y$ is not
incident with any other edge of weight 2.

Let $R_{D}$ be the set of vertices in $R$ incident with an edge
of weight 2, where the other vertex of this edge is contained in $D$,
and let $e$ be the number of edges of weight 2 in $L$. Define $\delta_{r}$
such that $dn=\left(1-\delta_{r}\right)2n/3$, so that $\delta_{r}\leq\delta$.
We calculate an upper bound on the number of edges of weight 2 as
follows: there are a maximum of $d/2$ such edges contained in $D$
(take a matching of these edges); there are a maximum of $r_{d}n$
such edges incident with $R_{D}$; there are a maximum of $\left(r-r_{d}\right)^{2}n^{2}/4$
such edges in the remainder of $R$ (because the graph of edges of
weight 2 is triangle-free). So we have
\begin{eqnarray*}
en^{2} & \leq & \frac{dn}{2}+r_{d}n+\frac{\left(r-r_{d}\right)^{2}n^{2}}{4}\\
 & = & \left(1-\delta_{r}\right)\frac{n}{3}+r_{d}n+\frac{\left(1+2\delta_{r}-9r_{d}\right)^{2}\frac{n^{2}}{9}}{4}\\
 & = & \frac{n}{3}\left[1-\delta_{r}+3r_{d}+\frac{n}{12}\left(1+2\delta_{r}-9r_{d}\right)^{2}\right]\\
 & \leq & \frac{n^{2}}{36}\left[1+2\delta\right]^{2}
\end{eqnarray*}
so that
\[
e\leq\frac{\left(1+2\delta\right)^{2}}{36}
\]
where we have assumed that $n$ is sufficiently large and used the
upper bound for $\delta_{r}$. 
\qed
These results enable us to prove the second lemma used in the stability
proof.

%\stabilitydbl*
\prf
By Lemma \ref{lem:doublemax}, there are at most $\left(1+2\delta\right)^{2}n^{2}/36$
edges of weight 2 in $L_{abc}$. As the preconditions of Lemma \ref{lem:nok4s}
are satisfied, $L$ does not contain a copy of $K_{4}$. Also, by
Proposition \ref{prop:twothirds}, each colour is incident with at
least $(2/3)\left(1-5\epsilon\delta'\right)$ of the vertices in $L_{abc}$.
Finally, any edge of weight 2 is not incident with any other colour;
therefore, any edge of weight 3 is not incident with any other edge.

Let $M_{xy}$ be the set of vertices consisting of a maximal matching
of edges of weight 2 and colours $x$ and $y$, let $M_{abc}$ be
the set of vertices incident with an edge of weight 3 and let $R=L_{abc}-\bigcup M_{xy}-M_{abc}$.
From the facts above about $L_{abc}$, we have that the $M_{xy}$
are disjoint, that $e(M_{abc})\leq(3/2)m_{abc}n$, that there are
no edges between $M_{abc}$ and any other set and that $e(R)\leq(1/3)r^{2}$.
Define $\delta_{r}$ such that $e(R)=(1/3)\left(1-\delta_{r}\right)r^{2}$. 

We form the partition of $L_{abc}$ consisting of $M_{ab},M_{bc},M_{ac},M_{abc}$
and $R$. Note that each of these sets is disjoint and that the maximum
size of each $M_{xy}$ is $n/3$. For $x\in\{a,b,c\}$, let $D_{x}$
be the set of vertices disjoint from colour $x$ and let $C_{x}$
be the set of vertices incident with colour $x$. Let $\left|C_{x}\right|=\left(2/3-\delta_{x}\right)n$
and so $\left|D_{x}\right|=\left(1/3+\delta_{x}\right)n$, where $\delta_{x}$
is less than $(10/3)\epsilon\delta'$, as guaranteed by Proposition
\ref{prop:twothirds}. Note that $M_{xy}\subseteq D_{z}$. We derive
expressions for the upper bound of the total number of edges in $L$
and ultimately show that this upper bound is less than the lower bound
of $(1/3)\left(1-10\epsilon\delta'\right)n^{2}$ unless the number
of vertices incident with edges of weight 2 is less than $16\epsilon\delta'$.
We form the upper bound for the number of edges in $L_{abc}$ by calculating
an upper bound for the number of edges within each subset in $L_{abc}$
and for the number of edges between each pair of subsets in $L_{abc}$.

The remaining densities in and between sets are provided by the following
Propositions.
\begin{prop}
\label{prop:mxydensity}The maximum number of edges in $M_{xy}$ is
$\frac{1}{2}\left(m_{xy}n\right)^{2}$. This may be allocated as $\frac{1}{4}\left(m_{xy}n\right){}^{2}+\alpha_{xy}n^{2}$,
where $\alpha_{xy}\leq\frac{1}{4}m_{xy}^{2}$ and there are at least
$\alpha_{xy}n^{2}$ edges of weight 2 in $M_{xy}$.\end{prop}
\prf
Ignoring the mulitiplicity of edges in $M_{xy}$ gives a simple graph
that is triangle-free, as $M_{xy}$ is incident only with edges of
colour $x$ and $y$ and there are no monochromatic or two-colour
triangles. If there are no edges of weight 2 in $M_{xy}$ then the
maximum number of edges is $\frac{1}{4}\left(m_{xy}n\right)^{2}$.
Accordingly, any edges above this number must consist of edges of
weight 2. Given a total of $\frac{1}{4}\left(m_{xy}n\right)^{2}+\alpha_{xy}n^{2}$
edges, it follows immediately that there must be at least $\alpha_{xy}n^{2}$
edges of weight 2 and that $\alpha_{xy}\leq\frac{1}{4}m_{xy}^{2}$.\qed
\begin{prop}
\label{2edgedensities}Let $xy$ be an edge of weight 2. Then the
maximum number of edges between $xy$ and any vertex incident with
$p$, the colour not contained in $xy$, is 1 and the maximum number
of edges between $xy$ and any vertex not incident with $p$ is 2.
It follows that the number of edges between $xy$ and any set $Q$
not incident with $p$ is $qn+\alpha_{q}n$, where $\alpha_{q}n$
is the number of edges of weight 2 between $xy$ and $Q$.\end{prop}
\prf
Assume, without loss of generality, that the colour of $xy$ is $ab$
and let the third vertex be $z$. Then $x$ and $y$ are only incident
with edges of colour $a$ and $b$. If $z$ is incident with $c$
it cannot be incident with an edge coloured $ab$ and so there can
only be edges of weight 1 between $x$ or $y$ and $z$. As $xyz$
is triangle-free, this gives a maximum of 2 edges where $z$ is not
incident with $c$ and 1 edge where $z$ is incident with $c.$ Given
a total of $qn+\alpha_{q}n$ edges and a maximum of $qn$ edges of
weight 1, it follows immediately that there must be at least $\alpha_{q}n$
edges of weight 2.
\qed
Let $P'=\{ab,ac,bc,abc\}$, $P=\{ab,ac,bc\}$ and $\alpha=\sum_{S\in P}\left(\alpha_{S}+\alpha_{abc-S}\right)$.
The total number of edges in $L_{abc}$ is at most:
\[
e(L_{abc})\leq n^{2}\left[\frac{1}{3}\left(1-\delta_{r}\right)\left(1-\sum_{S\in P'}m_{S}\right)^{2}+\frac{3m_{abc}}{2n}+\sum_{S\in P}\left[\frac{1}{4}m_{S}^{2}+\alpha_{S}+\alpha_{abc-S}+m_{S}\left\{ \frac{1}{2}\left(\frac{2}{3}-\delta_{abc-S}-\sum_{T\in P',T\neq S}m_{T}\right)+\frac{1}{2}\left(\frac{1}{3}+\delta_{abc-S}-m_{S}\right)+\frac{1}{4}\sum_{T\in P',T\neq S}m_{T}\right\} \right]\right]
\]


\[
\leq n^{2}\left[\frac{1}{3}\left(1-\delta_{r}\right)\left(1-\sum_{S\in P'}m_{S}\right)^{2}+\alpha+\sum_{S\in P}\left(\frac{1}{4}m_{S}+\frac{1}{3}-\frac{1}{2}\sum_{T\in P,T\neq S}m_{T}+\frac{1}{6}-\frac{1}{2}m_{S}+\frac{1}{4}\sum_{T\in P,T\neq S}m_{T}\right)\right]
\]


\begin{eqnarray*}
 & = & n^{2}\left[\frac{1}{3}\left(1-\delta_{r}\right)\left(1-\sum_{S\in P'}m_{S}\right)^{2}+\alpha+\sum_{S\in P}\left(\frac{1}{2}-\frac{1}{4}\sum_{T\in P}m_{T}\right)\right]\\
 & = & n^{2}\left[\frac{1}{3}\left(1-\delta_{r}\right)\left(1-\sum_{S\in P'}m_{S}\right)^{2}+\alpha+\frac{1}{2}\sum_{S\in P}m_{S}-\frac{1}{4}\left(\sum_{S\in P}m_{S}\right)^{2}\right]
\end{eqnarray*}
where, for the second inequality, we assume that $n$ is sufficiently
large that we may take $m_{abc}=0$.

We express the lower bound for the number of edges in $L_{abc}$ using
the same partition: 
\[
e(L{}_{abc})\geq\frac{1}{3}\left(1-10\epsilon\delta'\right)n^{2}=n^{2}\left[\frac{1}{3}\left(1-\sum_{S\in P}m_{S}\right)^{2}+\frac{1}{3}\sum_{S\in P}m_{S}^{2}+\sum_{S\in P}m_{S}\left\{ \frac{2}{3}\left(\frac{2}{3}-\delta_{abc-S}-\sum_{T\in P,T\neq S}m_{T}\right)+\frac{2}{3}\left(\frac{1}{3}+\delta_{abc-S}-m_{S}\right)+\frac{1}{3}\sum_{T\in P,T\neq S}m_{T}\right\} -\frac{10}{3}\epsilon\delta'\right]
\]


\[
=n^{2}\left[\frac{1}{3}\left(1-\sum_{S\in P}m_{S}\right)^{2}+\sum_{S\in P}m_{S}\left\{ \frac{1}{3}m_{S}+\frac{4}{9}-\frac{2}{3}\sum_{T\in P,T\neq S}m_{T}+\frac{2}{9}-\frac{2}{3}m_{S}+\frac{1}{3}\sum_{T\in P,T\neq S}m_{T}\right\} -\frac{10}{3}\epsilon\delta'\right]
\]


\begin{eqnarray*}
 & = & n^{2}\left[\frac{1}{3}\left(1-\sum_{S\in P}m_{S}\right)^{2}+\sum_{S\in P}m_{S}\left\{ \frac{2}{3}-\frac{1}{3}\sum_{T\in P}m_{T}\right\} -\frac{10}{3}\epsilon\delta'\right]\\
 & = & n^{2}\left[\frac{1}{3}\left(1-\sum_{S\in P}m_{S}\right)^{2}+\frac{2}{3}\sum_{S\in P}m_{S}-\frac{1}{3}\left(\sum_{S\in P}m_{S}\right)^{2}-\frac{10}{3}\epsilon\delta'\right]
\end{eqnarray*}


First we show that $\sum_{S\in P}m_{S}<1/4$. Combining the two inequalities
gives 
\begin{eqnarray*}
0 & \leq & n^{2}\left[-\frac{\delta_{r}}{3}\left(1-\sum_{S\in P}m_{S}\right)^{2}+\alpha-\frac{1}{6}\sum_{S\in P}m_{S}+\frac{1}{12}\left(\sum_{S\in P}m_{S}\right)^{2}+\frac{10}{3}\epsilon\delta'\right]
\end{eqnarray*}


Taking $\delta_{r}/3=0$, $(10/3)\epsilon\delta'=(10/3)(1/480)=1/144$
(weaker than our actual bound on $\epsilon\delta'$) and $\alpha=\left(1+2\delta\right)^{2}/36$,
we maximise $\left(\sum m_{s}\right)^{2}-\sum m_{s}^{2}$ by taking
$m_{s}=q$ for all $S$, so that $\left(\sum m_{s}\right)^{2}=9q^{2}$
and $\sum m_{s}=3q$. Then the upper bound becomes:
\[
n^{2}\left[\frac{\left(1+2\delta\right)^{2}}{36}+\frac{1}{144}+\frac{1}{12}\left(9q^{2}-6q\right)\right]
\]
from which it follows that
\[
3q^{2}-2q+\left[\frac{\left(1+2\delta\right)^{2}}{9}+\frac{1}{36}\right]\geq0
\]
and for $q\in\left[0,1/3\right]$ this gives $3q=\sum_{S\in P}m_{S}<1/4$,
so that we have an approximate bound on the maximum number of vertices
incident with an edge of weight 2. 

Next we use the bound on $\sum_{S\in P}m_{S}$ to deduce an upper
bound on $\delta_{r}$. We use the following version of the upper
bound for the number of edges in $L_{abc}:$
\[
e(L_{abc})\leq n^{2}\left[\frac{1}{3}\left(1-\delta_{r}\right)\left(1-\sum_{S\in P'}m_{S}\right)^{2}+\frac{1}{2}\sum_{S\in P}m_{S}^{2}+\frac{3m_{abc}}{2n}+\sum_{S\in P}m_{S}\left\{ \frac{1}{2}\left(\frac{2}{3}-\delta_{abc-S}-\sum_{T\in P,T\neq S}m_{T}\right)+\left(\frac{1}{3}+\delta_{abc-S}-m_{S}\right)+\frac{1}{4}\sum_{T\in P,T\neq S}m_{T}\right\} \right]
\]


\[
\leq n^{2}\left[\frac{1}{3}\left(1-\delta_{r}\right)\left(1-\sum_{S\in P}m_{S}\right)^{2}+\frac{1}{2}\sum_{S\in P}m_{S}^{2}+\sum_{S\in P}m_{S}\left\{ \frac{1}{2}\left(\frac{2}{3}-\delta_{abc-S}-\sum_{T\in P,T\neq S}m_{T}\right)+\left(\frac{1}{3}+\delta_{abc-S}-m_{S}\right)+\frac{1}{4}\sum_{T\in P,T\neq S}m_{T}\right\} \right]
\]


\[
=n^{2}\left[\frac{1}{3}\left(1-\delta_{r}\right)\left(1-\sum_{S\in P}m_{S}\right)^{2}+\sum_{S\in P}m_{S}\left\{ \frac{1}{2}m_{S}+\frac{1}{3}-\frac{1}{2}\delta_{abc-S}-\frac{1}{2}\sum_{T\in P,T\neq S}m_{T}+\frac{1}{3}+\delta_{abc-S}-m_{S}+\frac{1}{4}\sum_{T\in P,T\neq S}m_{T}\right\} \right]
\]
\begin{eqnarray*}
 & = & n^{2}\left[\frac{1}{3}\left(1-\delta_{r}\right)\left(1-\sum_{S\in P}m_{S}\right)^{2}+\sum_{S\in P}m_{S}\left\{ -\frac{1}{2}m_{S}+\frac{2}{3}-\frac{1}{4}\sum_{T\in P,T\neq S}m_{T}+\frac{1}{2}\delta_{abc-S}\right\} \right]\\
 & = & n^{2}\left[\frac{1}{3}\left(1-\delta_{r}\right)\left(1-\sum_{S\in P}m_{S}\right)^{2}+\sum_{S\in P}m_{S}\left\{ \frac{2}{3}-\frac{1}{4}m_{S}-\frac{1}{4}\sum_{T\in P}m_{T}+\frac{1}{2}\delta_{abc-S}\right\} \right]\\
 & = & n^{2}\left[\frac{1}{3}\left(1-\delta_{r}\right)\left(1-\sum_{S\in P}m_{S}\right)^{2}+\frac{2}{3}\sum_{S\in P}m_{S}-\frac{1}{4}\sum_{S\in P}m_{S}^{2}-\frac{1}{4}\left(\sum_{S\in P}m_{S}\right)^{2}+\frac{1}{2}\sum_{S\in P}m_{S}\delta_{abc-S}\right]
\end{eqnarray*}


where, in the second inequality, we assume that $n$ is sufficiently
large, so that $m_{abc}=0$. Combining this with the inequality for
the lower bound gives:
\[
0\leq n^{2}\left[-\frac{\delta_{r}}{3}\left(1-\sum_{S\in P}m_{S}\right)^{2}+\frac{1}{12}\left(\sum_{S\in P}m_{S}\right)^{2}-\frac{1}{4}\sum_{S\in P}m_{S}^{2}+\frac{1}{2}\sum_{S\in P}m_{S}\delta_{abc-S}+\frac{10}{3}\epsilon\delta'\right]
\]


We have $\sum_{S\in P}m_{S}\in\left[0,1/4\right]$, so $1-\sum_{S\in P}m_{S}\geq3/4$,
and an application of the Cauchy-Schwarz Inequality gives $\left[\left(m_{ab}+m_{bc}+m_{ac}\right)^{2}-3\left(m_{ab}^{2}-m_{bc}^{2}-m_{ac}^{2}\right)\right]\leq0$.
Putting these together gives
\begin{eqnarray*}
0 & \leq & n^{2}\left[\frac{10}{3}\epsilon\delta'+\frac{1}{2}\frac{1}{4}\frac{10}{3}\epsilon\delta'-\frac{\delta_{r}}{3}\frac{9}{16}\right]\\
 & = & n^{2}\left[\frac{15}{4}\epsilon\delta'-\frac{3}{16}\delta_{r}\right]
\end{eqnarray*}
which is negative if $\delta_{r}>20\epsilon\delta'$. This contradiction
proves the lemma when $\delta_{r}>20\epsilon\delta'$.

Finally we consider the case where $\delta_{r}\leq20\epsilon\delta'$. 

Assume that there are $\sqrt{\delta_{r}}r$ vertices of degree less
than $\left(1-2\sqrt{\delta_{r}}\right)2r/3$. Deleting them gives
a graph on $\left(1-\sqrt{\delta_{r}}\right)r$ vertices with at least
$\left(1-\delta_{r}-2\sqrt{\delta_{r}}\left(1-2\sqrt{\delta_{r}}\right)\right)r^{2}/3$
edges. But
\begin{eqnarray*}
\left(1-\sqrt{\delta_{r}}\right)^{2}\frac{r^{2}}{3} & = & \left(1+\delta_{r}-2\sqrt{\delta_{r}}\right)\frac{r^{2}}{3}\\
 & < & \left(1-2\sqrt{\delta_{r}}+4\delta_{r}-\delta_{r}\right)\frac{r^{2}}{3}
\end{eqnarray*}
which violates Tur\'an's theorem, as this subgraph is $K_{4}$-free.
Therefore, there are a maximum of $\sqrt{\delta_{r}}r$ vertices in
$R$ of degree less than $\left(1-2\sqrt{\delta_{r}}\right)\frac{2r}{3}$.
We label this set of vertices $R_{-}$ and the remainder of $R$ is
labelled $R_{+}$.

We consider now the number of edges between any set $M_{xy}$ and
the set $R$. If there is an edge between $x$ and any vertex in $R_{+}$,
then there is no edge between $x$ and any of the $\left(1-2\sqrt{\delta_{r}}\right)2r/3$
neighbours of this vertex. That is, $x$ is connected to a maximum
of $\left(1+4\sqrt{\delta_{r}}\right)r/3$ vertices in $R_{+}$. Similar
reasoning applies to $y$, so that the total number of edges between
$xy$ and $R$ is $2\left(1+4\sqrt{\delta_{r}}\right)r/3+\sqrt{\delta_{r}}r=\left(1+(11/2)\sqrt{\delta_{r}}\right)2r/3$.
Therefore, there are $\left(1-11\sqrt{\delta_{r}}\right)r/3$ vertices
in $R_{+}$ that are not connected to $xy$. We assume, for evaluating
the upper bound, that these vertices are in the set of vertices that
may only be connected to $xy$ by edges of weight 1. 

This gives the following version of the upper bound (where we assume,
as above, that $n$ is sufficiently large that $m_{abc}=0$):
\[
e(L_{abc})\leq n^{2}\left[\frac{1}{3}\left(1-\delta_{r}\right)\left(1-\sum_{S\in P}m_{S}\right)^{2}+\sum_{S\in P}m_{S}\left\{ \frac{1}{2}m_{S}+\frac{1}{2}\left(\frac{2}{3}-\delta_{abc-S}-\sum_{T\in P,T\neq S}m_{T}-\left(1-11\sqrt{\delta_{r}}\right)\frac{\left(1-\sum_{S\in P}m_{S}\right)}{3}\right)+\left(\frac{1}{3}+\delta_{abc-S}-m_{S}\right)+\frac{1}{4}\sum_{T\in P,T\neq S}m_{T}\right\} \right]
\]


\[
=n^{2}\left[\frac{1}{3}\left(1-\delta_{r}\right)\left(1-\sum_{S\in P}m_{S}\right)^{2}+\sum_{S\in P}m_{S}\left\{ -\frac{1}{4}m_{S}+\frac{2}{3}+\frac{1}{2}\delta_{abc-S}-\frac{1}{4}\sum_{T\in P}m_{T}-\frac{1}{2}\left(1-11\sqrt{\delta_{r}}\right)\frac{\left(1-\sum_{S\in P}m_{S}\right)}{3}\right\} \right]
\]


\[
=n^{2}\left[\frac{1}{3}\left(1-\delta_{r}\right)\left(1-\sum_{S\in P}m_{S}\right)^{2}-\frac{1}{4}\sum_{S\in P}m_{S}^{2}+\frac{2}{3}\sum_{S\in P}m_{S}+\frac{1}{2}\sum_{S\in P}m_{S}\delta_{abc-S}-\frac{1}{4}\left(\sum_{S\in P}m_{S}\right)^{2}-\frac{1}{2}\left(\sum_{S\in P}m_{S}\right)\left(1-11\sqrt{\delta_{r}}\right)\frac{\left(1-\sum_{S\in P}m_{S}\right)}{3}\right]
\]


and therefore, using the same lower bound as above:
\[
0\leq n^{2}\left[\frac{1}{12}\left[\left(\sum_{S\in P}m_{S}\right)^{2}-3\left(\sum_{S\in P}m_{S}^{2}\right)\right]+\frac{1}{2}\sum_{S\in P}m_{S}\delta_{abc-S}+\frac{10}{3}\epsilon\delta'-\frac{1}{2}\left(\sum_{S\in P}m_{S}\right)\left(1-11\sqrt{\delta_{r}}\right)\frac{\left(1-\sum_{S\in P}m_{S}\right)}{3}-\frac{\delta_{r}}{3}\left(1-\sum_{S\in P}m_{S}\right)^{2}\right]
\]


\[
<n^{2}\left[\frac{10}{3}\epsilon\delta'+\frac{1}{2}\frac{1}{4}\frac{10}{3}\epsilon\delta'-\left(\sum_{S\in P}m_{S}\right)\left(1-11\sqrt{\delta_{r}}\right)\frac{1}{4}-\frac{\delta_{r}}{4}\right]
\]
taking $\left(1-\sum_{S\in P}m_{S}\right)>3/4$ and again using Cauchy-Schwarz
to show $\left(\sum_{S\in P}m_{S}\right)^{2}-3\left(\sum_{S\in P}m_{S}^{2}\right)\leq0$. 

It follows that 
\begin{eqnarray*}
\sum_{S\in P}m_{S} & \leq & \left(15\epsilon\delta'-\delta_{r}\right)\left(\frac{1}{1-11\sqrt{\delta_{r}}}\right)\\
 & < & 16\epsilon\delta'
\end{eqnarray*}
because $\delta_{r}<(1/30976)=20\epsilon\delta'$.
\qed

\section{Stability For $F_{6}$}

The approach of this section is substantially the same as the proof
of Theorem 1.5, the stability result for $F_{5}$, in  \cite{KM}.
The principal difference is in the requirement for the stability lemmas
of the previous section and in certain other details of the argument
that we highlight below.

The following proposition is a slight variant of a case of the Simonovits
stability theorem.
\begin{thm}
\label{prop:k4stability}For any $\epsilon'>0$ there exists $\delta'>0$
and $n_{0}$ such that the following holds: if $G$ is a $K_{4}$-free
graph on $n>n_{0}$ vertices with at least $\left(1-\delta'\right)t_{3}(n)$
edges, then one can delete $\epsilon'n$ vertices from $G$ so that
the remaining graph is tripartite.
\end{thm}
This theorem is the stability version of the Tur\'an density for $F_{6}$.


\emph{Proof of Theorem \ref{thm:stabilityfsix}:}
We use constants that satisfy the following hierarchy: $\delta\ll\delta'\ll\epsilon'\ll\epsilon$.
In particular:
\begin{itemize}
\item Let $\epsilon'<10^{-8}\epsilon^{2}$.
\item Let $\delta'<\epsilon'$ and be the result of applying Theorem \ref{prop:k4stability}
with $\epsilon'$.
\item Let $\delta<12(\epsilon\delta')^{2}$.
\end{itemize}
Define $U_{0}\subset V(H)$. We add a small number of 'bad' vertices
to $U_{0}$ and show that all but a small number of hyperedges in
$H-U_{0}$ respect the partition.

Assume, to derive a contradiction, that there are $\epsilon\delta'n$
vertices of degree at most $(1-5\epsilon\delta')n^{2}/9$. Deleting
them gives a 3-graph $H'$ with $(1-\epsilon\delta')n$ vertices and
at least $\left(1-\delta-3\epsilon\delta'(1-5\epsilon\delta')\right)n^{2}/27$
edges. It follows that
\begin{eqnarray*}
e(H') & \geq & \left(1-\delta-3\epsilon\delta'(1-5\epsilon\delta')\right)\frac{n^{3}}{27}\\
 & = & \left(1-\delta-3\epsilon\delta'+15(\epsilon\delta')^{2}\right)\frac{n^{3}}{27}\\
 & > & \left(1-3\epsilon\delta'+3(\epsilon\delta')^{2}\right)\frac{n^{3}}{27}\\
 & = & \frac{\left[\left(1-\epsilon\delta'\right)n\right]^{3}}{27}+\frac{\left(\epsilon\delta'\right)^{3}n^{3}}{27}
\end{eqnarray*}


But this is contrary to Theorem \ref{main:thm}, for $n$ sufficiently
large. It follows that there are fewer than $\epsilon\delta'n$ vertices
of degree at most $\left(1-5\epsilon\delta'\right)n^{2}/9$ and we
add these to the set $U_{0}$.

Consider the 3-graph $H-U_{0}$. Every vertex in this 3-graph has
degree at least $\left(1-5\epsilon\delta'\right)(n^{2}/9)-(\epsilon\delta'n^{2}/2)\geq\left(1-10\epsilon\delta'\right)(n^{2}/9)$.
As $H$ has at least $\left(1-\delta\right)s_3(n)$ edges, by Proposition
\ref{lem:doublesize}, there is at least one hyperedge $abc$ in this
graph with total link neighbourhoods greater than $\left(1-\delta\right)(2/3)n$.
The preconditions of Lemma \ref{lem:stability2edges} are satisfied
so that the link graph of $abc$ is $K_{4}$-free and has a maximum
of $16\epsilon\delta'n$ vertices incident with an edge of weight
2. We add these to the set $U_{0}$. 

Let $J$ be the link graph of $abc$ in $H$. This graph is $K_{4}$-free
and has no edges of weight 2, that is, it is a simple graph.

Suppose that $J$ has $\delta'n$ vertices with degree at most $\left(1-10^{-3}\epsilon\right)2n/3$.
Then the graph $J'=J-\{x:d(x)\leq\left(1-10^{-3}\epsilon\right)2n/3\}$
has $\left(1-\delta'\right)n$ vertices and at least $\left(1-\delta-2\delta'\left(1-10^{-3}\epsilon\right)\right)n^{2}/3$
edges, but
\[
\frac{\left[\left(1-\delta'\right)n\right]^{2}}{3}=\left[1-2\delta'+\delta'{}^{2}\right]\frac{n^{2}}{3}
\]
 and
\[
\left(1-\delta-2\delta'\left(1-10^{-3}\epsilon\right)\right)\frac{n^{2}}{3}=\left(1-2\delta'+2\times10^{-3}\epsilon\delta'-\delta\right)\frac{n^{2}}{3}
\]
which gives a contradiction, because $2\times10^{-3}\epsilon\delta'-\delta>\delta'{}^{2}$,
which means that $J'$, which is $K_{4}$-free, violates Tur\'an's Theorem.

Therefore, we can remove the at most $\delta'n$ vertices from $H$
and $J'$ and add them to $U_{0}$. Let $L$ be the resulting link
graph of $abc$ in $H-U_{0}$. It has the property that every vertex
has degree at least $\left(1-10^{-3}\epsilon\right)2n/3$ and that
the graph has, trivially, at least $\left(1-\delta'\right)n^{2}/3$
edges. This enables us to apply Proposition \ref{prop:k4stability}.
So there are $\epsilon'n$ vertices which may be removed from $H$
such that the remaining link graph $L$ is tripartite. We add these
vertices to $U_{0}$. $L$ now has at least $\left(1-\delta'-3\epsilon'\right)n^{2}/3$
edges, which is greater than $\left(1-10^{-7}\epsilon^{2}\right)n^{2}/3$
by the choice of $\delta'$ and $\epsilon'$. It may be partitioned
into three vertex sets $V_{1}$, $V_{2}$ and $V_{3}$, each of which
contains no edges.

Note that $\left|\left|V_{i}\right|-n/3\right|<10^{-3}\epsilon n$
for each $i$. Assume otherwise, so that $V_{1}$, say, violates this
and $L$ would have at most
\[
\left|V_{1}\right|\left(n-\left|V_{1}\right|\right)+\frac{\left(n-\left|V_{1}\right|\right)^{2}}{4}=\frac{n^{2}}{3}-\frac{\left(3\left|V_{1}\right|-n\right)^{2}}{12}<\frac{n^{2}}{3}-\frac{3}{4}10^{-6}\epsilon^{2}n^{2}<\left(1-10^{-7}\epsilon^{2}\right)\frac{n^{2}}{3}
\]
edges, which gives a contradiction. It also follows that each vertex
in $V_{i}$ has degree at least $\left(1-10^{-3}\right)2n/3-\left(1/3+10^{-3}\epsilon\right)n>n/3-10^{-2}\epsilon n$
in both $V_{j}$, $j\neq i$.

Let $v_{1}v_{2}v_{3}$ be a triangle in $L$ with $v_{i}$ in $V_{i}$.
For every vertex $x$ in $L$, if $x\in V_{i}$ and it is not adjacent
to both $v_{j}$, $j\neq i$, then add it to $U_{0}$. There are at
most $6.10^{-2}\epsilon n$ such vertices. As all triangles are multicoloured,
we may assume that $v_{i}v_{j}$ has colour $k$ for $\{i,j,k\}=\{1,2,3\}$.
Then each vertex of $V_{k}$ is joined to the vertices $v_{i},v_{j}$
by one edge of colour $i$ and one of colour $j$. Let $V_{k}^{1}$
consist of those vertices $v$ in $V_{k}$ for which $vv_{i}$ has
colour $i$ and $vv_{j}$ has colour $j$ and $V_{k}^{2}=V_{k}-V_{k}^{1}$.

All edges from $v_{1}$ to $V_{2}^{1}\cup V_{3}^{1}$ have colour
$1$. Therefore there are no edges between $V_{2}^{1}$ and $V_{3}^{1}$,
and the same holds betwen $V_{i}^{1}$ and $V_{j}^{1}$ for any two
distinct $i,j\in\{1,2,3\}$. If both $V_{i}^{1}$ and $V_{j}^{1}$
have size at least $10^{-2}\epsilon n$, then $L$ has at most $n^{2}/3-\left(10^{-2}\epsilon n\right)^{2}<\left(1-10^{-7}\epsilon^{2}\right)n^{2}/3$
edges, which is impossible. It follows that there is at most one $l$
for which $\left|V_{l}^{1}\right|\geq10^{-2}\epsilon n$. Without
loss of generality we assume that $l=1$. Thus both $V_{2}^{1}$ and
$V_{3}^{1}$ have size at most $10^{-2}\epsilon n$, and we add their
vertices to $U_{0}$.

Now take any edge $pqr$ of $H$ in $V-V_{0}$. Consider first the
case where all 3 vertices are in one of the sets. Take $\{p,q,r\}\subset V_{1}^{1}$.
Then $x_{2}v_{2}p$, $x_{2}v_{2}q$ and $pqr$ are all edges of $H$.
Take a vertex $s$ in $V_{2}^{2}$ which is incident with $r$. The
edge $rs$ must be of colour $2$ as $rv_{3}$ is colour $3$ and
$v_{3}s$ is colour $1$. But then the edge $x_{2}rs$ completes a
copy of $F_{6}$. The other cases are similar. Therefore, $pqr$ is
not contained in any one of the sets.

Next take the case where 2 vertices are in one of the sets. Take $\{p,q\}\subset V_{1}^{1}$
and $r\in V_{2}^{2}$. But then the edges $x_{3}v_{3}p$, $x_{3}v_{3}q$,
$pqr$ and $x_{3}rv_{1}$ form a copy of $F_{6}$. The other cases
are similar. Therefore, $pqr$ does not have exactly two vertices
in any one set.

Finally, consider the case where $p\in V_{1}^{1}$, $q\in V_{1}^{2}$
and $r\in V_{2}^{2}$. If $qr$ is an edge it must be of colour $3$
as $pv_{3}$is colour $2$ and $v_{3}r$ is colour $1$. But then
$qrp$, $qrx_{3}$, $px_{3}v_{3}$ and $qv_{3}x_{2}$ form a copy
of $F_{6}$. Therefore, $qr$ is not an edge of $L$. Since $L$ has
at least $\left(1-10^{-7}\epsilon^{2}\right)n^{2}/3$ edges respecting
the partition out of $\left(V_{1},V_{2},V_{3}\right)$ out of at most
$n^{2}/3$ possible edges, there are at most $10^{-7}\epsilon^{2}n^{2}/3$
choices for $qr$, so at most $10^{-7}\epsilon^{2}n^{3}/3$ such hyperedges
$pqr$.

Similarly, there are at most $10^{-7}\epsilon^{2}n^{3}/3$ hyperedges
$pqr$ with $p\in V_{1}^{1}$, $q\in V_{1}^{2}$ and $r\in V_{3}^{2}$.
All other edges have one point in each of $V_{1}^{1}\cup V_{1}^{2}$,
$V_{2}^{2}$ and $V_{3}^{2}$. Define a tripartition $V=U_{1}\cup U_{2}\cup U_{3}$
so that $V_{1}^{1}\cup V_{1}^{2}\subseteq U_{1}$, $V_{2}^{2}\subseteq U_{2}$
and $V_{3}^{2}\subseteq U_{3}$ and the bad vertices $U_{0}$ are
distributed arbitrarily. Since $u_{0}<(1/2)\epsilon n$ and there
are fewer than $(1/2)\epsilon n^{3}$ exceptional edges all but at
most $\epsilon n^{3}$ edges of $H$ have one point in each $U_{i}$,
so the theorem is proved.
\qed