4
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Paul Wollan Nov 21 '13 at 20:34
  • $\begingroup$ 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$? $\endgroup$ – Tony Huynh Nov 28 '13 at 17:13
  • $\begingroup$ 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$? $\endgroup$ – Sergey Norin Nov 28 '13 at 19:50
  • $\begingroup$ 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! $\endgroup$ – Tony Huynh Nov 28 '13 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.