Prove the condition of the score sequence make the tournament strong

Question

Prove the theorem 4.19: A non-decreasing sequence $\pi:s_1,s_2,\ldots,s_n$ of nonnegative integers is a score sequence of a strong tournament if and only if

$$\sum_{i=1}^ks_i > \binom k 2 $$

for $1≤k≤n-1$

and

$$\sum_{i=1}^ns_i = \binom n 2 $$

Furthermore, every tournament whose score sequence satisfies these conditions is strong.

I know how to show that $\pi$ is the score sequence of $T$ if and only if it satisfy these 2 conditions, but I can't see how these 2 conditions make the tournament strong

Answer 1

I think that this argument is along the lines of the material that you’ve been studying.

Let’s say that a score sequence $\langle s_1,\ldots,s_n\rangle$ is a strong score sequence if $\sum_{i=1}^ks_i>\binom{k}2$ for $k=1,\ldots,n-1$. We want to show that a tournament is strong iff its score sequence is strong. The easier direction is to show that if a tournament is strong, so is its score sequence.

Suppose that $T$ is a tournament with score sequence $\langle s_1,\ldots,s_n\rangle$ that is not strong; then there is a $k<n$ such that $\sum_{i=1}^ks_i=\binom{k}2$.

• Show that $T$ has no edge from $\{v_1,\ldots,v_k\}$ to $\{v_{k+1},\ldots,v_n\}$, and conclude that $T$ cannot be strong.

The other direction is harder. Suppose that $T$ has the strong score sequence $\langle s_1,\ldots,s_n\rangle$, corresponding to vertices $v_1,\ldots,v_n$; we want to show that $T$ is strong. Note that since the score sequence is strong, $s_1\ge 1$.

Let $C$ be a maximal cycle in $T$. (There must be one; why?) If $C$ is Hamiltonian, we’re done: $T$ is strong. Suppose, then, that $C$ is not Hamiltonian, and let $v$ be vertex not in $C$.

• Suppose that there are vertices $x$ and $y$ in $C$ such that $xv$ and $vy$ are edges of $T$; show that in that case there are consecutive vertices $u$ and $w$ of $C$ (i.e., $uw$ is an edge of $C$) such that $uv$ and $vw$ are edges of $T$.

• Conclude that $C$ is not maximal and hence that either every edge between $v$ and $C$ is from $v$ to $C$, or every edge between $v$ and $C$ is from $C$ to $v$.

Let $A$ be the set of vertices $v\notin C$ such that $vx$ is an edge of $T$ for each $x\in C$, and let $B$ be the set of vertices $v\notin C$ such that $xv$ is an edge of $T$ for each $x\in C$.

• Show that if $x\in A$ and $y\in B$, then $xy$ is an edge of $T$. (HINT: If not, $C$ isn’t maximal.)

Now we have the following schematic:

$$\begin{array}{ccc} A&&\longrightarrow&&B\\ &\searrow&&\nearrow\\ &&C \end{array}$$

Note that $A$ or $B$ may be empty. Suppose that $B\ne\varnothing$.

• Show that if $|B|=k$, then $B=\{v_1,\ldots,v_k\}$, the $k$ vertices at the beginning of $T$’s score sequence. (HINT: Compare the out-degree of each vertex of $T$ with $k$.)
• Conclude further that $\sum_{i=1}^ks_i=\binom{k}2$, contradicting the assumption that $T$ has a strong score sequence.

This shows that $B=\varnothing$.

• Now suppose that $A\ne\varnothing$, and use essentially the same argument to get a contradiction.

We’ve now shown that $C$ is Hamiltonian and hence that $T$ is strong.

Answer 2

HINTS (I will add details if desired, but you will learn more if you try to find them by yourself).

Step 1: make a bipartite graph $G$ with bipartition $X,Y$. The vertices of $X$ are the edges of $K_n$, the vertices of $Y$ are the vertices $v_1,\ldots,v_n$, each with the desired multiplicity, i.e. there are $s_1$ copies of $v_1$, $s_2$ copies of $v_2$ etc. An vertex $e$ of $X$ is made adjacent to all copies of both its endpoints.

Step 1a: show that $|X|=|Y|$.

Step 2: show that Hall's condition holds in $G$ (for $X$).

Step 3: use the perfect matching you find as a consequence of the previous steps to obtain an orientation of $K_n$ with the desired score sequence.

Step 4: assume that the found orientation is not a strong orientation and obtain a contradiction with the result that every graph has a strong component without outarrows.

Answer 3

There's a much simpler answer:

Suppose we have $\sum_{i=1}^{k}s_i>\binom k 2$, for $1\leq k \leq n-1$. If the graph is not strongly connected, then its vertices can be decomposed into strong components, and one of these components has no outgoing edges. Name this component $S$ with size $t<n$. For any $v\in S$, we have $deg^+(v)<t$, and for any $v \notin S$ we have $deg^+(v)\geq t$. So the first $t$ vertices in score sequence are exactly the elements of $S$. Therefore we have $\sum_{i=1}^{t}s_i=\binom t 2$. This is a contradiction, and we can conclude that the tournament is strong.

Conversely, if the tournament is strong, but there exist a $k$ such that $k<n$ and $\sum_{i=1}^{k}s_i=\binom k 2$, then we name $S = \{v_1, . . ., v_k\}$, then no edge can go from $S$ to outside of $S$ (we have already $\binom n 2$ edges inside $S$). This also is a contradiction, so no such k exist, therefore we have $\sum_{i=1}^{k}s_i>\binom k 2$ for $1\leq k<n$. $\blacksquare$