CONSTRUCTIVE QUASI-RAMSEY NUMBERS ANDTOURNAMENT RANKING ∗A.CZYGRINOW †,S.POLJAK †,AND V.R ¨ODL†SIAM J.D ISCRETE M ATH .c1999Society for Industrial and Applied Mathematics Vol.12,No.1,pp.48–63Abstract.A constructive lower bound on the quasi-Ramsey numbers and the tournament ranking function was obtained in [S.Poljak,V.R¨o dl,and J.Spencer,SIAM J.Discrete Math .,(1)1988,pp.372–376].We consider the weighted versions of both problems.Our method yields a polynomial time heuristic with guaranteed lower bound for the linear ordering problem.Key words.discrepancy,linear ordering problem,derandomization,regularity lemmaAMS subject classifications.68R05,68R10,05D99PII.S08954801973183011.Introduction.The quasi-Ramsey number g (n )is defined as the maximum discrepancy between the number of edges and nonedges that appears on some induced subgraph of any graph of order n ,i.e.,g (n )=min f max S ⊆[n ]|f (S )|,where [n ]=1,...,n ,f is a function from [n ]2into {−1,1}and f (S )= e ∈S 2f (e ).It is well known (Erd¨o s and Spencer [4])that for some positive,absolute constants c 1,c 2c 1n 3/2≤g (n )≤c 2n 3/2.The tournament ranking function h (n )is defined as the maximum size of an acyclic (undirected)subgraph that appears in any tournament of order n .More precisely,let T n be a tournament on n vertices,P n a transitive tournament on n vertices,and let |T n ∩P n |denote the number of common oriented arcs of T n and P n ;thenh (n )=min T n max P n|T n ∩P n |.It was shown by Spencer ([14],[15])that 12 n 2+c 1n 3/2≤h (n )≤12 n 2 +c 2n 3/2where c 1and c 2are positive absolute constants.The proof of the upper bound has been simplified by Fernandez de La Vega [5].Using the method of Spencer,the lower bound on h (n )can be obtained by an algorithmic argument from the lower bound on g (n ).Poljak,R¨o dl,and Spencer [12]proposed a fast O (n 3log n )time algorithm thatfinds a set S with discrepancy at least π−1/224n 3/2,the corresponding result for thetournament ranking function h (n )is also presented in [12].We will consider the∗Receivedby the editors March 12,1997;accepted for publication (in revised form)March 5,1998;published electronically January 29,1999./journals/sidma/12-1/31830.html †Department of Mathematics and Computer Science,Emory University,Atlanta,GA 30322(aczygri@,rodl@).48CONSTRUCTIVE TOURNAMENT RANKING49 weighted version of both problems.Our algorithm uses the Erd¨o s–Selfridge method of conditional expectations that was also applied in[12].For the lower bound on the quasi-Ramsey number g(n)we prove the following result.Theorem1.Let f:[n]2→R be a weight function on the edges of a complete graph K n.Then there is a subset S⊂[n]such that|f(S)|≥112√πn−1/2 e∈[n]2|f(e)|.Moreover,S can be found in O(n3lg(nd)lg n)time,provided the weights are integers from{−d,...,d}.The weighted version of the tournament ranking problem is also known as the linear ordering problem(see Gr¨o tschel,J¨u nger,and Reinelt[10]).The problem can be formulated in the following way:For a given tournament T with weight c(i,j)on the arc(i,j)∈T,find the orderingσof vertices for which the sumc(i,j)(i,j)∈T,σ(i)<σ(j)is a maximum.The list of applications of the linear ordering problem can be found in Lenstra[11].It includes applications from different areas of econometrics(input-output matrix analysis),sociology(social choice),psychology,machine scheduling, and even archaeology.The problem is NP-complete(see Garey and Johnson[8]),but there were several methods developed for solving small instances,e.g.,up to order of 50by Gr¨o tschel,J¨u nger,and Reinelt[10].Using the algorithm from Theorem1,we will get a polynomial time heuristic with a guaranteed lower bound.Theorem2.Let T be a tournament on n vertices with nonnegative weights w(e) on edges.Then there is an orderingσsuch that the sum of weights on edges that agree with the ordering is at least12+14√πn−1/2 K,where K is the total sum of weights.The orderingσcan be constructed by a O(n3lg (nd)lg n)time algorithm,provided weights are integers from{0,...,d}.From the upper bound on h(n),we conclude that there exists weight function for which the heuristic is best possible(up to a constant factor).Given a real numberρ,0<ρ<1a polynomial time approximation scheme (PTAS)for an optimization problem is an algorithm which when given an instance of size n,finds in polynomial time(in n)a solution of value at least(1−ρ)OP T,where OP T is the optimal ing the regularity lemma and its constructive version of Alon et al.[1],we design a PTAS for the“dense”quasi-Ramsey problem and for tournament ranking.For the quasi-Ramsey number we have the following theorem. Let f:E(K n)→{−1,1}and OP T(f)=max S⊆[n]|f(S)|.Theorem3.Let c>0befixed.If OP T(f)≥cn2,then for everyρ,0<ρ<1, there is a O(n2.4)time algorithm that constructs set S such that|f(S)|≥(1−ρ)OP T(f).50 A.CZYGRINOW,S.POLJAK,AND V.R¨ODLFor the tournament ranking we prove the following theorem for the case whenOP T(T n)=max Pn|T n∩P n|for a tournament T n.Theorem4.For0<ρ<1there is a polynomial time algorithm that constructsan orderingσof vertices of T n so that at least(1−ρ)OP T(T n)of arcs agree withσ.Note that Theorem3and Theorem4are in some sense counterparts to Theorem1and Theorem2.For example,Theorem1provides the existence of a polynomialtime algorithm tofind the set S with|f(S)|being the guaranteed minimum;Theorem3gives for everyρthe const(ρ)n2.4algorithm thatfinds a set S with f(S)being a(1−ρ)multiple of the optimal.Theorem3is based on the algorithmic version of theregularity lemma which“approximates the graph with error ofǫn2”.Therefore,itcan be applied only to instances with OP T(f)≥cn2.On the other hand,in case ofTheorem4,clearly OP T(T n)≥12 n2 and,therefore,a PTAS for the linear ordering problem can be obtained with no additional assumptions.Independently,very re-cently Frieze and Kannan[6]and[7]applied a version of the regularity lemma to themaximum subgraph problem,an equivalent to tournament ranking.Our argumentsdiffer from those in[7].The rest of the paper is organized as follows:In section2,for a given−→v1,...,−→v n∈R k,we will show how to construct sign vector−→X=(X1,...,X n) such thatX1−→v1+···+X n−→v n ≥cn−1/2ni=1 −→v i ,where −→u = k j=1|u j|.The algorithm is later applied to quasi-Ramsey numbers and to the linear ordering problem.Section3includes the applications of the regularity lemma.We conclude with an open problem in section4.2.Constructing sign vectors.Set−→1=(1,...,1)and−→0=(0,...,0),and for−→u and−→v from R k,let −→v,−→u denote the dot product of−→v and−→u,and −→u its l1-norm,i.e., −→u = k j=1|u j|.Wefirst establish two auxiliary facts.Lemma5.−→X∈{−1,1}n | −→1,−→X |=2nn−1⌊n2⌋.The proof can be found in[12].For1≤i≤n,let X i be independent randomvariables with distribution P r(X i=1)=P r(X i=−1)=12.Lemma6.Let b1,...,b n and a be real numbers and let u be the arithmetic mean of|b1|,...,|b n|.Then we have the following inequality:E(|a+X1b1+···+X n b n|)≥E(|a+X1u+···+X n u|).Proof.We may assume that all b i’s are nonnegative since the random variables Z i=sgn(b i)X i have the same distribution as X i,i.e.,E(|a+X1b1+···+X n b n|)= E(|a+Z1b1+···+Z n b n|)=E(|a+X1|b1|+···+X n|b n||).Given a vector−→w=(w1,...,w n)∈R n,let−−→w(l)be the vector obtained from−→w by cyclic shifting,with i th coordinate w(l)i=w i+l mod n for i=1,2,...,n.We haveE(|a+X1b1+···+X n b n|)=12n −→X∈{−1,1}na+n i=1X i b i=12n −→X1n n l=1a+n i=1X(l)i b iCONSTRUCTIVE TOURNAMENT RANKING 51≥12n −→X 1n na +n i =1n l =1X (l )i b i =12n −→Xa +n i =1X i u =E (|a +X 1u +···+X n u |).Lemma 7.Let −→v 1,...,−→v n ∈R k .ThenE ( X 1−→v 1+···+X n −→v n )≥ 2πn −1/2n i =1−→v i .Proof.From Lemma 5and Stirling‘s formula,we obtainE (|X 1+···+X n |)=12n −→X ∈{−1,1}n| −→1,−→X |=2n 2−n n −1⌊n 2⌋ ≥ 2n π.Let u j be the arithmetic mean of absolute values of the j th components of −→v 1,...,−→v n ,where j =1,...,k and let −→u =(u 1,...,u k ).Using Lemma 6with a =0we have E ( X 1−→v 1+···+X n −→v n )≥E ( X 1−→u +···+X n −→u )=k j =1E (|X 1u j +···+X n u j |)=k j =1u j E (|X 1+···+X n |)≥ 2πn −1/2n i =1−→v i.Corollary 8.For given −→v 1,...,−→v n ∈R k ,there is a choice of signs (X 1,...,X n )∈{−1,1}n such thatX 1−→v 1+···+X n −→v n ≥ 2πn −1/2n i =1−→v i .Next we will show that a vector −→X =(X 1,...,X n )from Corollary 8can beconstructed by a polynomial time algorithm.The idea is as follows.We have E ( X 1−→v 1+···+X n −→v n )≥T ,where T =cn −1/2 −→v i in the beginning.(For later convenience,we write the vectors in the reverse order.)Let us assume that signs X n ,X n −1,...,X i +1are chosen,one in each step,such thatE ( X n −→v n +···+X i +1−−→v i +1+X i −→v i +···X 1−→v 1 )≥T.At this moment there are two possible choices of X i ,and we take the better one (the one that maximizes the value of the expectation).As we cannot compute quickly the expected value E ( X n −→v n +···+X i +1−−→v i +1+X i −→v i +···+X 1−→v 1 )for general −→v i ,...,−→v 1,we compute E ( X n −→v n +···+X i +1−−→v i +1+X i −→u +···+X 1−→u )instead,where −→u is the component-wise “average”of −→v 1,...,−→v n .To describe the algorithm more precisely,we need to introduce some notation.For vectors −→a =(a 1,...,a k ),−→b =(b 1,...,b k )∈R k we define the polynomialsW (b j ,i,a j )=E (|b j +X i a j +···+X 1a j |)=i l =0 il 2−i |b j +a j (i −2l )|,52 A.CZYGRINOW,S.POLJAK,AND V.R ¨ODLW (−→b ,i,−→a )=k j =1W (b j ,i,a j )=k j =1i l =0i l 2−i |b j +a j (i −2l )|.For given −→v i =(v i 1,...,v ik )∈R k ,i =1,...,n ,let u ij denote the arithmetic mean of absolute values of the j th coordinates of −→v i ,...,−→v 1,i.e.,u ij =1i (|v ij |+···+|v 1j |),and set −→u i =(u i 1,...,u ik ).By −→S i we denote the partial sums:let −→S n =−→0and −→S i =X n −→v n +···+X i +1−−→v i +1,where X n ,...,X i +1have already been defined.(Observe that E ( −→S i +X i −→u i +...X 1−→u i )=W (−→S i ,i,−→u i ).)Now we chooseX i = 1if W (−→S i +−→v i ,i −1,−−→u i −1)≥W (−→S i −−→v i ,i −1,−−→u i −1),−1otherwise .We can formalize the algorithm in the following procedure.Algorithm input:vectors −→v 1,...,−→v n ∈R k output:sign vector (X 1,...,X n )−→S n =−→0for i=n downto 1begin if i <n then −→S i =X n −→v n +···+X i +1−−→v i +1compute W +=W (−→S i +−→v i ,i −1,−−→u i −1)and W −=W (−→S i −−→v i ,i −1,−−→u i −1)if W +≥W −then X i =1else X i =−1endreturn (X 1,...,X n )Proposition 9.The above algorithm returns a vector (X 1,...,X n )such thatX 1−→v 1+···+X n −→v n ≥ 2πn −1/2n i =1−→v i .Proof.Since E ( −→S i +X i −→v i +X i −1−−→u i −1+···X 1−−→u i −1 )=12W (−→S i +−→v i ,i −1,−−→u i −1)+12W (−→S i −−→v i ,i −1,−−→u i −1),we have W (−−→S i −1,i −1,−−→u i −1)=W (−→S i +X i −→v i ,i −1,−−→u i −1)≥E ( −→S i +X i −→v i +X i −1−−→u i −1+···+X 1−−→u i −1 )≥E ( −→S i +X i −→u i +···X 1−→u i )=W (−→S i ,i,−→u i ).The first inequality holds by the choice of X i ,the second one by Lemma 6,and the (obvious)fact that u ij is an arithmetic mean of v ij and i −1copies of u i −1j .HenceX n −→v n +···+X 1−→v 1 ≥W (−→S 1,1,−→u 1)≥···≥W (−→S n ,n,−→u n )andW (−→S n ,n,−→u n )=k j =0n l =0 n l 2−n |u nj (n −2l )|=k j =0u nj 2−n n l =0 n l |n −2l |≥ 2πn 1/2k j =0u nj = 2πn −1/2n i =1−→v i.CONSTRUCTIVE TOURNAMENT RANKING53 Proposition10.For k=O(n),the time complexity of the above algorithm is O(n3lg(nd)lg n)provided the vectors−→v1,...,−→v n∈R k are integral and|v ij|≤d.Proof.The procedure consists of n iterations for computing X n,...,X1.At each step we evaluate the expression W(−→S i,i,−→u i).To keep the computation in integers we replace it byi2i W(−→S i,i,−→u i)=il=0 i l k j=1|iS ij+(i−2l)iu ij| ,where−→S i=(S i1,...,S ik).The O(n2)combinatorial coefficients i l can be evaluated in advance using the identity i l = i−1l + i−1l−1 .Since i is of size at most n and the terms S ij,iu ij are of size nd,we can compute|iS ij+(i−2l)iu ij|in O(lg n lg(nd))steps. The sum k j=1|iS ij+(i−2l)iu ij|can be evaluated in O(k lg n lg(nd))steps.The number i l is less than2n and so the multiplication i l ·( k j=1|iS ij+(i−2l)iu ij|) can be computed in O(lg(2n)lg(ndk))steps.The total complexity of the proce-dure is O(n2(k lg n lg(nd)+n lg(ndk))),which when k=O(n)becomes O(n3lg (nd)lg n).Using the divide and conquer technique,one can design a slightly faster algorithm that gives a little worse results(for details consult[2]).We will now apply the algorithm to quasi-Ramsey numbers and to the linear ordering problem.Let us start with the proof of Theorem1.Proof of the Theorem1.We use the same technique that was applied in[12].Let K= e∈[n]2|f(e)|.First we need tofind a large cut of K n with edge weights|f(e)|. Obviously,by a greedy procedure we can construct disjoint sets X and Y such that X∪Y=[n]andx∈X,y∈Y|f(x,y)|≥K2.Indeed,assume that sets X i∪Y i=[i]have been constructed.Let W i X= j∈X i f(j,i+ 1)and W i Y= j∈Y i f(j,i+1).If W i X≤W i Y then set X i+1=X i∪{i+1}and Y i+1=Y i;otherwise,set X i+1=X i and Y i+1=Y i∪{i+1}.(Using the Goemans–Williamson algorithm from[9],one can possibly improve a constant in our theorem. However,since the result in[9]provides.878approximation of the optimal cut,itdoes not guarantee that the produced cut is bigger than K2.For slightly better cutalgorithms consult[13].)Let X={x1,...,x n1},Y={y1,...,y n2}.We assume n1≤n/2.Assign a vector−→v i=(v i1,...,v in2)to each vertex x i,where v ij=f(x i,y j),i=1,...,n1,j=1,...,ing the algorithm from section2,we construct a sign vector(X1,...,X n1) such thatX1−→v1+···+X n1−→v n1 ≥ 2πn1−1/2K2≥2π(n2)−1/2K2≥1√πn−1/2K.We partition sets X=X+∪X−and Y=Y+∪Y−by X+={x i,X i=1},54A.CZYGRINOW,S.POLJAK,AND V.R ¨ODL Y +={y j , n 1i =1X i f (x i ,y j )≥0}and X −=X −X +,Y −=Y −Y +.ThenX 1−→v 1+···+X n 1−→v n 1 =n 2 j =1|n 1 i =1X i f (x i ,y j )|= y ∈Y +,x ∈X +f (x,y )+y ∈Y +,x ∈X −−f (x,y )+ y ∈Y −,x ∈X +−f (x,y )+y ∈Y −,x ∈X −f (x,y ).Hence,we can choose X ∗∈{X +,X −}and Y ∗∈{Y +,Y −}such that |f (X ∗,Y ∗)|= y ∈Y ∗,x ∈X ∗f (x,y ) ≥14√πn −1/2K.We also have f (X ∗,Y ∗)=f (X ∗∪Y ∗)−f (X ∗)−f (Y ∗).Let S be one of X ∗,Y ∗,X ∗∪Y ∗for which |f (S )|≥13|f (X ∗,Y ∗)|.We see that S is such that |f (S )|≥112√πn −1/2K .Taking K = n2 we obtain a lower bound on the quasi-Ramsey numbers.Corollary 11.g (n )≥124√πn 3/2.We can now apply the result of Theorem 1to the linear ordering problem.Since the proof resembles the reasoning for the corresponding result in [12],we omit the details.Proof of Theorem 2.Let w ij be the weight of the pair {i,j }.Define f :[n ]2→Z as follows.For i <j ,f (i,j )= w ij if (i,j )∈T ,−w ij if (j,i )∈T.Let X ∗,Y ∗be the sets constructed in the proof of Theorem 1and let R =[n ]−X ∗−Y ∗.Construct ≺in the following way.Construct ranking on X ∗such that at least half of the arcs with both endpoints in X ∗are consistent with the ranking.(This can be obtained by considering an arbitrary ordering and its inverse.)Similarly construct rankings of Y ∗and R .Assume that f (X ∗,Y ∗)≥0;then for x ∈X ∗and y ∈Y ∗let x ≺y .Suppose that f (X ∗∪Y ∗,R )≥0;then for r ∈R and z ∈X ∗∪Y ∗let z ≺r .3.Applications of the regularity lemma.In this section we present the applications of the regularity lemma to both quasi-Ramsey and tournament ranking functions.A variant of the regularity lemma was applied for max-cut,graph bisection,and a quadratic assignment problem in Frieze and Kannan [6]and for computing frequencies in graphs in Duke,Lefmann,and R¨o dl [3].For simplicity,we restrict our discussion to the unweighted case,but similar results can be obtained for weighted graphs and tournaments.Let (V,E )be a graph on n vertices,for V 1,V 2⊂V ,V 1∩V 2=Ø,the density d (V 1,V 2)is defined as d (V 1,V 2)=e(V 1,V 2)|V 1||V 2|,where e (V 1,V 2)denotes thenumber of edges between V 1and V 2.Definition 12.A pair of subsets (V 1,V 2)is called ǫ-regular if for every W 1⊂V 1,with |W 1|≥ǫ|V 1|and for every W 2⊂V 2,with |W 2|≥ǫ|V 2||d (W 1,W 2)−d (V 1,V 2)|<ǫ.CONSTRUCTIVE TOURNAMENT RANKING55 Definition13.A partition V1∪V1∪···∪V k of V isǫ-regular if(i)||V i|−|V j||≤1for all i,j and(ii)all except at mostǫ k2 pairs(V i,V j)areǫ-regularLet us now state the powerful regularity lemma of Szemer´e di[16].Lemma14.For everyǫ>0and every integer l there exist N and L such that any graph with at least N vertices admits anǫ-regular partition V1∪···∪V k with l≤k≤L.The following version can be easily concluded from the original proof[16].Lemma15.For everyǫ>0and every integer l,there exists an N such that for any graph with at least N=N(l,ǫ)vertices and any partition P of the graph into m subsets,there exists L=L(l,ǫ,m)and anǫ-regular partition V1∪···∪V k with l≤k≤L which is a refinement of P.The partition postulated in both lemmas can be found in O(n2.4)time using the algorithm described in Alon et al.[1].Proof of Theorem3.The algorithm is as follows:Letǫ=ρc7.1.Find anǫ-regular partition V1∪···∪V k with k≥1ǫof the graph G1=(V,f−1(1)).2.Check all2k subsets of V of the form S= l∈L V l,where L⊂[k]and chooseS that maximizes| 1≤i<j≤k(2d ij−1)|V i∩S||V j∩S||.Note that if(V i,V j)isǫ-regular with density d ij in G1=(V,f−1(1)),then(V i,V j)is ǫ-regular with density1−d ij in G−1=(V,f−1(−1)).Given the partition V1∪···∪V k, we define f∗:2[n]→R in the following way.For T⊂[n],f∗(T)= 1≤i<j≤k(2d ij−1)|V i∩T||V j∩T|,where d ij=d(V i,V j).Fact16.Let T∗be a minimal set that maximizes f∗.Then for every l such that V l∩T∗=∅the sum j=l(2d lj−1)|V j∩T∗|>0.Proof.We use proof by contradiction.Assume that there exists l such that V l∩T∗=∅and j=l(2d lj−1)|V j∩T∗|≤0.Thenf∗(T∗)= 1≤i<j≤k(2d ij−1)|V i∩T∗||V j∩T∗|= j=l(2d lj−1)|V l∩T∗||V j∩T∗| + i,j=l,i<j(2d ij−1)|V i∩T∗||V j∩T∗|=|V l∩T∗| j=l(2d lj−1)|V j∩T∗| + i,j=l,i<j(2d ij−1)|V i∩T∗||V j∩T∗|≤ i,j=l,i<j(2d ij−1)|V i∩T∗||V j∩T∗|= 1≤i<j≤k(2d ij−1)|V i∩(T∗\V l)||V j∩(T∗\V l)|=f∗(T∗\V l)and we get the contradiction with minimality of T∗.Fact17.Let T∗be a minimal set that maximizes f∗.If T∗∩V l=∅,then V l⊂T∗.Note that Fact17implies that if S is a set found by the algorithm,then|f∗(S)|≥f∗(T∗)as the algorithm checks all the possible unions of V i’s to maximize|f∗|.In the same way,one can show that|f∗(S)|≥−f∗(L∗)where L∗maximizes−f∗.56A.CZYGRINOW,S.POLJAK,AND V.R ¨ODLProof .f ∗(T ∗)=|V l ∩T ∗|j =l (2d lj −1)|V j ∩T ∗|+ i,j =l,i<j (2d ij −1)|V i ∩T ∗||V j ∩T ∗|≤|V l |j =l (2d lj −1)|V j ∩T ∗|+ i,j =l,i<j (2d ij −1)|V i ∩T ∗||V j ∩T ∗|= 1≤i<j ≤k (2d ij −1)|V i ∩(T ∗∪V l )||V j ∩(T ∗∪V l )|=f ∗(T ∗∪V l ).Hence,f ∗(T ∗)≤f ∗(T ∗∪V l )and the equality holds only if |V l ∩T ∗|=|V l |as j =l (2d lj −1)|V j ∩T ∗|>0by the previous fact.It will be convenient to use the following notation.For two functions A (n )and B (n ),we write A (n )=ǫB (n )if |A (n )−B (n )|≤ǫn 2for n large enough.Our main lemma shows that f ∗is a “good”approximation for the discrepancy function f .Lemma 18.For every U ⊂V |f ∗(U )−f (U )|<72ǫn 2.Proof .We divide the proof into five claims.Claim 19.f (U )=ǫ2 {i,j }∈[k ]2f (V i ∩U,V j ∩U ).Indeed,since |V i |≤n k and also |V i ∩U |≤n k ,we infer that |f (V i ∩U )|≤ n k 2 ≤n 22k 2.Therefore,|f (U )− {i,j }∈[k ]2f (V i ∩U,V j ∩U )|= k i =1f (V i ∩U ) ≤k i =1|f (V i ∩U )|≤n 22k ≤ǫ2n 2which proves Claim 19.We partition [k ]2=S ∪I ∪R as follows:{i,j }∈S if and only if either |V i ∩U |<ǫ|V i |or |V j ∩U |<ǫ|V j |,{i,j }∈I if and only if the pair (V i ,V j )is not ǫ-regular,R =[k ]2\(S ∪I ).Claim 20.f (U )=ǫ R ∪I f (V i ∩U,V j ∩U ).[k ]2f (V i ∩U,V j ∩U )− R ∪If (V i ∩U,V j ∩U ) = S f (V i ∩U,V j ∩U ) ≤ S |f (V i ∩U,V j ∩U )|≤S |V i ∩U ||V j ∩U |≤ k 2 ǫn 2k 2=ǫ2n 2.Since |f (U )− [k ]2f (V i ∩U,V j ∩U )|≤ǫ2by Claim 19,we infer that |f (U )− R ∪I f (V i ∩U,V j ∩U )|≤ǫ.Claim 21.f (U )=3ǫ2 R f (V i ∩U,V j ∩U ).Indeed,there are at most ǫk 22irregular pairs and for each of them |f (V i ∩U,V j ∩U )|≤(n k )2,which impliesR ∪I f (V i ∩U,V j ∩U )− R f (V i ∩U,V j ∩U ) = If (V i ∩U,V j ∩U )CONSTRUCTIVE TOURNAMENT RANKING 57≤ I |f (V i ∩U,V j ∩U )|≤ǫk 22 n k 2=ǫ2n 2.Together with Claim 20,this shows that f (U )=3ǫ2 R f (V i ∩U,V j ∩U ).Claim 22.f (U )=5ǫ2 R (2d ij −1)|U ∩V i ||U ∩V j |.From Claim 21we know that f (U )=3ǫ2 R f (U ∩V i ,U ∩V j ).For {i,j }∈R wecan approximate f (U ∩V i ,U ∩V j )by (2d ij −1)|U ∩V i ||U ∩V j |with 2ǫ(n k )2error,namely,|f (U ∩V i ,U ∩V j )−(2d ij −1)|U ∩V i ||U ∩V j ||=|d (U ∩V i ,U ∩V j )|U ∩V i ||U ∩V j |−(1−d (U ∩V i ,U ∩V j ))|U ∩V i ||U ∩V j |−(2d ij −1)|U ∩V i ||U ∩V j ||=2|d (U ∩V i ,U ∩V j )−d ij ||U ∩V i ||U ∩V j |≤2ǫ n k2.Thus, R f (U ∩V i ,U ∩V j )− R (2d ij −1)U ∩V i ||U ∩V j || ≤k 222ǫ n k 2=ǫn 2which proves the claim.Claim 23.f (U )=7ǫ2f ∗(U ).By definition,f ∗(U )= [k ]2(2d ij −1)|U ∩V i ||U ∩V j |and by Claim 22we have f (U )=5ǫ2 R (2d ij −1)|U ∩V i ||U ∩V j |.Similar computations show [k ]2(2d ij −1)|U ∩V i ||U ∩V j |− R(2d ij −1)|U ∩V i |U ∩V j ≤I ∪S |(2d ij −1)||U ∩V i ||U ∩V j |≤ k 2 ǫ n k 2+ǫ n k 2 ≤ǫn 2.From Lemma 18we can easily conclude that the set S found by the algorithm has discrepancy |f (S )|≥(1−ρ)OP T (f ).Indeed,let T be such that |f (T )|=OP T (f )and S be the set chosen by the algorithm.From the note after Fact 17we know that |f ∗(S )|≥|f ∗(T )|and Lemma 18implies|f (S )−f ∗(S )|≤72ǫn 2,|f (T )−f ∗(T )|≤72ǫn 2.Thus,|f (S )|=|f ∗(S )+f (S )−f ∗(S )|≥|f ∗(S )|−|f (S )−f ∗(S )|≥|f ∗(T )|−72ǫn 2=|f (T )+f ∗(T )−f (T )|−72ǫn 2≥|f (T )|−|f ∗(T )−f (T )|−72ǫn 2≥|f (T )|−7ǫn 2.Since |f (T )|≥cn 2and ǫ=ρc 7we get |f (S )|≥(1−ρ)|f (T )|.We will now turn our attention to the linear ordering problem.Let T n =(V,A )be a tournament with V =[n ].We denote by OP T (T n )=max P n |T n ∩P n |,where max is taken over all transitive tournaments of order n .For a pair of subsets (V 1,V 2)with V 1∩V 2=∅we define the tournament density d T (V 1,V 2)as follows:d T (V 1,V 2)=arcs (V 1,V 2)|V 1||V 2|,where arcs (V 1,V 2)is the number of arcs that start at V 1and end at V 2.Note that d T (V 1,V 2)=1−d T (V 2,V 1).Proof of Theorem 4.The ranking σ′can be constructed by the following proce-dure:Let ǫ=(ρ12)2.1.Define an auxiliary graph G T as G T =(V,E ),where E ={{v i ,v j }:i <j,(v i ,v j )∈A }.Let l =1ǫand let U i ={v n l (i −1),...,v n l i }where i =1,...,l .2.Apply Lemma 15to obtain an ǫ-regular partition of V into V 1∪···∪V k ,which is a refinement of U 1∪···∪U l .3.Check all k !permutations of the sets {V 1,...,V k }to find a permutation σthat maximizes1≤i 1<i 2≤k d T (V σ(i 1),V σ(i 2))|V σ(i 1)||V σ(i 2)|.4.Extend σinside each of V i in an arbitrary way to obtain the ranking σ′of V .Let us first observe that in the first two steps of the algorithm we actually con-struct an ǫ-regular partition of the tournament T ,where the regularity is defined as follows.Definition 24.A pair of subsets (V 1,V 2)of V with V 1∩V 2=∅is ǫ-regular in tournament (V,A )if for every W 1⊂V 1with |W 1|≥ǫ|V 1|,and every W 2⊂V 2with |W 2|≥ǫ|V 2|,|d T (W 1,W 2)−d T (V 1,V 2)|≤ǫ.Then,since max U i <min U j for i <j ,the following fact holds.Fact 25.For i <j let V i ⊂U i and V j ⊂U j .If (V i ,V j )is ǫ-regular in the graph G T with density d ij ,then the pair (V i ,V j )is ǫ-regular in tournament T with density d T (V i ,V j )=d ij .Thus V 1∪···∪V k is an ǫ-regular partition of a tournament T .Without loss of generality,we may assume that the optimal ordering of V is 1<2<···<n .For a subset S ⊂V ,define h (S )as the number of arcs of T that agree with the optimal ordering,i.e.,h (S )=|{(i,j )∈A :i <j ,and i,j ∈S }|.For sets S 1,S 2⊂V with S 1∩S 2=∅let h (S 1,S 2)be the number of arcs of T between S 1and S 2that agree with the optimal ordering,i.e.,h (S 1,S 2)=|{(i,j )∈A :i <j,i ∈S 1,j ∈S 2ori ∈S 2,j ∈S 1}|.Note that h (S 1,S 2)=h (S 2,S 1).Define sets Z j ={n s (j −1),...,ns j },where s =1√ǫand i =1,...,s .Simple computations show the following.Fact 26.1. s j =1h (Z j )≤√ǫ2n 2;2. ki =1h (V i )≤ǫ2n 2.Let W ij =V i ∩Z j where i =1,...,k and j =1,...,s .We defineh ∗= 1≤j 1<j 2≤si 1=i 2d T (V i 1,V i 2)|W i 1j 1||W i 2j 2|.We will show that the number of arcs that agree with the optimal ordering cannot bemuch larger than h ∗,namely,the following.Lemma 27.h (V )≤h ∗+12(3√ǫ+5ǫ)n 2.Before giving a proof we will establish some auxiliary facts.Claim 28.h (V )≤ 1≤j 1<j 2≤s i 1=i 2h (W i 1j 1,W i 2j 2)+12(ǫ+√ǫ)n 2.Indeed,since {W ij }is a partition of V we haveh (V )≤1≤j 1<j 2≤si 1=i 2h (W i 1j 1,W i 2j 2)+k i =1h (V i )+s j =1h (Z j )≤1≤j 1<j 2≤si 1=i 2h (W i 1j 1,W i 2j 2)+ǫ2n 2+√ǫ2n 2by Fact 26.We adopt the notation from the proof of Lemma 18.Let [k ]×[k ]=R ∪I where (i 1,i 2)∈I if and only if (V i 1,V i 2)is not ǫ-regular in a tournament T .Note that if (i 1,i 2)∈I ,then either•V i 1,V i 2⊂U i for some i ∈[l ]or•(V i 1,V i 2)is irregular in the graph G T .Claim 29.h (V )≤ 1≤j 1<j 2≤s (i 1,i 2)∈R h (W i 1j 1,W i 2j 2)+12(3ǫ+√ǫ)n 2.To prove the claim we bound 1≤j 1<j 2≤s(i 1,i 2)∈I h (W i 1j 1,W i 2j 2)from above.1≤j 1<j 2≤s(i 1,i 2)∈Ih (W i 1j 1,W i 2j 2)=(i 1,i 2)∈Ij 1<j 2h (W i 1j 1,W i 2j 2)≤l ih (U i )+ǫ k 2 n 2k 2≤l n l 2+ǫ2n 2≤ǫn 2.Thus,h (V )≤1≤j 1<j 2≤s(i 1,i 2)∈Rh (W i 1j 1,W i 2j 2)+12(3ǫ+√ǫ)n 2.Finally,let [s ]×[k ]=B ∪S ,where S ={(j,i ),|W ij |<ǫ|V i |}.Claim 30.h (V )≤ 1≤j 1<j 2≤s{h (W i 1j 1,W i 2j 2),(i 1,i 2)∈R,(j 1,i 1),(j 2,i 2)∈B }+12(3ǫ+3√ǫ)n 2.Indeed,for (j 1,i 1)∈S we have h (W i 1j 1,W i 2j 2)<ǫ|V i 1||W i 2j 2|.Therefore,j 1<j 2{h (W i 1j 1,W i 2j 2),(j 1,i 1)∈S,or (j 2,i 2)∈S }≤[k ]×[k ],i 1=i 2j 1<j 2ǫ|V i 1||W i 2j 2|≤[k ]×[k ],i 1=i 2sj 1=1s j 2=1ǫ|V i 1||W i 2j 2|≤ǫs[k ]×[k ],i 1=i 2|V i 1||V i 2|≤ǫsk 2n 2k2=√ǫn 2as s =1√ǫ.Proof of Lemma 27.To show Lemma 27,we need to prove that h (V )≤h ∗+12(7ǫ+3√ǫ)n 2.For j 1<j 2we haveh (W i 1j 1,W i 2j 2)=arcs (W i 1j 1,W i 2j 2)=d T (W i 1j 1,W i 2j 2)|W i 1j 1||W i 2j 2|.Since |W i 1j 1|≥ǫ|V i 1|,|W i 2j 2|≥ǫ|V i 2|,and (V i 1,V i 2)is ǫ-regular we can approximated T (W i 1j 1,W i 2j 2)≤d T (V i 1,V i 2)+ǫ.Clearly,j 1<j 2i 1=i 2ǫ|W i 1j 1||W i 2j 2|=ǫ i 1=i 2 j 1<j 2|W i 1j 1||W i 2j 2|=ǫ i 1=i 2|V i 1||V i 2|≤ǫn 2.From Claim 30h (V )≤1≤j 1<j 2≤s{h (W i 1j 1,W i 2j 2),(i 1,i 2)∈R,(j 1,i 1),(j 2,i 2)∈B }+12(3ǫ+3√ǫ)n 2≤j 1<j 2i 1=i 2d T (V i 1,V i 2)|W i 1j 1||W i 2j 2|+12(5ǫ+3√ǫ)n 2=h ∗+12(5ǫ+3√ǫ)n 2.To complete the proof of Theorem 4,we first introduce an auxiliary digraph Kwith vertices corresponding to sets W ij ,weights on arcs corresponding to approxi-mation of the number of arcs that are consistent with optimal ordering.More for-mally,let K be a complete k -partite,symmetric digraph with a vertex set V (K )={y ij :i ∈[k ],j ∈[s ]}and with weights on arcs defined as follows:w (y i 1j 1,y i 2j 2)=d T (V i 1,V i 2)|W i 1j 1||W i 2j 2|if i 1=i 2,and w (y i 1j 1,y i 1j 2)=0.Let Y i = j ∈[s ]{y ij }.Vertex y ij ∈Y i corresponds to the set W ij ⊂V i and Y i corresponds to V i ,i ∈[k ]y ij to Z j .We define the ordering ≺of V (K )in the following way:y i 1j 1≺y i 2j 2if and only if either j 1<j 2or j 1=j 2and i 1<i 2.Thenh ∗= 1≤j 1<j 2≤s i 1=i 2w (y i 1j 1,y i 2j 2)≤y i 1j 1≺y i 2j 2w (y i 1j 1,y i 2j 2).The final part of the proof is based on the following lemma.Lemma 31(ordering lemma ).There exists a permutation σ:[k ]→[k ]such that for every ordering ≺of V (K )y i 1j 1≺y i 2j 2w (y i 1j 1,y i 2j 2)≤1≤i 1<i 2≤k j 1,j 2∈[s ]w (y σ(i 1)j 1,y σ(i 2)j 2).In other words,the sum of weights of the arcs is maximized for an ordering <inwhich Y i 1<Y i 2<···<Y i k .We postpone the proof of Lemma 31until the end of this section.Lemma 32.h ∗≤max σ1≤i 1<i 2≤k d T (V σ(i 1),V σ(i 2))|V σ(i 1)||V σ(i 2)|Proof.By the ordering lemma,there exists a permutation σ:[k ]→[k ]such thath ∗≤y i 1j 1≺y i 2j 2w (y i 1j 1,y i 2j 2)≤ 1≤i 1<i 2≤kj 1,j 2∈[s ]w (y σ(i 1)j 1,y σ(i 2)j 2)=1≤i 1<i 2≤kj 1,j 2∈[s ]d T (V σ(i 1),V σ(i 2))|W i 1j 1||W i 2j 2|=1≤i 1<i 2≤kd T (V σ(i 1),V σ(i 2))|V σ(i 1)||V σ(i 2)|。
