EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 1, No. 3, 2008, (10-20) ISSN 1307-5543 – www.ejpam.com Score sequences in oriented k-hypergraphs S. Pirzada1,∗, Zhou Guofei2,† 1 Department of Mathematics, University of Kashmir, Srinagar, 190006, INDIA 2 Department of Mathematics, Nanjing University, Nanjing, 210093, P.R. CHINA Abstract. Given two non-negative integers n and k with n ≥ k > 1, an oriented k-hypergraph on n vertices is a pair (V, A), where V is a set of vertices with |V | = n and A is a set of k-tuples of vertices, called arcs, such that for any k-subset S of V , A contains at most one of the k! k-tuples whose entries belong to S. In this paper, we define the score of a vertex in an oriented k-hypergraph and then obtain a necessary and sufficient condition for the sequence of non-negative integers [s1, s2, · · · , sn] to be a score sequence of some oriented k-hypergraph. AMS subject classifications: 05C20 Key words: Hypergraphs, Oriented k-hypergraphs, Score Sequences 1. Introduction An edge of a graph is a pair of vertices and an edge of a hypergraph is a subset of the vertex set, consisting of at least two vertices. An edge in a hypergraph consisting of k vertices is called a k-edge, and a hypergraph all of whose edges are k-edges is called a k-hypergraph. A k-hypertournament is a complete k-hypergraph with each k-edge endowed with an orientation, that is, a linear arrangement of the vertices contained in the hyperedge. In other words, given two non-negative integers n and k with n ≥ k > 1, a k-hypertournament on n vertices is a pair (V, A), where V is a set of vertices with |V | = n and A is a set of k-tuples of vertices, called arcs, such that for any k-subset S of V , A contains exactly one of the k! k-tuples whose entries belong to S. If n< k, A= φ and this type of hypertournament is called a null-hypertournament. Clearly, a 2-hypertournament is simply a tournament. Instead of scores of vertices in a tournament, Zhou et al. [8] considered scores and losing scores of vertices in a k-hypertournament, and derived a result analogous to Landau’s theorem [5]. The score s(vi) or si of a vertex vi is the number of arcs containing vi and in which vi is not the last element, and the losing score r(vi) or ri of a vertex vi is the number of arcs containing vi and in which vi is the last element. The score sequence (losing score sequence) is formed by listing the scores (losing scores) in non-decreasing order. ∗Corresponding author. Email addresses: sdpirzada@yahoo.co.in (S. Pirzada) gfzhou@nju.edu.cn (Z. Guofei) †The work of the second author was supported in part by the National Natural Science Foundation of China and The Dr. Delia Koo Grant in Michigan State University http://www.ejpam.com 10 c© 2008 EJPAM All rights reserved. S. Pirzada, Z. Guofei / Eur. J. Pure Appl. Math, 1 (2008), (10-20) 11 The following characterizations of score sequences and losing score sequences in k-hypertournaments are due to Zhou et al. [8]. Theorem 1.1. Given two non-negative integers n and k with n≥ k > 1, a non-decreasing sequence R = [r1, r2, · · · , rn] of non-negative integers is a losing score sequence of some k- hypertournament if and only if for each j, j ∑ i=1 ri ≥ � j k � , with equality when j = n. Theorem 1.2. Given non-negative integers n and k with n ≥ k > 1, a non-decreasing se- quence S = [s1, s2, · · · , sn] of non-negative integers is a score sequence of some k-hypertournament if and only if for each j, j ∑ i=1 si ≥ j � n− 1 k− 1 � + � n− j k � − � n k � , with equality when j = n. Bang and Sharp [2] proved Landau’s theorem using Hall’s theorem on a system of distinct representatives of a collection of sets. Based on Bang and Sharp’s ideas, Koh and Ree [4] have given a different proof of Theorem 1.1 and 1.2. Some more results on scores of k- hypertournaments can be found in [3,7]. An oriented graph is a graph with each edge endowed with an orientation. As given by Avery [1], the score s(vi) or si of a vertex vi in an oriented graph with n vertices is s(vi) = n−1+d+(vi)−d−(vi), where d+(vi) and d−(vi) are respectively the outdegree and indegree of vi . The score sequence of an oriented graph is formed by listing the scores in non-decreasing order. The following result due to Avery [1] characterizes score sequences in oriented graphs, and a new proof of it is due to Pirzada et al. [6]. Theorem 1.3. A sequence S = [s1, s2, · · · , sn] of non-negative integers in non-decreasing order is a score sequence of an oriented graph if and only if for each j (1≤ j ≤ n) j ∑ i=1 si ≥ 2 � j 2 � , with equality when j = n. An oriented k-hypergraph is a k-hypergraph with each k-edge endowed with an orienta- tion, that is, a linear arrangement of the vertices contained in the hyperedge. In other words, given two non-negative integers n and k with n ≥ k > 1, an oriented k-hypergraph on n vertices is a pair (V, A), where V is a set of vertices with |V | = n and A is a set of k-tuples of vertices, called arcs, such that for any k-subset S of V , A contains at most one of the k! S. Pirzada, Z. Guofei / Eur. J. Pure Appl. Math, 1 (2008), (10-20) 12 k-tuples whose entries belong to S. Clearly, an oriented 2-hypergraph is simply an oriented graph. Let D = (V, A) denote an oriented k-hypergraph with n vertices and let 1< k ≤ n. Clearly, there can or cannot be an arc among any k distinct vertices v1, v2, · · · , vk of V . If there is an arc among v1, v2, · · · , vk, we denote it by e = (v1, v2, · · · , vk) and if there is not an arc among v1, v2, · · · , vk, it is denoted by v1, v2, · · · , vk � , and we call it a non arc. We note that D contains at most � n k � arcs, that is |A| ≤ � n k � , and a vertex vi in D can be in at most � n− 1 k− 1 � arcs. We denote by d+(vi) � d−(vi) � , the number of arcs in which vi is not the last element ((vi is the last element), furthermore, we denote by d+i (U) (d−i (U)) the number of arcs that are contained in U and in which vi is not the last element ((vi is the last element). Now, let V1 = {v1, v2, · · · , v j} ⊂ V and V2 = V − V1. If q is the number of those arcs which contain at least one vertex from V1 and at least one vertex from V2, then q ≤ k−1 ∑ i=1 � j i �� n− j k− i � . The set of those arcs having at least one vertex in V1 and at least one vertex in V2 is denoted by V1 ∗ V2. Let e = (v1, v2, · · · , vk) be an arc in D and i < j ≤ k. We denote by e(vi , v j) = (v1, · · · , vi−1, v j , vi+1, · · · , v j−1, vi , v j+1, · · · , vk), that is, the new arc obtained from e by interchanging vi and v j in e. Similarly, we denote by f ¬ vi , v j ¶ the new non arc obtained from the non arc f = ¬ v1, v2, · · · , v j ¶ by interchanging vi and v j in f . Define the score s(vi) or si of a vertex vi in oriented k-hypergraph D as s(vi) = (k− 1) � n− 1 k− 1 � + d+(vi)− (k− 1)d−(vi). Clearly, 0 ≤ si ≤ k � n− 1 k− 1 � . The score sequence S = [s1, s2, · · · , sn] of D is formed by listing the scores in non-decreasing order. Let R = [s1, s2, · · · , sn] be an integer sequence. For 1 ≤ i < j ≤ n, we define S(s+i , s−j ) = [s1, s2, · · · , si + 1, · · · , s j − 1, · · · , sn], and S+(s+i , s−j ) = (s ′ 1, s′2, · · · , s′n) denotes an arrangement of S(s+i , s−j ) such that s′1 ≤ s′2 ≤ · · · ≤ s′n. Let S = [s1, s2, · · · , sn] be a non-decreasing sequence of non-negative integers with each si having the form si = x ik+ yi(k− 1), where x i and yi are nonnegative integers and satisfy 0≤ x i , yi ≤ � n− 1 k− 1 � , S is called to be strict if for all si < s j , we have yi > y j . 2. Main results Our main result is the following theorem. S. Pirzada, Z. Guofei / Eur. J. Pure Appl. Math, 1 (2008), (10-20) 13 Theorem 2.1. Given two non-negative integers n and k with n≥ k > 1, a non-decreasing strict sequence S = [s1, s2, · · · , sn] of non-negative integers with si = x ik + yi(k − 1), where x i , yi are nonnegative integers and satisfies 0 ≤ x i , yi ≤ � n− 1 k− 1 � , is a score sequence of some oriented k-hypergraph if and only if j ∑ i=1 si ≥ j(k− 1) � n− 1 k− 1 � + k−1 ∑ i=1 (i− k) � j i �� n− j k− i � (2.1) with equality for j = n. In order to prove this theorem, we need some lemmas. Lemma 2.1. If D is an oriented k-hypergraph of order n, then s(vi) = xk+ y(k−1), where x and y are non-negative integers. Proof. Let d∗(vi) be the number of non arcs in which vertex vi is contained. Then, d+(vi) + d−(vi) + d∗(vi) = � n− 1 k− 1 � , or d−(vi) = � n− 1 k− 1 � − d+(vi)− d∗(vi). Therefore, s(vi) = (k− 1) � n− 1 k− 1 � + d+(vi)− (k− 1)d−(vi) gives s(vi) = (k− 1) � n− 1 k− 1 � + d+(vi)− (k− 1) �� n− 1 k− 1 � − d+(vi)− d∗(vi) � = kd+(vi) + (k− 1)d∗(vi) As d+(vi) and d∗(vi) are non-negative integers, the proof follows.� It follows from Lemma 2.1 that the score of a vertex vi besides satisfying 0 ≤ si ≤ k � n− 1 k− 1 � should also satisfy si = xk + y(k − 1), where x and y are non-negative inte- gers. A vertex vi if belonging to an arc and not the last element contributes k to the score of vi , and if not belonging to an arc contributes k− 1 to the score of vi . For k = 2, D is simply an oriented graph and the score of a vertex in that case becomes s(vi) = � n− 1 2 � + d+(vi)− d−(vi), which is same as defined by Avery. Lemma 2.2. If [s1, s2, · · · , sn] is a score sequence of an oriented k-hypergraph of order n, then n ∑ i=1 si = n(k− 1) � n− 1 k− 1 � . Proof. In the following, d+i and d−i denote d(vi)+ and d(vi)− respectively. Let D be an oriented k-hypergraph with score sequence [s1, s2, · · · , sn]. We have, S. Pirzada, Z. Guofei / Eur. J. Pure Appl. Math, 1 (2008), (10-20) 14 n ∑ i=1 si = n ∑ i=1 � (k− 1) � n− 1 k− 1 � + d+i − (k− 1)d−i � = n(k− 1) � n− 1 k− 1 � + n ∑ i=1 d+i − (k− 1) n ∑ i=1 d−i . Let D contains p k-arcs. Then, n ∑ i=1 d+i = (k− 1)p and n ∑ i=1 d−i = p. Therefore, n ∑ i=1 si = n(k− 1) � n− 1 k− 1 � + (k− 1)p− (k− 1)p = n(k− 1) � n− 1 k− 1 � � Lemma 2.3. If S = [s1, s2, · · · , sn] is a score sequence of an oriented k-hypergraph D with si < s j and si = xk + y(k − 1), s j = αk + β(k − 1), where x , y , α and β are non-negative integers. If y > β , then S+(s+i , s−j ) is a score sequence of an oriented k-hypergraph D′. Proof. For simplicity, A(D) denotes the set of arcs in D; A∗(D) denotes the set of non arcs in D. Since d(v)∗ = y > β ≥ 0, we have A∗(D) 6= ;. Case 1. There exists a non arc e∗ = 〈u1, u2, · · · , uk−1, vi〉 ∈ A∗(D) which does not contain v j and such that e = (u′1, u′2, · · · , u′k−1, v j) ∈ A(D), where (u′1, u′2, · · · , u′k−1) is a permutation of (u1, u2, · · · , uk−1). If there exists an arc e1 that contains both vi and v j and that vi is the last entry. Then by exchanging vi and v j in e1, adding the arc e′ = (u1, u2, · · · , uk−1, vi) to D, and deleting e from D, we get an oriented k-hypergraph D′ with S+(s+i , s−j ) as its score sequence. So in the following, we assume that for each arc containing both vi and v j , vi is not the last entry. If there exists a pair of arcs f = (w1, w2, · · · , wk−1, vi), and f ′ = (w′1, w′2, · · · , v j , · · · , w′k−1), where (w′1, w′2, · · · , w′k−1) is a permutation of (w1, w2, · · · , wk−1). Then by exchanging vi and v j between f and f ′, adding the arc e′ = (u1, u2, · · · , uk−1, vi) to D, and deleting e from D, we get an oriented k-hypergraph D′ with S+(s+i , s−j ) as its score sequence. So in the following, we assume that no such pair of arcs exist. Furthermore, for each f ′ = (w′1, w′2, · · · , v j , · · · , w′k−1), f = (w1, w2, · · · , vi , · · · , wk−1) must be an arc, where (w′1, w′2, · · · , w′k−1) is a permutation of (w1, w2, · · · , wk−1), otherwise, by adding (w1, w2, · · · , vi , · · · , wk−1) to D and deleting f ′ from D, we get an oriented k-hypergraph D′ with S+(s+i , s−j ) as its score sequence. And therefore, we have d+(v j) ≤ d+(vi). Meanwhile, since y > β , si < s j and by the proof of Lemma 2.1, si = kd+(vi) + (k− 1)d∗(vi) < s j = kd+(v j) + (k− 1)d∗(v j), which implies that k(d+(v j)− d+(vi)) > (k− 1)(d∗(vi)− d∗(v j)) > 0, thus we have (d+(v j)− d+(vi) > 0, which contradicts the fact that d+(v j)≤ d+(vi). S. Pirzada, Z. Guofei / Eur. J. Pure Appl. Math, 1 (2008), (10-20) 15 Case 2. For each non arc e∗ = 〈u1, u2, · · · , uk−1, vi〉, either f ∗ = 〈u1, u2, · · · , uk−1, v j〉 is a non arc, or {u1, u2, · · · , uk−1, v j} forms an arc, but v j is not the last entry. Note that the later case will deduce that result is valid, so we assume that for each non arc e∗ = 〈u1, u2, · · · , uk−1, vi〉, f ∗ = 〈u1, u2, · · · , uk−1, v j〉 is also a non arc. This implies that d∗(vi) ≤ d∗(v j), which contradicts that y > β .� We note when y ≤ β , Lemma 2.3 need not be true. To see this consider a 3-hypergraph D = (V, A) with V = {1, 2, 3,4} and A= {(1,2, 3), (3,4, 1)} it is easy to check that [5,5,7,7] is the score sequence of D. But the sequence [5,6,6,7], which is just S+(s+i , s−j ), where si = 5 and s j = 7, is not a score sequence of any 3-hypergraph. Lemma 2.4. If S = [s1, s2, · · · , sn] with s1 ≤ s2 ≤ · · · ≤ sn is a non-negative integer sequence satisfying (1), and if sn < k � n− 1 k− 1 � , then there exists p (1≤ p ≤ n−1) such that S(s+n , s−p ) is non-decreasing and satisfies (2.1). Proof. Let p be the maximum integer such that sp−1 < sp = sp+1 = · · ·= sn−1 with s0 = 0 if p = 1. To see S(s+n , s−p ) satisfies (2.1), we only need to show for each j (p ≤ j ≤ n− 1), j ∑ i=1 si > j(k− 1) � n− 1 k− 1 � + k−1 ∑ i=1 (i− k) � j i �� n− j k− i � . (2.2) Since sn < k � n− 1 k− 1 � , therefore n−1 ∑ i=1 si = n ∑ i=1 si − sn = n(k− 1) � n− 1 k− 1 � − sn > n(k− 1) � n− 1 k− 1 � − k � n− 1 k− 1 � = (n− 1)(k− 1) � n− 1 k− 1 � − � n− 1 k− 1 � . As � n− 1 k− 1 � ≤ k−1 ∑ i=1 (k− i) � n− 1 i �� n− (n− 1) k− i � , so − � n− 1 k− 1 � ≥− k−1 ∑ i=1 (k− i) � n− 1 i �� 1 k− i � = k−1 ∑ i=1 (i− k) � n− 1 i �� 1 k− i � . S. Pirzada, Z. Guofei / Eur. J. Pure Appl. Math, 1 (2008), (10-20) 16 Therefore, n−1 ∑ i=1 si > (n− 1)(k− 1) � n− 1 k− 1 � + k−1 ∑ i=1 (i− k) � n− 1 i �� 1 k− i � . Thus for p = 1, (2.2) holds. Now, we assume p ≤ n− 2. Clearly, (2.2) holds for j = n− 1. If there exists j0 (p ≤ j0 ≤ n− 2) such that j0 ∑ i=1 si = j0(k− 1) �n−1 k−1 � + k−1 ∑ i=1 (i− k) � j0 i ��n− j0 k−i � , choose j0 as large as possible. Since j0+1 ∑ i=1 si > ( j0+ 1)(k− 1) � n− 1 k− 1 � + k−1 ∑ i=1 (i− k) � j0+ 1 i �� n− ( j0+ 1) k− i � , therefore s j0 = s j0+1 = j0+1 ∑ i=1 si − j0 ∑ i=1 si > ( j0+ 1)(k− 1) � n− 1 k− 1 � + k−1 ∑ i=1 (i− k) � j0+ 1 i �� n− j0− 1 k− i � − j0(k− 1) � n− 1 k− 1 � = (k− 1) � n− 1 k− 1 � + k−1 ∑ i=1 (i− k) � j0+ 1 i �� n− j0− 1 k− i � Thus, j0−1 ∑ i=1 si = j0 ∑ i=1 si − s j0 < j0(k− 1) � n− 1 k− 1 � −  (k− 1) � n− 1 k− 1 � + k−1 ∑ i=1 (i− k) � j0+ 1 i �� n− j0− 1 k− i �   = ( j0− 1)(k− 1) � n− 1 k− 1 � − k−1 ∑ i=1 (i− k) � j0+ 1 i �� n− j0− 1 k− i � Now, � j0+ 1 i � = j0( j0+1) ( j0−i+1)( j0−i) � j0− 1 i � and � n− j0− 1 k− i � = (n− j0−k+i+1)(n− j0−k+i) (n− j0+1)(n− j0) � n− ( j0− 1) k− i � . So, j0−1 ∑ i=1 si < ( j0− 1)(k− 1) � n− 1 k− 1 � − k−1 ∑ i=1 (i−k) j0( j0+1)(n− j0−k+i+1)(n− j0−k+i) ( j0−i+1)( j0−i)(n− j0+1)(n− j0) � j0− 1 i �� n− ( j0− 1) k− i � , or j0−1 ∑ i=1 si < ( j0− 1)(k− 1) � n− 1 k− 1 � + k−1 ∑ i=1 (i− k) � j0− 1 i �� n− ( j0− 1) k− i � , S. Pirzada, Z. Guofei / Eur. J. Pure Appl. Math, 1 (2008), (10-20) 17 a contradiction to the hypothesis on S. Hence, (2.2) holds.� Proof of Theorem 2.1. Necessity. Let S = [s1, s2, · · · , sn] be the score sequence of an oriented k-hypergraph D. Further, let V1 = [v1, v2, · · · , v j] and V2 = V − V1. Clearly, � �V1 � � = j, � �V2 � �= n− j . Now, j ∑ i=1 si = j ∑ i=1 (k− 1) � n− 1 k− 1 � + d+i (D)− (k− 1)d−i (D) = j(k− 1) � n− 1 k− 1 � + j ∑ i=1 d+i (D)− (k− 1) j ∑ i=1 d−i (D) = j(k− 1) � n− 1 k− 1 � + j ∑ i=1 � d+i (V1) + d+i (V1 ∗ V2) � − (k− 1) j ∑ i=1 � d−i (V1) + d−i (V1 ∗ V2) � If there are α arcs in V , then j ∑ i=1 d+i (V1) = (k− 1)α and j ∑ i=1 d−i (V1) = α, so that j ∑ i=1 d+i (V1)− (k− 1) j ∑ i=1 d−i (V1) = (k− 1)α− (k− 1)α= 0. Also, j ∑ i=1 d−i (V1 ∗ V2)≤ k−1 ∑ i=1 � j i �� n− j k− i � , and j ∑ i=1 d+i (V1 ∗ V2)≥ k−1 ∑ i=1 (i− 1) � j i �� n− j k− i � . Therefore, j ∑ i=1 si ≥ j(k− 1) � n− 1 k− 1 � + k−1 ∑ i=1 (i− 1) � j i �� n− j k− i � − (k− 1) k−1 ∑ i=1 � j i �� n− j k− i � = j(k− 1) � n− 1 k− 1 � + k−1 ∑ i=1 (i− k) � j i �� n− j k− i � Sufficiency. Induct on n. If n= k, there is only one arc (or one non arc) in which case the scores are n, n, · · · , n, 0(n− 1, n− 1, · · · , n− 1), and the result is true. Assume n> k. Now, sn = n ∑ i=1 si − n−1 ∑ i=1 si ≤ n(k− 1) � n− 1 k− 1 � − (n− 1)(k− 1) � n− 1 k− 1 � − k−1 ∑ i=1 (i− k) � n− 1 i �� 1 k− i � = k � n− 1 k− 1 � . S. Pirzada, Z. Guofei / Eur. J. Pure Appl. Math, 1 (2008), (10-20) 18 Case 1. If sn = k � n− 1 k− 1 � . Let s′i = si − k(k−2) n−1 � n− 1 k− 1 � , 1≤ i ≤ n− 1 . Clearly, s′i is of the form xk+ y(k− 1). Then, n−1 ∑ i=1 s/i = n−1 ∑ i=1 � si − k(k− 2) n− 1 � n− 1 k− 1 �� = (n(k− 1)− k) � n− 1 k− 1 � − k(k− 2) � n− 1 k− 1 � , since n−1 ∑ i=1 si = n ∑ i=1 si − sn = n(k− 1) � n− 1 k− 1 � − k � n− 1 k− 1 � = (n(k− 1)− k) � n− 1 k− 1 � . So, n−1 ∑ i=1 s/i = (n(k− 1)− k(k− 2)) � n− 1 k− 1 � = (n(k− 1)− k(k− 2)) � n− 1 n− k � � n− 2 k− 1 � = (n− 1)(k− 1) � n− 2 k− 1 � . Also, for 1≤ j < n− 1, S. Pirzada, Z. Guofei / Eur. J. Pure Appl. Math, 1 (2008), (10-20) 19 j ∑ i=1 s/i = j ∑ i=1 � si − k(k− 2) n− 1 � n− 1 k− 1 �� ≥ j(k− 1) � n− 1 k− 1 � + k−1 ∑ i=1 (i− k) � j i �� n− j k− i � − jk(k− 2) n− 1 � n− 1 k− 1 � = � j(k− 1)− jk(k− 2) n− 1 �� n− 1 n− k � � n− 2 k− 1 � + k−1 ∑ i=1 (i− k) � j i �� n− j− 1 k− i � ≥ j(n− 1)(k− 1)− jk(k− 2) n− k � n− 2 k− 1 � + k−1 ∑ i=1 (i− k) � j i �� n− 1− j k− i � = j [(k− 1)(n− k) + 1] n− k � n− 2 k− 1 � + k−1 ∑ i=1 (i− k) � j i �� n− 1− j k− i � ≥ j(k− 1)(n− k) n− k � n− 2 k− 1 � + k−1 ∑ i=1 (i− k) � j i �� n− 1− j k− i � . Thus, the sequence [s′1, s′2, · · · , s′n−1] satisfies (2.1) and by induction hypothesis is a score sequence of some oriented k-hypergraph D′. Now, construct the oriented k-hypergraph D as follows. Let V (D′) = {v1, v2, · · · , vn−1} with s(vi) = s′i . Adding a new vertex vn, and taking all � n− 1 k− 1 � � 1 1 � arcs with vn not in the last entry in any of these arcs, we get an oriented k-hypergraph D of order n with score sequence � s/1+ k(k−2) n−1 � n− 1 k− 1 � , · · · , k(k−2) n−1 � n− 1 k− 1 � , k � n− 1 k− 1 �� = [s1, s2, · · · , sn]. Case 2. If sn < k � n− 1 k− 1 � . By (2.1), we get that sn ≥ (k − 1) � n− 1 k− 1 � . Let xn = sn− (k−1) � n− 1 k− 1 � , and yn = k � n− 1 k− 1 � − sn, then sn = kxn+(k−1)yn. Now applying Lemma 2.4 repeatedly until we obtain a new non-decreasing sequence S′ = [s′1, s′2, · · · , s′n] such that s′n = k � n− 1 k− 1 � . It is obvious that Lemma 2.4 is applied yn times. We denote by P1 the operation that makes S become some S1 = S(s+n , s−p1 ) and P2 the operation that makes S1 become some S2 = S1(s+n , s−p2 ), and so on. Furthermore will denote by P−1 i the corresponding reversal operation. Note that since si − 1 = (x i − 1)k + (yi + 1)(k − 1) and sn+ 1= (xn+ 1)k+ (yn− 1)(k− 1), the resulting sequence Syn = S′ is still strict. So by case 1, S′ is a score sequence of some oriented k-hypergraph. Now, we make the operations P−1 yn , · · · , P−1 2 , P−1 1 , applying Lemma 2.3 on each operation, we finally get the original non-decreasing sequence S = [s1, s2, · · · , sn]. Note that after each operation P−1 i , the REFERENCES 20 corresponding integer sequence remains strict, so by Lemma 2.3, S is a score sequence of an oriented k-hypergraph. Remark. If k = 2 in Theorem 2.1, then the necessary and sufficient condition for the sequence of non-negative integers [s1, s2, · · · , sn] in non-decreasing order becomes j ∑ i=1 si ≥ j � n− 1 1 � + 1 ∑ i=1 (i− 2) � j i �� n− j 2− i � = j � n− 1 1 � − � j 1 �� n− j 1 � = j(n− 1)− j(n− j) = j2− j = j( j− 1) with n ∑ i=1 si = n(2− 1) � n− 1 1 � = n(n− 1), which is Avery’s theorem for oriented graphs. References [1] P. Avery, Score sequences of oriented graphs, J. Graph Theory, Vol. 15, No. 3(1991) 251-257. [2] C. M. Bang and H. Sharp Jr., Score vectors of tournaments, J. Combin.Theory Ser. B 26 (1) (1979) 81-84. [3] Y. Koh and S. Ree, Score sequences of hypertournament matrices, J. Korea Soc. Math. Educ. Ser. B: Pure and Appl. Math. 8 (2) (2001) 185-191. [4] Y. Koh and S. Ree, On k-hypertournament matrices, Linear Algebra and its Applications 373 (2003) 183-195. [5] H. G. Landau, On dominance relations and the structure of animal societies. III. The condition for a score structure, Bull. Math. Biophys. 15 ( 1953 ) 143-148. [6] S. Pirzada, T. A. Naikoo and N. A. Shah, Score sequences in oriented graphs, J. Applied Mathe- matics and Computing (2006), 22(1-2) (2007) 257-268. [7] C. Wang and G. Zhou, Note on the degree sequences of k-hypertournaments, Discrete Mathe- matics, To appear. [8] G. Zhou, T. Yao and K. Zhang, On score sequences of k-hypertournaments, European J. Combin. 21 (8) (2000) 993-1000.