# Triangle-free triple systems

Peter Frankl, 1 Zoltán Füredi, 2 Ido Goorevitch, 3
Ron Holzman, 4 and Gábor Simonyi 5

( 1,2,5 HUN-REN Alfréd Rényi Institute of Mathematics,
Budapest, P. O. Box 127, 1364 Hungary
5 Department of Computer Science and Information Theory,
Faculty of Electrical Engineering and Informatics,
Budapest University of Technology and Economics, Budapest, Hungary
3,4 Department of Mathematics,
Technion-Israel Institute of Technology,
Haifa 3200003, Israel

E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>and<EMAIL_ADDRESS>††thanks: Research of the second
author was supported in part by the National Research Development and
Innovation Office, NKFIH, grants K–132696 and KKP 133819.
Research of the fifth author was partially supported by the National Research,
Development and Innovation Office (NKFIH) grants K–132696 and SNN–135643 of
NKFIH Hungary.
Subject Classification: Primary: 05D05. Secondary: 05C69, 05C76
Keywords: Extremal hypergraphs, triple systems, designs.  )

###### Abstract

There are four non-isomorphic configurations of triples that can form a
triangle in a $3$-uniform hypergraph. Forbidding different combinations of
these four configurations, fifteen extremal problems can be defined, several
of which already appeared in the literature in some different context. Here we
systematically study all of these problems solving the new cases exactly or
asymptotically. In many cases we also characterize the extremal constructions.

##  1 Introduction

###  1.1 Notations

A hypergraph ${\mathcal{F}}$ is a pair $(V({\mathcal{F}}),E({\mathcal{F}}))$
where the set of edges, $E({\mathcal{F}})$, is a family of subsets of the set
of vertices $V({\mathcal{F}})$ (see Berge [1], Lovász [20]). To simplify
notations we frequently identify ${\mathcal{F}}$ with $E({\mathcal{F}})$ (and
omit parentheses, etc.) if it does not cause ambiguity. If all edges of
${\mathcal{F}}$ have the same size, say $r$, then we speak of an $r$-graph, or
$r$-uniform hypergraph. With this terminology $2$-graphs are simple graphs
without loops and 3-uniform hypergraphs are also called triple systems. We
usually identify $V=V({\mathcal{F}})$ with the set of first $n$ positive
integers, $[n]:=\\{1,2,3,\dots,n\\}$. Then ${V\choose r}$ stands for the
complete $r$-graph with vertex set $V$, it is $\\{F:|F|=r,F\subseteq V\\}$.

We write $\partial{\mathcal{F}}$ for
$\\{F\setminus\\{x\\}:F\in{\mathcal{F}},x\in F\\}$, it is called the shadow of
${\mathcal{F}}$. If ${\mathcal{F}}$ is a triple system then its shadow is a
simple graph. The degree of $S\subseteq V({\mathcal{F}})$ is the number of
edges containing $S$, in notation

$\deg_{\mathcal{F}}(S):=|\\{F:F\in{\mathcal{F}},S\subseteq F\\}|.$

Given a triple system ${\mathcal{F}}$ we write ${\mathcal{F}}[x]$ for the
_link_ of $x$ in ${\mathcal{F}}$, i.e., the graph on
$V({\mathcal{F}})\setminus\\{x\\}$ whose edges are those pairs that form with
$x$ a triple in ${\mathcal{F}}$. If $F$ is an edge of a $3$-uniform hypergraph
${{\mathcal{F}}}$ such that $x,y\in F$, $x\neq y$, and there is no other
$F^{\prime}\in{{\mathcal{F}}}$ containing both $x$ and $y$, then we say that
the pair $xy$ is an own pair of $F$. With our previous notation,
$\deg_{\mathcal{F}}(xy)=1$.

###  1.2 Cycles in hypergraphs

In hypergraph theory a cycle of length $\ell$ is usually defined as a sequence
of distinct vertices $x_{1},x_{2},\dots,x_{\ell}$ together with a sequence of
distinct edges $E_{1},\dots,E_{\ell}$ such that $E_{i}$ contains $x_{i}$ and
$x_{i+1}$ for $1\leq i<\ell$ and $E_{\ell}$ contains $x_{\ell}$ and $x_{1}$.
We refer to a cycle of $\ell$ edges as an $\ell$-cycle. For ordinary graphs,
the above definition coincides with the definition of a cycle $C_{\ell}$ in
graphs. We call a 3-cycle a triangle.

One of the oldest problems in extremal graph theory is to investigate the
maximum number of edges of graphs without given short cycles, e. g., the
Turán-Mantel theorem says that a triangle-free graph on $n$ vertices has at
most $\lfloor\frac{1}{4}n^{2}\rfloor$ edges and the only extremal graph is the
complete bipartite graph with parts of sizes $\lfloor\frac{n}{2}\rfloor$ and
$\lceil\frac{n}{2}\rceil$, respectively. For further graph results see the
book of Bollobás [4].

Hypergraph problems are more complicated, but there are some results, e. g.,
that of Lazebnik and Verstraëte [19] saying that if ${\mathcal{F}}$ is
$3$-uniform, has $n$ vertices, girth five (i.e., no cycles of length less than
five) and a maximum number of edges, then
$|E({\mathcal{F}})|=\frac{1}{6}n^{3/2}+o(n^{3/2})$.

In this paper we deal with 3-uniform hypergraphs containing no triangles of
certain types.

###  1.3 Triangles in triple systems

One can easily realize that there are altogether four non-isomorphic
configurations of three triples that create a triangle. We will call these
configurations ${\mathbf{A}},{\mathbf{B}},{\mathbf{C}}$, and ${\mathbf{D}}$
(see Figure 1 below). The main goal of this paper is to study the maximum
number of triples one can have on $n$ vertices while excluding certain
combinations of the four triangle creating configurations.

Configuration ${\mathbf{A}}$ is the one needing six vertices, that is, it is
isomorphic to the hypergraph with $V=\\{1,\dots,6\\},E=\\{124,135,236\\}.$

Configuration ${\mathbf{B}}$ is on five vertices, where two of the three
triples involved intersect in two vertices and each of them meets the third
triple in a different vertex. Thus ${\mathbf{B}}$ is isomorphic to the
hypergraph with $V=\\{1,\dots,5\\},E=\\{125,134,234\\}.$

Configuration ${\mathbf{C}}$ is the one on four vertices, that is, it is
isomorphic to the hypergraph with $V=\\{1,\dots,4\\},E=\\{124,134,234\\}.$

Configuration ${\mathbf{D}}$ is on five vertices again, with one triple
sharing with each of the other two a different pair of vertices. It is
isomorphic to the hypergraph with $V=\\{1,\dots,5\\},E=\\{123,134,235\\}.$

Figure 1: The four configurations of three triples forming a triangle

Our starting point is a result (first proved by Győri [16]) giving the maximum
number of edges in a triangle-free $3$-uniform hypergraph, i.e., in case all
of ${\mathbf{A}},{\mathbf{B}},{\mathbf{C}}$ and ${\mathbf{D}}$ are forbidden
subconfigurations. In Section 2 we reprove it and also describe the extremal
families. Then we consider the fourteen other cases when some proper subset of
$\\{{\mathbf{A}},{\mathbf{B}},{\mathbf{C}},{\mathbf{D}}\\}$ is forbidden. Five
of these subsets define problems of long history, most of them are solved, but
not all. Then we go on to investigate the other nine. For all but one of those
nine combinations, we obtain an exact solution of the extremal problem (though
sometimes only for large enough $n$), often along with a characterization of
the extremal constructions. In the one exceptional case we give an asymptotic
solution.

To state our results let us introduce the notation ${\rm ex}(n,X_{1}\dots
X_{k})$ for
$\\{X_{1},\dots,X_{k}\\}\subseteq\\{{\mathbf{A}},{\mathbf{B}},{\mathbf{C}},{\mathbf{D}}\\}$.
It denotes the maximum number of triples in a $3$-uniform hypergraph on $n$
vertices which does not contain any of the configurations $X_{1},\dots,X_{k}$.
Table 1 below summarizes the results, including earlier ones and those in the
present paper.

|  | ${\mathbf{A}}{\mathbf{B}}$ |  |  |  |
---|---|---|---|---|---|---
|  |  ${n-1\choose 2}$ for $n\geq 5$ |  |  |  |
|  | and char. ext. |  |  |  |
|  | Theorem 2 |  |  |  |
${\mathbf{A}}$ |  | ${\mathbf{A}}{\mathbf{C}}$ |  | ${\mathbf{A}}{\mathbf{B}}{\mathbf{C}}$ |  |
${n-1\choose 2}$ for $n\geq n_{0}$ |  |  $\lfloor\frac{1}{4}(n-1)^{2}\rfloor$ for even $n$ |  | $\lfloor\frac{1}{4}(n-1)^{2}\rfloor$ |  |
and char. ext. |  |  $\frac{1}{4}(n-1)^{2}+1$ for odd $n\geq 5$ |  | and char. ext. |  |
Frankl&Füredi [12] |  | and char. ext. |  | Theorem 11 |  |
|  | Theorem 13 |  |  |  |
${\mathbf{B}}$ |  | ${\mathbf{A}}{\mathbf{D}}$ |  | ${\mathbf{A}}{\mathbf{B}}{\mathbf{D}}$ |  |
$\lfloor\frac{n}{3}\rfloor\lfloor\frac{n+1}{3}\rfloor\lfloor\frac{n+2}{3}\rfloor$ for $n\geq n_{0}$ |  |  $\lfloor\frac{1}{4}(n-1)^{2}\rfloor+2$ for even $n\geq 4$ |  |  $\lfloor\frac{1}{8}n^{2}\rfloor$ for $n\geq 8$ |  |
Frankl&Füredi [10] |  |  $\frac{1}{4}(n-1)^{2}$ for odd $n$ |  | and char. ext. |  |
char. ext. |  | and char. ext. |  | Theorem 19 |  | ${\mathbf{A}}{\mathbf{B}}{\mathbf{C}}{\mathbf{D}}$
Keevash&Mubayi [18] |  | Theorem 10 |  |  |  | $\lfloor\frac{1}{8}n^{2}\rfloor$
|  |  |  |  |  | Győri [16]
${\mathbf{C}}$ |  | ${\mathbf{B}}{\mathbf{C}}$ |  | ${\mathbf{A}}{\mathbf{C}}{\mathbf{D}}$ |  | char. ext.
$\geq\frac{2}{7}{n\choose 3}\bigl{(}1-o(1)\bigr{)}$ |  | $\lfloor\frac{n}{3}\rfloor\lfloor\frac{n+1}{3}\rfloor\lfloor\frac{n+2}{3}\rfloor$ |  | $\lfloor\frac{1}{4}(n-1)^{2}\rfloor$ |  | Theorem 1
Frankl&Füredi [11] |  | and char. ext. |  | and char. ext. |  |
$\leq.287{n\choose 3}$ for $n\geq n_{0}$ |  | Bollobás [3] |  | Corollary 9 |  |
Falgas-Ravry&Vaughan [9] |  |  |  |  |  |
${\mathbf{D}}$ |  | ${\mathbf{B}}{\mathbf{D}}$ |  | ${\mathbf{B}}{\mathbf{C}}{\mathbf{D}}$ |  |
$\frac{n(n-1)}{3}$, $n\equiv 1,4$ |  |  $\frac{n(n-1)}{3}$, $n\equiv 1,4$ |  | $\frac{1}{4}n^{2}\bigl{(}1-o(1)\bigr{)}$ |  |
$\frac{n(n-1)}{3}-4$, $n\equiv 7,10$ |  |  $\frac{n(n-1)}{3}-4$, $n\equiv 7,10$ |  | Theorem 22 |  |
$\frac{n(n-2)}{3}$, $n\equiv 0,2,3,6,8,9$ |  |  $\frac{n(n-2)}{3}$, $n\equiv 0,2,3,8$ |  |  |  |
$\frac{n(n-2)}{3}-1$, $n\equiv 5,11$ |  |  $\frac{n(n-2)}{3}-1$, $n\equiv 5,6,9,11$ |  |  |  |
$n\geq n_{0}$ (residues mod $12$) |  |  $n\geq n_{0}$ (residues mod $12$) |  |  |  |
Theorem 3 |  | Theorem 3 |  |  |  |
|  | ${\mathbf{C}}{\mathbf{D}}$ |  |  |  |
|  | $\lfloor\frac{1}{4}(n-1)^{2}\rfloor$ |  |  |  |
|  | and char. ext. |  |  |  |
|  | Theorem 8 |  |  |  |
Table 1: A summary of results. For each combination of excluded
configurations, we indicate the value of the extremum (the largest size of a
triple system on $n$ vertices obeying those exclusions) to the extent that it
is known. We also point out the existence of a characterization of the
extremal constructions when available. For earlier results we cite the papers,
for new ones we refer to the relevant theorems in the present paper.

##  2 The starting case: no triangle at all

How large can a triple system ${\mathcal{F}}$ on $n$ vertices be, if it
contains no triangle at all? Here is a construction originally suggested by
András Gyárfás as a conjectured optimum. Let $n\geq 3$ be given, and let $k$
be a positive integer such that $2k<n$. Partition the set $V$ of $n$ vertices
into $k$ pairs $A_{1},\ldots,A_{k}$ and a set $B$ of size $n-2k$. Let
${\mathcal{F}}_{n,k}$ consist of all $k(n-2k)$ triples of the form
$A_{i}\cup\\{b\\}$ where $1\leq i\leq k$ and $b\in B$. Then
${\mathcal{F}}_{n,k}$ contains no triangles. To maximize the size $k(n-2k)$
for a given $n$, we choose $k$ to be as close as possible to $\frac{n}{4}$
(this choice is unique unless $n\equiv 2\,(\mathrm{mod}\,4)$, in which case
the two choices $k=\frac{n\pm 2}{4}$ are equally good). With this optimal
choice of $k$ we have $|{\mathcal{F}}_{n,k}|=\lfloor\frac{1}{8}n^{2}\rfloor$.

The optimality of this construction among all triangle-free triple systems was
proved by Győri [16]. Here we reproduce the proof and extend the analysis to
obtain also a characterization of the extremal constructions.

######  Theorem 1.

${\rm
ex}(n,{\mathbf{A}}{\mathbf{B}}{\mathbf{C}}{\mathbf{D}})=\lfloor\frac{1}{8}n^{2}\rfloor$

and equality is attained by a triple system ${\mathcal{F}}$ if and only if it
is of the form ${\mathcal{F}}_{n,k}$ with $k$ chosen optimally as indicated
above.

###### Proof.

Let ${{\mathcal{F}}}$ be a triple system not containing any of
${\mathbf{A}},{\mathbf{B}},{\mathbf{C}},{\mathbf{D}}.$ First observe that not
containing ${\mathbf{C}}$ and ${\mathbf{D}}$ implies (in fact, is equivalent
to) that every triple contains at least two pairs which are its own. For those
triples containing three own pairs choose two that we single out as special.
Consider the graph $G$ on $V({{\mathcal{F}}})$ formed by the own pairs and the
special own pairs of the triples containing two or three own pairs,
respectively. We claim that $G$ is triangle-free. Indeed, if a triangle were
formed by own pairs of three different triples, then we would have a triangle
in ${{\mathcal{F}}}$ in the hypergraph sense, that is, one of our forbidden
configurations would appear. Thus at least two edges of a triangle in $G$
should be own pairs of the same triple $F$. However, in that case the third
edge of the triangle is also contained in $F$, thus it cannot be the own pair
of another triple $F^{\prime}$. But it also cannot be an edge of $G$ as a
third own pair of $F$ since every triple in ${{\mathcal{F}}}$ is represented
by exactly two pairs in $G$. Therefore a triangle in $G$ cannot occur. This
implies by Turán’s theorem that $|E(G)|\leq\frac{1}{4}n^{2}$. Since
$|E(G)|=2|{\mathcal{F}}|$, we got
$|{\mathcal{F}}|\leq\lfloor\frac{1}{8}n^{2}\rfloor.$

It remains to show that if $|{\mathcal{F}}|=\lfloor\frac{1}{8}n^{2}\rfloor$
then ${\mathcal{F}}$ must be of the form ${\mathcal{F}}_{n,k}$. Note that
$|E(G)|=2\lfloor\frac{1}{8}n^{2}\rfloor$, and this number equals
$\lfloor\frac{1}{4}n^{2}\rfloor$ unless $n\equiv 2\,(\mathrm{mod}\,4)$, in
which case it equals $\lfloor\frac{1}{4}n^{2}\rfloor-1$. By known
characterizations (see [7]) of the extremal and next-to-extremal cases for
Turán’s theorem, $G$ must be bipartite with parts $A$ and $B$ satisfying one
of the following:

  * (a)

$n\not\equiv 2\,(\mathrm{mod}\,4)$, $|A|$ and $|B|$ differ by at most $1$ and
$G$ is complete bipartite.

  * (b)

$n\equiv 2\,(\mathrm{mod}\,4)$, $|A|=|B|$ and $G$ is complete bipartite minus
one edge.

  * (c)

$n\equiv 2\,(\mathrm{mod}\,4)$, $|A|$ and $|B|$ differ by $2$ and $G$ is
complete bipartite.

Each triple in ${\mathcal{F}}$ contributes two own pairs to $G$, hence
contains two vertices in $A$ and one in $B$ or vice versa. We claim that all
triples in ${\mathcal{F}}$ must be of the same kind, i.e., the same part
contains two vertices from each triple. Assume, for the sake of contradiction,
that there are triples $F_{A},F_{B}\in{\mathcal{F}}$ such that $F_{A}\cap
A=\\{x,x^{\prime}\\}$ and $F_{B}\cap B=\\{y,y^{\prime}\\}$. Out of the four
pairs in $\\{x,x^{\prime}\\}\times\\{y,y^{\prime}\\}$, at most one is a non-
edge of $G$. Hence w.l.o.g. $x^{\prime}y,yx,xy^{\prime}$ form a path in $G$.
Say these edges of $G$ represent the triples $F_{1},F_{2},F_{3}$ in
${\mathcal{F}}$, respectively. Clearly, $F_{1},F_{2}$ and $F_{3}$ cannot all
be the same triple, so w.l.o.g. $F_{1}\neq F_{2}$, and neither $F_{1}$ nor
$F_{2}$ contains $\\{x,x^{\prime}\\}$. But then $F_{A},F_{1},F_{2}$ are three
distinct triples in ${\mathcal{F}}$ which form a forbidden triangle.

Thus, we assume w.l.o.g. that every triple in ${\mathcal{F}}$ contains two
vertices in $A$ and one in $B$. For each vertex $b\in B$, its link in
${\mathcal{F}}$ consists of disjoint pairs in $A$ (otherwise, we would have an
edge of $G$ that belongs to two triples in ${\mathcal{F}}$). This gives the
upper bound

$|{\mathcal{F}}|\leq\lfloor\frac{|A|}{2}\rfloor\cdot|B|.$

If $|A|$ is odd, this bound is strictly smaller than
$\lfloor\frac{1}{8}n^{2}\rfloor$. Thus $|A|$ must be even, ruling out case (b)
above. Moreover, the bound must hold as an equality, so the link of each $b\in
B$ is a partition of $A$ into $k$ pairs $A_{1},\ldots,A_{k}$, where
$k=\frac{|A|}{2}$. Furthermore, this partition must be the same for all $b\in
B$, otherwise there would be a forbidden triangle. This shows that
${\mathcal{F}}$ is of the form ${\mathcal{F}}_{n,k}$, and the conditions on
the difference between $|A|$ and $|B|$ in cases (a), (c) above imply the
optimal choice of $k$. ∎

##  3 Earlier results

The four cases where we exclude just one type of triangle creating
configurations ${\mathbf{A}},{\mathbf{B}},{\mathbf{C}}$, or ${\mathbf{D}}$,
were already investigated in some different context. In particular, ${\rm
ex}(n,{\mathbf{A}})={{n-1}\choose 2}$ for large enough $n$ is proven in [12]
(as Theorem 3.3). This result also determines that all extremal constructions
are full stars, $3$-uniform hypergraphs containing all edges through a fixed
vertex.

${\rm ex}(n,{\mathbf{A}})={n-1\choose 2}\text{ for }n\geq n_{0}.$

Observing that this construction also does not contain configuration
${\mathbf{B}}$, we have that the same holds for
${\mathbf{A}}{\mathbf{B}}$-free hypergraphs, too. Here (in Section 4) we prove
that $n_{0}=5$ for ${\rm ex}(n,{\mathbf{A}}{\mathbf{B}})$.

An early attempt to generalize Turán’s theorem to hypergraphs (for triple
systems) was proposed by Erdős and Katona, who conjectured that the largest
triple system on $n$ vertices such that no three distinct triples $A,B,C$
satisfy $A\bigtriangleup B\subset C$ is the complete $3$-partite hypergraph
with part sizes as equal as possible. Here $\bigtriangleup$ is the symmetric
difference, $A\bigtriangleup B=(A\setminus B)\cup(B\setminus A)$. One can see
that (for $A\neq B$) $A\bigtriangleup B\subset C$ can only occur when $A$ and
$B$ have two common vertices and the three triples form either a configuration
${\mathbf{B}}$ or ${\mathbf{C}}$. The conjecture was verified by Bollobás [3]
thus showing

${\rm ex}(n,{\mathbf{B}}{\mathbf{C}})=\lfloor{n\over
3}\rfloor\lfloor{{n+1}\over 3}\rfloor\lfloor{{n+2}\over 3}\rfloor.$

Frankl and Füredi (in [10] as Theorem 4) sharpened Bollobás’s theorem proving
that for $n\geq 3000$ it is sufficient to exclude only ${\mathbf{B}}$.
Subsequently, a new proof was given by Keevash and Mubayi [18] who also
significantly lowered the constraint for $n$:

${\rm ex}(n,{\mathbf{B}})=\lfloor{n\over 3}\rfloor\lfloor{{n+1}\over
3}\rfloor\lfloor{{n+2}\over 3}\rfloor\quad{\rm for\,\,}n\geq 33,$

with equality only for the balanced complete 3-partite hypergraph. They also
proved that the extremal family is rather stable, namely for any
$\varepsilon>0$ there exists $\delta>0$ such that if ${\mathcal{H}}$ is a
${\mathbf{B}}$-free triple system on $n$ vertices with at least
$(1-\delta)\frac{1}{27}n^{3}$ edges, then there exists a partition of the
vertex set of $\mathcal{H}$ as $V({\mathcal{H}})=V_{1}\cup V_{2}\cup V_{3}$ so
that all but at most $\varepsilon n^{3}$ edges of $\mathcal{H}$ have one
vertex in each $V_{i}$.

The value of ${\rm ex}(n,{\mathbf{C}})$ is not known, it is a famous problem
proposed by Erdős and Sós [8] that is thought to be difficult. Frankl and
Füredi [11] gave a recursive construction based on the design $S_{2}(6,3,2)$,
yielding the best known lower bound ${\rm
ex}(n,{\mathbf{C}})\geq\frac{2}{7}{n\choose 3}\bigl{(}1-o(1)\bigr{)}$. An
upper bound with $\frac{1}{3}$ instead of $\frac{2}{7}$ was proved by de Caen
[5] and Sidorenko [21]. A sequence of small improvements of the coefficient
$\frac{1}{3}$ followed. The current record, obtained by Falgas-Ravry and
Vaughan [9] using semi-definite programming, is slightly less than $0.287$
(close to but still larger than $\frac{2}{7}$). Thus

$\frac{2}{7}{n\choose 3}\bigl{(}1-o(1)\bigr{)}\leq{\rm ex}(n,{\mathbf{C}})\leq
0.287{n\choose 3}\bigl{(}1+o(1)\bigr{)}.$

Configuration ${\mathbf{D}}$ is the most restrictive in terms of the largest
size of a triple system excluding it: the upper bound ${\rm
ex}(n,{\mathbf{D}})\leq\frac{n(n-1)}{3}$ follows from Theorem 3.8 of Frankl
and Füredi [12]. Determining the exact value of ${\rm ex}(n,{\mathbf{D}})$
takes more work, which we carry out below in Section 5.

##  4 Excluding ${\mathbf{A}}$ and ${\mathbf{B}}$

Concerning ${\rm ex}(n,{\mathbf{A}}{\mathbf{B}})$ we prove a stronger
statement.

Define configuration ${\mathbf{A}}^{+}$ as a six vertex triple system of four
edges with $V=\\{1,\dots,6\\},E=\\{123,124,135,236\\}.$ This is the same as
${\mathbf{A}}$ with the middle triangle $123$ as an additional triple.
Similarly, configuration ${\mathbf{B}}^{+}$ on five vertices is the same as
${\mathbf{B}}$ with one more central triple $123$, i.e.,
$V=\\{1,\dots,5\\},E=\\{123,125,134,234\\}.$ We obviously have ${\rm
ex}(n,{\mathbf{A}}{\mathbf{B}})\leq{\rm
ex}(n,{\mathbf{A}}^{+}{\mathbf{B}}^{+})$. Since the full star contains neither
configuration ${\mathbf{A}}$ nor configuration ${\mathbf{B}}$, the following
theorem implies the similar statement for ${\rm
ex}(n,{\mathbf{A}}{\mathbf{B}})$ in place of ${\rm
ex}(n,{\mathbf{A}}^{+}{\mathbf{B}}^{+})$.

######  Theorem 2.

${\rm ex}(n,{\mathbf{A}}^{+}{\mathbf{B}}^{+})={n-1\choose 2}\text{ for }n\geq
5$

and the only extremal family is the full star.

###### Proof.

Let ${\mathcal{F}}\subseteq{[n]\choose 3}$ be an optimal
${\mathbf{A}}^{+}{\mathbf{B}}^{+}$-free family. Define
${\mathcal{F}}_{1}\subseteq{\mathcal{F}}$ as the family of triples with an own
pair,
${\mathcal{F}}_{1}:=\left\\{xyz\in{\mathcal{F}}:\min\\{\deg_{{\mathcal{F}}}(xy),\deg_{{\mathcal{F}}}(yz),\deg_{{\mathcal{F}}}(zx)\\}=1\right\\}$,
and let ${\mathcal{F}}_{2}:={\mathcal{F}}\setminus{\mathcal{F}}_{1}$. Our main
observation is that for every $F=xyz\in{\mathcal{F}}_{2}$ we have
$\deg_{{\mathcal{F}}}(xy)=\deg_{{\mathcal{F}}}(yz)=\deg_{{\mathcal{F}}}(zx)=2$.
Indeed, by definition, all these three pairs have degrees at least $2$, so one
can find triples $xya$, $yzb$, $zxc\in{\mathcal{F}}$ such that
$\\{x,y,z\\}\cap\\{a,b,c\\}=\emptyset$. These three triples together with
$xyz$ form a configuration ${\mathbf{A}}^{+}$ or ${\mathbf{B}}^{+}$ unless
$a=b=c$. We obtain that $a$ is unique so $\deg_{\mathcal{F}}(xy)=2$, and
similarly for $b$ and $c$.

Define a nonnegative function $w(e,F):{[n]\choose 2}\times{[n]\choose
3}\to\mathbb{R}$ as follows. It is always $0$ except when $e\subset F$,
$F\in{\mathcal{F}}$, when it is $\frac{1}{\deg_{\mathcal{F}}(e)}$. Note that
here $\frac{1}{\deg_{\mathcal{F}}(e)}\geq\frac{1}{n-2}$. For every pair
$e\in\partial{\mathcal{F}}$ we have

$w(e):=\sum_{F\in{\mathcal{F}}}w(e,F)=\sum_{F:e\subset
F\in{\mathcal{F}}}\frac{1}{\deg_{{\mathcal{F}}}(e)}=1.$

For every $F\in{\mathcal{F}}_{1}$, $F=xyz$ we have

$w(F):=\sum_{e\subset
F,|e|=2}w(e,F)=\frac{1}{\deg_{\mathcal{F}}(xy)}+\frac{1}{\deg_{\mathcal{F}}(yz)}+\frac{1}{\deg_{\mathcal{F}}(zx)}\geq
1+\frac{2}{n-2}=\frac{n}{n-2}.$

For each $F\in{\mathcal{F}}_{2}$ we have $w(F)=\frac{3}{2}$. Assuming that
$n\geq 6$, this is at least $\frac{n}{n-2}$, hence

${n\choose
2}\geq|\partial{\mathcal{F}}|=\sum_{e\in\partial{\mathcal{F}}}w(e)=\sum_{e}\sum_{F\in{\mathcal{F}}}w(e,F)=\sum_{F\in{\mathcal{F}}}w(F)\geq\frac{n}{n-2}|{\mathcal{F}}|.$

This yields ${n-1\choose 2}\geq|{\mathcal{F}}|$. For $n\geq 7$ we infer that
equality can hold only if ${\mathcal{F}}={\mathcal{F}}_{1}$, and each
$F\in{\mathcal{F}}$ has a unique own $2$-subset. The set-pair theorem of
Bollobás [2] gives that ${\mathcal{F}}$ is a full star.

In case of ${\mathcal{F}}_{2}=\emptyset$ the above proof works for all $n\geq
5$. If $n=6$ and ${\mathcal{F}}_{2}\neq\emptyset$ then it contains a
$\binom{[4]}{3}$. The additional triples must contain $\\{5,6\\}$, hence there
are at most four more of them ($x56$ with $1\leq x\leq 4$). We get
$|{\mathcal{F}}|\leq{4\choose 3}+4<{5\choose 2}$. Finally, in the case $n=5$
and ${\mathcal{F}}_{2}\neq\emptyset$ the family ${\mathcal{F}}$ consists of
the four triples of $\binom{[4]}{3}$, hence $|{\mathcal{F}}|<{4\choose 2}$. ∎

##  5 Excluding ${\mathbf{D}}$ (or ${\mathbf{B}}$ and ${\mathbf{D}}$)

As mentioned, the upper bound ${\rm ex}(n,{\mathbf{D}})\leq\frac{n(n-1)}{3}$
follows from [12]. Here we conduct a careful analysis showing that this bound
is either tight or nearly tight, depending on the residue of $n$ modulo $12$.
The same analysis also determines ${\rm ex}(n,{\mathbf{B}}{\mathbf{D}})$. The
following theorem summarizes our findings.

######  Theorem 3.

There exists $n_{0}$ such that for all $n\geq n_{0}$ we have:

${\rm ex}(n,{\mathbf{D}})={\rm
ex}(n,{\mathbf{B}}{\mathbf{D}})=\begin{cases}\dfrac{n(n-1)}{3}&\text{if
}n\equiv 1,4\,(\mathrm{mod}\,12)\\\ \dfrac{n(n-1)}{3}-4&\text{if }n\equiv
7,10\,(\mathrm{mod}\,12)\\\ \dfrac{n(n-2)}{3}&\text{if }n\equiv
0,2,3,8\,(\mathrm{mod}\,12)\\\ \dfrac{n(n-2)}{3}-1&\text{if }n\equiv
5,11\,(\mathrm{mod}\,12)\end{cases}$ ${\rm
ex}(n,{\mathbf{D}})=\frac{n(n-2)}{3}\text{ and }{\rm
ex}(n,{\mathbf{B}}{\mathbf{D}})=\frac{n(n-2)}{3}-1\text{ if }n\equiv
6,9\,(\mathrm{mod}\,12).$

Without the requirement $n\geq n_{0}$, the indicated quantities are always
valid as upper bounds, and as exact values for $n\equiv
0,1,3,4\,(\mathrm{mod}\,12)$.

###  5.1 Preparations for the proof

In preparation for the proof, we develop or recall some tools that will be
used in it. Let ${\mathcal{F}}$ be a triple system on a vertex set $V$,
$|V|=n$. We call two triples in ${\mathcal{F}}$ _contiguous_ if they share two
vertices. The contiguity relation defines a graph on ${\mathcal{F}}$, which
allows us to partition ${\mathcal{F}}$ uniquely into its connected components
with respect to contiguity:

${\mathcal{F}}=\bigcup_{i=1}^{r}{\mathcal{F}}_{i}$

Let us denote by $\partial{\mathcal{F}}_{i}$ the shadow of
${\mathcal{F}}_{i}$, i.e., the set of those pairs contained in some triple in
${\mathcal{F}}_{i}$. Viewing the $\partial{\mathcal{F}}_{i}$ as graphs, they
are edge-disjoint.

Two special types of ${\mathcal{F}}_{i}$ serve as building blocks of
${\mathbf{D}}$-free triple systems. One, that we call a _cluster_ , consists
of $3$ or $4$ triples on $4$ vertices; its shadow is a $K_{4}$ graph. The
other, that we call a $k$-_crown_ , consists of some number $k\geq 1$ of
triples, all sharing a fixed pair of vertices $x$ and $y$; its shadow is a
book graph $B_{k}$ on $k+2$ vertices, consisting of $k$ triangles sharing an
edge. In the case $k=1$ we get a single triple (triangle). The following easy-
to-check fact is recorded here for later reference.

######  Observation 4.

A triple system ${\mathcal{F}}$ is ${\mathbf{D}}$-free if and only if each of
its connected components ${\mathcal{F}}_{i}$ is either a cluster or a
$k$-crown for some $k\geq 1$.

Thus, constructing a ${\mathbf{D}}$-free triple system ${\mathcal{F}}$ on $V$
amounts to packing edge-disjoint copies of $K_{4}$ and some $B_{k}$’s in the
complete graph $K_{n}$. As we are interested in the largest possible
${\mathcal{F}}$, we may assume that each copy of $K_{4}$ contributes $4$
triples to ${\mathcal{F}}$. The ratio
$\frac{|{\mathcal{F}}_{i}|}{|E(\partial{\mathcal{F}}_{i})|}$ is $\frac{2}{3}$
in each cluster and less than $\frac{1}{2}$ in each crown. Hence we would like
to pack in $K_{n}$ as many copies of $K_{4}$ as we can, and use the leftover
edges, if any, to add copies of some $B_{k}$’s if possible. The maximum number
of copies of a fixed graph $H$ that can be packed in $K_{n}$ was determined
for large enough $n$ by Caro and Yuster [6]. Their main tool, which will also
be ours, was the following decomposition theorem of Gustavsson, which extends
Wilson’s theorem (see Theorem 23 below) from complete graphs to sufficiently
dense ones.

######  Theorem 5 (Gustavsson [15], Glock et al. [14]).

For every fixed graph $H$ there exist $n_{0}=n_{0}(H)$ and
$\varepsilon=\varepsilon(H)>0$ such that the following holds for all $n\geq
n_{0}$ and every graph $G$ on $n$ vertices with all vertex degrees greater
than $(1-\varepsilon)n$:
There exists a decomposition of the edge set $E(G)$ into copies of $H$ if and
only if the number of edges of $H$ divides that of $G$, and the greatest
common divisor of the vertex degrees in $H$ divides that of the vertex degrees
in $G$.

We will apply this theorem to $H=K_{4}$. In this case, the divisibility
conditions become: $6||E(G)|$ and $3|\deg_{G}(v)$ for all $v\in V$. These
conditions are satisfied by $G=K_{n}$ if and only if $n\equiv
1,4\,(\mathrm{mod}\,12)$. For all (not just large enough) $n\equiv
1,4\,(\mathrm{mod}\,12)$, a full packing of copies of $K_{4}$ in $K_{n}$ is
known to exist (Hanani [17]). When such a full packing does not exist, we will
use a decomposition into $K_{4}$’s of a large subgraph $G$ of $K_{n}$,
specified by describing its complement $\overline{G}$. In terms of
$\overline{G}$ the divisibility conditions become:

$|E(\overline{G})|\equiv{n\choose 2}\,(\mathrm{mod}\,6)\text{ and
}\deg_{\overline{G}}(v)\equiv n-1\,(\mathrm{mod}\,3)\text{ for all }v\in V.$

The graphs $\overline{G}$ that we will specify have constant maximum degree,
which ensures that all vertex degrees in $G$ will be greater than
$(1-\varepsilon)n$ for large enough $n$. The $K_{4}$-decomposition of $G$
provided by Theorem 5, plus some edge-disjoint $B_{k}$’s in $\overline{G}$
when available, will naturally define a large ${\mathbf{D}}$-free triple
system ${\mathcal{F}}$. In most cases this ${\mathcal{F}}$ will also be
${\mathbf{B}}$-free; when this is not the case we will modify $\overline{G}$
to get a slightly smaller triple system which is
${\mathbf{B}}{\mathbf{D}}$-free.

Another useful way to analyze triple systems ${\mathcal{F}}$ is by describing
their links. Recall that the link ${\mathcal{F}}[x]$ of a vertex $x$ is the
graph on $V\setminus\\{x\\}$ whose edges are those pairs of vertices that form
with $x$ a triple in ${\mathcal{F}}$. Here is another simple characterization
of ${\mathbf{D}}$-free triple systems.

######  Observation 6.

A triple system ${\mathcal{F}}$ is ${\mathbf{D}}$-free if and only if each of
its links ${\mathcal{F}}[x]$ is a vertex-disjoint union of triangles and stars
(including the cases of an isolated vertex or edge). For such ${\mathcal{F}}$,
denoting by $\mathrm{st}({\mathcal{F}}[x])$ the number of stars in
${\mathcal{F}}[x]$, we have

$|{\mathcal{F}}|=\frac{1}{3}\sum_{x\in
V}\bigl{(}n-1-\mathrm{st}({\mathcal{F}}[x])\bigr{)}.$

Note that this immediately implies the following upper bound:

${\rm ex}(n,{\mathbf{D}})\leq\begin{cases}\dfrac{n(n-1)}{3}&\text{if }n\equiv
1\,(\mathrm{mod}\,3)\\\ \dfrac{n(n-2)}{3}&\text{if }n\not\equiv
1\,(\mathrm{mod}\,3)\end{cases}$

In our detailed analysis, depending on the residue of $n$ modulo $12$, we will
construct ${\mathbf{D}}$ (and even ${\mathbf{B}}{\mathbf{D}}$)-free triple
systems that match this upper bound exactly or up to a small constant
difference, and prove their optimality.

###  5.2 Proof of Theorem 3

Case 1 $n\equiv 1,4\,(\mathrm{mod}\,12)$

We saw that $\frac{n(n-1)}{3}$ is an upper bound on the size of a
${\mathbf{D}}$-free triple system. A matching construction is obtained by
placing $4$ triples in each copy of $K_{4}$ in a full packing in $K_{n}$,
which exists by [17]. This gives a triple sytem ${\mathcal{F}}$ of size
$|{\mathcal{F}}|=4\cdot\frac{1}{6}{n\choose 2}=\frac{n(n-1)}{3}$, which is
${\mathbf{B}}$-free as well.

Case 2 $n\equiv 0,3\,(\mathrm{mod}\,12)$

We saw that $\frac{n(n-2)}{3}$ is an upper bound on the size of a
${\mathbf{D}}$-free triple system in this case. For a matching construction,
we use a packing of $\frac{n(n-3)}{12}$ copies of $K_{4}$ and $\frac{n}{3}$
triangles in $K_{n}$. Such a packing can be obtained by starting with a full
packing of copies of $K_{4}$ in $K_{n+1}$, which exists by [17], and deleting
one vertex. Placing $4$ triples in each copy of $K_{4}$ and one in each
triangle gives a ${\mathbf{B}}{\mathbf{D}}$-free triple system ${\mathcal{F}}$
of size $|{\mathcal{F}}|=\frac{n(n-3)}{3}+\frac{n}{3}=\frac{n(n-2)}{3}$.

Case 3 $n\equiv 2,8\,(\mathrm{mod}\,12)$

Again, $\frac{n(n-2)}{3}$ is an upper bound. For a matching construction for
large enough $n$, we use Theorem 5 as follows. We take $\overline{G}$ to be a
perfect matching in $K_{n}$, noting that it satisfies the required conditions:
$|E(\overline{G})|=\frac{n}{2}\equiv{n\choose 2}\,(\mathrm{mod}\,6)$ and
$\deg_{\overline{G}}(v)=1\equiv n-1\,(\mathrm{mod}\,3)$. Placing $4$ triples
in each copy of $K_{4}$ in a $K_{4}$-decomposition of $G$ we get a
${\mathbf{B}}{\mathbf{D}}$-free triple system ${\mathcal{F}}$ of size
$|{\mathcal{F}}|=\frac{2}{3}\bigl{(}{n\choose
2}-\frac{n}{2}\bigr{)}=\frac{n(n-2)}{3}$.

Case 4 $n\equiv 5,11\,(\mathrm{mod}\,12)$

We start with the construction for large enough $n$, using Theorem 5. We take
$\overline{G}$ to consist of a matching of $\frac{n-5}{2}$ edges and a star on
the remaining $5$ vertices. The required conditions are satisfied:
$|E(\overline{G})|=\frac{n-5}{2}+4\equiv{n\choose 2}\,(\mathrm{mod}\,6)$ and
$\deg_{\overline{G}}(v)\in\\{1,4\\}\equiv n-1\,(\mathrm{mod}\,3)$ for all
$v\in V$. Placing $4$ triples in each copy of $K_{4}$ in a decomposition of
$G$, we get a ${\mathbf{B}}{\mathbf{D}}$-free triple system ${\mathcal{F}}$ of
size $|{\mathcal{F}}|=\frac{2}{3}\bigl{(}{n\choose
2}-\frac{n+3}{2}\bigr{)}=\frac{n(n-2)}{3}-1$.

To see that this is optimal, assume that there is a ${\mathbf{D}}$-free triple
system ${\mathcal{F}}$ of size $|{\mathcal{F}}|=\frac{n(n-2)}{3}$. By
Observation 6, we must have $\mathrm{st}({\mathcal{F}}[x])=1$ for every vertex
$x$. Consider the mapping defined on $V$ by $x\mapsto y$, where $y\neq x$ is
the center of the star in the link ${\mathcal{F}}[x]$. This is well defined,
because there is a unique star and it has a unique center (the star cannot be
a single edge because it has $1\,(\mathrm{mod}\,3)$ vertices). Note also that
$x\mapsto y$ implies $y\mapsto x$, so this mapping partitions $V$ into pairs,
which is impossible because $n$ is odd.

Case 5a $n\equiv 6,9\,(\mathrm{mod}\,12)$, excluding ${\mathbf{D}}$

We saw that $\frac{n(n-2)}{3}$ is an upper bound in this case. For a matching
construction for large enough $n$, we use Theorem 5 as follows. We take
$\overline{G}$ to consist of $\frac{n-6}{3}$ vertex-disjoint triangles and a
$B_{4}$ on the remaining vertices. The required conditions are satisfied:
$|E(\overline{G})|=(n-6)+9\equiv{n\choose 2}\,(\mathrm{mod}\,6)$ and
$\deg_{\overline{G}}(v)\in\\{2,5\\}\equiv n-1\,(\mathrm{mod}\,3)$ for all
$v\in V$. Placing $4$ triples in each copy of $K_{4}$ in a decomposition of
$G$, one in each triangle in $\overline{G}$, and $4$ in the book $B_{4}$, we
get a ${\mathbf{D}}$-free triple system ${\mathcal{F}}$ of size
$|{\mathcal{F}}|=\frac{2}{3}\bigl{(}{n\choose
2}-n-3\bigr{)}+\frac{n-6}{3}+4=\frac{n(n-2)}{3}$.

Case 5b $n\equiv 6,9\,(\mathrm{mod}\,12)$, excluding
${\mathbf{B}}{\mathbf{D}}$

Note that the construction in Case 5a is not ${\mathbf{B}}$-free, because two
triples $xyz,xyw$ from the crown on $B_{4}$ form a ${\mathbf{B}}$
configuration with a triple containing $\\{z,w\\}$. We modify the
construction, letting $\overline{G}$ consist of $\frac{n-9}{3}$ vertex-
disjoint triangles and $4$ more triangles on the remaining vertices, all
sharing one vertex. The modification does not change the number of edges in
$\overline{G}$, and the only new degree is $8$, hence the required conditions
are satisfied. Placing $4$ triples in each copy of $K_{4}$ in a decomposition
of $G$ and one in each triangle in $\overline{G}$, we get a
${\mathbf{B}}{\mathbf{D}}$-free triple system ${\mathcal{F}}$ of size
$|{\mathcal{F}}|=\frac{2}{3}\bigl{(}{n\choose
2}-n-3\bigr{)}+\frac{n-9}{3}+4=\frac{n(n-2)}{3}-1$.

To see that this is optimal, assume that there is a
${\mathbf{B}}{\mathbf{D}}$-free triple system ${\mathcal{F}}$ of size
$|{\mathcal{F}}|=\frac{n(n-2)}{3}$. Then in each link ${\mathcal{F}}[x]$ there
must be exactly one star. We claim that none of the ${\mathcal{F}}_{i}$ (the
connected components of ${\mathcal{F}}$ with respect to contiguity, as defined
at the beginning of Subsection 5.1) can be a $k$-crown with $k\geq 2$. Suppose
that ${\mathcal{F}}_{i}$ is such a $k$-crown, consisting of the triples
$xyz_{i}$, $i=1,\ldots,k$. Then the link ${\mathcal{F}}[z_{1}]$ contains $xy$
as an isolated edge, and also $z_{2},\ldots,z_{k}$ as isolated vertices (the
latter is due to ${\mathbf{B}}$-freeness). This contradicts the uniqueness of
the star in each link. By Observation 4, it follows that each
${\mathcal{F}}_{i}$ is either a cluster or a $1$-crown (i.e., a triple
contiguous to no other triple). This implies that each link is a vertex-
disjoint union of $\frac{n-3}{3}$ triangles and an isolated edge. But this is
impossible: if every vertex appears in $\frac{n-3}{3}$ clusters, then the
number of clusters is $\frac{1}{4}n\cdot\frac{n-3}{3}$, which is not an
integer.

Case 6 $n\equiv 7,10\,(\mathrm{mod}\,12)$

We start with the construction for large enough $n$, using Theorem 5. We take
$\overline{G}$ to be the triangular prism graph (two vertex-disjoint triangles
with a perfect matching of their vertices) plus $n-6$ isolated vertices. The
required conditions are satisfied: $|E(\overline{G})|=9\equiv{n\choose
2}\,(\mathrm{mod}\,6)$ and $\deg_{\overline{G}}(v)\in\\{0,3\\}\equiv
n-1\,(\mathrm{mod}\,3)$ for all $v\in V$. Placing $4$ triples in each copy of
$K_{4}$ in a decomposition of $G$ and one in each of the two triangles in
$\overline{G}$, we get a ${\mathbf{B}}{\mathbf{D}}$-free triple system
${\mathcal{F}}$ of size $|{\mathcal{F}}|=\frac{2}{3}\bigl{(}{n\choose
2}-9\bigr{)}+2=\frac{n(n-1)}{3}-4$.

To see that this is optimal, assume that there is a ${\mathbf{D}}$-free triple
system ${\mathcal{F}}$ of size $|{\mathcal{F}}|=\frac{n(n-1)}{3}-3$. Consider
the decomposition of ${\mathcal{F}}$ into its connected components
${\mathcal{F}}_{i}$ with respect to contiguity. Let the graph $G$ be the edge-
disjoint union of the $K_{4}$’s that are the shadows of the cluster
${\mathcal{F}}_{i}$’s. Let $\overline{G}$ be the complement of $G$. The
divisibility conditions are:

$|E(\overline{G})|\equiv 3\,(\mathrm{mod}\,6)\text{ and
}\deg_{\overline{G}}(v)\equiv 0\,(\mathrm{mod}\,3)\text{ for all }v\in V.$

The shadows of the crown ${\mathcal{F}}_{i}$’s are edge-disjoint subgraphs of
$\overline{G}$, and the number of triples that each of them carries is less
than half its number of edges. Thus we have

$\frac{n(n-1)}{3}-3=|{\mathcal{F}}|\leq\frac{2}{3}|E(G)|+\frac{1}{2}|E(\overline{G})|=\frac{2}{3}{n\choose
2}-\frac{1}{6}|E(\overline{G})|$

from which we deduce that $|E(\overline{G})|\leq 18$. Together with the fact
that $|E(\overline{G})|\equiv 3\,(\mathrm{mod}\,6)$, this leaves only three
possibilities for $|E(\overline{G})|$, that we can rule out one-by-one:

  * •

$|E(\overline{G})|=3$
By $\deg_{\overline{G}}(v)\equiv 0\,(\mathrm{mod}\,3)$, all non-zero degrees
must be at least $3$, which is impossible with $3$ edges.

  * •

$|E(\overline{G})|=9$
All non-zero degrees must be exactly $3$, because there are not enough edges
to allow a degree of $6$ or more. Ignoring isolated vertices, $\overline{G}$
is a $3$-regular graph on $6$ vertices. A quick case check shows that such a
graph contains at most two triangles. Hence the total number of triples in
${\mathcal{F}}$ is at most the number in our construction, namely
$\frac{n(n-1)}{3}-4$.

  * •

$|E(\overline{G})|=15$
Let $t$ be the number of triples in ${\mathcal{F}}$ coming from
$\overline{G}$. From
$\frac{n(n-1)}{3}-3=|{\mathcal{F}}|\leq\frac{2}{3}\bigl{(}{n\choose
2}-15\bigr{)}+t$ we get that $t\geq 7$. The only way to obtain $7$ triples
from crowns whose edge-disjoint shadows have at most $15$ edges in total is to
use one $7$-crown. But then $\overline{G}$ is a book graph $B_{7}$ (plus
isolated vertices), having vertex degrees $2$ and $8$ which are not
$0\,(\mathrm{mod}\,3)$.

This completes the proof of Theorem 3. ∎

##  6 Excluding ${\mathbf{C}}$ and ${\mathbf{D}}$ (and ${\mathbf{A}}$,
optionally)

######  Observation 7.

The triple system ${\mathcal{F}}$ avoids ${\mathbf{C}}$ and ${\mathbf{D}}$ if
and only if each triple $F\in{\mathcal{F}}$ contains at least two own pairs.

Indeed, if $123\in{\mathcal{F}}$ with
$\deg_{\mathcal{F}}(12),\deg_{\mathcal{F}}(13)\geq 2$, then the three triples
$123,12x,13y$ either form a ${\mathbf{C}}$ (in case of $x=y$), or a
${\mathbf{D}}$ (in case of $x\neq y$). On the other hand, both ${\mathbf{C}}$
and ${\mathbf{D}}$ have a member with at most one own pair.

This observation gives ${\rm ex}(n,{\mathbf{C}}{\mathbf{D}})\leq{1\over
2}{n\choose 2}=\frac{1}{4}n^{2}\bigl{(}1-o(1)\bigr{)}$ and a construction of
matching order of magnitude is not hard to find. In this case, however, we
will give the exact value of ${\rm ex}(n,{\mathbf{C}}{\mathbf{D}})$ together
with a characterization of all the extremal constructions. As it turns out it
will be just one little step further to give a similar characterization of all
extremal ${\mathbf{A}}{\mathbf{C}}{\mathbf{D}}$-free constructions.

###  6.1 A construction based on a tournament

First we describe a construction we will call the tournament construction.
Consider a maximum size matching in the graph $K_{n}$. Fix a tournament $T$ on
a vertex set consisting of the edges of this matching. (Thus our tournament is
on $\lfloor{n\over 2}\rfloor$ vertices.) Let ${\mathcal{F}}_{T}$ be the
$3$-uniform hypergraph the edges of which are the triples consisting of a
matching edge plus a vertex of another matching edge into which the previous
matching edge (as a vertex of $T$) sends an edge in $T$. In case $n$ is odd,
the third vertex of an edge in ${\mathcal{F}}_{T}$ can also be the unique
unmatched vertex of our original $K_{n}$. The number of triples in
${\mathcal{F}}_{T}$ is $2{{n\over 2}\choose 2}$ if $n$ is even and
$2{{{n-1}\over 2}\choose 2}+{{n-1}\over 2}$ if $n$ is odd. (Both of the latter
can be written as $\lfloor\frac{1}{4}(n-1)^{2}\rfloor.$) It is easy to check
that each triple in ${\mathcal{F}}_{T}$ (for any possible $T$) contains two
own pairs, thus ${\mathbf{C}}$ and ${\mathbf{D}}$ do not appear in
${\mathcal{F}}_{T}$. This gives ${\rm
ex}(n,{\mathbf{C}}{\mathbf{D}})\geq\lfloor\frac{1}{4}(n-1)^{2}\rfloor.$

######  Theorem 8.

${\rm ex}(n,{\mathbf{C}}{\mathbf{D}})=\lfloor\frac{1}{4}(n-1)^{2}\rfloor$

and equality is attained by a triple system ${\mathcal{F}}$ if and only if it
is of the form ${\mathcal{F}}_{T}$ for some tournament $T$.

Before the proof we obtain the following immediate consequence.

######  Corollary 9.

${\rm
ex}(n,{\mathbf{A}}{\mathbf{C}}{\mathbf{D}})=\lfloor\frac{1}{4}(n-1)^{2}\rfloor$

and equality is attained by a triple system ${\mathcal{F}}$ if and only if it
is of the form ${\mathcal{F}}_{T}$ for the transitive tournament $T$.

Proof of Corollary 9. If $T$ is not transitive then it contains a cyclically
oriented triangle which gives rise to a configuration ${\mathbf{A}}$ in
${\mathcal{F}}_{T}$. On the other hand, if $T$ is transitive then
${\mathbf{A}}$ cannot occur in ${\mathcal{F}}_{T}$. This observation and the
trivial inequality ${\rm ex}(n,{\mathbf{A}}{\mathbf{C}}{\mathbf{D}})\leq{\rm
ex}(n,{\mathbf{C}}{\mathbf{D}})$ imply the statement by Theorem 8. ∎

###  6.2 Proof of Theorem 8

Let ${\mathcal{F}}$ be a triple system not containing ${\mathbf{C}}$ and
${\mathbf{D}}$ and having the maximum number of triples. Then
$|{\mathcal{F}}|\geq|{\mathcal{F}}_{T}|=\lfloor\frac{1}{4}(n-1)^{2}\rfloor$.
We have already observed that each $F\in{\mathcal{F}}$ has at least two own
pairs. We form a graph $G$ on $V({\mathcal{F}})$ by taking as edges exactly
two own pairs from each $F\in{\mathcal{F}}$. Let $\overline{G}$ be the
complement of $G$. Note that every $F\in{\mathcal{F}}$ has two of its pairs in
$G$ and the third in $\overline{G}$.

We claim that the edges of $\overline{G}$ form a matching of size
$\lfloor\frac{n}{2}\rfloor$. First, observe that $|E(G)|=2|{\mathcal{F}}|\geq
2\lfloor\frac{1}{4}(n-1)^{2}\rfloor=\lfloor\frac{1}{2}(n-1)^{2}\rfloor$. Hence
$|E(\overline{G})|\leq{n\choose
2}-\lfloor\frac{1}{2}(n-1)^{2}\rfloor=\lfloor\frac{n}{2}\rfloor$. Now we
distinguish two cases. If every vertex $x\in V({\mathcal{F}})$ is incident to
an edge of $\overline{G}$, then $\overline{G}$ must be a perfect matching (and
$n$ is even). In the other case, consider a vertex $x$ all of whose pairs are
edges of $G$. These $n-1$ pairs are own pairs of triples containing $x$, so
$n$ is odd and these triples are of the form
$xy_{1}z_{1},\ldots,xy_{(n-1)/2}z_{(n-1)/2}$ where
$y_{1}z_{1},\ldots,y_{(n-1)/2}z_{(n-1)/2}$ form a perfect matching in
$V({\mathcal{F}})\setminus\\{x\\}$ and each of them is an edge of
$\overline{G}$ (as the third pair of its triple). In this case, too, we get
that $\overline{G}$ is a matching of size $\lfloor\frac{n}{2}\rfloor$. In
particular, the inequalities above must hold as equalities, proving the first
part of the theorem.

To establish the tournament structure, we take the edges of $\overline{G}$ as
the maximum size matching (the vertices of the tournament). We already know
that each triple in ${\mathcal{F}}$ contains an edge of $\overline{G}$. Given
any two distinct edges of $\overline{G}$, the four crossing pairs between them
must be edges of $G$, hence own pairs of triples. This prevents the existence
of triples going both ways between two edges of $\overline{G}$, and implies
the tournament structure for ${\mathcal{F}}$. ∎

##  7 Excluding ${\mathbf{A}}$ and ${\mathbf{D}}$

For the combination ${\mathbf{A}}{\mathbf{D}}$, by our previous analysis for
${\mathbf{A}}{\mathbf{C}}{\mathbf{D}}$, we can write

${\rm ex}(n,{\mathbf{A}}{\mathbf{D}})\geq{\rm
ex}(n,{\mathbf{A}}{\mathbf{C}}{\mathbf{D}})=\lfloor\frac{1}{4}(n-1)^{2}\rfloor.$

We recall that ${\rm ex}(n,{\mathbf{A}}{\mathbf{C}}{\mathbf{D}})$ is attained
uniquely by the construction ${\mathcal{F}}_{T}$ based on a transitive
tournament $T$.

It turns out that the answer for ${\mathbf{A}}{\mathbf{D}}$ is similar, but a
bit more subtle. For any even $n\geq 4$ we can add two triples to
${\mathcal{F}}_{T}$ as indicated next, and still avoid ${\mathbf{A}}$ and
${\mathbf{D}}$. Say the pairs $12$ and $34$ are the elements of the tournament
$T$ with the lowest and second lowest outdegree, respectively. On these four
vertices, ${\mathcal{F}}_{T}$ contains the two triples $134,234$, and we can
add the other two triples $123,124$ without forming an ${\mathbf{A}}$ or
${\mathbf{D}}$. We denote this augmented construction by
${\mathcal{F}}_{T}^{+}$. For odd $n$ we cannot do better than
$\frac{1}{4}(n-1)^{2}$, but we can modify ${\mathcal{F}}_{T}$ as indicated
next, and get another extremal construction (assuming $n\geq 5$). Say
$0,12,34$ are the singleton and the two lowest outdegree elements of $T$,
respectively. On these five vertices, ${\mathcal{F}}_{T}$ contains the four
triples $012,034,134,234$. We can replace $012$ and $034$ by $123$ and $124$
without forming an ${\mathbf{A}}$ or ${\mathbf{D}}$. We denote this modified
construction by ${\mathcal{F}}_{T}^{\pm}$.

######  Theorem 10.

${\rm
ex}(n,{\mathbf{A}}{\mathbf{D}})=\begin{cases}\lfloor\frac{1}{4}(n-1)^{2}\rfloor+2&\text{if
}n\geq 4\text{ is even}\\\ \frac{1}{4}(n-1)^{2}&\text{if }n\text{ is
odd}\end{cases}$

and equality is attained by a triple system ${\mathcal{F}}$ if and only if it
is of the form ${\mathcal{F}}_{T}^{+}$ (for even $n\geq 4$) or one of the two
forms ${\mathcal{F}}_{T}$ or ${\mathcal{F}}_{T}^{\pm}$ (for odd $n\geq 5$) for
a transitive tournament $T$.

###### Proof.

We argue by induction on $n$. The base cases $n=3,4$ are trivial, so we assume
$n\geq 5$. Let ${\mathcal{F}}$ be an ${\mathbf{A}}{\mathbf{D}}$-free triple
system on the vertex set $V$, with $|V|=n$ and

$|{\mathcal{F}}|\geq
f(n)\coloneqq\begin{cases}\lfloor\frac{1}{4}(n-1)^{2}\rfloor+2&\text{if
}n\text{ is even}\\\ \frac{1}{4}(n-1)^{2}&\text{if }n\text{ is
odd}\end{cases}$

We have to show that $|{\mathcal{F}}|=f(n)$ and ${\mathcal{F}}$ is of one of
the specified forms.

Assume first that ${\mathcal{F}}$ is ${\mathbf{C}}$-free as well. Then by
Corollary 9 we have $|{\mathcal{F}}|\leq\lfloor\frac{1}{4}(n-1)^{2}\rfloor$,
so this is possible only when $n$ is odd, in which case we get
$|{\mathcal{F}}|=f(n)$ and ${\mathcal{F}}$ is of the form ${\mathcal{F}}_{T}$
(again by Corollary 9).

From now on, we assume that ${\mathcal{F}}$ does contain a ${\mathbf{C}}$
configuration, say on vertices $1,2,3,4$. Note that any triple in
${\mathcal{F}}$ that is not contained in $\\{1,2,3,4\\}$ intersects it in at
most one vertex – otherwise we get a ${\mathbf{D}}$ configuration. When $n=5$
this immediately implies that ${\mathcal{F}}$ consists only of the $4$ triples
in $\\{1,2,3,4\\}$, which form an ${\mathcal{F}}_{T}^{\pm}$. When $n=6$ this
implies that ${\mathcal{F}}$ consists of those $4$ triples and another $4$
triples of the form $i56$, $i=1,2,3,4$, yielding an ${\mathcal{F}}_{T}^{+}$.
Henceforth we assume $n\geq 7$, which will allow us to apply the induction
hypothesis to the family of those triples in ${\mathcal{F}}$ contained in
$V^{\prime}\coloneqq V\setminus\\{1,2,3,4\\}$.

For $i=1,2,3,4$, let $G_{i}$ be the graph whose edges are those pairs in
$V^{\prime}$ that form with the vertex $i$ a triple in ${\mathcal{F}}$. By the
absence of ${\mathbf{D}}$, the graph $G_{i}$ has no path of three edges,
implying that each connected component of $G_{i}$ is either a star (including
the cases of an isolated vertex or edge) or a triangle. By the absence of
${\mathbf{A}}$, an edge of $G_{i}$ and an edge of $G_{j}$, $j\neq i$, cannot
share exactly one vertex. Let $G$ be the multigraph on $V^{\prime}$ formed by
the $G_{i}$, $i=1,2,3,4$. By the two observations just made, each connected
component of $G$ is either a pair of vertices with $2,3$ or $4$ parallel edges
between them (say there are $m$ such pairs $P_{1},\ldots,P_{m}$), or a star or
triangle whose edges belong to a single $G_{i}$.

As the number of edges is at most $4$ in each $P_{j}$, and at most the number
of vertices in every other component of $G$, we can write

$|E(G)|\leq 4m+\bigl{(}n-4-2m\bigr{)}=n+2m-4.$

On the other hand, using the induction hypothesis and the equality
$f(n)-f(n-4)=2n-6$, we get

$f(n)\leq|{\mathcal{F}}|\leq 4+|E(G)|+f(n-4)=|E(G)|+f(n)-2n+10,$

implying that $|E(G)|\geq 2n-10$. Comparing these two bounds on $|E(G)|$, we
immediately get $2m\geq n-6$, so $\cup_{j=1}^{m}P_{j}$ covers all but at most
two vertices of $V^{\prime}$. Actually, it cannot leave out two vertices,
because then our upper bound on $|E(G)|$ is not tight (those two vertices
carry at most one edge). It follows that $P_{1},\ldots,P_{m}$ is a maximum
matching in $V^{\prime}$, i.e., $m=\lfloor\frac{n-4}{2}\rfloor$. Our bounds on
$|E(G)|$ become

$2n-10\leq|E(G)|\leq 4\lfloor\frac{n-4}{2}\rfloor.$

For odd $n$ the bounds coincide, implying that each $P_{j}$ has $4$ parallel
edges. For even $n$ there is a slack of $2$, so there may be one exceptional
$P_{j}$ with $2$ parallel edges, or at most two exceptional $P_{j}$ with $3$
parallel edges each. Note that in any case, for any two distinct
$P_{j},P_{k}$, there is a graph $G_{i}$ having an edge in both $P_{j}$ and
$P_{k}$.

We claim that any triple $F\in{\mathcal{F}}$, $F\subseteq V^{\prime}$ must
contain one of the pairs $P_{j}$, $j=1,\ldots,m$. If not, then $F$ is of the
form $xyz$ where $x\in P_{j}$, $y\in P_{k}$, $k\neq j$, and $z$ is either in a
third $P_{\ell}$ or (when $n$ is odd) is the unpaired vertex of $V^{\prime}$.
Let $x^{\prime}$ and $y^{\prime}$ be the other vertices of $P_{j}$ and
$P_{k}$, respectively, and let $i\in\\{1,2,3,4\\}$ be such that $E(G_{i})$
contains both $xx^{\prime}$ and $yy^{\prime}$. Then
$xyz,ixx^{\prime},iyy^{\prime}$ give an ${\mathbf{A}}$ configuration, which is
forbidden.

We claim further that for any two distinct pairs $P_{j}$ and $P_{k}$, there
cannot coexist in ${\mathcal{F}}$ a triple made of $P_{j}$ and a vertex of
$P_{k}$ and a triple made of $P_{k}$ and a vertex of $P_{j}$. Indeed, two such
triples and a triple of the form $P_{j}\cup\\{i\\}$, $i\in\\{1,2,3,4\\}$,
would yield a ${\mathbf{D}}$ configuration.

To summarize, the possible triples $F\in{\mathcal{F}}$, $F\subseteq
V^{\prime}$ are either contained in some $P_{j}\cup P_{k}$, $j\neq k$ (and
there are at most two such triples for each $j\neq k$), or consist of some
$P_{j}$ and the unpaired vertex of $V^{\prime}$ (when $n$ is odd). This gives
the following upper bound on $|{\mathcal{F}}|$:

$|{\mathcal{F}}|\leq\begin{cases}4+4\frac{n-4}{2}+2{\frac{n-4}{2}\choose
2}&\text{if }n\text{ is even}\\\ 4+4\frac{n-5}{2}+2{\frac{n-5}{2}\choose
2}+\frac{n-5}{2}&\text{if }n\text{ is odd}\end{cases}$

A calculation shows that for either parity, this bound equals $f(n)$. We
conclude that $|{\mathcal{F}}|=f(n)$ and all the triples counted in the upper
bound are in fact in ${\mathcal{F}}$. This ${\mathcal{F}}$ is easily seen to
be of the form ${\mathcal{F}}_{T}^{+}$ in the even case and
${\mathcal{F}}_{T}^{\pm}$ in the odd case, for a tournament $T$ in which
$P_{j}$ beats $P_{k}$ if the two triples in $P_{j}\cup P_{k}$ contain $P_{j}$,
and every $P_{j}$ beats $12$ and $34$. The tournament must be transitive in
order to avoid an ${\mathbf{A}}$ configuration. ∎

##  8 Excluding ${\mathbf{A}},{\mathbf{B}}$ and ${\mathbf{C}}$

###  8.1 A construction based on the Turán graph

Let ${{\mathcal{F}}^{*}_{n}}$ be the following triple system on a set $V$ of
$n$ vertices. Fix a vertex $x\in V$, and consider a complete bipartite graph
on $V\setminus\\{x\\}$ with parts of size $\lfloor{{n-1}\over 2}\rfloor$ and
$\lceil{{n-1}\over 2}\rceil$, respectively. Let the triple $F$ be in
${\mathcal{F}}^{*}_{n}$ if and only if $F$ consists of $x$ and an edge of the
complete bipartite graph. It is easy to check that none of ${\mathbf{A}}$,
${\mathbf{B}}$ and ${\mathbf{C}}$ is contained in ${\mathcal{F}}^{*}_{n}$, and
its size is $\lfloor\frac{1}{4}(n-1)^{2}\rfloor$.

######  Theorem 11.

${\rm
ex}(n,{\mathbf{A}}{\mathbf{B}}{\mathbf{C}})=\lfloor\frac{1}{4}(n-1)^{2}\rfloor$

and equality is attained by a triple system ${\mathcal{F}}$ if and only if it
is isomorphic to ${\mathcal{F}}^{*}_{n}$.

###  8.2 The structure of nearly extremal triangle-free graphs

We will need the following lemma about triangle-free graphs on $n$ vertices
having at least $\lfloor\frac{1}{4}(n-1)^{2}\rfloor$ edges. Given a graph
$G=(V,E)$, two vertices $x,y\in V$ are called _remote_ if the distance between
them in $G$ is greater than $2$.

######  Lemma 12.

Let $G=(V,E)$ be a triangle-free graph with $|V|=n$ and
$|E|\geq\lfloor\frac{1}{4}(n-1)^{2}\rfloor$. Then either

  1. 1.

$G$ is bipartite, and if $|E|>\lfloor\frac{1}{4}(n-1)^{2}\rfloor$ then no two
vertices of the same part are remote, or

  2. 2.

$G$ is non-bipartite, and there are at most two pairs of remote vertices (none
if $|E|>\lfloor\frac{1}{4}(n-1)^{2}\rfloor$).

###### Proof.

Our proof extends a classical one by Andrásfai, Erdős and Gallai (see [7]),
who showed that a triangle-free graph with at least
$\lfloor\frac{1}{4}(n-1)^{2}\rfloor+2$ edges must be bipartite.

Suppose first that $G$ is bipartite with parts $A$ and $B$ of cardinality $a$
and $b$, respectively, where $a+b=n$, $a\leq b$. If some two vertices of the
same part are remote, then at least $a$ pairs in $A\times B$ are non-edges in
$G$. This implies that $|E|\leq a(b-1)\leq\lfloor\frac{1}{4}(n-1)^{2}\rfloor$,
proving the assertion in the first part of the lemma.

Next, suppose that $G$ is non-bipartite, and let $C_{\ell}$ be a shortest odd
cycle in $G$, of length $\ell\geq 5$. To avoid a shorter odd cycle, $C_{\ell}$
must be induced, and every vertex in $V\setminus V(C_{\ell})$ can have at most
two neighbors in $V(C_{\ell})$. Using these facts, and Turán’s theorem for the
graph induced on $V\setminus V(C_{\ell})$, we get the upper bound

$|E|\leq\ell+2(n-\ell)+\lfloor\frac{1}{4}(n-\ell)^{2}\rfloor.$

This bound is a decreasing function of $\ell$, and for $\ell=7$ it is strictly
less than $\lfloor\frac{1}{4}(n-1)^{2}\rfloor$. Hence we must have $\ell=5$,
for which the bound becomes $|E|\leq\lfloor\frac{1}{4}(n-1)^{2}\rfloor+1$.

If $|E|=\lfloor\frac{1}{4}(n-1)^{2}\rfloor+1$ then $G$ has the following
structure: a $5$-cycle $C_{5}$, a complete bipartite graph
$K_{\lfloor\frac{n-5}{2}\rfloor,\lceil\frac{n-5}{2}\rceil}$ on $V\setminus
V(C_{5})$, and every vertex of the latter is joined by edges to two non-
adjacent vertices of the former. This graph is easily seen to have diameter
$2$, i.e., no pair of remote vertices. If
$|E|=\lfloor\frac{1}{4}(n-1)^{2}\rfloor$ then one of the two terms $2(n-5)$
and $\lfloor\frac{1}{4}(n-5)^{2}\rfloor$ in the upper bound on $|E|$ was off
by $1$. If it was the former, then there is a unique vertex $x$ in $V\setminus
V(C_{5})$ that has a single neighbor $y$ in $V(C_{5})$. Denoting the two
vertices of $C_{5}$ at distance $2$ from $y$ by $z$ and $w$, we see that there
are at most two pairs of remote vertices, $\\{x,z\\}$ and $\\{x,w\\}$. If it
was the latter, then the triangle-free graph induced on $V\setminus V(C_{5})$
has $\lfloor\frac{1}{4}(n-5)^{2}\rfloor-1$ edges, one less than the Turán
bound. This induced graph can only be of one of the following forms: the Turán
graph minus an edge, or (when $n-5$ is even) a
$K_{\frac{n-5}{2}-1,\frac{n-5}{2}+1}$, or (when $n-5=5$) another copy of
$C_{5}$. In each of these cases, one can check that there are at most two
pairs of remote vertices. ∎

###  8.3 Proof of Theorem 11

Let ${\mathcal{F}}$ be an ${\mathbf{A}}{\mathbf{B}}{\mathbf{C}}$-free triple
system on $n$ vertices. Then each triple in ${\mathcal{F}}$ has at least one
own pair. Choosing exactly one own pair from each triple, we get a graph
$G=(V,E)$ with $|E|=|{\mathcal{F}}|$. The absence of
${\mathbf{A}}{\mathbf{B}}{\mathbf{C}}$ in ${\mathcal{F}}$ implies that $G$ is
triangle-free, and for each triple in ${\mathcal{F}}$, one of its pairs is an
edge of $G$ and the other two pairs are remote in $G$.

We assume that $|E|=|{\mathcal{F}}|\geq\lfloor\frac{1}{4}(n-1)^{2}\rfloor$,
and apply Lemma 12 to the graph $G$. As each triple in ${\mathcal{F}}$
contributes two pairs of remote vertices, case 2 of the lemma cannot occur.
Thus we are in case 1, and $G$ is bipartite with bipartition $V=A\cup B$. Each
triple in ${\mathcal{F}}$ must contain an edge of $G$, hence two vertices in
one part and one in the other. By the above, the two vertices in the same part
are remote. If $|E|>\lfloor\frac{1}{4}(n-1)^{2}\rfloor$ we get a contradiction
to the statement of case 1 of the lemma. This proves that ${\rm
ex}(n,{\mathbf{A}}{\mathbf{B}}{\mathbf{C}})=\lfloor\frac{1}{4}(n-1)^{2}\rfloor$.

It remains to show that if
$|{\mathcal{F}}|=\lfloor\frac{1}{4}(n-1)^{2}\rfloor$ then ${\mathcal{F}}$ is
of the form ${\mathcal{F}}^{*}_{n}$. For this, it suffices to show that all
triples in ${\mathcal{F}}$ share some fixed vertex $x$. Indeed, by the absence
of ${\mathbf{C}}$, the link of such $x$ in ${\mathcal{F}}$ has to be a
triangle-free graph on $V\setminus\\{x\\}$ with
$\lfloor\frac{1}{4}(n-1)^{2}\rfloor$ edges, hence it must be the Turán graph.

Let $\overline{G}$ be the bipartite complement of $G$, i.e., $E(\overline{G})$
is the set of pairs in $A\times B$ which are not edges of $G$. As $|A|+|B|=n$,
we have
$|E(\overline{G})|=|A|\cdot|B|-\lfloor\frac{1}{4}(n-1)^{2}\rfloor\leq\min\\{|A|,|B|\\}$.
On the other hand, if there is a triple in ${\mathcal{F}}$ with two vertices
in $A$ then they are remote in $G$, hence every vertex in $B$ is incident to
an edge of $\overline{G}$. Similarly, if there is a triple in ${\mathcal{F}}$
with two vertices in $B$ then every vertex in $A$ is incident to an edge of
$\overline{G}$.

Assume first that there are triples of both kinds. We conclude that $|A|=|B|$
and $\overline{G}$ is a perfect matching between $A$ and $B$. Now, if
$|A|=|B|\geq 3$ then no two vertices of the same part are remote and we get a
contradiction. The only possibility is $|A|=|B|=2$, in which case $n=4$,
$|{\mathcal{F}}|=2$ and the two triples in ${\mathcal{F}}$ must share two
vertices.

Thus, we may assume that all triples in ${\mathcal{F}}$ are of the same kind,
having w.l.o.g. two vertices in $A$ and one in $B$. Let $x\in A$ and $y\in B$
form an edge of $\overline{G}$. Since every vertex in $B$ is incident to an
edge of $\overline{G}$, and there are at most $|B|$ such edges, $xy$ is the
only edge of $\overline{G}$ incident to $y$. Hence, no two vertices in
$A\setminus\\{x\\}$ are remote. Therefore, every triple in ${\mathcal{F}}$
must contain $x$, completing the proof. ∎

##  9 Excluding ${\mathbf{A}}$ and ${\mathbf{C}}$

###  9.1 ${\mathbf{A}}{\mathbf{C}}$-free constructions

We have already encountered two different equally large constructions of
${\mathbf{A}}{\mathbf{C}}$-free triple systems: ${\mathcal{F}}_{T}$, the one
based on the transitive tournament (which also avoids ${\mathbf{D}}$), and
${\mathcal{F}}^{*}_{n}$, the one based on the Turán graph (which also avoids
${\mathbf{B}}$), both of size $\lfloor\frac{1}{4}(n-1)^{2}\rfloor$. It turns
out that these are optimal ${\mathbf{A}}{\mathbf{C}}$-free constructions for
even $n$, but we can do better by $1$ for odd $n\geq 5$.

Given an ${\mathbf{A}}{\mathbf{C}}$-free family ${\mathcal{F}}$ on the
$n$-element vertex set $V$ one can define another
${\mathbf{A}}{\mathbf{C}}$-free family ${\mathcal{F}}^{+2}$ on the vertex set
$V\cup\\{1,2\\}$ as follows. ${\mathcal{F}}^{+2}:={\mathcal{F}}\cup\\{12v:v\in
V\\}$. We call this new family a $2$-extension of ${\mathcal{F}}$. One can
define an ${\mathbf{A}}{\mathbf{C}}$-free family ${\mathcal{F}}^{+4}$ on the
vertex set $V\cup\\{1,2,3,4\\}$ as

${\mathcal{F}}^{+4}:={\mathcal{F}}\cup\\{12v:v\in V\\}\cup\\{34v:v\in
V\\}\cup\\{123,234\\}.$

Note that if $V\neq\emptyset$ then $({\mathcal{F}}^{+2})^{+2}$ is not the same
as ${\mathcal{F}}^{+4}$, although they only differ by replacing $124$ by
$234$. For even $n\geq 2$ let ${\mathbf{F}}_{(n)}$ denote the class of
$n$-vertex triple systems one can obtain by an arbitrary sequence of
$2$-extensions and $4$-extensions starting with a system of the form
${\mathcal{F}}^{*}_{n-2k}$ for some $0\leq k\leq\frac{n-2}{2}$ (the case $k=0$
gives ${\mathcal{F}}^{*}_{n}$ without extensions, the case $k=\frac{n-2}{2}$
applies a sequence of extensions starting from the empty triple system on $2$
vertices and gives ${\mathcal{F}}_{T}$ when it uses only $2$-extensions). All
families ${\mathcal{F}}\in{\mathbf{F}}_{(n)}$, $n$ even, have the same size
$|{\mathcal{F}}|=\lfloor\frac{1}{4}(n-1)^{2}\rfloor$.

For $n=5$ we arrange the vertices $1,2,3,4,5$ cyclically, and let
${\mathcal{F}}^{5}_{5}$ consist of the five triples of consecutive vertices
$123,234,345,451,512$. We call such a triple system a _five-ring_ , and note
that it contains no ${\mathbf{A}}$ or ${\mathbf{C}}$. Its size is
$5=\frac{1}{4}(5-1)^{2}+1$. For odd $n\geq 5$ the members of the class
${\mathbf{F}}_{(n)}$ are those $n$-vertex triple systems obtained from a five-
ring by an arbitrary sequence of $2$\- and $4$-extensions. By induction we
have $|{\mathcal{F}}|=\frac{1}{4}(n-1)^{2}+1$ for all odd $n\geq 5$ when
${\mathcal{F}}\in{\mathbf{F}}_{(n)}$.

######  Theorem 13.

Define

$f(n):=\begin{cases}\lfloor\frac{1}{4}(n-1)^{2}\rfloor&\text{if }n\text{ is
even or }n=1,3\\\ \frac{1}{4}(n-1)^{2}+1&\text{if }n\text{ is odd, }n\neq
1,3\end{cases}$

Then ${\rm ex}(n,{\mathbf{A}}{\mathbf{C}})=f(n)$. Moreover, for $n\geq 4$ the
only extremal ${\mathbf{A}}{\mathbf{C}}$-free families are the members of
${\mathbf{F}}_{(n)}$.

It is easy to calculate that for $n$ even ${\mathbf{F}}_{(n)}$ has exactly
$2f_{n/2}-1$ members (up to isomorphism), where $f_{1},f_{2},\dots$ is the
Fibonacci sequence defined as $f_{1}=f_{2}=1$ and $f_{k}=f_{k-1}+f_{k-2}$ for
$k>2$. For odd $n\geq 5$ the size of ${\mathbf{F}}_{(n)}$ can also be obtained
from a Fibonacci number, $|{\mathbf{F}}_{(n)}|=f_{(n-3)/2}$. The multitude of
extremal constructions may explain why the proof of Theorem 13 turned out to
be more complicated than other proofs in this paper. Before turning to the
proof itself, we further investigate the structure of possible maximal
families and we also need a graph theoretic lemma (presented in Subsection
9.5).

###  9.2 Reducing ${\mathbf{A}}{\mathbf{C}}$-free families

Suppose that the ${\mathbf{A}}{\mathbf{C}}$-free triple system ${\mathcal{F}}$
on $n$ vertices has a pair $u,v\in V$ such that $\deg_{\mathcal{F}}(uv)=n-2$
and let ${\mathcal{H}}$ be the family of triples of ${\mathcal{F}}$ contained
in $V\setminus\\{u,v\\}$. Then ${\mathcal{F}}={\mathcal{H}}^{+2}$. This
observation leads to the following useful lemma.

######  Lemma 14.

Let ${\mathcal{F}}$ be an ${\mathbf{A}}{\mathbf{C}}$-free triple system on the
$n$-vertex set $V$. Suppose that there are disjoint pairs
$e_{1},\dots,e_{k}\subset V$ ($1\leq k<\frac{n}{2}$), $K:=\cup e_{i}$, having
the following properties:

  1. (K1)

There is no triple $F\in{\mathcal{F}}$ such that $|F\cap K|=1$.

  2. (K2)

If $F\in{\mathcal{F}}$ meets both $e_{i}$ and $e_{j}$ then $F\subset e_{i}\cup
e_{j}$ (for all $1\leq i\neq j\leq k$).

Let ${\mathcal{H}}$ denote the family of triples of ${\mathcal{F}}$ contained
in $V\setminus K$. Then

$|{\mathcal{F}}|-\lfloor\frac{1}{4}(n-1)^{2}\rfloor\leq|{\mathcal{H}}|-\lfloor\frac{1}{4}(n-2k-1)^{2}\rfloor,$
(1)

and here equality holds if and only if there is a sequence of $2$\- and
$4$-extensions of ${\mathcal{H}}$ resulting in ${\mathcal{F}}$.

If ${\mathcal{F}}$ possesses such a set of pairs, then we call it reducible.

Proof of Lemma 14. The family ${\mathcal{F}}\setminus{\mathcal{H}}$ contains
two kinds of triples, those meeting $V\setminus K$ and containing an $e_{i}$
and those contained in some $e_{i}\cup e_{j}$. Since every four vertices can
carry at most two triples we get

$|{\mathcal{F}}|-|{\mathcal{H}}|\leq
k(n-2k)+2\binom{k}{2}=\lfloor\frac{1}{4}(n-1)^{2}\rfloor-\lfloor\frac{1}{4}(n-2k-1)^{2}\rfloor.$

We are done with inequality (1).

In the case of equality we have $e_{i}\cup\\{v\\}\in{\mathcal{F}}$ for all
$1\leq i\leq k$ and $v\in V\setminus K$, and each $e_{i}\cup e_{j}$ contains
exactly two triples from ${\mathcal{F}}$. Define an oriented graph $T_{K}$
with vertex set $\\{e_{1},\dots,e_{k}\\}$ as follows. Add an arrow from
$e_{i}$ to $e_{j}$ if there is a triple $F$ containing $e_{i}$ and meeting
$e_{j}$. Note that $T_{K}$ has at least one edge between $e_{i}$ and $e_{j}$,
and it also might have two edges in opposite directions. However, $T_{K}$ does
not contain oriented triangles because ${\mathcal{F}}$ is ${\mathbf{A}}$-free.
This implies that the pairs $\\{e_{i},e_{j}\\}$ with double arrows are
pairwise disjoint, so they form a matching, say $L$. We obtain that $T_{K}$
consists of a transitive tournament (say, there is an arrow from $e_{i}$ to
$e_{j}$ for $1\leq j<i\leq k$) together with a few reversed arrows $e_{i}\to
e_{i+1}$ for $\\{e_{i},e_{i+1}\\}\in L$. Every $e_{i}$ outside $L$ corresponds
to a 2-extension, and the pairs from $L$ define 4-extensions. ∎

###  9.3 The structure of ${\mathbf{A}}{\mathbf{C}}$-free families:
partitioning the triples and the pairs

Let ${\mathcal{F}}$ be an ${\mathbf{A}}{\mathbf{C}}$-free triple system on
$[n]$. Recall that a five-ring is a triple system consisting of $5$ triples on
$5$ vertices that is isomorphic to ${\mathcal{F}}^{5}_{5}$ (defined in
Subsection 9.1). Five-rings that are contained in the triple system
${\mathcal{F}}$ will play a special role in our analysis. Suppose that
${\mathcal{P}}\subseteq{\mathcal{F}}$ is a five-ring. Then $V({\mathcal{P}})$
contains no more triples from ${\mathcal{F}}\setminus{\mathcal{P}}$. Also, the
case of $|F\cap V({\mathcal{P}})|=2$ for some $F\in{\mathcal{F}}$ would create
an ${\mathbf{A}}$ configuration. We conclude that triples in
${\mathcal{F}}\setminus{\mathcal{P}}$ can meet $V({\mathcal{P}})$ in at most
one vertex. So the 10 pairs of ${\mathcal{P}}$ are contained only in the
triples from ${\mathcal{P}}$. Let ${\mathcal{R}}\subseteq{\mathcal{F}}$ be the
family of triples contained in five-rings and let $G_{R}$ be the graph on
$[n]$ whose edges are the pairs contained in members of ${\mathcal{R}}$. If
needed we split $G_{R}$ into two graphs, $G_{R1}$ and $G_{R2}$ to indicate if
an edge is covered once or twice. We have
$|{\mathcal{R}}|=|E(G_{R1})|=|E(G_{R2})|$ and $|E(G_{R})|=2|{\mathcal{R}}|$.

Every triple $F\in{\mathcal{F}}$ contains at least one own pair. We partition
${\mathcal{F}}\setminus{\mathcal{R}}$ into
${\mathcal{F}}_{1}\cup{\mathcal{F}}_{2}$ where ${\mathcal{F}}_{1}$ consists of
the triples with exactly one own pair, and ${\mathcal{F}}_{2}$ of those with
at least two own pairs. Let $G_{1}$ be the graph on $[n]$ whose edges are the
own pairs of the triples in ${\mathcal{F}}_{1}$. Picking exactly two own pairs
of every triple in ${\mathcal{F}}_{2}$, let $G_{2}$ be the graph on $[n]$
formed by them. Thus $|E(G_{1})|=|{\mathcal{F}}_{1}|$ and
$|E(G_{2})|=2|{\mathcal{F}}_{2}|$. As all edges in $G_{1}$ and $G_{2}$ are own
pairs of some $F\in{\mathcal{F}}$ we have $E(G_{1})\cap E(G_{2})=\emptyset.$

Define the graph ${G}_{3}$ as

$E({G}_{3})=\\{xy\colon x,y\text{ are joined by a path of length $2$ in
}G_{1}\\}.$

We will require the following fact about the edges of $G_{3}$.

######  Lemma 15.

If $xy\in E(G_{3})$ then no triple in ${\mathcal{F}}$ contains both $x$ and
$y$.

###### Proof.

Let $v$ be a vertex such that $xv,vy\in E({G}_{1})$, and let $F_{1}$ and
$F_{2}$ be the triples in ${{\mathcal{F}}}_{1}$ having $xv$ and $vy$,
respectively, as their unique own pair. Assume for the sake of contradiction
that the triple $F_{3}$ in ${\mathcal{F}}$ contains $x$ and $y$. Clearly,
$xvy$ cannot be a triple in ${\mathcal{F}}$ because it contains both $xv$ and
$vy$. Therefore $F_{1},F_{2},F_{3}$ are all distinct and each of them contains
a different pair from $\\{x,v,y\\}$ and a vertex outside it. Say $F_{1}=xvw$,
$F_{2}=vyz$, $F_{3}=xyu$. To avoid forming an ${\mathbf{A}}$ or a
${\mathbf{C}}$, two of the vertices $w,z,u$ must be the same and the third
must be different.

We consider first the case when $w=z$. Since $xw$ is not an own pair of
$F_{1}$, there is another triple in ${\mathcal{F}}$ containing it, say
$F_{4}=xws$. If $s\notin\\{y,u\\}$ then $F_{2},F_{3},F_{4}$ form a forbidden
${\mathbf{A}}$. If $s=y$ then $F_{1},F_{2},F_{4}$ form a forbidden
${\mathbf{C}}$. Thus $s=u$ is the only possibility. Repeating the same
arguments for $yw$ which is not an own pair of $F_{2}$, we find the triple
$F_{5}=ywu$ in ${\mathcal{F}}$. But now $F_{3},F_{4},F_{5}$ form a
${\mathbf{C}}$, giving a contradiction.

Thus, we are left with the case when $w\neq z$ and $u$ is equal to one of
them, w.l.o.g. $u=w$. Since $vw$ is not an own pair of $F_{1}$, there is
another triple in ${\mathcal{F}}$ containing it, say $F_{4}=vws$. If
$s\notin\\{y,z\\}$ then $F_{2},F_{3},F_{4}$ form a forbidden ${\mathbf{A}}$.
If $s=y$ then $F_{1},F_{3},F_{4}$ form a forbidden ${\mathbf{C}}$. Thus $s=z$
is the only possibility. Since $yz$ is not an own pair of $F_{2}$, there is
another triple in ${\mathcal{F}}$ containing it, say $F_{5}=yzt$. If
$t\notin\\{x,w\\}$ then $F_{3},F_{4},F_{5}$ form a forbidden ${\mathbf{A}}$.
If $t=w$ then $F_{2},F_{4},F_{5}$ form a forbidden ${\mathbf{C}}$. Thus $t=x$
is the only possibility. Summarizing, we have the following five triples in
${\mathcal{F}}$:

$F_{1}=vwx,F_{3}=wxy,F_{5}=xyz,F_{2}=yzv,F_{4}=zvw.$

They form a five-ring, contradicting the fact that $F_{1}$ and $F_{2}$ are in
${{\mathcal{F}}}_{1}$, hence not part of a five-ring. ∎

Our Lemma 15 implies that $E(G_{3})$ is disjoint from $E(G_{R})\cup
E(G_{1})\cup E(G_{2})$, so the following four edge sets are pairwise disjoint:

$E({G}_{R}),\;E({G}_{1}),\;E(G_{2}),\;E(G_{3}).$

By adding a fifth one

$E(G_{4}):=\\{xy\colon x\neq y,xy\text{ is in none of the above}\\},$

we obtain a partition of $E(K_{n})$ into five graphs. Figure 2 shows, for
every possible triple in ${\mathcal{F}}$, to which of the above graphs its
pairs belong. Again, if needed, we split $G_{4}$ into three graphs, $G_{40}$,
$G_{41}$ and $G_{42}$ to indicate if an edge is not covered, covered once or
at least twice by members of ${\mathcal{F}}$, respectively.

Figure 2: Assignment of the pairs of each triple in ${\mathcal{F}}$ to graphs

The discussion above yields the following observations, to be used later:

$\displaystyle\deg_{{\mathcal{F}}}(xy)>2$ $\displaystyle\>\Rightarrow\>xy\in
E(G_{42})$ (2) $\displaystyle\deg_{{\mathcal{F}}}(xy)=2$
$\displaystyle\>\Rightarrow\>xy\in E(G_{R2})\cup E(G_{42})$ (3)
$\displaystyle\deg_{{\mathcal{F}}}(xy)=0$
$\displaystyle\>\Leftrightarrow\>xy\in E(G_{3})\cup E(G_{40})$ (4)

###  9.4 Proof of Theorem 13: three cases without induction

Let ${\mathcal{F}}$ be an ${\mathbf{A}}{\mathbf{C}}$-free triple system on
$[n]$ and suppose that $|{\mathcal{F}}|={\rm ex}(n,{\mathbf{A}}{\mathbf{C}})$.
Constructions showing $|{\mathcal{F}}|\geq f(n)$ were given above. It is
trivial to check their optimality for $n\leq 4$, so from now on we may suppose
that $n\geq 5$. We will prove that $|{\mathcal{F}}|\leq f(n)$ and
${\mathcal{F}}\in{\mathbf{F}}_{(n)}$. We break the argument into six cases.

####  9.4.1 Case 1: There is an isolated vertex in $G_{4}$

Here we assume that $x$ is an isolated vertex in $G_{4}$. In this case all
edges $xy$ belong to either $G_{2}$ or $G_{R}$. Indeed, $xy\notin E(G_{4})$.
Also $xy\in E(G_{1})$ implies that there is an $xzy\in{\mathcal{F}}_{1}$, so
there is a path $x$-$z$-$y$ in $G_{4}$. But this is impossible since there is
no $xz\in E(G_{4})$, so $xy\notin E(G_{1})$. If there is no $xy$ edge in
$E(G_{1})$ then there is no $xy\in E(G_{3})$ either.

Consider the graph ${\mathcal{F}}[x]$, the link of $x$ in ${\mathcal{F}}$. If
the pair $xy$ is contained in $d$ triples (i.e., $\deg_{\mathcal{F}}(xy)=d$)
then the degree of the vertex $y$ in the graph ${\mathcal{F}}[x]$ is exactly
$d$. Since $xy\not\in E(G_{4})$ all the degrees in ${\mathcal{F}}[x]$ are at
most 2 by observation (2). Moreover, if a component $C$ of ${\mathcal{F}}[x]$
has a vertex of degree 2 then by observation (3), $V(C)\cup\\{x\\}$ is the
vertex set of a five-ring, and $C$ is a path of length $3$. Thus, any
component $C$ of ${\mathcal{F}}[x]$ that is not an isolated vertex is of one
of two forms:

  1. I

A single edge $e$.
We let $k\geq 0$ be the number of such components, and denote them by
$e_{1},...,e_{k}$. We denote by $K$ the set of vertices of these components,
$|K|=2k$.

  2. II

A path $P$ of length $3$.
We let $\ell\geq 0$ be the number of such components, and denote them by
$P_{1},...,P_{\ell}$. We denote by $L$ the set of vertices of these
components, $|L|=4\ell$.

Note that $xy\in E(G_{2})$ for any $y\in K$, and $xy\in E(G_{R})$ for any
$y\in L$. We claim that there are no isolated vertices in ${\mathcal{F}}[x]$.
Indeed, suppose that $z$ is an isolated vertex. Then
$\deg_{{\mathcal{F}}}(xz)=0$ and hence by observation (4), $xz\in E(G_{3})\cup
E(G_{40})$. This contradicts the observation above that all edges incident to
$x$ belong to either $G_{2}$ or $G_{R}$.

Thus, ${\mathcal{F}}[x]$ gives the following decomposition of
$[n]\setminus\\{x\\}$:

$[n]\setminus\\{x\\}=K\cup L,\text{ where }|K|=2k,\;|L|=4\ell.$

Note that $n$ must be odd in this case since $n=|K|+|L|+1$. Next, we bound the
number of triples contained in $K\cup L$:

  * -

Each $P_{i}$ contains two triples (those triples in the five-ring that do not
include $x$). Other than those, no triple in $K\cup L$ contains two vertices
of the same $P_{i}$.

  * -

To avoid an ${\mathbf{A}}$ configuration, no triple in $K\cup L$ meets three
components of ${\mathcal{F}}[x]$, and no triple meets $P_{i}$ and $P_{j}$ when
$i\neq j$.

  * -

Thus, any triple in $K\cup L$ that is not contained in a $P_{i}$, consists of
both vertices of some $e_{i}$, and one vertex of another component.

  * -

To avoid a ${\mathbf{C}}$ configuration, for every $i\neq j$ there are at most
$2$ triples contained in $e_{i}\cup e_{j}$.

In total, we have

$|{\mathcal{F}}|\leq k+5\ell+2{{k}\choose{2}}+k\cdot
4\ell=(k+2\ell)^{2}+5\ell-4\ell^{2}\leq\left(\frac{n-1}{2}\right)^{2}+1=f(n),$
(5)

which completes the proof of the upper bound in Case 1.

If equality holds in (5) then $\ell=1$, $k=\frac{n-5}{2}$. If $k=0$ then $n=5$
and ${\mathcal{F}}$ is a five-ring, i.e.,
${\mathcal{F}}\in{\mathbf{F}}_{(5)}$. Suppose now that $k\geq 1$. According to
the above observations $K$ and ${\mathcal{F}}$ satisfy the two constraints of
Lemma 14, so ${\mathcal{F}}$ is reducible. Inequality (1) and
$|{\mathcal{F}}|=f(n)$ yield

$|{\mathcal{F}}|-\lfloor\frac{1}{4}(n-1)^{2}\rfloor=|{\mathcal{H}}|-\lfloor\frac{1}{4}(n-2k-1)^{2}\rfloor=|{\mathcal{H}}|-4=1$

where ${\mathcal{H}}$ is a five-ring. Then Lemma 14 gives that ${\mathcal{F}}$
is obtained from ${\mathcal{H}}$ by a sequence of $2$\- and $4$-extensions,
i.e., ${\mathcal{F}}\in{\mathbf{F}}_{(n)}$. ∎

####  9.4.2 Case 2: There is a pendant $G_{4}$ edge which is in $G_{40}$

Let $x$ be a degree one vertex of $G_{4}$, and let $y$ be its unique neighbor
in $G_{4}$. In this case we suppose that $\deg_{\mathcal{F}}(xy)=0$, the pair
$xy$ does not occur in any triple of ${\mathcal{F}}$. Again, as in Case 1,
there is no $G_{1}$ edge incident to $x$, so there is no such $G_{3}$ edge
either.

Consider the structure of the link ${\mathcal{F}}[x]$, similar to what we did
in Case 1. The vertex $y$ is isolated in ${\mathcal{F}}[x]$ and
$[n]\setminus\\{x\\}=K\cup L\cup\\{y\\}$. In particular $n$ is even here,
$n=2k+4\ell+2$. The only possible triples in ${\mathcal{F}}$ that contain $y$
and do not give rise to an ${\mathbf{A}}$ configuration are of the form
$e_{i}\cup\\{y\\}$. There are at most $k$ of those. Thus, like in (5), we get

$|{\mathcal{F}}|\leq k+5\ell+2{{k}\choose{2}}+k\cdot
4\ell+k=\lfloor\left(\frac{n-1}{2}\right)^{2}\rfloor+3\ell-4\ell^{2}\leq
f(n).$

If equality holds here then $\ell=0$, $k=\frac{n-2}{2}$, and Lemma 14 can be
applied to obtain ${\mathcal{F}}\in{\mathbf{F}}_{(n)}$. ∎

####  9.4.3 Case 3: There is a pendant $G_{4}$ edge which is in $G_{41}$

Let $x$ be a degree one vertex of $G_{4}$, and let $y$ be its unique neighbor
in $G_{4}$. In this case we suppose that $\deg_{\mathcal{F}}(xy)=1$, the pair
$xy$ occurs in a triple $xyz\in{\mathcal{F}}$ with
$\deg_{\mathcal{F}}(xz)=\deg_{\mathcal{F}}(yz)=1$. In the process creating the
graph $G_{2}$ we selected $xz$ and $yz$ and put $xy$ to $G_{41}$. Redefine
these graphs on these three pairs, put $yz$ into $G_{41}$ and the other pairs
to $G_{2}$. Then $x$ becomes isolated in the new $G_{4}$. That case has been
solved as Case 1. ∎

###  9.5 Pairs of vertices joined by a path of length $2$

Given a graph $G$, we define a new graph $T=T(G)$ on the same vertex set as
follows: two vertices $x\neq y$ form an edge in $T$ if they are joined by a
path of length $2$ in $G$, i.e., there exists a vertex $z$ such that both $xz$
and $zy$ are edges of $G$.

######  Lemma 16.

Let $G$ be a graph on $n$ vertices, and let $T=T(G)$ be the graph defined
above. Then

$|E(T)|\geq|E(G)|-\lfloor\frac{n}{2}\rfloor.$ (6)

This inequality holds with equality if and only if one of the following is the
case:

  1. (L1)

$n$ is even, and $G$ is the disjoint union of balanced complete bipartite
graphs $K(A_{i},B_{i})$ with $|A_{i}|=|B_{i}|=d_{i}$, $i=1,...,r$ where
$d_{i}\geq 1,r\geq 1,\sum_{i=1}^{r}d_{i}=\frac{n}{2}$.

  2. (L2)

$n$ is odd, and $G$ is as above except that one of the components is of the
form $K(A_{i},B_{i})$ with $|A_{i}|=d_{i}$ and $|B_{i}|=d_{i}+1$ or is an
isolated vertex.

Moreover, if $n$ is even and $|E(T)|=|E(G)|-\frac{n}{2}+1$, then either

  1. (L3)

one component of $G$ is a $K_{d,d}$ with one edge left out, $d\geq 2$ (denote
this as $K_{d,d}^{-}$), and the other components are balanced complete
bipartite graphs, or

  2. (L4)

there are positive integers $d_{1},d_{2},\dots,d_{r}$, $r\geq 2$ such that
$\sum_{i=1}^{r}d_{i}=\frac{n}{2}+1$ and the components of $G$ are complete
bipartite graphs $K_{d_{1},d_{1}-1}$, $K_{d_{2},d_{2}-1}$, and
$K_{d_{i},d_{i}}$ for $i>2$.

The inequality (6) was proved in dual form by Füredi [13]. Below we also prove
the characterization of equality and at the same time re-prove the inequality.

Note that in each of the cases (L1)–(L4) the graph $T(G)$ is a disjoint union
of complete graphs. Also, in cases (L1) and (L3) the graph $G$ has no isolated
vertex.

Proof of Lemma 16. The graphs described in (L1) and (L2) satisfy inequality
(6) with equality. We show that all other graphs satisfy (6) with strict
inequality.

For a graph $H$ and a vertex $v$, we denote by $N_{H}(v)$ the set of neighbors
of $v$ in $H$. We observe that for every vertex $x$,

$N_{T}(x)=\bigcup_{y\in N_{G}(x)}\left(N_{G}(y)\setminus\\{x\\}\right).$

In particular, if $x$ has a neighbor $y$ with $\deg_{G}(x)<\deg_{G}(y)$ then
$\deg_{T}(x)\geq\deg_{G}(x)$. This implies that there always exists a vertex
$x$ with $\deg_{T}(x)\geq\deg_{G}(x)$, unless every connected component
$C_{i}$ of $G$ is $d_{i}$-regular for some $d_{i}\geq 1$, and moreover, in
$C_{i}$ the $d_{i}$ neighbors of $x$ all have the same $d_{i}-1$ neighbors in
addition to $x$, which means that $C_{i}\cong K_{d_{i},d_{i}}$. In other
words, if $G$ is not of the form indicated in (L1), then there exists a vertex
$x$ with $\deg_{T}(x)\geq\deg_{G}(x)$.

We now proceed by induction on $n$. The base case $n=1$ is trivial. For the
induction step, we assume that $G$ and $T=T(G)$ are graphs on $n\geq 2$
vertices, and the lemma is true for $n-1$.

Assuming that $G$ is not of the form indicated in (L1), let $x$ be a vertex
with $\deg_{T}(x)\geq\deg_{G}(x)$. Applying the induction hypothesis to
$G\setminus\\{x\\}$ we get

$|E(T(G\setminus\\{x\\}))|\geq|E(G\setminus\\{x\\})|-\lfloor\frac{n-1}{2}\rfloor.$
(7)

Therefore

$\begin{split}|E(T)|&\geq|E(T(G\setminus\\{x\\}))|+\deg_{T}(x)\\\
&\geq|E(G\setminus\\{x\\})|-\lfloor\frac{n-1}{2}\rfloor+\deg_{G}(x)=|E(G)|-\lfloor\frac{n-1}{2}\rfloor.\end{split}$
(8)

When $n$ is odd, equality in (6) is possible, but it requires that all the
above inequalities hold with equality. In particular, we must have equality in
(7), hence by induction $G\setminus\\{x\\}$ has to be of the form (L1).
Consider $N_{G}(x)$. If it meets two or more components of
$G\setminus\\{x\\}$, or two sides of the same component, then $T(G)$ has at
least one edge with vertices in $G\setminus\\{x\\}$ that is not in
$E(T(G\setminus\\{x\\}))$. This makes the first inequality in (8) strict. We
conclude that there is a component $K(A_{i},B_{i})$ of $G\setminus\\{x\\}$
with $|A_{i}|=|B_{i}|=d_{i}$ such that $N_{G}(x)$ is contained in one of its
parts, say in $A_{i}$. If $\emptyset\subsetneq N_{G}(x)\subsetneq A_{i}$ then
$\deg_{T}(x)=d_{i}>\deg_{G}(x)$, making the second inequality in (8) strict.
This leaves only two possibilities: either $N_{G}(x)=A_{i}$, in which case we
can add $x$ to $B_{i}$ and get a $K_{d_{i},d_{i}+1}$, or $N_{G}(x)=\emptyset$
making $x$ an isolated vertex in $G$. In either case, $G$ fits the description
in part (L2) of the lemma.

If $n$ is even then $\lfloor\frac{n-1}{2}\rfloor<\lfloor\frac{n}{2}\rfloor$,
hence (8) implies that inequality (6) holds strictly. This completes the proof
of (6) together with (L1) and (L2).

Consider now the case $|E(T)|=|E(G)|-\frac{n}{2}+1$. Again equality must hold
in (7) and (8) so $\deg_{T}(x)=\deg_{G}(x)$, $G\setminus\\{x\\}$ has to be of
the form (L2). If $N_{G}(x)=\emptyset$ then $G$ is of the form (L4). If
$N_{G}(x)\neq\emptyset$ then it meets only one component $C$. This component
could not be an isolated vertex, because that would give $\deg_{G}(x)=1$,
$\deg_{T}(x)=0$. So $C=K(A_{i},B_{i})$ and $N_{G}(x)$ is a subset of one side
of $C$ while $N_{T}(x)$ is the entire other side. Given that
$\deg_{T}(x)=\deg_{G}(x)$, there are two possibilities. If $|A_{i}|=|B_{i}|$
then $N_{G}(x)$ is a full side of $C$, say $B_{i}$, so we get
$K(A_{i}\cup\\{x\\},B_{i})$, yielding case (L4). If $|A_{i}|=|B_{i}|-1$ then
$N_{G}(x)=B_{i}\setminus\\{y\\}$ for some $y\in B_{i}$, so we get
$K(A_{i}\cup\\{x\\},B_{i})$ minus $xy$, yielding case (L3). ∎

####  9.5.1 Remark

We do not use but can prove an even stronger version of Lemma 16.

######  Claim 17.

Let $G$ be a graph, and let $T=T(G)$ be the graph defined above. Suppose that
$\\{e_{1},\dots,e_{\ell}\\}$ is a maximal matching of $G$, i.e.,
$A:=V(G)\setminus(\cup e_{i})$ is an independent set of vertices. Then

$|E(T)|\geq|E(G)|-\ell.$ (9)

This inequality holds with equality if and only if each component of $G$ is
either a balanced complete bipartite graph, or a $K_{d,d}^{-}$ (with $d\geq
2$) contributing $d-1$ edges to the maximal matching, or a $K_{d,d+1}$ ($d\geq
1$), or an isolated vertex.

Sketch of proof of Claim 17. For two distinct edges $e_{i},e_{j}$ in the
maximal matching, let $E(G[e_{i},e_{j}])$ denote the set of edges of $G$ with
one end in $e_{i}$ and the other in $e_{j}$, and let $E(T[e_{i},e_{j}])$
denote the analogous set for $T$. Similarly, for an edge $e_{i}$ and a vertex
$a\in A$, let $E(G[e_{i},a])$ and $E(T[e_{i},a])$ denote the corresponding
sets of edges with one end in $e_{i}$ and the other equal to $a$.

By inspection, we have $|E(T[e_{i},e_{j}])|\geq|E(G[e_{i},e_{j}])|$ and
$|E(T[e_{i},a])|\geq|E(G[e_{i},a])|$ for any two edges $e_{i},e_{j}$ and
vertex $a\in A$. As this accounts for all edges of $G$ apart from
$e_{1},\ldots,e_{\ell}$, it implies (9). In case of equality we must have
equalities above and moreover, no $e_{i}$ and no two vertices in $A$ can form
an edge in $T$. We obtain that $E(G[e_{i},e_{j}])$ should be either empty or
two disjoint edges, and similarly $E(G[e_{i},a])$ is either empty or a single
edge. The rest of the proof is just to check how these edges can fit together
so as to maintain the above conditions for equality. ∎

###  9.6 The core inequality of the proof, and more reductions in case of a
pendant $G_{4}$ edge

We will prove by induction on $n$ that $|{\mathcal{F}}|\leq f(n)$ and
${\mathcal{F}}\in{\mathbf{F}}_{(n)}$.

Look at the partition $[n]=C_{1}\cup\cdots\cup C_{r}$ where the $C_{i}$ are
the connected components of $G_{4}$. By Case 1 we may suppose that
$p_{i}:=|C_{i}|\geq 2$ for every $i$. Note that every edge of $G_{1}$ is
contained in some $C_{i}$ and the same is true for every edge of $G_{3}$. If
$C$ is one of the $C_{i}$, we write $G_{4}^{C},G_{1}^{C},G_{3}^{C}$ for the
corresponding graph restricted to $C$. We have

$\begin{split}2|{\mathcal{F}}|&=2|{\mathcal{R}}|+2|{\mathcal{F}}_{1}|+2|{\mathcal{F}}_{2}|\\\
&=|E(G_{R})|+2|E(G_{1})|+|E(G_{2})|\\\
&=|E(G_{R})|+|E(G_{1})|+|E(G_{2})|+|E(G_{3})|+|E(G_{4})|-\frac{n}{2}\\\
&{}\quad+\left(n-|E(G_{4})|\right)+\left(|E(G_{1})|-|E(G_{3})|-\frac{n}{2}\right)\\\
&={n\choose
2}-\frac{n}{2}+\sum_{i}\left(\left(p_{i}-|E(G^{C_{i}}_{4})|\right)+\left(|E(G_{1}^{C_{i}})|-|E(G_{3}^{C_{i}})|-\frac{p_{i}}{2}\right)\right).\end{split}$
(10)

In the last line for every component $C_{i}$ we have
$p_{i}-|E(G_{4}^{C_{i}})|\leq 1$ and Lemma 16 applied to
$G_{3}^{C_{i}}=T(G_{1}^{C_{i}})$ states
$|E(G_{1}^{C_{i}})|-|E(G_{3}^{C_{i}})|-\lfloor\frac{p_{i}}{2}\rfloor\leq 0$.
So (10) yields a pretty good upper bound for $|{\mathcal{F}}|$ and to improve
it further we will investigate the components where $G_{4}^{C_{i}}$ is a tree,
and also the cases when
$|E(G_{1}^{C_{i}})|-|E(G_{3}^{C_{i}})|-\frac{p_{i}}{2}\geq-1$.

Call a component $C$ of size $p$ near optimal  if

$|E(G_{3}^{C})|\leq|E(G_{1}^{C})|-\frac{p-2}{2}.$ (11)

For not near optimal components the quantity

$\sigma(C_{i}):=\left(p_{i}-|E(G^{C_{i}}_{4})|\right)+\left(|E(G_{1}^{C_{i}})|-|E(G_{3}^{C_{i}})|-\frac{p_{i}}{2}\right)$

is at most $-\frac{1}{2}$. Since $|{\mathcal{F}}|\geq f(n)$ we must have at
least one near optimal component. In such a component, Lemma 16 and (11) imply
that $G_{3}^{C}$ consists of vertex disjoint complete graphs (including
isolated vertices, of course).

####  9.6.1 Case 4: There is a pendant $G_{4}$ edge in a near optimal
component

In this subsection we suppose that $C$ is a near optimal component and $x\in
C$ is a degree one vertex of $G_{4}$. Let $y$ be its unique neighbor in
$G_{4}$. Since we have already discussed the case $\deg_{\mathcal{F}}(xy)=0$
(Case 2) and $\deg_{\mathcal{F}}(xy)=1$ (Case 3) we may suppose that
$\deg_{\mathcal{F}}(xy)=:q\geq 2$.

Consider the structure of the link ${\mathcal{F}}[x]$, similar to what we did
in Case 1. There are two further forms of components in ${\mathcal{F}}[x]$ in
addition to forms I and II which appear in $K$ and $L$, respectively.

  1. III

A star $S_{q}$ centered at $y$ and having $q$ leaves, $q\geq 2$.
There is exactly one such component in ${\mathcal{F}}[x]$. The leaves of
$S_{q}$ can be partitioned into two (possibly empty) parts:

$\begin{split}U&\coloneqq\\{u\colon xyu\in{\mathcal{F}}_{1},xu\in
E(G_{1}),yu\in E(G_{4})\\},\\\ V&\coloneqq\\{v\colon
xyv\in{\mathcal{F}}_{2},xv,yv\in E(G_{2})\\}.\end{split}$

We write $|U|=s$, $|V|=t$, $s+t=q$.

  2. IV

An isolated vertex $z$.
We let $m\geq 0$ be the number of isolated vertices, and denote by $M$ the set
of isolated vertices. We remark that isolated vertices in ${\mathcal{F}}[x]$
are now permissible because $x$ has neighbors in $G_{1}$ (provided that
$s>0$), which allows the isolated vertices to be neighbors of $x$ in $G_{3}$.

We summarize: ${\mathcal{F}}[x]$ looks as in Figure 3, and
$[n]\setminus\\{x\\}=K\cup L\cup M\cup\\{y\\}\cup U\cup V$ with
$K=e_{1}\cup\dots\cup e_{k}$ and $L=P_{1}\cup\dots\cup P_{\ell}$.

Figure 3:  The structure of ${\mathcal{F}}[x]$ in Case 4

Our next arguments exploit and combine structural information about
${\mathcal{F}}[x]$ and about $G_{1}^{C},G_{3}^{C},G_{4}^{C}$ based on Lemma
16. Since the $G_{1}$ and $G_{3}$ neighbors of $x$ are in the same component,
we already know that

  * (C1)

$\\{x,y\\},M,U\subseteq C$.

Since $G_{3}^{C}$ consists of cliques and the $G_{3}$ neighborhood of $x$ is
exactly $M$ we get

  * (C2)

$M\cup\\{x\\}$ is a (maximal) clique in $G_{3}$.

Similarly, since $U$ is the $G_{1}$ neighborhood of $x$, by definition

  * (C3)

$U$ is a clique in $G_{3}$.

It follows from Lemma 15 that no two vertices in $M\cup\\{x\\}$ belong
together to a triple in ${\mathcal{F}}$ and similarly $U$ meets every triple
in ${\mathcal{F}}$ in at most one vertex.

  * (C4)

We may assume that $K=\emptyset$.

Proof. Suppose that $k\geq 1$. First we show that the constraints (K1) and
(K2) of Lemma 14 are valid for ${\mathcal{F}}$. Suppose, on the contrary to
(K1), that there is a $vwz\in{\mathcal{F}}$, $K\cap vwz=\\{v\\}$, $v\in
e_{i}$. We have $x\notin vwz$, because we know ${\mathcal{F}}[x]$. If $wz\cap
L\neq\emptyset$ then we get an ${\mathbf{A}}$ configuration. If one of $w,z$
is $y$, say $w=y$, we can choose a $z^{\prime}\in U\cup V$, $z^{\prime}\neq z$
(since $|U\cup V|\geq 2$) and find the ${\mathbf{A}}$ configuration
$e_{i}\cup\\{x\\},vyz,xyz^{\prime}$. Thus we may assume that $w,z\in M\cup
U\cup V$, and by (C2) at least one of them, say $z$, is in $U\cup V$. But now
$e_{i}\cup\\{x\\},vwz,xyz$ form an ${\mathbf{A}}$. To check (K2) is obvious.
Applying (1), we get

$\varepsilon(n):=f(n)-\lfloor\frac{1}{4}(n-1)^{2}\rfloor\leq|{\mathcal{F}}|-\lfloor\frac{1}{4}(n-1)^{2}\rfloor\leq|{\mathcal{H}}|-\lfloor\frac{1}{4}(n-2k-1)^{2}\rfloor,$

implying $|{\mathcal{H}}|\geq f(n-2k)-\varepsilon(n-2k)+\varepsilon(n)$. Thus
$|{\mathcal{H}}|\geq f(n-2k)$. By induction, this must hold with equality and
${\mathcal{H}}\in{\mathbf{F}}_{(n-2k)}$. Also (1) holds with equality, so
${\mathcal{F}}$ is obtained from ${\mathcal{H}}$ by a sequence of $2$\- and
$4$-extensions, i.e., ${\mathcal{F}}\in{\mathbf{F}}_{(n)}$. ∎

  * (C5)

$L=\emptyset$.

Proof. Suppose that $\ell\geq 1$. By a case check similar to the proof of
(C4), one can verify that any triple $vwz\in{\mathcal{F}}$ that meets $P_{1}$
in a single vertex creates an ${\mathbf{A}}$ configuration. Thus, the only
triples in ${\mathcal{F}}$ that meet $P_{1}$ are those in its five-ring. Let
${\mathcal{H}}$ be the rest of the triples. We obtain

$f(n)\leq|{\mathcal{F}}|=|{\mathcal{H}}|+5\leq f(n-4)+5.$

This is a contradiction, noting that under our conditions $n\geq 8$. ∎

  * (C6)

We may assume that $M\neq\emptyset$, therefore $U\neq\emptyset$.

Indeed, $M=\emptyset$ implies $[n]=\\{x,y\\}\cup U\cup V$ with
$\deg_{\mathcal{F}}(xy)=n-2$. As we have seen before Lemma 14, this implies
that ${\mathcal{F}}$ is a $2$-extension of ${\mathcal{F}}\setminus\\{x,y\\}$,
and we are done by induction.

  * (C7)

$y$ is an isolated vertex in $G_{1}^{C}$.

Indeed, suppose that $yz\in E(G_{1}^{C})$. Clearly $z\in M$. Every $z\in M$
has a $G_{1}$ neighbor in $U$, say $zw\in E(G_{1})$. Then, by definition, the
two $G_{1}$ edges $yz$ and $zw$ place $yw$ in $G_{3}$. However, $yw$ is a
$G_{4}$ pair.

Since $y$ is isolated in $G_{1}^{C}$, according to the structure of
$G_{1}^{C}$ described in Lemma 16, only cases (L2) or (L4) are possible, so
every other component of $G_{1}^{C}$ is a (balanced or almost balanced)
complete bipartite graph. Consider the $G_{1}$ component $\widetilde{C}$ to
which $x$ belongs. We know from ${\mathcal{F}}[x]$ that $N_{G_{1}^{C}}(x)=U$
and $N_{G_{3}^{C}}(x)=M$. Thus, $\widetilde{C}$ is a complete bipartite graph
of $G_{1}$-edges with parts $\\{x\\}\cup M$ and $U$.

Let us conclude this case with the following statement.

######  Claim 18.

Suppose that $|C|=p$ is even and $C$ is a near optimal component with a
pendant $G_{4}$ edge. Then equality holds in (11), i.e.,
$|E(G_{1}^{C})|-|E(G_{3}^{C})|-\frac{p}{2}=-1$.

Proof. By (C7) the graph $G_{1}^{C}$ has an isolated vertex (namely $y$). Then
(L1) is not possible in Lemma 16. ∎

####  9.6.2 Case 5: The $G_{4}$ edges form a tree in a near optimal component

It is, in fact a subcase and a continuation of Case 4. We maintain the
assumptions and conclusions of Case 4, and add the assumption that $G_{4}^{C}$
is a tree. Again let $x$ be a degree one vertex of $G_{4}^{C}$, and let $y$ be
its unique neighbor in $G_{4}$.

  * (C8)

The $G_{4}$ neighborhood of $y$ is $\\{x\\}\cup M\cup U$.

Proof. We already know that the vertices in $\\{x\\}\cup U$ are in the $G_{4}$
neighborhood of $y$, and those in $V$ are not. As $K=L=\emptyset$, it remains
to show that $M\subseteq N_{G_{4}}(y)$.

The arguments leading to (C7) can be carried out for any choice of a leaf of
$G_{4}^{C}$. We may assume that all such leaves are incident to $G_{42}$
edges, otherwise we are done. Thus, for every leaf of $G_{4}^{C}$ its unique
neighbor in $G_{4}^{C}$ is an isolated $G_{1}^{C}$ vertex. If there is only
one isolated vertex in $G_{1}^{C}$ (namely $y$), then it must be that vertex,
regardless of the choice of the leaf of $G_{4}^{C}$. This implies that
$G_{4}^{C}$ is a star, and it is centered at $y$. In particular, $M\subseteq
N_{G_{4}}(y)$.

Consider the case when $G_{1}^{C}$ has at least two isolated vertices, $y$ and
$y^{\prime}$. The near optimality of $C$ and Lemma 16 imply that only the case
(L4) is possible, there are no more isolated vertices. By (C7) each leaf of
the tree $G_{4}^{C}$ is adjacent to an isolated vertex of $G_{1}^{C}$. So the
tree $G_{4}^{C}$ consists of two stars with centers $y$ and $y^{\prime}$ and a
path connecting these centers. In particular, all but one of the $G_{4}^{C}$
neighbors of $y$ are leaves. According to (L4) the non-isolated components of
$G_{1}^{C}$ are balanced complete bipartite graphs, in particular such is
$\widetilde{C}=K(\\{x\\}\cup M,U)$, so $|U|=|\\{x\\}\cup M|\geq 2$. All
vertices in $U$ are $G_{4}^{C}$ neighbors of $y$, so at least one of them, say
$u$, is a leaf in $G_{4}^{C}$ adjacent to $y$. Now consider any vertex $z\in
M$. As $zu\in E(G_{1}^{C})$, $z$ and $u$ must have a common $G_{4}^{C}$
neighbor, which can only be $y$. This shows that $z\in N_{G_{4}}(y)$,
completing the proof. ∎

  * (C9)

For every pair $ab$ with $a\in\\{x\\}\cup M$, $b\in U$, the unique triple in
${\mathcal{F}}$ containing it is $aby$.

Indeed, suppose $abz$ is that unique triple. Then $az,bz\in E(G_{4}^{C})$, so
$z$ is the middle vertex of a path of length $2$ in $G_{4}^{C}$. Since
$G_{4}^{C}$ is a tree, this path $a$-$z$-$b$ is the unique path connecting $a$
to $b$ in the tree. But $ay$ and $by$ are tree edges by (C8) so $z=y$. ∎

  * (C10)

$|U|\geq 2$.

Indeed, by Lemma 16 and the near optimality of $C$ we know that $K(\\{x\\}\cup
M,U)$ is balanced or almost balanced. We have $(|M|+1)-|U|\leq 1$, so $|U|\leq
1$ gives $|M|\leq 1$. Writing $M=\\{z\\}$, $U=\\{u\\}$, we have
$zuy\in{\mathcal{F}}$ by (C9). As $zu$ is the only own pair of this triple,
there must be another triple $zyv\in{\mathcal{F}}$. The only remaining options
are $v=x$ or $v\in V$. Both are impossible: the former because
$\deg_{\mathcal{F}}(xz)=0$, the latter because the pair $yv$, $v\in V$, is an
own pair of $xyv$. ∎

Next, we give an upper bound on the number of triples in ${\mathcal{F}}$.

  * -

Triples containing no vertex of $V$:
Since $\\{x\\}\cup M$ and $U$ are cliques in $G_{3}$, any triple in
${\mathcal{F}}$ can contain at most one vertex from each of them (Lemma 15).
Thus triples avoiding $V$ must be of the form $aby$ with $a\in\\{x\\}\cup M$,
$b\in U$. By (C9) all these are indeed triples in ${\mathcal{F}}$, so we have
$(m+1)s$ of them.

  * -

Triples containing exactly one vertex of $V$:
There are $t$ such triples containing $xy$. There are no other such triples.
Indeed, any other such triple would have to be of the form $zuv$, $z\in M,u\in
U,v\in V$. But then, taking $w\in U\setminus\\{u\\}$, we get an ${\mathbf{A}}$
configuration: $zuv,zwy,xyv$.

  * -

Triples containing exactly two vertices of $V$:
There are no such triples. Indeed, suppose $zvw$ is such a triple, with
$v,w\in V$. Then $z\neq x$, because $vw$ is not an edge of ${\mathcal{F}}[x]$.
If $z=y$ we get a ${\mathbf{C}}$ configuration: $yvw,xyv,xyw$. If $z\in M$
then taking $u\in U$ we get an ${\mathbf{A}}$ configuration: $zvw,zuy,xyv$.
Finally, suppose $z\in U$. Since $zy$ is not an own pair of $xyz$, there is
another triple $zya\in{\mathcal{F}}$ containing it. The vertex $a$ cannot be
in $V$ (by the previous paragraph), so we get an ${\mathbf{A}}$ configuration:
$zvw,zya,xyv$.

  * -

Triples contained in $V$:
By the induction hypothesis, there are at most $f(t)$ such triples.

Altogether, we get that the number of triples in ${\mathcal{F}}$ is at most
$(m+1)s+t+f(t)$. Using $(m+1)+s=n-t-1$, $n\geq t+5$, and the notation
$\delta(t):=f(t)-\frac{1}{4}(t-1)^{2}$ with the convention
$\delta(0)=-\frac{1}{4}$, we obtain

$\begin{split}|{\mathcal{F}}|-\frac{1}{4}(n-1)^{2}&\leq-\frac{1}{4}(n-1)^{2}+\frac{1}{4}(n-t-1)^{2}+t+\frac{1}{4}(t-1)^{2}+\delta(t)\\\
&=\frac{1}{4}(2t^{2}+4t+1-2nt)+\delta(t)\leq\frac{1}{4}(1-6t)+\delta(t).\end{split}$

Note that $\delta(t)=-\frac{1}{4}$ for even $t$, and for odd $t$ we have
$\delta(1)=\delta(3)=0$ and $\delta(t)=1$ when $t\geq 5$. We know that
$|{\mathcal{F}}|-\frac{1}{4}(n-1)^{2}\geq\delta(n)\geq-\frac{1}{4}$, whereas
the upper bound $\frac{1}{4}(1-6t)+\delta(t)$ is at most $-\frac{5}{4}$ for
$t\geq 1$. So we must have $t=0$ and $n$ even. In this case, as we have seen,
${\mathcal{F}}$ consists of all triples $aby$ with $a\in\\{x\\}\cup M$, $b\in
U$. Thus ${\mathcal{F}}$ is the construction based on the Turán graph with the
vertex $y$ common to all triples, i.e., ${\mathcal{F}}={\mathcal{F}}^{*}_{n}$,
completing the proof of ${\mathcal{F}}\in{\mathbf{F}}_{(n)}$ in Case 5. ∎

###  9.7 Proof of Theorem 13: the end

Recall that we partitioned $[n]$ into the connected components
$C_{1},...,C_{r}$ of $G_{4}$ of sizes $p_{1},\dots,p_{r}$, $p_{i}\geq 2$ for
all $i$. We may also suppose that each pendant $G_{4}$ edge is a $G_{42}$
edge.

####  9.7.1 Case 6: The opposite of Case 5

This is the last case, and we will show that it leads to a contradiction. We
suppose that for each component $C$ of size $p$ either $G_{4}^{C}$ is not a
tree, i.e., $p-|E(G_{4}^{C})|\leq 0$, call this Case 6/1, or it is not near
optimal, i.e., $|E(G_{1}^{C})|-\frac{p-2}{2}<|E(G_{3}^{C})|$ (Case 6/2). Note
that in both cases

$\lceil\frac{p}{2}\rceil-|E(G_{4}^{C})|+|E(G_{1}^{C})|-|E(G_{3}^{C})|\leq 0.$
(12)

Indeed, Lemma 16 states
$|E(G_{1}^{C})|-\lfloor\frac{p}{2}\rfloor\leq|E(G_{3}^{C})|$. Adding this to
$p-|E(G_{4}^{C})|\leq 0$ we obtain (12) in Case 6/1. In Case 6/2 we add
$|E(G_{1}^{C})|-\frac{p-3}{2}\leq|E(G_{3}^{C})|$ to the obvious
$p-1-|E(G_{4}^{C})|\leq 0$ and get
$\frac{p+1}{2}-|E(G_{4}^{C})|+|E(G_{1}^{C})|-|E(G_{3}^{C})|\leq 0$.

Hence in the sum in the last line of (10) each term $\sigma(C_{i})$ is non-
positive. Even more, in Case 6/1 we have $\sigma(C_{i})\leq-\frac{1}{2}$ when
$p_{i}$ is odd, and $\sigma(C_{i})$ is negative in Case 6/2 as well. Therefore
in Case 6 we get $|{\mathcal{F}}|\leq\frac{1}{4}(n^{2}-2n)\leq f(n)$. Here
equality must hold, so to avoid negative terms each $p_{i}$ should be even and
Case 6/2 is also excluded.

So from now on, we may suppose 6/1 holds with equality in (12) for each $i$.
So each $p_{i}$ is even, $p_{i}=|E(G_{4}^{C_{i}})|$, and equality holds in
Lemma 16, i.e., (L1) holds. Thus $C_{i}$ contains a perfect matching of
$G_{1}$ edges. Then Claim 18 implies that $G_{4}^{C_{i}}$ has no pendant edge,
each degree is at least $2$. So $G_{4}^{C_{i}}$ should be $2$-regular,
connected, i.e., each $G_{4}^{C_{i}}$ is an even cycle, $p_{i}\geq 4$.

We are going to show that each $p_{i}$ is exactly $4$. Let the vertex set of
$C$ be $[p]$ with $G_{4}^{C}$ edges $12,23,...,(p-1)p$, and $p1$. The
$G^{C}_{1}$ edges are diagonals of length 2 in $G_{4}^{C}$. They also contain
a matching of size $\frac{p}{2}$, and this is only possible if there are
crossing edges like $13$ and $24$ with $123,234\in{\mathcal{F}}_{1}$.

Suppose that there exists a triple containing $14$, say $14z\in{\mathcal{F}}$.
Since $13$ and $24$ are covered exactly once by the triples of ${\mathcal{F}}$
we have $z\notin\\{1,2,3,4\\}$. The pair $12$ is not a $G_{41}$ edge (because
$123$ does not have two own pairs) so it is a $G_{42}$ edge, there exists a
triple $12w\in{\mathcal{F}}$, $w\neq 3$, containing it. The triples
$12w,14z,234$ form an ${\mathbf{A}}$ configuration unless $w\in\\{4,z\\}$. To
avoid ${\mathbf{C}}$ we have $w\neq 4$, so $w=z$ and $12z\in{\mathcal{F}}$.
One can have the same argument starting with the pair $34$ in place of $12$
and obtain $34z\in{\mathcal{F}}$. Then we got a five-ring with vertex set
$\\{1,2,3,4,z\\}$, a contradiction, because $12$, etc., are $G_{4}$ edges.

We conclude that the pair $14$ is uncovered. If it is a $G_{3}$ edge then
there are two $G_{1}$ pairs $w1$ and $w4$, both diagonals of length $2$. But
this is impossible since $p$ is even and the arc $1234$ is of odd length. So
$14$ is a $G_{40}$ edge. Thus $1234$ form a $4$-cycle in $G_{4}$, $p=4$. This
must be true for each component, so $G_{4}$ is a vertex disjoint union of
$4$-cycles such that each contains two triples and a $G_{40}$ pair. So $G_{1}$
is a perfect matching and there is no $G_{3}$ edge at all.

Consider any $4$-cycle $C$ in $G_{4}$, say with $123,234\in{\mathcal{F}}$,
$14\in E(G_{40})$ and $12,23,34\in E(G_{42})$. We have a triple
$12z\in{\mathcal{F}}$ with $z\neq 3$, and (to avoid ${\mathbf{C}}$) $z\neq 4$.
Every pair $4z$ with $z\notin C$ is contained in a triple, so we have some
triple $4zw\in{\mathcal{F}}$. The triples $12z,234,4zw$ form an ${\mathbf{A}}$
configuration unless $w\in\\{1,2,3\\}$. The case $w=1$ is not allowed because
$14\in E(G_{40})$, and the case $w=2$ is not allowed because $24\in E(G_{1})$.
So $w=3$, $34z\in{\mathcal{F}}$. The triples $12z,34z$ have no $G_{1}$ pair,
hence their pairs $1z,2z,3z,4z$ are $G_{2}$ pairs. The pair $23$ cannot appear
in any triple in ${\mathcal{F}}$ except $123,234$. Indeed, $23z$ is excluded
because $2z,3z$ are own pairs of other triples, and $23w$ for $w\notin
C\cup\\{z\\}$ creates the ${\mathbf{A}}$ configuration $12z,34z,23w$. We
conclude that the set of triples in ${\mathcal{F}}$ that meet $C$ in exactly
two vertices is of the form $\\{12z,34z:z\in Z_{C}\\}$ where $Z_{C}$ is a non-
empty set disjoint from $C$.

Next, we discuss five-rings. We claim that they must be vertex disjoint.
Indeed, any two of them can meet in at most one vertex. If two of them on
vertex sets $R_{1},R_{2}$ share a vertex $x$, then in order to avoid an
${\mathbf{A}}$ configuration all $16$ pairs $ab$, $a\in
R_{1}\setminus\\{x\\}$, $b\in R_{2}\setminus\\{x\\}$ must be uncovered.
However, the only uncovered pairs are $G_{40}$ edges and they are pairwise
disjoint.

Now, for any two distinct $4$-cycles $C_{i},C_{j}$ in $G_{4}$, we write
$C_{i}\to C_{j}$ if $Z_{C_{i}}\cap C_{j}\neq\emptyset$. As shown above, in
this case all pairs in $C_{i}\times(Z_{C_{i}}\cap C_{j})$ are $G_{2}$ edges.
For any $i\neq j$, exactly one of $C_{i}\to C_{j}$ and $C_{j}\to C_{i}$ holds.
Indeed, if both held then pairs in $(Z_{C_{j}}\cap C_{i})\times(Z_{C_{i}}\cap
C_{j})$ would be $G_{2}$ edges contained in two triples in ${\mathcal{F}}$. If
neither held then all pairs in $C_{i}\times C_{j}$ would have to be $G_{R}$
edges (nothing else is allowed), which is impossible because adjacent $G_{R}$
edges must come from the same five-ring (as five-rings are disjoint).

We have thus defined a tournament $T$ on $\\{C_{1},\ldots,C_{r}\\}$. As
$Z_{C_{i}}\neq\emptyset$ for every $i$, every $C_{i}$ has at least one out-
neighbor in $T$, so $T$ cannot be transitive. But then it contains a directed
triangle, which gives rise to an ${\mathbf{A}}$ configuration. This
contradiction completes the proof. ∎

##  10 Excluding ${\mathbf{A}}$, ${\mathbf{B}}$ and ${\mathbf{D}}$

Recall that ${\rm
ex}(n,{\mathbf{A}}{\mathbf{B}}{\mathbf{C}}{\mathbf{D}})=\lfloor\frac{1}{8}n^{2}\rfloor$
for all $n\geq 1$ and in Theorem 1 in Section 2 we have described
${\mathcal{F}}_{n,k}$, the extremal families. In this section we show that for
large enough $n$, excluding ${\mathbf{A}}$, ${\mathbf{B}}$ and ${\mathbf{D}}$
has the same effect on the size of a triple system as excluding all triangles.
For finitely many cases ${\rm ex}(n,{\mathbf{A}}{\mathbf{B}}{\mathbf{D}})$ can
exceed $\lfloor\frac{1}{8}n^{2}\rfloor$, e.g., for $n=4$ the complete triple
system $K^{3}_{4}:=\binom{[4]}{3}$ is
${\mathbf{A}}{\mathbf{B}}{\mathbf{D}}$-free, while
$\lfloor\frac{1}{8}n^{2}\rfloor=2$. For $n=7$ two $K^{3}_{4}$ sharing a vertex
give ${\rm ex}(7,{\mathbf{A}}{\mathbf{B}}{\mathbf{D}})\geq 8$ (and here
equality holds) while $\lfloor\frac{1}{8}n^{2}\rfloor=6$. For $n=16$ the
family of $8$ $K_{4}^{3}$ occupying the rows and columns of a $4\times 4$
square lattice is ${\mathbf{A}}{\mathbf{B}}{\mathbf{D}}$-free and has a
completely different structure than ${\mathcal{F}}_{n,k}$. Denote this triple
system by ${\mathcal{Q}}^{4\times 4}$, and note that $|{\mathcal{Q}}^{4\times
4}|=\lfloor\frac{1}{8}n^{2}\rfloor=32$.

######  Theorem 19.

${\rm
ex}(n,{\mathbf{A}}{\mathbf{B}}{\mathbf{D}})=\lfloor\frac{1}{8}n^{2}\rfloor\,\text{
for }n\geq 8.$

Moreover, for $n\geq 11$ the families ${\mathcal{F}}_{n,k}$ described in
Section 2 are the only extremal systems, except that ${\mathcal{Q}}^{4\times
4}$ is also extremal in the case $n=16$.

For $n=8,9,10$ here is the complete list of extremal families.
$n=8$: ${\mathcal{F}}_{8,2}=\\{12x:5\leq x\leq 8\\}\cup\\{34x:5\leq x\leq
8\\}$,
${\mathcal{Q}}_{8}^{2}=$ two $K^{3}_{4}$ sharing a vertex (this triple system
has an isolated vertex),
${\mathcal{Q}}_{8}^{3}=$ two vertex disjoint $K^{3}_{4}$.
$n=9$: ${\mathcal{F}}_{9,2}=\\{12x:5\leq x\leq 9\\}\cup\\{34x:5\leq x\leq
9\\}$,
${\mathcal{Q}}_{9}^{2}=$ two $K^{3}_{4}$ on 1234 and 1567 with two additional
triples $289$, $589$.
$n=10$: ${\mathcal{F}}_{10,2}=\\{12x:5\leq x\leq 10\\}\cup\\{34x:5\leq x\leq
10\\}$,
${\mathcal{F}}_{10,3}=\\{12x:7\leq x\leq 10\\}\cup\\{34x:7\leq x\leq
10\\}\cup\\{56x:7\leq x\leq 10\\}$,
${\mathcal{Q}}_{10}^{3}=$ three $K^{3}_{4}$ sharing a vertex,
${\mathcal{Q}}_{10}^{4}=$ three $K^{3}_{4}$ forming a path,
$\\{1234,4567,789X\\}$.

###  10.1 Non-uniform triangle-free hypergraphs

Győri [16] proved his upper bound in the following more general form. Let
${\mathcal{H}}$ be a triangle-free multi-hypergraph on $n\geq 100$ vertices.
Then

$\sum_{E\in{\mathcal{H}}}\bigl{(}|E|-2\bigr{)}\leq\lfloor\frac{1}{8}n^{2}\rfloor.$
(13)

In this formulation, ${\mathcal{H}}$ may contain edges of different sizes, and
may contain multiple copies of the same set of vertices. Such multiple copies
are considered distinct for the purpose of forming a triangle, and are counted
with multiplicity in the summation in (13).

Given an ${\mathbf{A}}{\mathbf{B}}{\mathbf{D}}$-free triple system
${\mathcal{F}}$ one can prove
$|{\mathcal{F}}|\leq\lfloor\frac{1}{8}n^{2}\rfloor$ for $n\geq 100$ using (13)
as follows. Let ${\mathcal{Q}}:=\\{Q_{1},\ldots,Q_{q}\\}$ be all the vertex
sets of ${\mathbf{C}}$ configurations in ${\mathcal{F}}$, i.e., $|Q_{i}|=4$
and at least three triples within $Q_{i}$ are in ${\mathcal{F}}$. Note that
distinct $Q_{i}$ can share at most one vertex, otherwise we get a
${\mathbf{D}}$ configuration. Let ${\mathcal{H}}$ be the multi-hypergraph
having the following edges: two copies of each $Q_{i}$, $i=1,\ldots,q$ and one
copy of each $F\in{\mathcal{F}}$ such that $F\not\subseteq Q_{i}$,
$i=1,\ldots,q$. Note that

$|{\mathcal{F}}|\leq
4|{\mathcal{Q}}|+|{\mathcal{F}}\setminus(\partial{\mathcal{Q}})|=\sum_{E\in{\mathcal{H}}}\bigl{(}|E|-2\bigr{)}.$
(14)

Indeed, the inequality holds because each $Q_{i}$ contains at most $4$ triples
in ${\mathcal{F}}$. The equality holds because each $Q_{i}$ contributes
$\bigl{(}4-2\bigr{)}+\bigl{(}4-2\bigr{)}=4$ to the sum, and every other triple
in ${\mathcal{F}}$ contributes $3-2=1$. Upon checking that ${\mathcal{H}}$ is
triangle-free, (13) implies the desired bound $\lfloor\frac{1}{8}n^{2}\rfloor$
for the right-hand side of (14).

The above proof does not yield the extremal systems and only works for $n\geq
100$.

######  Definition 20.

A (simple) hypergraph ${\mathcal{H}}$ is called a $Q4$-family on $[n]$ if
there is a partition
${\mathcal{H}}={\mathcal{Q}}\cup{\mathcal{T}}\cup{\mathcal{E}}$ such that

  * –

${\mathcal{Q}}\subseteq{[n]\choose 4}$, ${\mathcal{T}}\subseteq{[n]\choose
3}$, ${\mathcal{E}}\subseteq{[n]\choose 2}$,

  * –

${\mathcal{H}}$ is triangle-free, and

  * –

$|H\cap H^{\prime}|\leq 1$ for any two distinct members
$H,H^{\prime}\in{\mathcal{H}}$.

######  Lemma 21.

Let ${\mathcal{H}}$ be a $Q4$-family on $[n]$ with
${\mathcal{Q}}\neq\emptyset$ and suppose $n\geq 15$. Then

$8|{\mathcal{Q}}|+\frac{7}{2}|{\mathcal{T}}|+|{\mathcal{E}}|<2\lfloor\frac{1}{8}n^{2}\rfloor$
(15)

except in the case when ${\mathcal{T}}={\mathcal{E}}=\emptyset$ and
$\partial{\mathcal{Q}}$ is the triple system ${\mathcal{Q}}^{4\times 4}$.

This is a simplified version of an inequality from [16] where Győri considered
$8|{\mathcal{Q}}|+4|{\mathcal{T}}|+|{\mathcal{E}}|$. Although (15) does not
seem to imply (13), and it does not apply to multi-hypergraphs, its proof is
simpler and valid for $15\leq n<100$, too.

###### Proof.

Let
$\sigma({\mathcal{H}}):=8|{\mathcal{Q}}|+\frac{7}{2}|{\mathcal{T}}|+|{\mathcal{E}}|$,
and $\sigma_{3}(n):=\max\\{\sigma({\mathcal{H}}):{\mathcal{H}}$ is a
$Q4$-family on $[n]$ with ${\mathcal{Q}}=\emptyset\\}$. Since a complete
bipartite graph can be considered as a $Q4$-family we have
$\sigma_{3}(n)\geq\lfloor\frac{1}{4}n^{2}\rfloor$. As a first step we prove
that for all $n\geq 0$

$\frac{7}{2}|{\mathcal{T}}|+|{\mathcal{E}}|\leq\frac{1}{4}(n^{2}+5).$ (16)

Indeed, $\sigma_{3}(0)=\sigma_{3}(1)=0$, $\sigma_{3}(2)=1=\frac{1}{4}2^{2}$,
$\sigma_{3}(3)=\frac{7}{2}=\frac{1}{4}(3^{2}+5)$. By inspection we can see
that $\sigma_{3}(n)$ is maximized for $n=4,5,6$ when ${\mathcal{H}}$ consists
of a single triple and an edge, two triples sharing a vertex, or two disjoint
triples joined by three disjoint pairs. This gives
$\sigma_{3}(4)=\frac{9}{2}=\frac{1}{4}(4^{2}+2)$,
$\sigma_{3}(5)=7=\frac{1}{4}(5^{2}+3)$, and
$\sigma_{3}(6)=10=\frac{1}{4}(6^{2}+4)$.

For $n\geq 7$ let $T_{1},\dots,T_{\ell}$ be a maximal family of pairwise
disjoint triples from ${\mathcal{T}}$, let $L=\cup T_{i}$, $|L|=3\ell$, and
$\overline{L}:=[n]\setminus L$. The case $\ell=0$ is obvious, so we may
suppose that $\ell\geq 1$. Make a tally of the pairs in
$G:=(\partial{\mathcal{T}})\cup{\mathcal{E}}$. Every vertex $x\in[n]\setminus
T_{i}$ has at most one $G$-neighbor in $T_{i}$, so $G$ can have at most
$3\ell+3{\ell\choose 2}$ edges in $L$, $\ell(n-3\ell)$ edges joining $L$ and
$\overline{L}$. Since $G$ is triangle-free on $\overline{L}$ it can have at
most $\frac{1}{4}(n-3\ell)^{2}$ edges in it. Define weights $w(e)$ on the
edges of $G$ as follows. The weight $w(e)=\frac{7}{6}$ if $e$ lies in $L$,
$w(e)=\frac{5}{4}$ if $e$ joins $L$ and $\overline{L}$, and finally $w(e)=1$
for edges in $\overline{L}$. The sum of the weights of the three pairs in
$T\in{\mathcal{T}}$ is $3\times\frac{7}{6}$ if $T\subseteq L$, it is
$\frac{7}{6}+2\times\frac{5}{4}$ if $|T\cap L|=2$, it is
$2\times\frac{5}{4}+1$ if $|T\cap L|=1$, and there is no $T\in{\mathcal{T}}$
such that $|T\cap L|=0$. So every triangle $T$ in $G$ belongs to
${\mathcal{T}}$ and receives at least $\frac{7}{2}$ total weight. Hence

$\begin{split}\frac{7}{2}|{\mathcal{T}}|+|{\mathcal{E}}|&\leq\frac{7}{6}\left(3\ell+3{\ell\choose
2}\right)+\frac{5}{4}\ell(n-3\ell)+\frac{1}{4}(n-3\ell)^{2}\\\
&=\frac{1}{4}\left(n^{2}+\ell^{2}-n\ell+7\ell\right).\end{split}$ (17)

The polynomial $p_{n}(\ell):=\ell^{2}-n\ell+7\ell$ attains its maximum over
$0\leq\ell\leq\lfloor\frac{n}{3}\rfloor$ at $\ell=0$ or
$\ell=\lfloor\frac{n}{3}\rfloor$, so it is at most $4$ for $n=7$, at most $2$
for $n=8$, at most $3$ for $n=9$, and at most $0$ for $n\geq 10$. This
completes the proof of inequality (16).

Next, consider the case $|{\mathcal{Q}}|\geq 1$ and let $Q_{1},\dots,Q_{k}$ be
a maximal family of pairwise disjoint quadruples from ${\mathcal{Q}}$, let
$K=\cup Q_{i}$, $|K|=4k$, and $\overline{K}:=[n]\setminus K$. Define the
hypergraph ${\mathcal{H}}_{3}$ on the vertex set $\overline{K}$ as

  * –

the triples of ${\mathcal{T}}$ and the pairs of ${\mathcal{E}}$ contained in
$\overline{K}$, and

  * –

the triples of the form $Q\cap\overline{K}$ when $Q\in{\mathcal{Q}}$, $|Q\cap
K|=1$, and

  * –

the pairs of the form $Q\cap\overline{K}$ when $Q\in{\mathcal{Q}}$, $|Q\cap
K|=2$, and

  * –

the pairs of the form $T\cap\overline{K}$ when $T\in{\mathcal{T}}$, $|T\cap
K|=1$.

This is a $Q4$-family without any quadruple, so (16) gives

$\sigma({\mathcal{H}}_{3})\leq\frac{1}{4}((n-4k)^{2}+5).$

Let $\partial_{2}{\mathcal{H}}$ be the set of pairs that are contained in some
edge of ${\mathcal{H}}$. Define the graph $G$ as the set of pairs in
$\partial_{2}{\mathcal{H}}$ meeting $K$. As before, $G$ can have at most
$6k+4{k\choose 2}$ edges in $K$ and $k(n-4k)$ edges joining $K$ and
$\overline{K}$. Define weights $w(e)$ on the edges of $G$ as follows. The
weight $w(e)=\frac{4}{3}$ if $e$ lies in $K$, $w(e)=\frac{3}{2}$ if $e$ joins
$K$ to $\overline{K}$. Define weights on the members of ${\mathcal{H}}_{3}$ as
needed, $w(S)=\frac{7}{2}$ for triples in ${\mathcal{H}}_{3}$ and $w(e)=1$ for
pairs in ${\mathcal{H}}_{3}$.

It is easy to check that the total weight in each member of
$Q\in{\mathcal{Q}}$ is at least 8, it is at least $\frac{7}{2}$ for the
members of ${\mathcal{T}}$, and it is at least 1 for pairs in ${\mathcal{E}}$.
Indeed, if $Q\subseteq K$ then it gets $6\times\frac{4}{3}=8$, if $|Q\cap
K|=3$ then it gets $3\times\frac{4}{3}+3\times\frac{3}{2}$, if $|Q\cap K|=2$
then it gets $\frac{4}{3}+4\times\frac{3}{2}+1$, and if $|Q\cap K|=1$ then it
gets $3\times\frac{3}{2}+\frac{7}{2}$. If $T\in{\mathcal{T}}$ and $T\subseteq
K$ then it gets $3\times\frac{4}{3}$, if $|T\cap K|=2$ then it gets
$\frac{4}{3}+2\times\frac{3}{2}$, if $|T\cap K|=1$ then it gets
$2\times\frac{3}{2}+1$, and if $T\cap K=\emptyset$ then its weight is
$\frac{7}{2}$. Finally, the weight of the (relevant) pairs is at least $1$.
Hence

$\displaystyle 8|{\mathcal{Q}}|+\frac{7}{2}|{\mathcal{T}}|+|{\mathcal{E}}|$
$\displaystyle\leq$ $\displaystyle\sum_{e\in G}w(e)+\sigma_{3}(n-4k)$ (18)
$\displaystyle\leq$ $\displaystyle\frac{4}{3}\left(6k+4{k\choose
2}\right)+\frac{3}{2}k(n-4k)+\frac{1}{4}\left((n-4k)^{2}+5\right)$
$\displaystyle=$
$\displaystyle\frac{1}{4}n^{2}+\frac{1}{12}\left(8k^{2}-6kn+64k+{15}\right).$

Here $2k(4k-n+32-2n)+{15}<-12$ for $n\geq 18$ (and $1\leq
k\leq\lfloor\frac{n}{4}\rfloor$), it is less than $-3$ for $n=17$, and it is
negative for $n=16$ and $k=1,2,3$.

For the case $n=16$ and $k=4$ we have $K=V(G)$ and $G$ has $24$ edges in
$Q_{1},\dots,Q_{4}$ and at most $4\times{4\choose 2}=24$ further edges. Recall
that the weight of each edge is $\frac{4}{3}$. So every $Q\in{\mathcal{Q}}$
gets weight 8, $T\in{\mathcal{T}}$ gets weight 4, and a pair
$E\in{\mathcal{E}}$ has weight $\frac{4}{3}$. So $\sigma({\mathcal{H}})\leq
48\times\frac{4}{3}=64$, as claimed. Here equality can hold only if
${\mathcal{T}}$ and ${\mathcal{E}}$ are both empty, and $|{\mathcal{Q}}|=8$.
Then ${\mathcal{Q}}$ must have the lattice structure.

Finally, in the case $n=15$ we use (18) directly. By (17) we have
$\sigma_{3}(15-4)\leq\frac{1}{4}11^{2}$ so in the case $(n,k)=(15,1)$ instead
of (10.1) we have
$\sigma({\mathcal{H}})\leq\frac{1}{4}n^{2}+\frac{1}{12}\left(8k^{2}-6kn+64k\right)$
which is less than $2\lfloor\frac{1}{8}n^{2}\rfloor$. Similarly, in the case
$(n,k)=(15,2)$ using $\sigma_{3}(15-2\times 4)\leq\frac{1}{4}(7^{2}+4)$ leads
to $\sigma({\mathcal{H}})<2\lfloor\frac{1}{8}n^{2}\rfloor$.

In the case $(n,k)=(15,3)$ we define another weight function on the edges of
$\partial_{2}{\mathcal{H}}$. We assign weight $\frac{4}{3}$ to each pair. With
this weighting every member of ${\mathcal{Q}}$ receives a total weight $8$, a
triple in ${\mathcal{T}}$ gets $4$ and a pair from ${\mathcal{E}}$ gets
$\frac{4}{3}$. The graph $\partial_{2}{\mathcal{H}}$ has $18$ edges covered by
$Q_{1},Q_{2}$, and $Q_{3}$, there are at most $12$ edges between these three
quadruples, there are at most $3\times 3$ edges from $\overline{K}$ to $K$,
and at most $\binom{|{\overline{K}}|}{2}=3$ edges in $\overline{K}$. Hence
$|\partial_{2}{\mathcal{H}}|\leq 42$ and $\sigma({\mathcal{H}})\leq
56=2\lfloor\frac{1}{8}n^{2}\rfloor$. However, here equality can hold only if
all the $42$ pairs of $\partial_{2}{\mathcal{H}}$ belong to members of
${\mathcal{Q}}$. But it is not possible to add to $Q_{1},Q_{2},Q_{3}$ four
more quadruples that form with them a $Q4$-family. This completes the proof of
the lemma. ∎

###  10.2 Proof of Theorem 19

Let ${\mathcal{F}}$ be an ${\mathbf{A}}{\mathbf{B}}{\mathbf{D}}$-free triple
system on $[n]$ with $|{\mathcal{F}}|\geq\lfloor\frac{1}{8}n^{2}\rfloor$,
$n\geq 8$. Our aim is to prove that
$|{\mathcal{F}}|=\lfloor\frac{1}{8}n^{2}\rfloor$ and ${\mathcal{F}}$ is among
the families prescribed earlier. We start as in the beginning of Subsection
10.1.

Let ${\mathcal{Q}}:=\\{Q_{1},\ldots,Q_{q}\\}$ be all the vertex sets of
${\mathbf{C}}$ configurations in ${\mathcal{F}}$, i.e., $|Q_{i}|=4$ and at
least three triples within $Q_{i}$ are in ${\mathcal{F}}$. Define
${\mathcal{F}}_{3}$ as the set of triples from ${\mathcal{F}}$ having three
own pairs, and let
${\mathcal{F}}_{2}:={\mathcal{F}}\setminus(\partial{\mathcal{Q}}\cup{\mathcal{F}}_{3})$.
Each member of ${\mathcal{F}}_{2}$ has exactly two own pairs, the set of these
are denoted by ${\mathcal{E}}$. Then the family
${\mathcal{H}}={\mathcal{Q}}\cup{\mathcal{F}}_{3}\cup{\mathcal{E}}$ is a
$Q4$-family.

If ${\mathcal{Q}}=\emptyset$ then ${\mathcal{F}}$ is
${\mathbf{A}}{\mathbf{B}}{\mathbf{C}}{\mathbf{D}}$-free and Theorem 1 can be
applied. So from now on, we may suppose that $q\geq 1$. In case of $n\geq 15$
we can apply Lemma 21. We get

$2|{\mathcal{F}}|\leq
8|{\mathcal{Q}}|+2|{\mathcal{F}}_{3}|+|{\mathcal{E}}|\leq\sigma({\mathcal{H}})<2\lfloor\frac{1}{8}n^{2}\rfloor$

unless ${\mathcal{F}}={\mathcal{Q}}^{4\times 4}$. So the proof is complete for
$n\geq 15$.

From now on we may suppose that $n\leq 14$ (and $q\geq 1$). These are finitely
many cases so one can check them with a computer. For completeness we sketch a
case by case check in the next subsection. ∎

####  10.2.1 The case $8\leq n\leq 14$

Starting with $Q_{1}=1234$ and adding new quadruples one by one it can be seen
that there are 16 possibilities for ${\mathcal{Q}}$. The list is presented
below (also see Figure 4). $\kappa$ denotes $|\cup{\mathcal{Q}}|$,
$U:=\cup{\mathcal{Q}}$, and $i^{\prime}$ denotes the element $10+i$.

Figure 4: The 16 possibilities for ${\mathcal{Q}}$ on 14 vertices

  1. 1.

$q=1$, $\kappa=4$, ${\mathcal{Q}}_{1}=\\{1234\\}$

  2. 2.

$q=2$, $\kappa=7$, ${\mathcal{Q}}_{2}=\\{1234,1567\\}$

  3. 3.

$q=2$, $\kappa=8$, ${\mathcal{Q}}_{3}=\\{1234,5678\\}$

  4. 4.

$q=3$, $\kappa=10$, ${\mathcal{Q}}_{4}=\\{1234,1567,1890^{\prime}\\}$

  5. 5.

$q=3$, $\kappa=10$, ${\mathcal{Q}}_{5}=\\{1234,4567,7890^{\prime}\\}$

  6. 6.

$q=3$, $\kappa=11$, ${\mathcal{Q}}_{6}=\\{1234,1567,890^{\prime}1^{\prime}\\}$

  7. 7.

$q=3$, $\kappa=12$,
${\mathcal{Q}}_{7}=\\{1234,5678,90^{\prime}1^{\prime}2^{\prime}\\}$

  8. 8.

$q=4$, $\kappa=12$,
${\mathcal{Q}}_{8}=\\{1234,5678,1590^{\prime},261^{\prime}2^{\prime}\\}$

  9. 9.

$q=4$, $\kappa=13$,
${\mathcal{Q}}_{9}=\\{1234,5678,90^{\prime}1^{\prime}2^{\prime},1593^{\prime}\\}$

  10. 10.

$q=4$, $\kappa=13$,
${\mathcal{Q}}_{10}=\\{1234,1567,1890^{\prime},11^{\prime}2^{\prime}3^{\prime}\\}$

  11. 11.

$q=4$, $\kappa=13$,
${\mathcal{Q}}_{11}=\\{1234,1567,1890^{\prime},81^{\prime}2^{\prime}3^{\prime}\\}$

  12. 12.

$q=4$, $\kappa=13$,
${\mathcal{Q}}_{12}=\\{1234,4567,7890^{\prime},0^{\prime}1^{\prime}2^{\prime}3^{\prime}\\}$

  13. 13.

$q=4$, $\kappa=14$,
${\mathcal{Q}}_{13}=\\{1234,5678,890^{\prime}1^{\prime},1^{\prime}2^{\prime}3^{\prime}4^{\prime}\\}$

  14. 14.

$q=4$, $\kappa=14$,
${\mathcal{Q}}_{14}=\\{1234,1567,890^{\prime}1^{\prime},82^{\prime}3^{\prime}4^{\prime}\\}$

  15. 15.

$q=4$, $\kappa=14$,
${\mathcal{Q}}_{15}=\\{1234,5678,590^{\prime}1^{\prime},52^{\prime}3^{\prime}4^{\prime}\\}$

  16. 16.

$q=5$, $\kappa=14$,
${\mathcal{Q}}_{16}=\\{1234,5678,90^{\prime}1^{\prime}2^{\prime},1593^{\prime},260^{\prime}4^{\prime}\\}$.

In all cases we define a graph $G$ by selecting two own pairs from each triple
in ${\mathcal{F}}\setminus(\partial{\mathcal{Q}})$. This $G$ is triangle-free.
Then we find an upper bound $\alpha$ for the possible number of edges of $G$
in $U$, a bound $\beta$ for the number of $G$-edges joining $U$ to
$[n]\setminus U$, and a bound $\gamma$ for the number of $G$-edges in
$[n]\setminus U$. In particular, we have
$\gamma\leq\lfloor\frac{1}{4}(n-\kappa)^{2}\rfloor$. Then

$|{\mathcal{F}}|\leq 4|{\mathcal{Q}}|+\frac{1}{2}|E(G)|\leq
4q+\lfloor\frac{1}{2}(\alpha+\beta+\gamma)\rfloor.$ (20)

In almost all cases (20) immediately gives
$|{\mathcal{F}}|<\lfloor\frac{1}{8}n^{2}\rfloor$.

— Case of ${\mathcal{Q}}_{1}$. $\alpha=0$, $\beta\leq n-4$,
$\gamma\leq\frac{1}{4}(n-4)^{2}$, so $|{\mathcal{F}}|\leq
4+\frac{1}{2}(\alpha+\beta+\gamma)\leq\frac{1}{8}(n^{2}-4n+32)$. This is less
than $\lfloor\frac{1}{8}n^{2}\rfloor$ for $n\geq 9$. In case of $n=8$ equality
must hold, $G$ is a $4$-cycle on $[8]\setminus Q_{1}$ plus four edges to
$Q_{1}$. But this cannot be realized by triples.

— Case of ${\mathcal{Q}}_{2}$. $\alpha=0$, $\beta\leq 2(n-7)$,
$\gamma\leq\lfloor\frac{1}{4}(n-7)^{2}\rfloor$. So
$|{\mathcal{F}}|<\lfloor\frac{1}{8}n^{2}\rfloor$ for $n\geq 11$ by (20). In
case of $n=10$ we have that $\gamma=2$ and $\beta=6$, but this cannot be
realized. In case of $n=9$ we obtain ${\mathcal{Q}}_{9}^{2}$. The case of
$n=8$ is obvious, ${\mathcal{F}}=\partial{\mathcal{Q}}$
($={\mathcal{Q}}_{8}^{2}$).

— Case of ${\mathcal{Q}}_{3}$. For $n\geq 11$ we have $\alpha\leq 4$,
$\beta\leq 2(n-8)$, so
$|{\mathcal{F}}|\leq\frac{1}{8}(n^{2}-8n+80)<\lfloor\frac{1}{8}n^{2}\rfloor$.
In case of $n=8$ we have ${\mathcal{F}}=\partial{\mathcal{Q}}$
($={\mathcal{Q}}_{8}^{3}$). If $n=9$ then only one more triple can be added to
${\mathcal{Q}}_{8}^{3}$, and in case of $n=10$ at most two more can be added.
These are too few, so we are done.

— Case of ${\mathcal{Q}}_{4}$. Here $\alpha=0$, $\beta\leq 3(n-10)$ so (20)
gives $|{\mathcal{F}}|<\lfloor\frac{1}{8}n^{2}\rfloor$ for $n\geq 11$. In case
of $n=10$ we have ${\mathcal{F}}=\partial{\mathcal{Q}}$
($={\mathcal{Q}}_{10}^{3}$).

— Case of ${\mathcal{Q}}_{5}$. Here $\alpha=3$, $\beta\leq 3(n-10)$ so (20)
gives
$|{\mathcal{F}}|\leq\frac{1}{8}(n^{2}-8n+88)<\lfloor\frac{1}{8}n^{2}\rfloor$
for $n\geq 12$. In case of $n=10$ we have
${\mathcal{F}}=\partial{\mathcal{Q}}$ ($={\mathcal{Q}}_{10}^{4}$). In case of
$n=11$ one can add at most one new triple to ${\mathcal{Q}}_{5}$, so we have
$|{\mathcal{F}}|\leq 13$.

— Case of ${\mathcal{Q}}_{6}$. Here $\alpha=7$, $\beta\leq 3(n-11)$ so (20)
gives
$|{\mathcal{F}}|\leq\frac{1}{8}(n^{2}-10n+113)<\lfloor\frac{1}{8}n^{2}\rfloor$
for $n\geq 12$. In case of $n=11$ we have
${\mathcal{F}}=\partial{\mathcal{Q}}$ so $|{\mathcal{F}}|\leq 12$.

— Case of ${\mathcal{Q}}_{7}$. Here $\alpha=12$, $\beta\leq 3(n-12)$ so (20)
gives
$|{\mathcal{F}}|\leq\frac{1}{8}(n^{2}-12n+144)<\lfloor\frac{1}{8}n^{2}\rfloor$
for $n\geq 13$. In case of $n=12$ one can add at most four disjoint new
triples to ${\mathcal{Q}}_{7}$, so we have $|{\mathcal{F}}|\leq 16$.

— Case of ${\mathcal{Q}}_{8}$. Here $\alpha=4$, $\beta\leq 4(n-12)$ so (20)
gives
$|{\mathcal{F}}|\leq\frac{1}{8}(n^{2}-8n+96)<\lfloor\frac{1}{8}n^{2}\rfloor$
for $n\geq 13$. In case of $n=12$ one cannot add any new triple to
${\mathcal{Q}}_{8}$, so we have $|{\mathcal{F}}|\leq 16$.

In the rest of the cases $n\in\\{13,14\\}$ and $|U|\geq 13$. Let $\eta$ (or
$\eta_{n}$) be the size of ${\mathcal{F}}\setminus(\partial{\mathcal{Q}})$.
Since $|{\mathcal{Q}}|$ is at least 4 we have more restrictions, it is easier
to give an upper bound for $\eta$. In the cases
${\mathcal{Q}}_{9}$–${\mathcal{Q}}_{15}$ we have to show that
$\eta_{13}<21-16=5$, and $\eta_{14}<8$. In the case ${\mathcal{Q}}_{16}$ we
need $\eta_{14}<4$.

— Case of ${\mathcal{Q}}_{9}$. No more triples meeting $1593^{\prime}$, so
$\eta_{13}\leq 3$ and $\eta_{14}\leq 6$.

— Case of ${\mathcal{Q}}_{10}$. Obviously $\eta_{13}=0$ and $\eta_{14}=0$.

— Case of ${\mathcal{Q}}_{11}$. $\eta_{13}=0$ and $\eta_{14}\leq 2$.

— Case of ${\mathcal{Q}}_{12}$. $\eta_{13}=0$ and $\eta_{14}\leq{4\choose 2}$.

— Case of ${\mathcal{Q}}_{13}$. No more triples meeting
$890^{\prime}1^{\prime}$, so $\eta\leq 3$.

— Case of ${\mathcal{Q}}_{14}$ and ${\mathcal{Q}}_{15}$. $\eta=0$.

— Case of ${\mathcal{Q}}_{16}$. $\eta\leq 2$. ∎

##  11 Excluding ${\mathbf{B}}$, ${\mathbf{C}}$ and ${\mathbf{D}}$

For ${\mathbf{B}}{\mathbf{C}}{\mathbf{D}}$-free families we know the upper
bound

${\rm ex}(n,{\mathbf{B}}{\mathbf{C}}{\mathbf{D}})\leq{\rm
ex}(n,{\mathbf{C}}{\mathbf{D}})=\lfloor\frac{1}{4}(n-1)^{2}\rfloor.$

The extremal construction for ${\rm ex}(n,{\mathbf{C}}{\mathbf{D}})$ – of the
form ${\mathcal{F}}_{T}$ for some tournament $T$ – does contain ${\mathbf{B}}$
configurations, so this bound cannot be exactly matched. But we do have an
asymptotically matching construction.

######  Theorem 22.

${\rm
ex}(n,{\mathbf{B}}{\mathbf{C}}{\mathbf{D}})=\frac{1}{4}n^{2}\bigl{(}1-o(1)\bigr{)}.$

Our construction uses Wilson’s well-known decomposition theorem, which we
recall now.

######  Theorem 23 (Wilson [22]).

For every fixed graph $H$ there exists $n_{0}=n_{0}(H)$ such that the
following holds for all $n\geq n_{0}$:
There exists a decomposition of the edge set $E(K_{n})$ of the complete graph
on $n$ vertices into copies of $H$ if and only if the number of edges of $H$
divides ${n\choose 2}$, and the greatest common divisor of the vertex degrees
in $H$ divides $n-1$.

Proof of Theorem 22. For every integer $m\geq 2$ we construct a graph $H_{m}$
to which we will apply Theorem 23. It has $m^{2}$ vertices, partitioned into
${m\choose 2}$ pairs $A_{1},\ldots,A_{{m\choose 2}}$ and a set $B$ of size
$m$. The graph induced on each $A_{i}\cup B$, $1\leq i\leq{m\choose 2}$, is
complete, and these are all the edges of $H_{m}$. Thus

  * •

$|E(H_{m})|={m\choose 2}(2m+1)+{m\choose 2}={m\choose 2}(2m+2)=m(m-1)(m+1)$.

  * •

$\gcd\bigl{(}\\{\deg_{H_{m}}(v)\colon v\in
V(H_{m})\\}\bigr{)}=\gcd(m+1,m^{2}-1)=m+1$.