25.6. 25.6 Imbalances in -tournaments

A -tournament is a digraph in which multiarcs multiarcs are permitted, and which has no loops [ 97 ].

At first we consider the special case , then the -tournaments.

25.6.1. 25.6.1 Imbalances in -tournaments

A -tournament is a directed graph (shortly digraph) without loops and without multiple arcs, is also called simple digraph [ 97 ]. The imbalance of a vertex in a digraph is (or simply ) , where and are respectively the outdegree and indegree of . The imbalance sequence of a simple digraph is formed by listing the vertex imbalances in nonincreasing order. A sequence of integers with is feasible if the sum of its elements is zero, and satisfies , for .

The following result provides a necessary and sufficient condition for a sequence of integers to be the imbalance sequence of a simple digraph.

Theorem 25.14 (Mubayi, Will, West [ 187 ]) A sequence is realizable as an imbalance sequence of a -tournament if and only if it is feasible.

The above result is equivalent to saying that a sequence of integers with is an imbalance sequence of a -tournament if and only if

for with equality when .

On arranging the imbalance sequence in nondecreasing order, we have the following observation.

Corollary 25.15 A sequence of integers with is an imbalance sequence of a -tournament if and only if

for , with equality when .

Various results for imbalances in different tournaments can be found in [ 127 ], [ 128 ], [ 223 ], [ 224 ].

25.6.2. 25.6.2 Imbalances in -tournaments

A -tournament is a digraph in which multiarcs are permitted, and which has no loops [ 97 ]. If then a -tournament is an orientation of a simple multigraph and contains at most edges between the elements of any pair of distinct vertices. Let be a -tournament with vertex set , and let and respectively denote the outdegree and indegree of vertex . Define (or simply ) as imbalance of . Clearly, . The imbalance sequence of is formed by listing the vertex imbalances in nondecreasing order.

We remark that -digraphs are special cases of -digraphs containing at least and at most edges between the elements of any pair of vertices. Degree sequences of -tournaments have been studied by Mubayi, West, Will [ 187 ] and Pirzada, Naikoo and Shah [ 223 ].

Let and be distinct vertices in . If there are arcs directed from to and arcs directed from to , then we denote this by , where .

A double in is an induced directed subgraph with two vertices , and having the form , where , and , and is the number of arcs directed from to , and is the number of arcs directed from to . A triple in is an induced subgraph with tree vertices , , and having the form , where , and , , , and the meaning of , , , , , is similar to the meaning in the definition of doubles. An oriented triple in is an induced subdigraph with three vertices. An oriented triple is said to be transitive if it is of the form , or , or , or , or , otherwise it is intransitive. An -graph is said to be transitive if all its oriented triples are transitive. In particular, a triple in an -graph is transitive if every oriented triple of is transitive.

The following observation can be easily established and is analogue to Theorem 2.2 of Avery [ 12 ].

Lemma 25.16 (Avery 1991 [ 12 ]) If and are two -tournaments with same imbalance sequence, then can be transformed to by successively transforming (i) appropriate oriented triples in one of the following ways, either (a) by changing the intransitive oriented triple to a transitive oriented triple , which has the same imbalance sequence or vice versa, or (b) by changing the intransitive oriented triple to a transitive oriented triple , which has the same imbalance sequence or vice versa; or (ii) by changing a double to a double , which has the same imbalance sequence or vice versa.

The above observations lead to the following result.

Theorem 25.17 (Pirzada, Naikoo, Samee, Iványi 2010 [ 224 ]) Among all -tournaments with given imbalance sequence, those with the fewest arcs are transitive.

Proof. Let be an imbalance sequence and let be a realization of that is not transitive. Then contains an intransitive oriented triple. If it is of the form , it can be transformed by operation i(a) of Lemma 25.16 to a transitive oriented triple with the same imbalance sequence and three arcs fewer. If contains an intransitive oriented triple of the form , it can be transformed by operation i(b) of Lemma 25.16 to a transitive oriented triple same imbalance sequence but one arc fewer. In case contains both types of intransitive oriented triples, they can be transformed to transitive ones with certainly lesser arcs. If in there is a double , by operation (ii) of Lemma 25.16, it can be transformed to , with same imbalance sequence but two arcs fewer.

The next result gives necessary and sufficient conditions for a sequence of integers to be the imbalance sequence of some -tournament.

Theorem 25.18 (Pirzada, Naiko, Samee, Iványi [ 224 ]) A nondecreasing sequence of integers is an imbalance sequence of a -tournament if and only if

with equality when .

Proof. Necessity. A subtournament induced by vertices has a sum of imbalances at least .

Sufficiency. Assume that is a nonincreasing sequence of integers satisfying conditions (25.27) but is not the imbalance sequence of any -tournament. Let this sequence be chosen in such a way that is the smallest possible and is the least with that choice of . We consider the following two cases.

Case (i). Suppose equality in (25.27) holds for some , so that

for .

By minimality of , is the imbalance sequence of some -tournament with vertex set, say . Let . Consider

for , with equality when . Therefore, by the minimality for , the sequence forms the imbalance sequence of some -tournament with vertex set, say . Construct a new -tournament with vertex set as follows.

Let with, and the arc set containing those arcs which are in and . Then we obtain the -tournament with the imbalance sequence , which is a contradiction.

Case (ii). Suppose that the strict inequality holds in (25.27) for some , so that

for . Let , so that satisfies the conditions (25.27). Thus by the minimality of , the sequences is the imbalances sequence of some -tournament with vertex set, say . Let and . Since , there exists a vertex such that , or , or , or , and if these are changed to , or , or , or respectively, the result is a -tournament with imbalances sequence , which is again a contradiction. This proves the result.

Arranging the imbalance sequence in nonincreasing order, we have the following observation.

Corollary 25.19 (Pirzada, Naiko, Samee, Iványi [ 224 ]) A nondecreasing sequence of integers is an imbalance sequence of a -tournament if and only if

for , with equality when .

The converse of a -tournament is a -graph , obtained by reversing orientations of all arcs of . If with is the imbalance sequence of a -tournament , then is the imbalance sequence of .

The next result gives lower and upper bounds for the imbalance of a vertex in a -tournament .

Theorem 25.20 If is an imbalance sequence of a -tournament , then for each

Proof. Assume to the contrary that , so that for ,

That is,

Adding these inequalities, we get

which contradicts Theorem 25.18.

Therefore, .

The second inequality is dual to the first. In the converse -tournament with imbalance sequence we have, by the first inequality

Since , therefore

Hence, .

Now we obtain the following inequalities for imbalances in -tournament.

Theorem 25.21 (Pirzada, Naikoo, Samee, Iványi 2010 [ 224 ]) If is an imbalance sequence of a -tournament with , then

for , with equality when .

Proof. By Theorem 25.18, we have for , with equality when

implying

from where

and so we get the required

or