An Extended Theorem Based on Landau’s Theorem for Facilitating Tournament Score Sequence Reconstruction

Bowen Liu

Faculty of Computational Mathematics and Cybernetics, Shenzhen MSU-BIT University, Shenzhen, China.

DOI: 10.4236/jamp.2025.134087                

Abstract

The score set of a tournament refers to the collection of its distinct out-degrees. While it is known that for any set of nonnegative integers D , there exists a tournament T with D as its degree set, an efficient algorithm for reconstructing the full score sequence is still lacking. To bridge this gap, this paper focuses on extending the existing Landau’s theorem to establish a new, easily verifiable theorem. By introducing additional constraints beyond Landau’s classical criteria, we aim to offer deeper insights that could facilitate the development of efficient reconstruction algorithms. These findings have practical applications in sports analytics, ranking prediction, and machine learning, particularly in learning-to-rank models and data imputation. In these domains, the ability to reconstruct partial rankings or sequences plays a crucial role in recommendation systems and anomaly detection.

Keywords

Tournament, Score Sequence, Score Set, Algorithm Design, Reid Conjec-ture

1. Introduction

Reconstructing score sequences from the score sets of tournament graphs is a fundamental problem in tournament theory. Reid [1] proposed the conjecture that for any set of nonnegative integers $D$ , there exists a tournament $T$ whose degree set is $D$ . Yao later provided an arithmetical proof of this conjecture [2]. Despite these theoretical advancements, an efficient algorithm for reconstructing score sequences remains unknown [3].

To bridge this gap, this paper focuses on extending Landau’s theorem by establishing a new, easily verifiable theorem for reconstructing score sequences from tournament score sets. By refining existing constraints, we aim to offer deeper insights that could facilitate the development of efficient reconstruction algorithms. Establishing such conditions is a crucial step toward better understanding the structure of tournament graphs and designing more effective methods for score sequence reconstruction.

Beyond its theoretical significance, this problem has practical applications across various domains. In sports tournaments, reconstructing score sequences can aid in ranking assessments, schedule fairness evaluations, and team strength analysis [4]. In machine learning, it relates to ranking problems and data imputation, where recovering missing information is essential for recommendation systems and anomaly detection [5].

The rest of the paper is organized as follows. Section 2 presents the necessary preliminaries. Section 3 introduces the extended theorem for score sequence reconstruction. Section 4 discusses the benefits of the theorem. Finally, conclusions and future research directions are presented in Section 5.

2. Preliminaries

To introduce this paper, we first review the definition of tournament graphs and provide examples to illustrate their structure. A tournament graph is a directed graph obtained by assigning a direction to each edge of a complete graph. In other words, for any pair of distinct vertices, there exists exactly one directed edge between them. Tournament graphs naturally arise in competitive settings, where each vertex represents a player or team, and a directed edge from vertex $u$ to vertex $v$ indicates that $u$ has defeated $v$ .

Below, we provide an example of a tournament (Figure 1). The score sequence of a tournament graph is the list of out-degrees of its vertices, representing the number of wins for each player.

Figure 1. Example of a tournament with its corresponding adjacency matrix.

With this foundation, we proceed to review Landau’s theorem and its reformulation, as the subsequent results in this paper build directly upon this theory and its reformulation.

Theorem (Landau [6])

A non-decreasing sequence of non-negative integers $S=s_1,s_2,\dots ,s_n$ is a score sequence of an n-tournament if and only if

${\displaystyle {\sum }_{i=1}^k{s}_i}\ge k\left(k-1\right)/2,\forall k\in N,1\le k\le n$ ,

with equality when $k=n$ .

To illustrate this, consider Figure 1, where the non-decreasing sequence of non-negative integers $S$ is given by $S=\left\{0,1,3,3,3,5\right\}$ . This sequence satisfies Landau’s theorem. For example, when $k=3$ , the left-hand side of the inequality, denoted as ${\displaystyle {\sum }_{i=1}^k{s}_i}$ , equals 4, while the right-hand side, denoted as $k\left(k-1\right)/2$ , equals 3, ensuring that $4\ge 3$ .

Now, we consider only the case where $n\ge 2$ . Let the degree set be $D=\left\{{\alpha }_i|{\alpha }_{i\backslash inN},{\alpha }_i\ge 0,i=\overline{1,n}\right\}$ , where the elements ${\alpha }_i$ are arranged in increasing order.

Define the exponent set of the score as $E=\left\{x_i|x_i\in N,x_i\ge 1,i=\overline{1,n}\right\}$ , where each $x_i$ represents the number of times the score ${\alpha }_i$ appears in a given score sequence.

For example, in Figure 1, the degree set is $D=\left\{0,1,3,5\right\}$ , and the corresponding exponent set is $E=\left\{1,1,3,1\right\}$ , indicating how often each score occurs.

Note that in this paper, the terms “degree set” and “score set” refer to the same concept.

Now let’s look at another reformulation of Landau’s theorem that also appears in [7].

Theorem 2.2.

A score sequence, characterized by a degree set $D$ and an exponent set $E$ , represents the score sequence of a tournament if and only if ${\displaystyle {\sum }_{i=1}^k{\alpha }_i\cdot x_i}\ge {\displaystyle {\sum }_{i=1}^k{x}_i}\left({\displaystyle {\sum }_{i=1}^k{x}_i}-1\right)/2$ , $\forall k\in N,1\le k\le n$ , with equality holding when $k=n$ .

Verifying Theorem 2.2 for Figure 1, we check that the inequality holds for different values of $k$ . For instance, when $k=3$ , we compute the left-hand side:

${\displaystyle {\sum }_{i=1}^3{\alpha }_i\cdot x_i}=0\cdot 1+1\cdot 1+3\cdot 3=0+1+9=10.$

On the right-hand side, we calculate:

${\displaystyle {\sum }_{i=1}^3{x}_i}\left({\displaystyle {\sum }_{i=1}^3{x}_i}-1\right)/2=\left(1+1+3\right)\cdot \left(\left(1+1+3\right)-1\right)/2=5\cdot 4/2=10.$

Since $10\ge 15$ , the condition of Theorem 2.2 is satisfied for $k=3$ . A similar check for all $k$ confirms that the given score sequence satisfies the theorem.

3. The Extended Theorem

In this section, we present the extended theorem, building upon the existing Landau’s theorem, to address the problem of reconstructing score sequences from score sets of tournament graphs. The extended theorem refines the conditions laid out in Landau’s original work, providing a more efficient approach for facilitating the reconstruction of correct score sequences. This extension is a crucial step toward developing effective algorithms for score sequence reconstruction.

Additionally, we introduce the following sums, which play an important role in formulating and proving the extended theorem. These sums capture the relationships between the out-degrees of vertices and help derive the necessary conditions for reconstructing score sequences. By analyzing the degree sets through these sums, we gain a clearer understanding of the combinatorial properties involved.

$p_i={\displaystyle {\sum }_{k=1}^i{x}_k},\text{where}{p}_0=0;q_i={\displaystyle {\sum }_{k=1}^i{\alpha }_k\cdot x_k},\text{where}{q}_0=0.$

Theorem 3.1.

Assume there exists a degree set $D$ and an exponent set $E$ that satisfy the following condition:

${\displaystyle {\sum }_{i=1}^k{\alpha }_i\cdot x_i}\ge {\displaystyle {\sum }_{i=1}^k{x}_i}\left({\displaystyle {\sum }_{i=1}^k{x}_i}-1\right)/2,\forall k\in N,1\le k\le n$ ,

with equality when $k=n$ , if and only if

$\forall k\in N,1\le k\le n,$

$1\le x_k\le \left(2\left({\alpha }_k-p_{k-1}\right)+1+\sqrt{{\left(2\left({\alpha }_k-p_{k-1}\right)+1\right)}^2+8\left(q_{k-1}-p_{k-1}\left(p_{k-1}-1\right)/2\right)}\right)/2$ ,

and $q_{k-1}-p_{k-1}\left(p_{k-1}-1\right)/2\ge 0$ , with equality holding on the right-hand side when $k=n$ .

Proof

$\forall k\in N,1\le k\le n,$

$\begin{array}{l}{\displaystyle {\sum }_{i=1}^k{\alpha }_i\cdot x_i}\ge {\displaystyle {\sum }_{i=1}^k{x}_i}\left({\displaystyle {\sum }_{i=1}^k{x}_i}-1\right)/2\\ \equiv 2\left({\displaystyle {\sum }_{i=1}^k{\alpha }_i\cdot x_i}\right)\ge {\left({\displaystyle {\sum }_{i=1}^k{x}_i}\right)}^2-{\displaystyle {\sum }_{i=1}^k{x}_i}\\ \equiv 2\cdot q_{k-1}+2{\alpha }_k\cdot x_k\ge {\left(p_{k-1}+x_k\right)}^2-p_{k-1}-x_k\\ \equiv 2\cdot q_{k-1}+2{\alpha }_k\cdot x_k\ge p_{k-1}{}^2+x_k{}^2+2x_k{p}_{k-1}-p_{k-1}-x_k\\ \equiv 0\ge x_k{}^2-\left(2\left({\alpha }_k-p_{k-1}\right)+1\right)x_k-2\left(q_{k-1}-p_{k-1}\left(p_{k-1}-1\right)/2\right),\end{array}$

Define $\Delta$ as follows:

$\Delta ={\left(2\left({\alpha }_k-p_{k-1}\right)+1\right)}^2+8\left(q_{k-1}-p_{k-1}\left(p_{k-1}-1\right)/2\right)$

From the first part of Theorem 3.1, ${\displaystyle {\sum }_{i=1}^k{\alpha }_i\cdot x_i}\ge {\displaystyle {\sum }_{i=1}^k{x}_i}\left({\displaystyle {\sum }_{i=1}^k{x}_i}-1\right)/2$ , $\forall k\in N$ , $1\le k\le n$ , it follows that for $k\ge 2$ , $q_{k-1}-p_{k-1}\left(p_{k-1}-1\right)/2\ge 0$ , thus $\Delta \ge 0$ . For $k=1$ , it follows from the hypothesis that both $p_0$ and $q_0$ are zero. Moreover, $q_{k-1}-p_{k-1}\left(p_{k-1}-1\right)/2=0$ , which implies $\Delta \ge 0$ .

From the second part of Theorem 3.1, we also have $\Delta \ge 0$ . Therefore:

$\left(\left(2\left({\alpha }_k-p_{k-1}\right)+1\right)-\sqrt{\Delta }\right)/2\le x_k\le \left(\left(2\left({\alpha }_k-p_{k-1}\right)+1\right)+\sqrt{\Delta }\right)/2$

As previously established, we always have $q_{k-1}-p_{k-1}\left(p_{k-1}-1\right)/2\ge 0$ . Therefore, $\left(\left(2\left({\alpha }_k-p_{k-1}\right)+1\right)-\sqrt{\Delta }\right)/2<0$ .

From the left-hand side of Theorem 3.1, it follows that $\exists x_k\ge 1,x_k\in N$ satisfying $\left(\left(2\left({\alpha }_k-p_{k-1}\right)+1\right)-\sqrt{\Delta }\right)/2\le x_k\le \left(\left(2\left({\alpha }_k-p_{k-1}\right)+1\right)+\sqrt{\Delta }\right)/2$ . Thus, we obtain the right-hand side of Theorem 3.1. From the right-hand side of Theorem 3.1 it follows that there exists $x_k$ satisfying $1\le x_k\le \left(\left(2\left({\alpha }_k-p_{k-1}\right)+1\right)+\sqrt{\Delta }\right)/2$ , thus $x_k\in N$ satisfies $\left(\left(2\left({\alpha }_k-p_{k-1}\right)+1\right)-\sqrt{\Delta }\right)/2\le x_k\le \left(\left(2\left({\alpha }_k-p_{k-1}\right)+1\right)+\sqrt{\Delta }\right)/2$ and $x_k\ge 1$ . Thus, we obtain the left-hand side of Theorem 3.1.

4. Benefits of the Extended Theorem

The newly derived theorem provides a straightforward method for determining the range of $x_k$ using the previously obtained values $p_{k-1}$ and $q_{k-1}$ , as seen in the formula in Theorem 3.1. This formula offers a simple approach to narrowing down the possible values for $x_k$ by analyzing $p_{k-1}$ and $q_{k-1}$ . Additionally, by setting $x_i=1$ for all $i\ge k+1$ and using the previously obtained values $p_{k-1}$ and $q_{k-1}$ , we can obtain $n-k$ inequalities that are solely dependent on #Math_89# :

$1\le \left(\left(2\left({\alpha }_i-P_i\right)+1\right)+\sqrt{{\left(2\left({\alpha }_i-P_i\right)+1\right)}^2+8\left(Q_i-P_i\left(P_i-1\right)/2\right)}\right)/2,$

here $P_i=p_{k-1}+x_k+i-\left(k+1\right)$ , $Q_i=q_{k-1}+x_k\cdot {\alpha }_k+{\displaystyle {\sum }_{j=k+1}^{i-1}{\alpha }_j}$ .

This enables us to refine the bounds for $x_k$ by solving a set of one-variable inequalities. It is important to note that not all values of $x_k$ within the derived range by Theorem 3.1 can potentially be part of a correct score sequence. If $x_k$ does not satisfy the newly identified bounds, even if it satisfies the formula in Theorem 3.1, the subsequent values $x_i$ for $i\ge k+1$ will inevitably include an $x_i$ where, for any choice of remaining $x_j$ , $j\ge k+1,j\ne i$ , there will be no value of $x_i$ that can satisfy Theorem 3.1, meaning that it will not be possible to find a correct score sequence. Thus, by using this method, we can narrow down the possibilities for $x_k$ and identify values that are more likely to contribute to a correct score sequence.

Figure 2. Example of a tournament.

Figure 3. The adjacency matrix of Figure 2.

To illustrate this phenomenon, consider the competition graph shown in Figure 2, with degree set $D=\left\{2,4,7,14\right\}$ . Its adjacency matrix is displayed in Figure 3. From this set $D$ , we aim to reconstruct an exponent set $E$ that satisfies Theorem 2.2. When evaluating $x_1$ , the formula derived earlier gives the range $1\le x_1\le 5$ . However, if $x_1=5$ , the formula implies $x_2\le 0$ , which clearly cannot be a valid range for $x_2$ , as $x_2$ must be greater than 1. Furthermore, as shown in Table 1, there is no valid score sequence where $x_1\ge 4$ . (Table 1 lists all possible exponent sets $E$ for degree set $D=\left\{2,4,7,14\right\}$ .)

Table 1. All possible exponent sets $E$ for degree set $D=\left\{2,4,7,14\right\}$ .

5. Conclusion

This paper proposes a new theorem for the problem of reconstructing score sequences from score sets of tournament graphs. Moving forward, I will continue exploring this theorem to develop an efficient algorithm for reconstructing score sequences.

Acknowledgements

I would like to thank Professor Boris Melnikov for bringing to my attention the problem of reconstructing the score sequence from a tournament’s score set.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Reid, K.B. (1978) Score Sets for Tournaments. Congressus Numerantium, 21, 607-618.
[2]	Yao, T.X. (1989) On Reid Conjecture of Score Sets for Tournaments. Chinese Science Bulletin, 34, 804-808.
[3]	Iványi, A. (2014) Reconstruction of Score Sets. Acta Universitatis Sapientiae, Informatica, 6, 210-229.[CrossRef]
[4]	Suksompong, W. (2021) Tournaments in Computational Social Choice: Recent Developments. Proceedings of the 30th International Joint Conference on Artificial Intelligence, Montreal-Themed Virtual Reality, 19 - 26 August 2021, 4611-4618.[CrossRef]
[5]	Miao, J., Tao, H., Xie, H., Sun, J. and Cao, J. (2024) Reconstruction-Based Anomaly Detection for Multivariate Time Series Using Contrastive Generative Adversarial Networks. Information Processing & Management, 61, Article ID: 103569.[CrossRef]
[6]	Landau, H.G. (1953) On Dominance Relations and the Structure of Animal Societies: III the Condition for a Score Structure. The Bulletin of Mathematical Biophysics, 15, 143-148.[CrossRef]
[7]	Iványi, A., Lucz, L., Matuszka, T. and Gombos, G. (2013) Score Sets in Multi-Tournaments I: Mathematical Results. Annales Universitatis Scientiarum Budapestinensis, Section Computationes, 40, 307-319.