Question

Show that a transitive tournament can have its vertices ordered so that if $a$ precedes $b$. then the score of $a$ is greater than or equal to the score of $b$.

Short answer

The vertices of a transitive tournament can be ordered such that each vertex's score is at least the score of any subsequent vertex in the order.

Step-by-step solution

Understanding a Transitive Tournament

A transitive tournament is a directed graph where for every three vertices $a,b,$ and $c$, if there is a path from $a$ to $b$, and a path from $b$ to $c$, then there is always a path from $a$ to $c$. This means that the graph is acyclic and has a strict order among its vertices.

Define the Score of a Vertex

The score of a vertex in a tournament (or digraph) is the number of vertices it has a direct edge towards. If a vertex $v$ has edges directed towards vertices $u_1,u_2,\dots ,u_k$, then the score of $v$ is $k$.

Order Vertices by Transitivity

Since it's a transitive tournament, we can arrange the vertices $v_1,v_2,\dots ,v_n$ such that for any two vertices $v_i$ and $v_j$ in this list where $i<j$, there is a directed edge from $v_i$ to $v_j$. This means $v_i$ must be able to reach $v_j$ since $i<j$.

Compare Scores in Order

As the vertices are ordered using transitivity, for a vertex $v_i$, all possible vertices it connects to will come after it in the order. Therefore, if $v_i$ connects to any vertex $v_j$ with $j>i$, the possible options for it to connect to reduce with increasing $i$. This implies that the score of $v_i$ is greater than or equal to the score of $v_j$.

Verify by Example or Induction

We can verify this setup by taking a small transitive tournament and ordering the vertices in this manner. For any vertex $v$, its connections are to those after it in the order, ensuring the score can only decrease or stay the same. Alternatively, mathematical induction can formally establish that given the ordered arrangement, the vertex scores adhere to this rule.

Key concepts

Directed Graph

A directed graph is a collection of nodes connected by edges, each having a specific direction from one vertex to another. This means that if there is an edge from vertex $u$ to vertex $v$, you can travel from $u$ to $v$, but not necessarily the other way around. These kinds of graphs are often used to represent relationships or processes that have a direction, such as a one-way street or a sequence of tasks that need to be completed in order.

Directed graphs are different from undirected graphs, where the connections between nodes have no direction. They provide a robust way to model dynamics where the directionality of connections is important. In the context of the exercise, a transitive tournament is a special type of directed graph, where there is a strict hierarchy or ordering among the vertices.

Vertex Score

The concept of vertex score is an integral part of understanding tournaments in graph theory. In a directed graph, particularly a transitive tournament, the score of a vertex refers to how many vertices it has a direct link to, or in other words, how many edges are going out of it.

To put it simply, if a vertex $v$ in a tournament is connected to three other vertices through outgoing edges, then the score of $v$ is 3. The importance of vertex scores becomes apparent when ordering the vertices. In a transitive tournament, it's shown through mathematical reasoning that vertices can be ordered such that if one vertex precedes another, its score is greater than or equal to the vertex that comes after.

Acyclic Graph

An acyclic graph is a graph that does not contain any cycles. This means you cannot start at one vertex and return to it by following a path of edges in the graph. In other words, there is no way to "loop" back to the starting point. A common example is a tree, where the lack of cycles ensures a hierarchical structure.

In the context of a transitive tournament, the graph being acyclic ensures that for any three vertices $a,b,$ and $c$, if $a$ can reach $b$, and $b$ can reach $c$, then $a$ can reach $c$ directly. This structural property allows the vertices to be ordered in a way that respects their scores. In such a setting, the absence of cycles helps maintain clarity in vertex ordering and score calculation.

Mathematical Induction

Mathematical induction is a technique used for proving statements that apply to all natural numbers or any sequentially ordered set. It's like dominoes: if you can knock over the first one, and show that if one domino falls, the next one will too, then all of them will fall in sequence.

To use induction, you start with a base case, proving the statement for the initial value. Then, you assume it's true for some value $k$, and prove it for $k+1$. This process ensures the statement holds for all applicable cases.

In solving graph-related problems, especially like the one in the exercise, mathematical induction can be used to verify properties of ordered vertices in a transitive tournament. By showing that an order exists for the first few vertices that satisfies the condition, and that this pattern continues as you add more vertices, you provide a comprehensive proof that the order can be maintained throughout the graph.