The simplicity index of tournaments
Abderrahim Boussaïri Soufiane Lakhlifi Imane Talbaoui
math.CO 05C20, 05C12





Laboratoire Topologie, Algèbre, Géométrie et Mathématiques Discrètes, Faculté des Sciences Aïn Chock, Hassan II University of Casablanca, Maroc.


The simplicity index of tournaments
    
	Abderrahim BoussaïriCorresponding author: Abderrahim Boussaïri. Email: aboussairi@hotmail.com , Soufiane Lakhlifi and Imane Talbaoui

    
===========================================================================================================================================





An n-tournament T with vertex set V is simple if there is no 
subset M of V such that 2≤| M|≤ n-1 
and for every x∈ V∖ M, either M→ x or x
→ M. The simplicity index of an n-tournament T is the 
minimum number s(T) of arcs whose reversal yields a non-simple 
tournament. Müller and Pelant (1974) proved that s(T)≤n-1/
2, and that equality holds if and only if T is doubly regular. As 
doubly regular tournaments exist only if n≡ 34, s(T)<n-1/2 for n≢34. In this paper, we study the class 
of n-tournaments with maximal simplicity index for n≢34.


Keywords:
Doubly regular tournament, arc reversal, module, simplicity index.

MSC Classification:
05C20, 05C12.



§ INTRODUCTION

  
	A tournament T consists of a finite set V of vertices
 together with a set A of ordered pairs of distinct vertices, called 
arcs, such that for all x≠y∈ V, (x,y)∈ A if and only 
if (y,x)∉ A. Such a tournament is denoted by T=(V,A).  Given x
≠ y∈ V,  we say that x dominates y and we write x
→ y when (x,y)∈ A. Similarly, given two disjoint subsets X and Y of V, we write X→ Y if x→ y holds 
for every (x,y)∈ X× Y.  Throughout this paper, we mean by an 
n-tournament a tournament with n vertices. 

     A tournament is regular if there is an integer k≥ 1 such that each vertex dominates exactly k vertices.
     It is doubly regular if there is an integer k≥ 1 such that every unordered pair of vertices dominates exactly k vertices.
    
    A tournament is transitive, if for any vertices x, y and z, x→ y and y→ z implies that x→ z. 
    A tournament T=(V,A) is reducible if V admits a bipartition {X,Y} such that 
    X→ Y. 
    The notion of simple tournament was introduced by Fried and Lakser <cit.>, it was motivated by questions in algebra. It is closely related to modular decomposition <cit.> which involves the notion of module. Recall that a module of a tournament T=(V,A) is a subset M of V such that for every x∈ V∖ M either M→{x} or {x}→ M. For example, ∅, {x}, where x∈ V, and V are modules of T called trivial modules.  
    An n-tournament is simple <cit.> (or prime <cit.> or primitive <cit.> or indecomposable <cit.>) if n≥ 3 and all its modules are trivial. The simple tournaments with at most 5 vertices are shown in Figure <ref>. A tournament is decomposable if it admits a non-trivial module.
       
     
    
 
    
    
	Given an n-tournament T, the Slater index i(T) of T is 
the minimum number of arcs that must be reversed to make T transitive 
<cit.>. It is not difficult to see that i(T)
≤n(n-1)/4. However, we do not know an exact determination 
of the upper bound of i(T). Erdős and Moon <cit.> 
proved that this bound is asymptotically equal to n^2/4.  
Recently, Satake <cit.> proved that the Slater 
index of doubly regular n-tournaments is at least n(n-1)/4-n^3/2log_2(2n). 

      
Kirkland <cit.> defined the reversal index i_R(T)
of a tournament T as the minimum number of arcs whose reversal makes T 
reducible. Clearly, i_R(T)≤ i(T). Kirkland <cit.> 
proved that i_R(T)≤⌊n-1/2⌋ and 
characterized all the tournaments for which equality holds. 

     
The indices above can be interpreted in terms of distance between 
tournaments. The distance d(T_1,T_2) between two tournaments T_1 
and T_2 with the same vertex set is the number of pairs {x, y} of 
vertices for which the arc between x and y has not the same direction in T_1 and T_2. Let ℱ be a family of tournaments with vertex set V. The distance from a tournament T to the family ℱ is d(T,
ℱ)=min{ d(T,T^'):T^'∈ℱ}. If ℱ is the family of transitive tournaments on V, then i(T)=d(T,ℱ
). If ℱ is the family of reducible tournaments on V, then i_R
(T)=d(T,ℱ). 

     
By considering the family of decomposable tournaments, we obtain the simplicity 
index introduced by Müller and Pelant <cit.>. 
Precisely, consider an n-tournament T, where n≥ 3. The 
simplicity index s(T) of T (also called the arrow-simplicity of T in <cit.>) is the minimum number of arcs that must be 
reversed to make T non-simple. For example, the tournaments shown in Figure 
<ref> have simplicity index 1. Obviously, s(T)≤ i_R(T) and s(T)
≤n-1/2. Müller and Pelant proved that s(T)=n-1/2 if 
and only if T is doubly regular.

	A dual notion of the simplicity index is the decomposability index <cit.>, 
which is 
obtained by considering the family of simple tournaments.

	In this paper, we provide an upper bound for s(T), where T is an n-tournament for n≢34. More precisely, we obtain the 
following result.

Given an n-tournament T, the following statements hold 
	
    
  * if n=4k+2, then s(T)≤2k;
    
  * if n=4k+1, then s(T)≤2k-1;
    
  * if n=4k, then s(T)≤2k-2.
  

    
To prove that the bounds in this theorem are the best possible, we use 
the double regularity as follows.
    


  Let l∈{1,2,3}. Consider a doubly regular tournament T of order 
4k+3, where k≥ l. The simplicity index of a tournament obtained 
from T by removing l vertices is (2k+1)-l.


     
    As shown by the next result, the opposite direction in Theorem <ref> holds when l=1. 
    
    
  Given a tournament T with 4k+2 vertices, where k≥ 1, if s(T)=2k,
then T is obtained from a doubly regular tournament by removing one vertex. 
    
     
	The existence of doubly regular tournaments is equivalent to the 
existence of skew-Hadamard matrices <cit.>. Wallis <cit.> conjectured that n× n skew-Hadamard matrices 
exist if and only if n=2 or n is divisible by 4. Infinite 
families of skew-Hadamard matrices can be found in <cit.>.

	The most known examples of a doubly regular tournament are obtained 
from Paley construction.	For a prime power q≡34, the Paley
tournament of order q is the tournament whose vertex set is the 
finite field 𝔽_q, such that x dominates y if and only if x - y is a non-zero quadratic residue in 𝔽_q.     



§ PRELIMINARIES

    
  Let T=(V,A) be an n-tournament and let x∈ V. The 
out-neighborhood of x is N_T^+(x):={y∈ V:x→ y
}, and the in-neighborhood of x is N_T^-(x):=
{y∈ V:y→ x}. The out-degree of x (
resp. the in-degree of x) is δ_T^+(x):=| N_T
^+(x)| (resp. δ_T^-(x):=| N_T^-(x)
|). The out-degree of x is also called the 
score of x in T. Recall that 

    z∈ V∑δ_T^+(z)=z∈ V∑δ_T^-(z)=n(n-1)/2.

    A tournament is near-regular if there exists an integer k>0 such that the out-degree of every vertex equals k or k-1.
 
    
     Let T be an n-tournament. It follows from (<ref>) that
    
    
  * T is regular if and only if n is odd and every vertex has out-degree
    (n-1)/2;
    
  * T is near-regular if and only if n is even and T has n/2 vertices of out-degree n/2 and n/2 vertices of out-degree (n-2)/2.
    
    
    
    
    Let T=(V,A) be a near-regular tournament of order 4k+2. We can partition V into two (2k+1)-subsets, V_ even:={z∈ V,δ_T^+(z)=2k} and 
    V_ odd:={z∈ V,δ_T^+(z)=2k+1}. 
    
     
     Let x,y be distinct vertices of an n-tournament T=(V,A). 
      The set
     V∖{x,y} can be partitioned into four
     subsets:N_T^+(x)∩ N_T^+(y), N_T^-(x)∩ N_T^-(y), N_T^+(x)∩ N_T^-(y) and N_T^-(x)∩
     N_T^+(y). The out-degree (resp. the in-degree) of (x,y) is
     δ_T^+(x,y):=| N_T^+(x)∩ N_T^+(y)| (resp. δ_T^-(x,y):=| N_T^-(x)∩ N_T^-(y)|). The elements of (N_T^+(x)∩ N_T^-(y))∪(N_T^-(x)∩ N_T^+(y)) are called separators of x,y and their
     number is denoted by σ_T(x,y). 
    
    Let T be an n-tournament with vertex set V. For any x≠ y∈ V, we have
    
    
  * σ_T(x,y)+δ_T^-(x,y)+δ_T^+(x,y)=n-2;
    
  * δ_T^-(x,y)-δ_T^+(x,y)=δ_T^-(x)-δ_T^+(y).
    
    In particular, if T is regular, then for any x≠ y∈ V, δ_T^-(x,y)=δ_T^+(x,y).
    
     
    The first assertion is obvious. For the second assertion, we have 
    | N_T^-(x)| =| N_T^-(x)∩ N_T^-(y)|
        +| N_T^-(x)∩ N_T^+(y)| +| N_T^-(x)∩{ y}|

    and 
    | N_T^+(y)| =| N_T^+(y)∩ N_T^+(x)|
        +| N_T^+(y)∩ N_T^-(x)| +| N_T^+(y)∩{ x}|.

    Moreover, y∈ N_T^-(x) if and only if x∈ N_T^+(y). Then | N_T^-(x)∩{  y}| =| N_T^+(y)∩{
    x}| and hence 
    
    | N_T^-(x)∩ N_T^-(y)|
        -| N_T^+(x)∩ N_T^+(y)| =| N_T^-(x)| -| N_T^+(y)|.

    
    Let T=(V,A) be a tournament. For each vertex z∈ V, we have
    
    δ_T^-(z)δ_T^+(z) = |{{x,y}∈V2:z∈ (N_T^-(x)∩ N_T^+(y))∪ (N_T^+(x)∩ N_T^-(y))}|.

    By double-counting, we obtain 
    
    z∈ V∑δ_T^+(z)δ_T^-(z)={x,y}∈V2∑σ_T(x,y).

      
    In the next proposition, we give some basic properties of doubly regular
    tournaments. For the proof, see <cit.>.
    
    
    Let T=(V,A) be a doubly regular n-tournament. There exists k≥0 
    such that n=4k+3, T is regular, and for all x,y∈ V such that x→ y, we have
    
    | N_T^+(x)∩ N_T^+(y)| =| N_T^-(x)∩ N_T^-(y)| =
        | N_T^+(x)∩ N_T^-(y)| =k
 
    
    and| N_T^-(x)∩ N_T^+(y)| =k+1.

    




§ PROOF OF THEOREM <REF>

    
    Let T=(V, A) be a tournament. 
    Given a subset B of A, we denote by Inv(T,B) the tournament obtained from T by reversing all the arcs of B.
    We also use the following notation: δ_T^+ =min{δ_T^+(x):x∈ V}, δ_T^- =min{δ_T^-(x):x∈ V}, δ_T=min(δ_T^+,δ_T^-), and σ_T=min{σ_T(x,y):x≠ y∈ V}. 
    The next proposition provides an upper bound of the simplicity index of a tournament. 
    
    
     For a tournament T=(V,A) with at least 3 vertices, we have
    s(T)≤min(δ_T,σ_T).
    
    
    
    Let x∈ V. Clearly, the subset V∖{x} is a non-trivial module of 
    Inv(T,{x}× N_T^+(x)) and Inv(T,N_T^-(x)×{x}). It follows that 
    s(T)≤min_x∈ V(δ_T^+(x),δ_T^-(x))=δ_T.

    
    Now, consider an unordered pair {x,y} of vertices of T and let
    
    B:=({x}×((N_T^+(x)∩ N_T^-(y))∪(N_T^+(y)∩ N_T^-(x))×{x}).
 Clearly, {x,y} is a module of
    Inv(T,B). It follows that 
    s(T)≤| B| =| N_T^+(x)∩ N_T^-(y)| +| N_T^+(y)∩ N_T^-(x)| =σ_T(x,y).
 Hence, s(T)≤σ_T.
    
    In addition to the previous proposition, the proof of Theorem
    <ref> requires the following lemma.
    
    Given an n-tournament T=(V,A) with n≥ 2, we have 
    
    δ_T≤⌊n-12⌋ and 
        σ_T≤⌊n-12⌋.

    
    
    For every x∈ V, we have min(
    δ_T^+(x),δ_T^-(x))  ≤n-1/2. Thus, 
    δ_T≤⌊n-1/2⌋ .

    
    Now, to verify that σ_T≤⌊n-12⌋, observe that 
    σ_T≤1/| V |2{  x,y}∈V
    2∑σ_T(x,y).
 
    It follows from (<ref>) that 
     
    σ_T   ≤2/n(n-1)z∈ V∑δ_T^+
        (z)δ_T^-(z)
       ≤2/n(n-1)z∈ V∑(δ_T
        ^+(z)+δ_T^-(z)/2)^2
       ≤(n-1)/2.

    
    
    
    For the first statement, suppose that n=4k+2. By Proposition <ref> and Lemma
    <ref>, we have 
    s(T)≤δ_T≤⌊n-1/2⌋ =2k.

    
    For the second statement, suppose that n=4k+1. 
    By Proposition <ref>, s(T)≤δ_T. 
    If T is not
    regular, then δ_T<n-1/2 and hence s(T)≤2k-1. Suppose that
    T is regular and let x≠ y∈ V. By Lemma <ref>,
    σ_T(x,y)=n-2- δ_T^-(x,y)-δ_T^+(x,y) and δ_T^-(x,y)=δ_T^+(x,y). Therefore, σ_T(x,y) is odd, and hence σ_T is odd as well. By Lemma <ref>, σ_T≤⌊n-1/2⌋=2k. Since σ_T is odd, we obtain σ_T≤2k-1. 
    It follows from Proposition <ref> that s(T)≤2k-1.
    
    For the third statement, suppose that n=4k. 
    If T is not near-regular, then δ_T<2k-1, and hence s(T)≤2k-2 
    by Proposition <ref>. Suppose that T is near-regular.
    By Remark <ref>, for every z∈ V, δ_T^+
    (z)∈{2k,2k-1}. It follows from (<ref>) that
    
    {  x,y}∈V2∑σ_T
        (x,y)=z∈ V∑δ_T^+(z)δ_T^-(z)=8k^2
        (2k-1).

    Thus, we obtain
    
    σ_T   ≤1/| V |2{  x,y}∈V2∑σ_T(x,y)
       ≤2/4k(4k-1)8k^2(2k-1)
       ≤(2k-1)+2k-1/4k-1
       ≤ 2k-1.

    Since s(T)≤σ_T by Proposition <ref>, we obtain 
    s(T)≤σ_T≤2k-1. 
    Seeking a contradiction, suppose that s(T)=2k-1. We obtain σ_T=2k-1. 
    Let x∈ V_ even and y∈ V_ odd (see Notation <ref>). It follows from Lemma <ref> that σ_T(x,y) is
    even and hence σ_T(x,y)≥2k. Thus, there are at least (2k)^2
    unordered pairs {x,y} satisfying σ_T(x,y)≥2k. For the other 
    22k2 unordered pairs, we have σ_T(x,y)≥σ_T=2k-1. It follows that
    
    {  x,y}∈V2∑σ_T
        (x,y)≥22k2(2k-1)+(2k)^2(2k)>8k^2(2k-1),
 which contradicts
    (<ref>). Consequently, s(T)≤2k-2.
    
    
    

§ PROOF OF THEOREM <REF>

   
	To begin, recall that a graph is defined by a vertex set V 
and an edge set E. Two distinct vertices x and y of G are 
adjacent if {x,y}∈ E. For a vertex x in G, the  set N_G(x):=
{y ∈ V: {x,y}∈ E } is called the neighborhood of x in G. The degree of x is δ_G(x):=| N_G(x) |. 
    
    Let T=(V,A) be a tournament. To each subset C of V, 
    we associate a graph in the following way. 
    Denote by s_C(T) the minimum number of arcs that must be reversed to make
    C a module of T. Clearly, 
    
    s(T)=min{  s_C(T):2≤|
        C|≤ n-1}.
 
    A graph G=(V,E) is called a
    decomposability graph for C if | E| =s_C(T) and C is a module of the tournament 
    Inv(T,{(x,y)∈ A:{x,y}∈ E})
 
    obtained from T by reversing the arc between x and y for each edge 
    {x,y} of G. 
        In the next lemma, we provide some of the properties of decomposability graphs.
    
     Let T=(V,A) be a n-tournament and let C be a
    subset of V such that 2≤| C|≤ n-1. Given a decomposability graph G=(V,E) for C, the following assertions hold
    
    
  * G is bipartite with bipartition {C,V∖ C};
    
  * for each x∈ V∖ C, N_G(x)=N_T^+(x)∩ C or N_G(x)=N_T^-(x)∩ C, and δ_G(x)=min(| N_T^-(x)∩ C| ,| N_T^+(x)∩ C|).
    
    
    
    
   The first assertion follows from the minimality of | E| =s_C(T). 
        For the second assertion, consider x∈ V∖ C. 
        Since C is a module of the tournament 
        Inv(T,{(x,y)∈ A:{x,y}∈ E}), we have 
        N_G(x)=N_T^+(x)∩ C or N_G(x)=N_T^-(x)∩ C. 
        Furthermore, it follows from the minimality of | E| =s_C(T) that 
        δ_G(x)=min(| N_T^-(x)∩ C| ,| N_T^+(x)∩ C|). 
    
    
    The next proposition is useful to prove Theorems <ref> and <ref>. 
    
    
    
    Let T=(V,A) be an n-tournament and let C be a
    subset of V such that 2≤| C|≤ n-1. Given a decomposability graph G=(V,E) for C, the following statements hold
    
    
  * if n-δ_T≤| C|, then s_C(T)
    ≥δ_T;
    
  * if | C|≤σ_T, then s_C(T)≥σ_T.
    
    
    
    Before showing the first assertion, we establish 
    
    | E|≥(n-| C| )(| C| -(n-1-δ_T)).

    Let x∈ V∖ C. By the second assertion of Lemma
    <ref> 
    
    δ_G(x)   =min ( | N_T^-(x)∩ C| ,|
        N_T^+(x)∩ C| )
       =| C| -max ( | N_T^-(x)∩ C|
        ,| N_T^+(x)∩ C| ).

    Therefore, we obtain  
     
    δ_G(x)   ≥| C| -max (| N_T^-(x)|,| N_T^+(x)| )
       ≥(| C| -(n-1-δ_T)).

    Since G is bipartite with bipartition {C,V∖ C}, we have 
    
    | E| =
        ∑_x∈ V∖ Cδ_G(x).
 
    It follows from (<ref>) that 
    
    | E|   ≥| V∖ C|
        (| C| -(n-1-δ_T))
       ≥ (n-| C| )(| C| -(n-1-δ_T)).

    Thus, (<ref>) holds. 
    Moreover, we have 
    (n-| C| )(| C| -(n-1-δ
        _T))-δ_T=(n-1-| C| )(| C|
        -(n-δ_T)).

    
    Now, to prove the first assertion, suppose that 
    n-δ_T≤| C|. 
    We obtain 
    (n-1-| C| )(| C|
    -(n-δ_T)≥0, and hence (n-| C| )(| C| -(n-1-δ
    _T))≥δ_T. It follows that
    s_C(T)=| E|≥δ_T. 
    
    Before showing the second assertion, we establish 
    
    | E|≥| C|/2(2-| C| +σ_T).

    Consider two vertices x≠ y∈ C. 
    For convenience, denote by 𝒮_T(x,y) the set of separators of 
    {x,y}. 
    Clearly, we have (𝒮_T(x,y)∖ C)⊆ N_G(x)∪ N_G(y). 
    It follows that 
    δ_G(x)+δ_G(y)≥ |𝒮_T(x,y)∖ C|≥σ_T(x,y)-(| C| -2).

   Consequently, we obtain 
    
    δ_G(x)+δ_G(y)≥σ_T-| C| +2.

    Furthermore, observe that
     
    ∑_{x,y}∈C2(δ_G(x)+δ_G(y))=(|
        C| -1)∑_x∈ Cδ_G(x).

    It follows from (<ref>) that 
    
    (| C| -1)∑_x∈ Cδ_G(x)≥| C|2(2-| C| +σ_T).

    Therefore, we have 
    
    ∑_x∈ Cδ_G(x)≥| C|/2(2-| C| +σ_T).

    Since G is bipartite with bipartition {C,V∖ C}, we have 
    
    | E| =∑_x∈ Cδ_G(x).

    We obtain 
    
    | E|≥| C|/2(2-| C| +σ_T),
 so (<ref>) holds. 
    
    Finally, to prove the second assertion, suppose that 
    | C|≤σ_T. 
    We obtain 
    | C|/2(2-| C| +σ_T)≥σ_T. 
    Since s_C(T)=| E|, it follows from (<ref>) that s_C(T)≥σ_T. 
    
    
     
    Let l∈{1,2,3}. 
    Consider  a tournament R from T by removing l vertices v_1,…,v_l. 
    Set V':= V∖{v_1,…,v_l}. 
    It follows from Theorem <ref> that s(R)≤ (2k+1)-l. 
    It remains to show that s(R)≥ (2k+1)-l. 
    By (<ref>), it suffices to verify that s_C(R)≥ (2k+1)-l for every 
    subset C of V' such that 2≤| C|≤ (4k+2)-l. 
    Let C⊆ V' such that 2≤| C|≤ (4k+2)-l. 
    We distinguish the following three cases. 
    
    
  * Suppose that 2≤| C|≤ (2k+1)-l. 
    Since T is doubly regular, it follows from Proposition <ref> that 
    σ_T=2k+1. 
    Therefore, σ_R≥ (2k+1)-l. 
    Since 2≤| C|≤ (2k+1)-l, 
    σ_R≥| C|. 
    It follows from Proposition <ref>
    that s_C(R)≥σ_R, and hence s_C(R)≥ (2k+1)-l. 
    
  * Suppose that 2k+2≤| C|≤ (4k+2)-l. 
    Since T is doubly regular, it follows from Proposition <ref> that T is regular. 
    Thus, δ_T=2k+1. It follows that δ_R≥ (2k+1)-l. 
    Since 2k+2≤| C|≤ (4k+2)-l, we obtain 
    | C| + δ_R≥ (4k+3)-l. 
    It follows from Proposition <ref>
    that s_C(R)≥δ_R, and hence s_C(R)≥ (2k+1)-l. 
    
  * Suppose that (2k+2)-l≤| C|≤ 2k+1. 
    Let G=(E',V') be a decomposability graph for C. 
    We verify that 
    
    |{x∈ V'∖ C:δ_G(x)≠ 0}|≥ |V'∖ C|-1.

    Otherwise, there exist x≠ y∈ V'∖ C such that 
    δ_G(x)=δ_G(y)=0. 
    It follows from the second assertion of Lemma <ref> applied to R that C is contained in  one of the following intersections: (N_R^-(x)∩ N_R^+(y)), (N_R^-(x)∩ N_R^-(y)), (N_R^+(x)∩ N_R^+(y)), or 
    (N_R^+(x)∩ N_R^-(y)). 
    Thus, C is contained in (N_T^-(x)∩ N_T^+(y)), (N_T^-(x)∩ N_T^-(y)), (N_T^+(x)∩ N_T^+(y)), or 
    (N_T^+(x)∩ N_T^-(y)). 
    It follows from Proposition <ref> that | C|≤ k+1, 
    which contradicts 
    | C|≥ (2k+2)-l because k≥ l. 
    Consequently, (<ref>) holds. 
    Since G is bipartite with bipartition {C,V'∖ C}, we have 
    | E'| =∑_x∈ V'∖ Cδ_G(x). 
    Since | E'| =s_C(R), we obtain 
        
    s_C(R)   =∑_x∈ V'∖ Cδ_G(x)
       ≥| V' ∖ C | -1(by (<ref>))
       ≥ (2k+1)-l(because | C|≤ 2k+1).

    
    
    




§ PROOF OF THEOREM <REF>

    If a tournament T is obtained from a doubly regular (4k+3)-tournament by deleting one vertex, then T is near-regular and it follows from Proposition <ref> that
    
    
    
  (C1) if x,y∈ V_ even (see Notation <ref>) or x,y∈ V_ odd, then σ_T(x,y)=2k+1.
    
  (C2) if x∈ V_ even and y∈ V_ odd, then σ_T(x,y)=2k.
    
    Conversely, we have the following proposition. 
    
    
    Let T=(V,A) be a near-regular tournament of order 4k+2. 
    If T satisfies (C1) and (C2), then the tournament U obtained from T by adding a vertex ω which dominates V_ odd and is dominated by V_ even is doubly regular.
    
     The proof of this proposition uses the following lemma.
    
    Under the notation and conditions of Proposition <ref>, for every x,y∈ V such that x→ y, we have
    
    
  * if x,y∈ V_ odd, then 
    
    | N_T^-(x)∩ N_T^+(y)| =
        k+1 and | N_T^+(x)∩ N_T^-(y)|= k;

    
  * if x,y∈ V_ even, then 
    | N_T^-(x)∩ N_T^+(y)| = k+1 and | N_T^+(x)∩ N_T^-(y)| = k;

    
  * if x∈ V_ odd and y∈ V_ even, then 
    | N_T^-(x)∩ N_T^+(y)|= k and | N_T^+(x)∩ N_T^-(y)|= k;

    
  * if x∈ V_ even and y∈ V_ odd, then 
    | N_T^-(x)∩ N_T^+(y)|= k+1 and | N_T^+(x)∩ N_T^-(y)|
        = k-1.

    
    
    
    We have
    
    | N_T^-(x)∩ N_T^-(y)| +| N_T^-(x)∩ N_T^+(y)|
        =| N_T^-(x)|
    and
    | N_T^+(x)∩ N_T^+(y)| +| N_T^-(x)∩ N_T^+(y)|
        =| N_T^+(y)|.

    By using Lemma <ref>, we obtain 
    
    | N_T^-(x)∩ N_T^+(y)| =1/2(| N_T^-(x)|+| N_T^+(y)| -4k+σ_T(x,y)).

     
    Using Assertions (C1) and (C2), we obtain the desired values of | N_T^-(x)∩ N_T^+(y)|. Then, | N_T^+(x)∩ N_T^-(y) | follows immediately because
    | N_T^+(x)∩ N_T^-(y) | = σ(x,y)-| N_T^-(x)∩ N_T^+(y) |.
    
    
    
     Clearly, U is regular. Furthermore, by Lemma
    <ref>, 
    δ_U^+(x,y)=4k-σ_U(x,y)+1/2
 for distinct x,y∈ V∪{ω}. Therefore, U is doubly regular if and only if σ_U(x,y)=2k+1 for every x,y∈ V∪{ω}. This equality follows directly from (C1) and (C2) when x,y∈ V. Hence, it remains to prove that 
    
    σ_U
        (ω,z)=2k+1 for every z∈ V.

    Consider z∈ V. It is not difficult to see that
    
    σ
            _U(ω,z)=| N_T^+(z)∩ V_ even| +| N_T^-(z)∩
            V_ odd|.

    
     Let A_ odd:=(N_T^+(z)∩ V_ odd),
    A_ even:=( N_T^+(z)∩ V_ even), B_ odd:=(N_T^-(z)∩
    V_ odd), and B_ even:=(N_T^-(z)∩ V_ even). 
    We determine 
    | A_ odd|, | A_ even|, | B_ odd|, and | B_ even| as follows. 
    
    To begin, suppose that
    z∈ V_ odd. By counting the number of arcs from N_T^+(z) to N_T^-(z) in two ways, we get 
    
    ∑_t∈ A_ odd| N_T^-(z)∩ N_T^+(t)| +
        ∑_t∈ A_ even| N_T^-(z)∩ N_T^+(t)|
    
        =   ∑_t∈ B_ odd| N_T^-(t)∩ N_T^+(z)| +
        ∑_t∈ B_ even| N_T^-(t)∩ N_T^+(z)| .

    It follows from Lemma <ref> that
    
    (k+1)| A_ odd| +k| A_ even|
        =(k+1)(| B_ odd| +| B_ even|).

    Since z∈ V_ odd, we have | A_ odd| +|
    A_ even| =2k+1, | B_ odd| +|
    B_ even| =2k, | A_ odd| +| B_ odd| =2k, and | A_ even| +| B_ even|
    =2k+1.
    It follows that | A_ odd| = k, |
    B_ odd| =k, | B_ even| =k, and |
    A_ even| =k+1.
    
    Similarly, if z∈ V_ even, then |
    A_ odd| = k, | B_ odd| =k+1,
    | B_ even| =k, and | A_ even| =k.
    
    Consequently, (<ref>) holds whatever the parity of δ^+_T(z).
    

    
    
    
    Given k≥ 1, consider a tournament T, with 4k+2 vertices, such that s(T)=2k. 
    By Proposition <ref>, δ_T≥ 2k. 
   Thus, 
    T is near-regular. 
    We conclude by applying Proposition <ref>. 
    Therefore, it suffices to verify that (C1) and (C2) are satisfied. 
    
    By Proposition <ref>, σ_T(x,y)≥2k for distinct 
    x,y∈ V. 
    Moreover, it follows from Lemma <ref> that if x,y∈ V_ even or
    x,y∈ V_ odd (see Notation <ref>), then σ_T(x,y) is odd and hence σ_T(x,y)≥2k+1. 
    
    Lastly, seeking a contradiction, suppose that (C1) or (C2) are not satisfied. 
   One of the following situations occurs 
    
    
  * there are distinct x,y∈ V_ even such that σ_T(x,y)>2k+1,
    
  * there are distinct x,y∈ V_ odd such that σ_T(x,y)>2k+1,
    
  * there are x∈ V_ even and y∈ V_ odd such that σ
    _T(x,y)>2k.
    
    We obtain 
    
    ∑_{x,y}∈V2σ_T(x,y)   > (2k+1)| V_ even|2+(2k+1)| V_ odd|2+2k| V_ even|| V_ odd|
       =4k(2k+1)^2,

    which contradicts (<ref>). 
    Consequently, (C1) and (C2) are satisfied.
    




§ CONCLUDING REMARKS


    1. An n-tournament with n=4k+1 is called near-homogeneous 
    <cit.> if every unordered pair of its vertices belongs to k or (k+1) 3-cycles. 
    The existence of near-homogeneous tournaments is discussed in <cit.>, <cit.>, and <cit.>. 
    For n≡14 or n≡04, the n-tournaments given in 
    Theorem <ref> are not the only ones with a maximal simplicity index. Indeed, 
    let T be a near-homogeneous tournament T with 4k+1 vertices. 
    By adapting the proof of Theorem <ref>, we can verify that s(T)=2k-1. Moreover, by removing one vertex from T, we obtain a (4k)-tournament whose simplicity index is 2k-2. 
    Consequently, an analogue of Theorem <ref> does not exist when 
    l=2 or 3. 
    
	2. The score vector of a n-tournament T is the ordered sequence
of the scores of T listed in a non-decreasing order. Kirkland
<cit.> proved that the reversal index of an n-tournament T is equal to

    min{∑_i=1^js_i-j2:1≤ j≤ n},

where (s_1,s_2,…,s_n) is the score vector of T.

    An equivalent form of this result was obtained earlier by Li and 
Huang <cit.>. As a consequence, two tournaments with the 
same score vector have the same reversal index. This fact is not true 
for the simplicity index. Indeed, for an odd number n, consider the
n-tournament R_n whose vertex set is the additive group ℤ_n=
{0,1,…,n-1} of integers modulo n, such that i dominates j if 
and only if i-j ∈{1,…,(n-1)/2}. It is not difficult to 
verify that the tournament R_n is regular and simple. Moreover, by 
reversing the arc (0,n-1/2), we obtain a non-simple 
tournament. Hence, the simplicity index of R_n is 1. If n is prime 
and n≡ 3  4, the Paley tournament P_n is also regular but 
its simplicity index is n-1/2.
    
	Let T be an n-tournament with vertex set {v_1, … , v_n}. 
The sequences L_1=(δ^+_T(v_i))_1≤ i≤ n
and L_2=(δ^+_T(v_i,v_j))_1≤ i<j≤ n are frequently used in our study
of the simplicity index. It is natural to ask whether the simplicity index
of T can be expressed in terms of L_1 and L_2.

plain


