Constructive Quasi-Ramsey Numbers and Tournament Ranking.
A constructive lower bound on the quasi-Ramsey numbers and the tournament ranking function was obtained in [S. Poljak, V. Rdl, 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.
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.,
f
a function from [n] 2 into {-1, 1} and
It is well known (Erdos and Spencer [4]) that for some positive, absolute constants
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
| denote the number of common oriented arcs of T n and P n ; then
It was shown by Spencer ([14], [15]) that2
are 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, Rodl, and Spencer [12] proposed a fast O(n 3 log n) time algorithm that
finds a set S with discrepancy at least # -1/2n 3/2 , the corresponding result for the
tournament ranking function h(n) is also presented in [12]. We will consider the
# Received by the editors March 12, 1997; accepted for publication (in revised form) March 5,
1998; published electronically January 29, 1999.
http://www.siam.org/journals/sidma/12-1/31830.html
Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322
(aczygri@mathcs.emory.edu, rodl@mathcs.emory.edu).
CONSTRUCTIVE TOURNAMENT RANKING
weighted version of both problems. Our algorithm uses the Erdos-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.
Theorem 1.
# R be a weight function on the edges of a complete
graph K n . Then there is a subset S # [n] such that
|f(e)|.
Moreover, S can be found in O(n 3 lg (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 Grotschel, Junger, and Reinelt [10]). The problem can
be formulated in the following way: For a given tournament T with weight c(i,
the arc (i, find the ordering # of vertices for which the sum
c(i,
is a maximum. The list of applications of the linear ordering problem can be found
in Lenstra [11]. It includes applications from di#erent 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
50 by Grotschel, Junger, and Reinelt [10]. Using the algorithm from Theorem 1, we
will get a polynomial time heuristic with a guaranteed lower bound.
Theorem 2. 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 least
where K is the total sum of weights. The ordering # can be constructed by a O(n 3 lg
(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 < # < 1 a 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 - #)OPT , where
OPT is the optimal value. Using 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.
Theorem 3. Let c > 0 be fixed. If OPT (f) # cn 2 , then for every #, 0 < # < 1,
there is a O(n 2.4 that constructs set S such that
50 A. CZYGRINOW, S. POLJAK, AND V. R
ODL
For the tournament ranking we prove the following theorem for the case when
tournament T n .
Theorem 4. For 0 < # < 1 there is a polynomial time algorithm that constructs
an ordering # of vertices of T n so that at least (1 - #)OPT (T n ) of arcs agree with #.
Note that Theorem 3 and Theorem 4 are in some sense counterparts to Theorem
1 and Theorem 2. For example, Theorem 1 provides the existence of a polynomial
time algorithm to find the set S with |f(S)| being the guaranteed minimum; Theorem
3 gives for every # the const(#)n 2.4 algorithm that finds a set S with f(S) being a
multiple of the optimal. Theorem 3 is based on the algorithmic version of the
regularity lemma which "approximates the graph with error of #n 2 ". Therefore, it
can be applied only to instances with OPT (f) # cn 2 . On the other hand, in case of
Theorem 4, clearly OPT (T n
therefore, a PTAS for the linear ordering
problem can be obtained with no additional assumptions. Independently, very recently
Frieze and Kannan [6] and [7] applied a version of the regularity lemma to the
maximum subgraph problem, an equivalent to tournament ranking. Our arguments
di#er from those in [7]. The rest of the paper is organized as follows: In section 2, for
a given -# v 1 , . , -# v n # R k , we will show how to construct sign vector -#
such that
|. The algorithm is later applied to quasi-Ramsey numbers and
to the linear ordering problem. Section 3 includes the applications of the regularity
lemma. We conclude with an open problem in section 4.
2. Constructing sign vectors. Set -#
for -# u and -# v from R k , let # v , -# u # denote the dot product of -# v and -# u , and # u #
its l 1 - norm, i.e., # u
We first establish two auxiliary facts.
Lemma 5.
# .
The proof can be found in [12]. For independent random
variables with distribution P r(X and a be real numbers and let u be the arithmetic mean
of |b 1 |, . , |b n |. Then we have the following inequality:
E(|a
Proof. We may assume that all b i 's are nonnegative since the random variables
have the same distribution as X i , i.e., E(|a
E(|a Given a vector -#
w (l) be the vector obtained from -# w by cyclic shifting, with ith
coordinate w (l)
We have
a
a
CONSTRUCTIVE TOURNAMENT RANKING 51
a
Lemma 7. Let -# v 1 , . , -# v n # R k . Then
Proof. From Lemma 5 and Stirling's formula, we obtain
Let u j be the arithmetic mean of absolute values of the jth components of -# v 1 , . , -# v n ,
Corollary 8. For given -# v 1 , . , -# v n # R k , there is a choice of signs (X 1 , . ,
{-1, 1} n such that
Next we will show that a vector -# Corollary 8 can be
constructed by a polynomial time algorithm. The idea is as follows. We have
in the beginning. (For
later convenience, we write the vectors in the reverse order.) Let us assume that signs
are chosen, one in each step, such that
E(#X
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 -#
we compute E(#X n -#
the component-wise "average" of -# v 1 , . , -# v n .
To describe the algorithm more precisely, we need to introduce some notation.
For vectors -# a we define the polynomials
l
52 A. CZYGRINOW, S. POLJAK, AND V. R
ODL
l
For given -# the arithmetic mean
of absolute values of the jth coordinates of -# v i , . , -# v 1 , i.e.,
and set -# u we denote the partial sums: let -# S
that E(# S i +X i -# Now we choose
otherwise.
We can formalize the algorithm in the following procedure.
Algorithm
input: vectors -# v 1 , . , -# v n # R k
output: sign vector (X 1 , . ,
for i=n downto 1
begin
compute
else
return
Proposition 9. The above algorithm returns a vector (X 1 , . , X n ) such that
Proof. Since
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 - 1 copies of u i-1j .
Hence
and
l
l
CONSTRUCTIVE TOURNAMENT RANKING 53
Proposition 10. For O(n), the time complexity of the above algorithm is
O(n 3 lg (nd) lg n) provided the vectors -# v 1 , . , -# v n # R k are integral and |v ij | # d .
Proof. The procedure consists of n iterations for computing X n , . , X 1 . At each
step we evaluate the expression W ( -# S i , i, -# u i ). To keep the computation in integers we
replace it by
l
where
l # can be evaluated
in advance using the identity # i
l # i-1
l # i-1
l-1 # . Since i is of size at most n and the
are of size nd, we can compute |iS ij ij | in O(lg n lg (nd)) steps.
The sum # k
can be evaluated in O(k lg n lg (nd)) steps. The
number # i
l # is less than 2 n and so the multiplication # i
l # k
can be computed in O(lg steps. The total complexity of the procedure
is
(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 Theorem 1.
Proof of the Theorem 1. We use the same technique that was applied in [12]. Let
First we need to find 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#X,y#Y
KIndeed, assume that sets X i
1) and W i
1). If W i
Y then set X
#{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 .878 approximation of the optimal cut, it
does not guarantee that the produced cut is bigger than K
2 . For slightly better cut
algorithms consult [13].)
vector -# v to each vertex x i ,
1, . , n 2 . Using the algorithm from section 2, we construct a sign vector (X 1 , . ,
such that
n) -1/2 K
We partition sets
54 A. CZYGRINOW, S. POLJAK, AND V. R
ODL
|
Hence, we can choose X # {X
We also have f(X # , Y # be one of X # , Y # ,
We see that S is such that |f(S)| #12 #
Taking
# we obtain a lower bound on the quasi-Ramsey numbers.
Corollary 11.
We can now apply the result of Theorem 1 to 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}.
as follows. For
be the sets constructed in the proof of Theorem 1 and let
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. 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 Rodl [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
, the density d(V 1 , defined as d(V 1 ,
denotes the
number of edges between V 1 and V 2 .
Definition 12. A pair of subsets called #-regular if for every W 1
with |W 1 | #|V 1 | and for every W
CONSTRUCTIVE TOURNAMENT RANKING 55
Definition 13. A partition of V is #-regular if
(ii) all except at most # k
are #-regular
Let us now state the powerful regularity lemma of Szemeredi [16].
Lemma 14. For every # > 0 and every integer l there exist N and L such that
any graph with at least N vertices admits an #-regular partition
l # k # L.
The following version can be easily concluded from the original proof [16].
Lemma 15. For every # > 0 and every integer l, there exists an N such that for
any graph with at least vertices and any partition P of the graph into
m subsets, there exists m) and an #-regular partition
l # k # L which is a refinement of P .
The partition postulated in both lemmas can be found in O(n 2.4 using the
algorithm described in Alon et al. [1].
Proof of Theorem 3. The algorithm is as follows: Let #c
7 .
1. Find an #-regular partition
of the graph G
2. Check all 2 k subsets of V of the form choose
S that maximizes | #
Note that if (V i ,
#-regular with density 1-d ij in G-1 = (V, f -1 (-1)). Given the partition V 1 #V k ,
we define f
R in the following way. For T # [n], f # (T
Fact 16. Let T # be a minimal set that maximizes f # . Then for every l such that
the sum
Proof. We use proof by contradiction. Assume that there exists l such that
and we get the contradiction with minimality of T # .
Fact 17. Let T # be a minimal set that maximizes f # . If T # V l #, then
Note that Fact 17 implies that if S is a set found by the algorithm, then |f # (S)| #
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 # .
A. CZYGRINOW, S. POLJAK, AND V. R
ODL
Proof.
Hence, f # (T # f # (T # V l ) and the equality holds only if |V l # T # l | as
by the previous fact.
It will be convenient to use the following notation. For two functions A(n) and
B(n), we write 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)| < 7
Proof. We divide the proof into five claims.
Indeed, since |V i | # n
and also
, we infer that |f(V i #U)| # n
Therefore,
which proves Claim 19.
We partition [k] I #R as follows: {i, j} # S if and only if either |V i #U | <
I if and only if the pair (V i ,
we infer that |f(U) -
Indeed, there are at most # k 2irregular pairs and for each of them |f(V i #U,V j #
R#I
CONSTRUCTIVE TOURNAMENT RANKING 57
I
Together with Claim 20, this shows that
From Claim 21 we know that
can approximate f(U #
namely,
Thus,
which proves the claim.
By definition, f #
| and by Claim 22 we have
computations show
From Lemma we can easily conclude that the set S found by the algorithm has
discrepancy |f(S)| # (1 - #)OPT (f ). Indeed, let T be such that |f(T
and S be the set chosen by the algorithm. From the note after Fact 17 we know that
Thus,
58 A. CZYGRINOW, S. POLJAK, AND V. R
ODL
Since |f(T )| # cn 2 and #cwe get |f(S)| # (1 - #)|f(T )|.
We will now turn our attention to the linear ordering problem. Let T
be a tournament with We denote by OPT (T n
is taken over all transitive tournaments of order n. For a pair of subsets
with we define the tournament density d T
is the number of arcs that start at V 1 and end at V 2 .
Note that d T
Proof of Theorem 4. The ranking # can be constructed by the following proce-
dure: Let #) 2 .
1. Define an auxiliary graph G T as G
and let U
l (i-1) , . , v n
l i } where
2. Apply Lemma 15 to obtain an #-regular partition of V into
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 maximizes # 1#i1<i2#k d T (V #(i1
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 construct
an #-regular partition of the tournament T , where the regularity is defined as
follows.
Definition 24. A pair of subsets is #-regular in
tournament (V, for every W 1 and every W 2 # V 2 with
|d
Then, since maxU i < minU j for i < j, the following fact holds.
Fact 25. For i < #-regular in the graph
G T with density d ij , then the pair (V i , tournament T with density
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., S}|. For sets
with be the number of arcs of T between S 1 and S 2 that
agree with the optimal ordering, i.e., h(S 1 ,
{ n
s
(j -1), . , n
s
computations show the following.
Fact 26.
1. # s
2.
1#j1<j2#s
We will show that the number of arcs that agree with the optimal ordering cannot be
much larger than h # , namely, the following.
Lemma 27. h(V
Before giving a proof we will establish some auxiliary facts.
CONSTRUCTIVE TOURNAMENT RANKING 59
Indeed, since {W ij } is a partition of V we have
1#j1<j2#s
s
1#j1<j2#s
by Fact 26.
We adopt the notation from the proof of Lemma 18. Let [k]
I if and only if
) is not #-regular in a tournament T . Note that if
.
.
is irregular in the graph G T .
To prove the claim we bound
) from above.
1#j1<j2#s
l
Thus,
1#j1<j2#s
Finally, let [s]
Indeed, for (j 1 ,
Therefore,
s
s
as
Proof of Lemma 27. To show Lemma 27, we need to prove that h(V
A. CZYGRINOW, S. POLJAK, AND V. R
ODL
is #-regular we can approximate
From Claim
1#j1<j2#s
To complete the proof of Theorem 4, we first introduce an auxiliary digraph K
with vertices corresponding to sets W ij , weights on arcs corresponding to approximation
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
with weights on arcs defined as follows: w(y
corresponds to the set W ij # V i and Y i corresponds to V i , #
to Z j . We define the ordering # of V (K) in the following way: y
if and
only if either
1#j1<j2#s
w(y
w(y
The final part of the proof is based on the following lemma.
Lemma (ordering lemma). There exists a permutation # : [k] # [k] such that
for every ordering # of V (K)
w(y
w(y #(i1 )j 1
In other words, the sum of weights of the arcs is maximized for an ordering < in
which Y i 1
. We postpone the proof of Lemma 31 until the end of
this section.
Proof. By the ordering lemma, there exists a permutation # : [k] # [k] such that
w(y
w(y #(i1 )j 1
CONSTRUCTIVE TOURNAMENT RANKING 61
The number of arcs that are consistent with constructed ranking # is at least
which by Lemma 27 and Lemma
32 is at least h(V
. When we combine it with the lower bound
mentioned in the introduction we conclude that the number
of arcs that are consistent with constructed ordering is at least (1 - #)OPT (T n ) since
We will now prove the ordering lemma.
Proof of the ordering lemma. To prove the lemma, it is su#cient to show that the
sum of weights of arcs is maximized for an ordering in which every Y i is an interval.
Let # be an ordering of V (K). We denote by h(#) the sum
w(y
and for every Y i , where we define a gap-number as the
minimum number of intervals I ij such that Y
Note that the gap-numbers
depend on the ordering of V (K).
there exists an ordering # such that
1. h(# h(# ),
2. gap# (Y i 0
3. gap# (Y i
Applying the claim to Y 1 , Y 2 , . , Y k , we construct the ordering in which every
are intervals.
Proof of the claim. Since gap# (Y i 0
there exist two intervals I
that I i
and
I
Without loss of generality we may assume that d T
|. Then the sum of the weights
of arcs between intervals I
which equals the sum of weights of arcs between intervals
I
Therefore, we can reduce the number of gaps of Y i 0
4. Conclusions and an open problem. In this paper, we considered the
weighted version of discrepancy and tournament ranking problems. In the first part
of the paper we generalized the approach from [12] to weighted graphs. In the second
part we presented algorithms for both problems which were based on the algorithmic
regularity lemma. We want to conclude with the following open problem.
A. CZYGRINOW, S. POLJAK, AND V. R
ODL
Open Problem 1. For a given n, construct an m  n matrix of
+1's and -1's with m small which has the following property. For every vector -# u #
{-1, 1} nm
for some constant c.
By probabilistic method one can show the existence of matrix M with
and a constant su#ciently small. Note that Hadamard matrices do not
possess the required property, taking -# u as one of the row vectors of M results in
Let us observe that we can use the solution matrix M to our initial problem of
finding a sign vector. Namely, for given -# v 1 , . , -# v n # {-1, 1} n , there is an O(n 2 m)
algorithm that finds -# such that
Indeed, let -# We can construct a sign
vector in the following way: For every row vector -# m i of matrix M we compute
and we choose -# m i such that the sum is the largest.
By the property of the matrix M , we know that for every vector -# w j ,
This implies that if a vector
chosen by the algorithm, then # n
We
verify that
In computing the sum
numbers of size O(1). Note that
the same argument can be repeated (resulting in di#erent constant c) if -# v 1 , . , -# v n #
As long as m is smaller then n lg n this will improve the time complexity of results
in [12]. A similar question can be asked for the weighted case.

Acknowledgments

. We would like to thank referees for helpful comments and
suggestions.



--R

The algorithmic aspects of the regularity lemma
On the Linear Ordering Problem
A fast algorithm for computing frequencies in a given graph
Probabilistic Methods in Combinatorics

The regularity lemma and approximation schemes for dense prob- lems
Quick Approximation to Matrices and Applications
Computers and Intractability.

A cutting plane algorithm for the linear ordering problem
Sequencing by Enumerative Methods
Tournament ranking with expected profit in polynomial time
A polynomial time heuristic for certain subgraph optimization problems with guaranteed lower bound
Optimal ranking of tournaments
Nonconstructive Methods in Discrete Mathematics

--TR

--CTR
Penny Haxell , Brendan Nagle , Vojtch Rdl, Integer and fractional packings in dense 3-uniform hypergraphs, Random Structures & Algorithms, v.22 n.3, p.248-310, May
Y. Dementieva , P. E. Haxell , B. Nagle , V. Rdl, On characterizing hypergraph regularity, Random Structures & Algorithms, v.21 n.3-4, p.293-335, October 2002
V. Rdl , M. Schacht , M. H. Siggers , N. Tokushige, Integer and fractional packings of hypergraphs, Journal of Combinatorial Theory Series B, v.97 n.2, p.245-268, March, 2007
Eldar Fischer, Testing graphs for colorable properties, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.873-882, January 07-09, 2001, Washington, D.C., United States
Packing directed cycles efficiently, Discrete Applied Mathematics, v.155 n.2, p.82-91, January, 2007
linear ordering problem;discrepancy;derandomization;regularity lemma