Mathematics Asked by user146215 on December 14, 2020

There is a transitive tournament (T) with $n > 1$ vertices and the score sequence is defined as $s_1, s_2, ldots,s_n$

Prove that T is transitive if and only if the score of the $k^{th}$ vertex ($s_k$) = ‘$k-1$’ for $k =1,2,ldots. n $

i.e $s_k = k-1$ for all $k= 1,2,3,ldots, n$

I have been researching and noticed that this is similar to the Landau’s Theorem (1953), however i am completely lost with the proof. I know that the score is the out degree, and i know that the out degree is the total number of edges going out of the vertex which is of course also (0,1,2,3…n-1).

I know that a tournament must have a unique ranking, and i also know that at transitive tournament must have at least one in degree on 0 .

I also know that a transitive tournament must have a score sequence of $(0,1,2,3,…n-1)$, and obviously the in degree is the number of edges minus that.

I have tried going along the lines of proof by contradiction, but i am completely stuck

I would really like to find a proof for this, please help!

We want to show that a transitive tournament with $n$ vertices has the score sequence of $(0,1,2,…,n−1)$. Now suppose that it holds for all the transitive tournaments.

The proof is by induction on the number of vertices of $T$, the result being trivial for transitive tournaments with at most two vertices.

Let T be a transitive tournament with $n+1$ vertices. We know that a tournament is an orientation of a complete graph. In addition, transitivity implies that $T$ is acyclic. So $T$ has a vertex $V$ with out-degree of $n$. If we delete $V$ and it's incident edges, then the graph that remains is a transitive tournament with $n$ vertices and it has a vertex with out-degree of $n-1$. By our induction hypothesis, this graph has the score sequence of $(0,1,2,…,n−1)$. Appending the score of V to it gives the score sequence of $T$ which is $(0,1,2,...,n)$.

Now we want to show that if score sequence $(S_1,S_2,S_3,...,S_n)$ where $S_k=k-1$ for all $k=1,2,3,…,n$ then $T$ is transitive.

Remove leaf vertex $V$ and it's incident edges. Removing $V$ will decrease all of the remaining vertices in-degrees by one so there will be another leaf vertex. Keep removing leaf vertices, we will eventually remove all vertices: The tournament is acyclic therefore transitive.

Answered by Root G on December 14, 2020

Get help from others!

Recent Answers

- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP