Short Score Certificates for Upset Tournaments

Jeffrey L. Poet and Bryan L. Shader Department of Mathematics University of Wyoming Laramie, Wyoming 82071, jpoet@uwyo.edu, bshader@uwyo.edu.

Submitted: January 15, 1998; Accepted: May 5, 1998.

Abstract

A score certificate for a tournament, T, is a collection of arcs of T which can be uniquely completed to a tournament with the same scorelist as T ’s, and the score certificate number of T is the least number of arcs in a score certificate of T. Upper bounds on the score certificate number of upset tournaments are derived. The upset tournaments on n vertices are in one–to–one correspondence with the ordered partitions of n−3, and are “almost” transitive tournaments. For each upset tournament on n vertices a general construction of a score certificate with at most 2n − 3 arcs is given. Also, for the upset tournament, T_{λ}, corresponding to the ordered partition λ, a score certificate with at most n + 2k + 3 arcs is constructed, where k is the number of parts of λ of size at least 2. Lower bounds on the score certificate number of T_{λ} in the case that each part is sufficiently large are derived. In particular, the score certificate number of the so-called nearly transitive tournament on n vertices is shown to be n + 3, for n ≥ 10.

1 Introduction

Some recent research has been concerned with the problem of efficiently conveying the information contained in a binary relation [AR, KTF, R]. In this paper we continue this line of research by studying the problem for a specific class of binary relations. Throughout we use the graph-theoretic notation and terminology in [CL].

Let V = {v_{1}, v_{2}, …, v_{n}}. A tournament, T, on V is a directed graph obtained by replacing each edge of the complete graph on V with a directed arc. Thus, a tournament represents a complete, asymmetric, irreflexive binary relation. Throughout we use the notation and terminology for tournaments in [M]. We denote the arc from vertex v_{i} to vertex v_{j} by the ordered pair (v_{i}, v_{j}). The score of a vertex v_{j} ∈ V is its outdegree. The score-list of T is the multiset of outdegrees of the vertices of T.

In this paper we are concerned with efficiently conveying the information contained in a tournament. More precisely, a score certificate for T is a subset, D, of arcs such that T is the unique tournament on V that contains each arc in D and whose score-list is the same as T ’s. In other words, a score certificate for T is a collection, D, of arcs with the property that T can be unambiguously determined by knowing the arcs of D and the score-list of T. The score certificate number of T is the least number of arcs in a score certificate for T, and is denoted by sc(T).

Score certificates were first studied in [FKT, KTF], where it is proven that if T is not a regular tournament on 3 or 5 vertices, then

n − 1 ≤ sc(T).  (1)

Thus, to convey the results of a tournament on n vertices (via score certificates) at least n − 1 arcs are required in all but the two exceptional cases. Note that the score certificate number of the transitive tournament on n vertices is n − 1. In [AR], it is shown that there exists an ϵ > 0 independent of n such that

sc(T) ≤ (1/2 − ϵ)n^{2}  (2)

for all tournaments T of order n. Also, in [AR] it is noted that there exist tournaments on n vertices with score certificates at least (7/24 + o(1))n^{2}. In [FKT] it is shown that

n − 1 ≤ sc(N_{n}) ≤ 3n − 9,

where N_{n} is the tournament with vertices {v_{1}, v_{2}, …, v_{n}}, and arcs (v_{1}, v_{n}) and (v_{i}, v_{j}) for all other {v_{i}, v_{j}} with i > j. The tournament N_{n} is called the nearly transitive tournament on n vertices. Other than these results, little is known about the score certificate number.

In this paper, we study the score certificate number for a special family of tournaments which generalize the nearly transitive tournament. An upset tournament on n ≥ 4 vertices is a tournament whose score-list is

{1, 1, 2, 3, …, n − 4, n − 3, n − 2, n − 2}.

Properties of upset tournaments have been studied in [BL].

In Section 2, we show that

sc(T) ≤ 2n − 3  (3)

for each upset tournament T on n vertices. The upset tournaments on n vertices possess special structural properties. In particular, they each have a unique hamiltonian cycle and they are in one–to–one correspondence with the ordered partitions of n − 3. In Section 2, we also give an upper bound on the score certificate number of an upset tournament which is in terms of the corresponding ordered partition. In most cases, this bound improves that of (3). In Section 3, we derive lower bounds for a special family of upset tournaments. As a consequence we show that the score certificate number of the nearly transitive tournament on n vertices equals n + 3, for n ≥ 10.

We conclude this introductory section with necessary preliminaries concerning upset tournaments. Clearly, a transitive tournament is not strongly connected and has no 3-cycles. It follows from results in [M] that each upset tournament on n vertices has exactly n − 2 3-cycles, and this is the least among strongly connected tournaments on n vertices. Thus, one can view the upset tournaments as a class of strongly connected tournaments that are “almost” transitive. Since equality holds in (1) for the transitive tournaments, it is natural to examine the score certificate number of upset tournaments.

It follows from the results in [BL] that the upset tournaments have a special structure, which we now describe. An ordered partition of the positive integer ℓ is a tuple of positive integers whose sum is ℓ. An ordered partition λ = (p_{1}, p_{2}, …, p_{k}) of n − 3 determines a tournament T_{λ} on n vertices as follows. Let V = {v_{1}, …, v_{n}} and let v_{i} and v_{j} be vertices with i < j. If (v_{i}, v_{j}) is (v_{1}, v_{2}), (v_{n−1}, v_{n}) or one of

(v_{2}, v_{2+p_{1}}), (v_{2+p_{1}}, v_{2+p_{1}+p_{2}}), …, (v_{2+p_{1}+···+p_{k−1}}, v_{2+p_{1}+···+p_{k−1}+p_{k}}),

then (v_{i}, v_{j}) is an arc of T_{λ}. Otherwise, (v_{j}, v_{i}) is an arc of T_{λ}. It is easy to verify that T_{λ} is an upset tournament. For example, the nearly transitive tournament on n vertices is isomorphic to T_{(n−3)}. It follows from results in [BL] that the nonisomorphic upset tournaments of order n are precisely the T_{λ} where λ runs over all ordered partitions of n − 3. Hence, there are exactly 2^{n−4} non-isomorphic upset tournaments of order n.

An arc (v_{i}, v_{j}) of a tournament T is an upset arc provided the score of v_{i} is less than or equal to that of v_{j}. The upset arcs of T_{λ} are precisely the arcs (v_{1}, v_{2}), (v_{n−1}, v_{n}), and (v_{2+p_{1}+p_{2}+···+p_{j}}, v_{2+p_{1}+p_{2}+···+p_{j}+p_{j+1}}) for j = 0, 1, 2, …, k − 1. Note that upset arcs of an upset tournament form a path, which we call its upset path.

An upset tournament T with vertices v_{1}, …, v_{n} is in standard form provided (v_{i}, v_{j}) with i < j is an arc of T if and only if (v_{i}, v_{j}) is in T ’s upset path. Thus, each T_{λ} is in standard form, and each upset tournament can be put into standard form by relabelling its vertices.

Pictorially, each upset tournament, T, in standard form can be constructed by placing the vertices v_{1}, v_{2}, …, v_{n} in order from bottom to top on a vertical line, drawing an path from v_{1} to v_{n} that goes through v_{2} and v_{n−1} and consists entirely of upward-oriented arcs, and orienting all other arcs downward. Moreover, up to isomorphism, the upset tournaments are precisely the tournaments which have this type of picture. For example, the upset tournaments with 6 vertices (in standard form) are given in Figure 1. Here, as is customary when illustrating tournaments, only the upwardoriented arcs are shown.

[figure: λ_{1} = (3); v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}; λ_{2} = (2, 1); v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}; λ_{3} = (1, 2); v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}; λ_{4} = (1, 1, 1); v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}]

2 Upper bounds

In this section we derive two linear upper bounds on the score certificate number of an arbitrary upset tournament on n vertices. The first does not depend upon the partition corresponding to the tournament, but the second does. We begin by describing certain arcs that are contained in each score certificate of an upset tournament.

Let T be an upset tournament of order n. We define a forced arc of T to be an arc (v_{i}, v_{j}) of T where the score of v_{i} is 1 more than the score of v_{j}. If (v_{i}, v_{j}) is a forced arc, then the tournament obtained from T by reversing this arc is also an upset tournament. Thus, every score certificate of T contains each forced arc of T.

It is easy to determine the forced arcs of the upset tournament T_{λ} corresponding to the ordered partition λ = (p_{1}, p_{2}, …, p_{k}) of n − 3. When n = 4, all non-upset arcs are forced arcs. Otherwise the forced arcs of T_{λ} are (v_{n}, v_{n−2}), (v_{3}, v_{1}), and each of the arcs in each of the paths

v_{2+p_{1}+···+p_{j−1}+p_{j}}, v_{2+p_{1}+···+p_{j−1}+p_{j}−1}, v_{2+p_{1}+···+p_{j−1}+p_{j}−2}, …, v_{2+p_{1}+···+p_{j−1}}

where p_{j} ≥ 2. For example, the forced arcs of the nearly transitive tournament on n ≥ 5 vertices are the arcs (v_{n}, v_{n−2}), (v_{3}, v_{1}), and the arcs in the path v_{n−1}, v_{n−2}, …, v_{2}.

We call the two vertices of an upset tournament with outdegree 1 the bottom vertices and the two vertices with indegree 1 the top vertices. The following shows that each upset tournament can be unambiguously determined given its bottom vertices and any collection of its arcs which contains each upset arc and each forced arc.

Lemma 2.1 Let T be an upset tournament in standard form with vertices v_{1}, v_{2}, …, v_{n}. Let α be a subset of arcs of T containing each forced arc and each upset arc. Let T′ be an upset tournament with vertices v_{1}, v_{2}, …, v_{n} such that v_{1} and v_{2} are the bottom vertices of T′ and each arc in α is an arc of T′. Then T′ = T.

Proof. Let D be the digraph with vertices v_{1}, v_{2}, …, v_{n} whose arcs are those in α, and let γ be the set of arcs in T that are not in T′. Note that T′ is the tournament obtained from T by reversing the arcs in γ.

We claim that γ is empty, and hence T′ = T. For suppose not. Since either (v_{j}, v_{j+1}) or (v_{j+1}, v_{j}) is in α for j = 1, …, n − 1 and α contains T ’s upset arcs, all arcs in γ have the form (v_{j}, v_{i}) where j − 1 > i. Among all the arcs in γ choose one, say (v_{j}, v_{i}), such that i is minimum. Since v_{1} and v_{2} are the bottom vertices of T and of T′, i ∉ {1, 2}. Since neither v_{n−1} nor v_{n} is a terminal vertex of an arc in γ, i ≤ n − 2. Thus, the score of v_{i} in T is i − 1.

We claim that no vertex, v_{k}, in T′ has score equal to i − 1. If k < i, then the choice of (v_{j}, v_{i}) implies that the scores of v_{k} in T and in T′ are equal, and hence less than i − 1. If k = i, then the score of v_{i} in T is less than its score in T′. Suppose that i < k < n. Then the score of v_{k} in T is k − 1. There are at most k − i − 1 arcs in γ of the form (v_{k}, v_{ℓ}) where k − 1 > ℓ ≥ i. Thus, the score of v_{k} in T′ is at least k − 1 − (k − i − 1) = i. Finally, suppose that k = n. Then the score of v_{k} in T is n − 2. The arcs (v_{n}, v_{n−1}), and (v_{n}, v_{n−2}) are not in γ. It follows that the score of v_{n} in T′ is at least n − 2 − (n − i − 2) = i. Therefore, we have reached the contradiction that no vertex in T′ has score i − 1.

We conclude that γ is empty, and hence that T is the unique upset tournament which contains α and has bottom vertices v_{1} and v_{2}.

We now use Lemma 2.1 to construct a score certificate with 2n − 3 arcs for each upset tournament on n vertices.

Theorem 2.2 Let T be an upset tournament on n vertices. Then

sc(T) ≤ 2n − 3.

Proof. Without loss of generality we may assume that T is in standard form. It is easy to verify the result for T = T_{(1)}, T = T_{(1,1)} and T = T_{(2)}. Hence, we may assume that n ≥ 6.

Let α be the set consisting of the upset arcs and the forced arcs of T. Consider the digraph, D, whose vertices are those of T and whose arcs are those in α. We first determine the outdegree of each vertex in D.

The vertices v_{1}, v_{2} and v_{n} each have outdegree 1 in D. The outdegree of v_{3} in D is 2. If v_{j} is a vertex which is not on the upset path and 4 ≤ j < n, then (v_{j}, v_{j−1}) is a forced arc of T and v_{j} has outdegree 1 in D. Otherwise, v_{j} is a vertex on the upset path with 4 ≤ j < n. Let (v_{i}, v_{j}) be the upset arc whose terminal vertex is v_{j}. If j − i = 1, then the outdegree of v_{j} in D is 1. If j − i ≠ 1, then (v_{j}, v_{j−1}) is a forced arc of T, and the outdegree of v_{j} in D is 2.

Since n ≥ 6, it can be verified that at least one of v_{4} or v_{5} has outdegree 1 in D. Let m be the smallest index such that m ∉ {1, 2, n} and v_{m} has outdegree 1 in D. Note that m ≥ 4. Let

β = {(v_{j}, v_{j−2}) : m < j < n, and v_{j} has outdegree 1 in D} ∪ {(v_{n}, v_{n−3})}.

It is easy to verify that β is a collection of arcs in T that are not in α. Let D′ be the digraph whose vertices are v_{1}, v_{2}, …, v_{n} and whose arcs are those in α∪β. By construction, each vertex in D′ other than v_{1}, v_{2}, v_{m} has outdegree 2, and each of these 3 vertices has outdegree 1. Hence α ∪ β has 2n − 3 arcs.

We show that α ∪ β is a score certificate for T. Suppose that T′ is an upset tournament with vertices v_{1}, v_{2}, …, v_{n} which has all the arcs in α ∪ β. We show that T′ is T.

The vertices of outdegree 1 in D′ are v_{1}, v_{2}, and v_{m}. Also, (v_{1}, v_{2}) is an arc of D′, the arc in D′ with initial vertex v_{2} does not terminate at v_{m}, and the arc in D′ with initial vertex at v_{m} does not terminate at v_{1} or v_{2}. If the outdegree of v_{m} in T′ is 1, then (v_{1}, v_{m}) and (v_{2}, v_{m}) are arcs of T′, and we are led to the contradiction that v_{m} is the only vertex in T′ with outdegree 1. Hence v_{1} and v_{2} are the bottom vertices of T′. Lemma 2.1 now implies that T′ = T, and thus α ∪ β is a score certificate for T.

Later we will show that the bound in Theorem 2.2 is not sharp in general. The construction of score certificates for upset tournaments given in the proof of Theorem 2.2 makes little use of the special structure of upset tournaments. We now present a construction which exploits the following property.

Proposition 2.3 Let T be an upset tournament on n vertices. Then T contains a unique hamiltonian cycle.

Proof. Without loss of generality we may assume that the vertices of T are labelled so that T is in standard form. Since T is strongly connected, it is well-known (see [M]) that T has a hamiltonian cycle.

Let H denote a hamiltonian cycle in T. The upset path must be a subpath of H, since it is the unique path from v_{1} to v_{n}. All other arcs (v_{i}, v_{j}) in T have i > j. Thus, the subpath of H from v_{n} to v_{1} must be the path which starts at v_{n}, traverses through the vertices not on the upset path in decreasing order, and ends at v_{1}. Therefore, H is unique.

Let T be a tournament with a hamiltonian cycle H. For vertices u and v, we denote the subpath of H from u to v by uHv. If (v_{i}, v_{j}) and (v_{k}, v_{ℓ}) are arcs of T not in H, we say that (v_{k}, v_{ℓ}) is nested inside (v_{i}, v_{j}) provided v_{i}Hv_{j} contains v_{k}Hv_{ℓ}. The following lemma is useful in identifying the location of the bottom vertices along the hamiltonian cycle of an upset tournament.

Lemma 2.4 Let T be an upset tournament with hamiltonian cycle H. Suppose (v_{i}, v_{j}) and (v_{k}, v_{ℓ}) are arcs of T not in H such that (v_{k}, v_{ℓ}) is nested inside (v_{i}, v_{j}). Then neither of the bottom vertices of T is on v_{i}Hv_{k}.

Proof. Neither v_{i} nor v_{k} is a bottom vertex, since each is the initial vertex of an arc in H and an arc not in H. Similarly, neither v_{j} nor v_{ℓ} is a top vertex.

Suppose to the contrary that a bottom vertex w is on v_{i}Hv_{k}. Then T ’s top vertices must occur on wHv_{ℓ}, for otherwise, (v_{k}, v_{ℓ}) is an upset arc not in H. Hence, the scores of the vertices along v_{ℓ}Hv_{i} are in decreasing order. In particular, the score of v_{j} is greater than that of v_{i}, which leads to the contradiction that (v_{i}, v_{j}) is an upset arc of T not in H.

We now note that each of the six arcs in the upset tournament T_{(1)} is a forced arc or is on the hamiltonian cycle. Hence, T_{(1)} has a score certificate consisting of the forced arcs and the arcs in its hamiltonian cycle. For upset tournaments on five or more vertices we have the following result.

Theorem 2.5 Let T be an upset tournament on n ≥ 5 vertices. There exists a score certificate for T consisting of the arcs in its unique hamiltonian cycle, its forced arcs, and one other arc.

Proof. Let H be the hamiltonian cycle of T. Without loss of generality we may assume T = T_{λ} where λ = (p_{1}, p_{2}, …, p_{k}). Let β be the set consisting of the arcs in H and the forced arcs of T.

By Lemma 2.1, it suffices to show that there exists an arc e such that each upset tournament, T′, on the same vertices as T which contains e and the arcs in β has the same bottom vertices as T.

The choice of the arc e depends upon λ. We consider four cases.

Case 1: Each p_{i} equals 1.

Since n ≥ 5, the arc (v_{n−1}, v_{1}) is in T but not in β. Take e to be this arc. Note that e is nested inside the arc (v_{3}, v_{1}) of T, and that (v_{3}, v_{1}) is not in H. Applying Lemma 2.4, we conclude that none of the vertices v_{3}, v_{4}, …, v_{n−1} is a bottom vertex of T′. Since v_{n} is the initial vertex of two arcs in β, v_{n} is not a bottom vertex of T′. Hence, T′ has the same bottom vertices as T.

Case 2: For some j ≥ 2, p_{1} = p_{2} = ⋯ = p_{j−1} = 1 and p_{j} ≥ 2.

Then (v_{j+2}, v_{j+1}) is a forced arc of T, (v_{j+2}, v_{1}) ∈ H and there exists a unique vertex v_{q} such that (v_{q}, v_{j+2}) ∈ H. Clearly, (v_{q}, v_{1}) is an arc of T not in H. Take e to be this arc. Note that e is nested inside the arc (v_{3}, v_{1}), and that (v_{3}, v_{1}) is not in H. Applying Lemma 2.4, we conclude that the bottom vertices of T′ are contained in {v_{1}, v_{2}, v_{j+2}}. Since (v_{j+2}, v_{1}) and (v_{j+2}, v_{j+1}) are in β, v_{j+2} is not a bottom vertex of T′. Hence, T′ has the same bottom vertices as T.

Case 3: k = 1.

Then p_{1} = n − 3, and since n ≥ 5 the arc (v_{n}, v_{2}) is in T and not in β. Take e to be this arc. Note that (v_{3}, v_{2}) is an arc of β not in H, and is nested inside e. By Lemma 2.4, we conclude that the bottom vertices of T′ are contained in {v_{1}, v_{2}, v_{n−1}}. Since (v_{n−1}, v_{n}) and (v_{n−1}, v_{n−2}) are arcs in β, v_{n−1} is not a bottom vertex of T′. Hence, T′ has the same bottom vertices as T.

Case 4: k ≥ 2 and p_{1} ≥ 2.

Then (v_{3}, v_{2}) is a forced arc of T which is not in H. The arc (v_{2+p_{1}+p_{2}}, v_{2}) is an arc of T not in β. Take e to be this arc. Then (v_{3}, v_{2}) is nested inside e. By Lemma 2.4, we conclude that the bottom vertices of T′ are contained in {v_{1}, v_{2}, v_{2+p_{1}}}. Since (v_{2+p_{1}}, v_{2+p_{1}+p_{2}}) and (v_{2+p_{1}}, v_{1+p_{1}}) are in β, v_{2+p_{1}} is not a bottom vertex of T′. Hence, T′ has the same bottom vertices as T.

The desired conclusion is reached in each case, and the proof is complete.

Examples of score certificates, constructed as in the proof of Theorem 2.5, for three upset tournaments on 11 vertices are given in Figure 2. Using Theorem 2.5 we can derive an upper bound on the score certificate number of T_{λ}.

[figure: λ = (8); v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}; v_{7}; v_{8}; v_{9}; v_{10}; v_{11}; λ = (1, 1, 1, 1, 1, 1, 1, 1); v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}; v_{7}; v_{8}; v_{9}; v_{10}; v_{11}; λ = (2, 2, 2, 2); v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}; v_{7}; v_{8}; v_{9}; v_{10}; v_{11}]

Figure 2

Corollary 2.6 Let λ = (p_{1}, p_{2}, …, p_{k}) be an ordered partition of n−3, where n ≥ 5. Then

sc(T_{λ}) ≤ n + 2x + y + 1

where x equals |{i : 1 ≤ i ≤ k and p_{i} ≥ 2}|, and y equals |{i : i ∈ {1, k} and p_{i} = 1}|.

Proof. By Theorem 2.5, there is a score certificate for T_{λ} consisting of the arcs in its hamiltonian cycle, its forced arcs, and one additional arc. The hamiltonian cycle has n arcs, the number of forced arcs not in the hamiltonian cycle and not incident to v_{1} or v_{n} is 2x, and the number of forced arcs incident to v_{1} or v_{n} and not in the hamiltonian cycle is y. The result now follows.

If λ = (2, 2, …, 2), then by Corollary 2.6, sc(T_{λ}) ≤ 2n − 3 + 1, and this bound is worse than that given in Theorem 2.2. However, it can be verified that the score certificate for T_{(2,2,...,,2)} constructed in the proof of Corollary 2.6 is not minimal (with respect to set inclusion). For example, one can delete the arcs (v_{6}, v_{1}) and (v_{10}, v_{11}) from the score certificate for T_{(2,2,2,2)} shown in Figure 2 and still have a score certificate.

For arbitrary λ, it is easy to see that the bound for sc(T_{λ}) in Corollary 2.6 is usually better than that in Theorem 2.2. Indeed, Corollary 2.6 implies that the score certificate number of the nearly transitive tournament on n vertices is at most n + 3.

3 Lower bounds

In this section we derive lower bounds for the score certificate number of certain upset tournaments. In particular, we show that the score certificate number of the nearly transitive tournament on n vertices equals n + 3, for n ≥ 10.

The class of upset tournaments that we study in this section is the class of T_{λ} where each part p_{i} of λ = (p_{1}, …, p_{k}) is at least k + 6. For such tournaments, Corollary 2.6 guarantees a score certificate with n + 2k + 1 arcs. We begin by showing that for such a tournament, each score certificate with less than n + 2k + 1 arcs contains each arc in its upset path, other than (v_{1}, v_{2}) and (v_{n−1}, v_{n}). For convenience, we define the truncated upset path of T_{λ} to be the path obtained from its upset path by removing the first and last arc.

Lemma 3.1 Let λ = (p_{1}, …, p_{k}) be an ordered partition of n − 3 such that each p_{i} ≥ k + 6. Then each score certificate for T_{λ} of cardinality less than n + 2k + 1 contains each arc in T_{λ}’s truncated upset path.

Proof. Suppose to the contrary that there exists a score certificate, D, for T_{λ} with less than n + 2k + 1 arcs that does not contain each arc in the truncated upset path. Note that if γ is a cycle of T_{λ}, then the tournament obtained from T_{λ} by reversing the arcs of γ has the same score-list as T_{λ}. Since D is a score certificate, it follows that D contains at least one arc in each cycle of T_{λ}.

For m = 1, 2, …, k, let x_{m} be the number of non-forced arcs in D having both initial and terminal vertices in

{v_{r}, v_{r+1}, …, v_{t}},

where r = 2+p_{1} +p_{2} +⋯+p_{m−1} and t = 2+p_{1} +p_{2} +⋯+p_{m}. First suppose that the upset arc (v_{r}, v_{t}) is not in D. For each s with r + 1 < s < t − 1,

v_{t} → v_{s} → v_{r} → v_{t}

is a 3-cycle in T_{λ}, and hence D contains at least one of the non-forced arcs (v_{t}, v_{s}) and (v_{s}, v_{r}). Therefore, x_{m} ≥ p_{m} − 3 ≥ k + 3. If (v_{r}, v_{t}) is in D, then certainly x_{m} ≥ 1.

It follows that the number of non-forced arcs in D is at least

∑_{m=1}^{k} x_{m} ≥ (k − 1) + k + 3 = 2k + 2.

Since D contains the n − 1 forced arcs, we are led to the contradiction that D has at least n + 2k + 1 arcs.

Let λ = (p_{1}, …, p_{k}) be an ordered partition of n − 3 with each p_{i} ≥ k + 6. An immediate consequence of Lemma 3.1 is that

sc(T_{λ}) ≥ n + k − 1.  (4)

In the remainder of this paper we show that this bound can be improved to

sc(T_{λ}) ≥ n + k + 2.

The technique employed is as follows. Let δ be the set consisting of the arcs in the truncated upset path of T_{λ} and the forced arcs of T_{λ}. We exhibit a family T_{1}, …, T_{5} of upset tournaments on the vertices v_{1}, …, v_{n} with the following properties:

(a) T_{i} ≠ T_{λ} for i = 1, 2, 3, 4, 5, and (b) for each pair e and f of arcs which are in T_{λ} and not in δ, there exists

a j such that both e and f are arcs of T_{j}.

We claim that this implies that sc(T_{λ}) ≥ n + k + 2. To see this, let D be a score certificate for T_{λ}. If D does not contain the truncated upset path of T_{λ}, then Lemma 3.1 implies that D has at least n + 2k + 1 arcs. Otherwise, D contains each arc in δ. The existence of such T_{1}, …, T_{5} implies that no set of arcs consisting of δ and at most two other arcs is a score certificate for T_{λ}. Thus, D has at least 3 arcs not in δ. Therefore, D has at least n + k + 2 arcs.

In order to easily describe the tournaments T_{1}, …, T_{5}, we introduce some notation. Throughout the remainder of the paper we identify the vertex v_{i} with the index i. Let T be an upset tournament with vertices 1, 2,…, n not necessarily in standard form. Let π be the permutation so that when T is put in standard form, the vertices from bottom to top are π(1), π(2), …, π(n). If we start with the n-tuple (π(1), π(2), …, π(n)) and boldface each entry in the n-tuple corresponding to a vertex on T ’s upset path, we obtain a n-tuple which completely describes T. For example, the nearly transitive tournament on n vertices in standard form is denoted by the n-tuple

(1, 2, 3, 4, …, n − 3, n − 2, n − 1, n),

and the 7-tuple (3, 4, 1, 7, 2, 5, 6) determines the upset tournament illustrated in Figure 3.

[figure: 3; 4; 1; 7; 2; 5; 6]

If T is the tournament described by a given n-tuple, then (i, j) is an arc of T if and only if

(1) both i and j are boldfaced and j is the first boldfaced entry to the right of i,

(2) both i and j are boldfaced, j is to the left of i and there is at least one boldfaced entry between j and i, or

(3) i or j is not boldfaced and j occurs to the left of i.

Theorem 3.2 Let λ = (p_{1}, …, p_{k}) be an ordered partition of n−3 such that each p_{i} ≥ k + 6. Then sc(T_{λ}) ≥ n + k + 2.

Proof. It suffices to exhibit tournaments T_{1}, …, T_{5} satisfying (a) and (b) above.

Without loss of generality we may assume that T_{λ} has upset path 1, 2, i_{1}, i_{2}, …, i_{k−1}, n − 1, n and hence is determined by

(1, 2, 3, …, i_{1} − 1,
i_{1}, i_{1} + 1, …, i_{2} − 1,
i_{2}, i_{2} + 1, …, i_{3} − 1,
⋮
i_{k−1}, i_{k−1} + 1, …, n − 2,
n − 1, n).

Let T_{1} be the upset tournament determined by

(1, 4, 3, 2, 5, …, i_{1} − 1,
i_{1}, i_{1} + 1, …, i_{2} − 1,
i_{2}, i_{2} + 1, …, i_{3} − 1,
⋮
i_{k−1}, i_{k−1} + 1, …, n − 2,
n − 1, n).

It is easy to verify that T_{1} contains T_{λ}’s truncated upset path and forced arcs. Also, the set of arcs in T_{λ} that are not in T_{1} is

X = {(4, 2), (4, 1)(1, 2)}.

Analogously, we define T_{2} to be the upset tournament determined by

(1, 2,
3, …, i_{1} − 1, i_{1},
i_{1} + 1, …, i_{2} − 1, i_{2}
⋮
i_{k−2} + 1, …, i_{k−1} − 1, i_{k−1},
i_{k−1} + 1, …, n − 4, n − 1, n − 2, n − 3, n).

and observe that the set of arcs in T_{λ} that are not in T_{2} is

Y = {(n, n − 3), (n − 1, n), (n − 1, n − 3)}.

Note that X and Y are disjoint. Let e and f be arcs of T_{λ} that are not forced arcs and not in its truncated upset path. If it is not the case that X contains one of e or f and Y contains the other, then the arcs e and f are simultaneously in at least one of T_{1} and T_{2}. Thus, we assume without loss of generality that e ∈ X and f ∈ Y.

Let T_{3} be the upset tournament determined by

(i_{1} − 1, i_{1} − 2, 1, i_{1} − 3, i_{1} − 4, …, 3, 2,
i_{1}, i_{1} + 1, i_{1} + 2, …, i_{2} − 1,
i_{2}, i_{2} + 1, …, i_{3} − 1
⋮
i_{k−1}, i_{k−1} + 1, …, n − 2,
n − 1, n),

where we identify i_{1} and n − 1 in the case k = 1. It can be verified that T_{3} contains T_{λ}’s truncated upset path and forced arcs. Also T_{3} contains the arcs in {(4, 1)} ∪ Y, and hence if e = (4, 1) then T_{3} contains both e and f.

Analogously, we define T_{4} to be the upset tournament determined by

(1, 2 3, 4, …, i_{1} − 1, i_{1} i_{1} + 1, i_{1} + 2, …, i_{2} − 1, i_{2} ⋮ i_{k−2} + 1, i_{k−2} + 2, …, i_{k−1} − 1, i_{k−1} n − 1, n − 2, …, i_{k−1} + 3, n, i_{k−1} + 2, i_{k−1} + 1) ,

where we identify vertices 2 and i_{k−1} in the case that k = 1, and conclude that if f = (n, n − 3) then T_{4} contains both e and f.

Finally, let T_{5} be the upset tournament determined by

(n, n − 2, n − 3, n − 1, n − 4, n − 5, …, 5, 2, 4, 3, 1),

where each of the entries between n − 5 and 5 is boldfaced. It can be verified that T_{1} contains T_{λ}’s truncated upset path and forced arcs. Also, T_{5} contains the arcs in {(1, 2), (4, 2), (n − 1, n), (n, n − 2)}. Hence, if e ≠ (4, 1) and f ≠ (n, n − 3), then T_{5} contains both e and f.

Therefore, the upset tournaments T_{1}, …, T_{5} satisfy property (b), and it is clear that they also satisfy property (a).

In Figure 4, we illustrate the tournaments T_{1}, …, T_{5} which are constructed in the proof of Theorem 3.2 for the upset tournament T_{(8,8)}.

The following is an immediate consequence of Corollary 2.6 and Theorem 3.2.

Corollary 3.3 Let n ≥ 10, and let N_{n} be the nearly transitive tournament on n vertices. Then

sc(N_{n}) = n + 3.

The following chart summarizes the results for tournaments on n vertices corresponding to the partition λ = (p_{1}, …, p_{k}), where each p_{i} ≥ k + 6, and is a consequence of Corollary 2.6 and Theorem 3.2.

number of minimum number minimum size lower bound upper bound
parts of λ  of vertices  of each part for sc(T_{λ})  for sc(T_{λ})
1  10  7  n + 3  n + 3
2  19  8  n + 4  n + 5
3  30  9  n + 5  n + 7
4  43  10  n + 6  n + 9
k  k^{2} + 6k + 3  k + 6  n + k + 2  n + 2k + 1

[figure: 1; 4; 3; 2; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; T_{1}; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 18; 17; 16; 19; T_{2}; 9; 8; 1; 7; 6; 5; 4; 3; 2; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; T_{3}; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 18; 17; 16; 15; 14; 13; 19; 12; 11; T_{4}; 19; 17; 16; 18; 15; 14; 13; 12; 11; 10; 9; 8; 7; 6; 5; 2; 4; 3; 1; T_{5}]

Figure 4

References

[AR] N. Alon and M. Ruszinkó, Short certificates for tournaments, The Electronic Journal of Combinatorics, (1997), 4:# R12.

[BL] R. Brualdi and Q. Li, Upsets in round robin tournaments, J. Combinatorial Theory B, (1983), 35:62-77.

[CL] G. Chartrand and L. Lesniak, Graphs and Digraphs, Third edition, Chapman and Hall, London, 1996.

[FKT] P. Fishburn, J. H. Kim, and P. Tetali, Tournament Certificates, Technical Memorandum, AT& T Bell Laboratories, (1994), DI-MACS Technical Report No. 94-05.

[KTF] J. H. Kim, P. Tetali, and P. Fishburn, Score certificates for tournaments, J. Graph Theory, (1997), 24:117-138.

[M] J. W. Moon, Topics on Tournaments, Holt, Rinehart, and Winston, Inc., New York, 1968.

[RB] K. B. Reid and L. W. Beineke, Selected Topics in Graph Theory (L. W. Beineke and R. J. Wilson, Eds.), Chap. 7, 385-415, Academic Press, New York, 1978.

[R] A. Rubinstein, Why are certain properties of binary relations relatively more common in natural language?, Econometrica, (1996), 64:343-355.