# Extremal functions for tournaments

We are looking at directed graphs with no loops or parallel edges, but given two vertices $x$ and $y$, we allow the presence of both the edge $(x, y)$ and $(y, x)$. Thus, if $G$ is a directed graph on $n$ vertices, $|E(G)| \le n(n-1)$.

A tournament is a directed complete graph where for any pair of vertices $x$ and $y$, exactly one of the edges $(x, y)$ and $(y, x)$ is present.

The question is, given a fixed tournament $T$, how many edges (as a function of $n$) must a graph on $n$ vertices have in order to force the existence of $T$ as a subgraph?

An obvious obstruction is the following. Assume $T$ has $k$ vertices, and let $G$ be any undirected graph which does not have $K_k$ as a subgraph. Let $\bar{G}$ be obtained from $G$ by adding two directed edges, one in each direction, for every edge of $G$. Then $\bar{G}$ does not have $T$ as a subgraph. Thus, the extremal function for $T$ is at least twice the extremal function for $K_k$ in undirected graphs. Could this be the correct bound?

An easy induction argument shows that if $T$ has 3 vertices, then $|E(G)| > n^2/2$ implies $G$ contains $T$ as a subgraph. Thus, the extremal function for $T$ is exactly twice the extremal function for the presence of a triangle.

The final question is, the above question seems quite basic, and I would be surprised if no one had considered it before. Does anyone know of a reference looking at these questions?

Short answer: Yes, the bound you are suggesting is correct.

The problem was solved by Brown and Harary in Extremal digraphs" (1970). I could not find the complete text of the paper, so let me try to give a (possibly different) proof here. (Disclosure: The proof has been substantially modified after Paul found an error in the original.)

Let $t_k(n)$ denote the number of edges in the almost balanced $(k-1)$-partite graph on $n$ vertices. We will show the following.

Let $D$ be a simple digraph on $n$ vertices. If $E(D)>2t_k(n)$ then $D$ contains every tournament on $k$ vertices of the subgraph.

Let $G$ be a simple graph and $w:E(G) \to \{1,2\}$ a weight function. We say that a clique $S \subseteq V(G)$ is an anti-matching if the set of edges in $E(G[S])$ with weight $1$ is a matching. Considering a simple weighted digraph $G_D$ corresponding to a digraph $D$, where a pair of oppositely directed edges in $D$ correspond to edges of weight $2$ in $G_D$. It is easy to derive our claim above from the following.

Let $G$ be a simple graph on $n$ vertices, and let $w:E(G) \to \{1,2\}$ a weight function. If $G$ does not contain an anti-matching of size $k$ then $w(E(G)) \leq 2t_k(n)$.

Suppose for a contradiction that $G$ does not contain an anti-matching of size $k$ and $w(E(G)) > 2t_k(n)$. Choose such $G$ with $n=|V(G)|$ minimum. For $U \subseteq V(G)$, let $w(U)$ denote the total weight of all edges incident to $U$, and let $w(U,V(G)-U)$ denote the total weight of all edges with one end in $U$ and another in $V(G)-U$. Let $S$ be an anti-matching in $G$ chosen so that $w(E(G[S]))$ is maximum. We claim that $w(S,\{v\}) \leq 2|S|-2$ for every $v \in V(G)-S$. Consider for a contradiction $v \in V(G)-S$ such that $w(S,\{v\}) \geq 2|S|-1$. It is clear from the choice of $S$ that $w(S,\{v\}) = 2|S|-1$. Let $u$ be the unique vertex of $S$ such that $w(uv) = 1.$ If $u$ is not incident to any edge of weight $1$ in $E(G[S])$, then $S \cup \{v\}$ contradicts the choice of $S$. Otherwise, $(S \cup \{v\})-\{u\}$ contradicts the choice of $S$. We have $$w(U) \leq |S|(|S|-1)+2(n-|S|)(|S|-1) \leq 2(t_k(n)-t_k(n-|S|)).$$ Thus $G \setminus S$ contradicts the choice of $G$.

• Hi Sergey, thanks for the answer. For the proof, I don't believe it holds that if the weight of a subgraph on $k$ vertices is $k(k-1)-2$, then there is a subgraph on $k-1$ vertices of weight $(k-1)(k-2)$. Consider if every edge of the $k$ vertex graph has weight two except for two non-incident edges with weight one. Then any $k-1$ vertex subgraph will contain one of the weight one edges. – Paul Wollan Nov 21 '13 at 20:34
• Hi Sergey, thanks for the edit. I cannot see why $(S \cup \{v\})-\{u\}$ contradicts the choice of $S$. Doesn't it have exactly the same total weight as $S$? – Tony Huynh Nov 28 '13 at 17:13
• Hi Tony, isn't it true that in $(S \cup \{v\})-\{u\}$ the vertex $v$ is incident only to edges of weight $2$, while $u$ was incident to an edge of weight $1$ in $S$? – Sergey Norin Nov 28 '13 at 19:50
• Yes, you are right, was going to delete my comment before you responded, but went to have a beer instead. Sorry about that. Good proof! – Tony Huynh Nov 28 '13 at 20:05