Asymptotic Size Ramsey Results for Bipartite Graphs.
We show that $\lim_{n\to\infty}\hat r(F_{1,n},\dots,F_{q,n},F_{q+1},\dots,F_{r})/n$ exists, where the bipartite graphs $F_{q+1},\dots,F_r$ do not depend on $n$ while, for $1\le i\le q$, $F_{i,n}$ is obtained from some bipartite graph $F_i$ with parts $V_1\cup V_2=V(F_i)$ by duplicating each vertex $v\in V_2$ $(c_v+o(1))n$ times for some real $c_v>0$.In fact, the limit is the minimum of a certain mixed integer program. Using the Farkas lemma we show how to compute it when each forbidden graph is a complete bipartite graph, in particular answering the question of Erdos, Faudree, Rousseau, and Schelp [Period.\ Math.\ Hungar., 9 (1978), pp. 145--161], who asked for the asymptotics of $\hat r(K_{s,n},K_{s,n})$ for fixed $s$ and large $n$. Also, we prove (for all sufficiently large $n$) the conjecture of Faudree, Rousseau, and Sheehan in [Graph Theory and Combinatorics, B. Bollobas, ed., Cambridge University Press, Cambridge, UK, 1984, pp. 273--281] that $\hat r(K_{2,n},K_{2,n}) =18n-15$.
Introduction
. Let be an r-tuple of graphs which are called for-
bidden. We say that a graph G arrows any r-colouring of E(G),
the edge set of G, there is a copy of F i of colour i for some i 2 [r] := rg. We
denote this arrowing property by G !
The (ordinary) Ramsey number asks for the minimum order of such G. Here,
however, we deal exclusively with the size Ramsey number
which is the smallest number of edges that an arrowing graph can have.
Size Ramsey numbers seem hard to compute, even for simple forbidden graphs.
For example, the old conjecture of Erd}os [6] that ^ r(K 1;n ; K 3
recently been disproved in [16], where it is shown that ^
any xed 3-chromatic graph F . (Here, K m;n is the complete bipartite graph with
parts of sizes m and n; Kn is the complete graph of order n.)
This research initiated as an attempt to nd the asymptotics of ^ r(K 1;n
xed graph F . The case treated in [17] (and [16] deals with
What can be said if F is a bipartite graph?
Faudree, Rousseau and Sheehan [11] proved that
for every m  9 if n is su-ciently large (depending on m) and stated that their
method shows that ^ r(K 1;n ; K 2;2 They also observed that K s;2n arrows the
is a cycle of order 2s; hence ^ r(K 1;n ; C 2s )  2sn.
Let P s be the path with s vertices. Lortz and Mengersen [14] showed that
conjectured that
this is sharp for any s  4 provided n is su-ciently large, that is,
Supported by a Research Fellowship, St. John's College, Cambridge. Part of this research was
carried out during the author's stay at the Humboldt University, Berlin, sponsored by the German
Academic Exchange Service (DAAD).
y DPMMS, Centre for Mathematical Sciences, Cambridge University, Cambridge CB3 0WB, Eng-
land, O.Pikhurko@dpmms.cam.ac.uk
The conjecture was proved for 4  s  7 in [14].
Size Ramsey numbers ^
(and in some
papers F 1 is a small star) are also studied in [9, 5, 2, 3, 8, 10, 13, 12] for example.
It is not hard to see that, for xed s
This follows, for example, by assuming that s
considering K v1
s
e. The latter graph
has the required arrowing property. Indeed, for any r-colouring, each vertex of V 2 is
incident to at least s edges of same colour; hence there are at least v 2 monochromatic
K s;1 -subgraphs and some S 2 V1
s
appears in at least rtn such subgraphs of which
at least tn have same colour.
Here we will show that the limit lim exists if each forbidden
graph is either a xed bipartite graph or a subgraph of K s;btnc which 'dilates'
uniformly with n (the precise denition will be given in Section 2). In particular,
tends to a limit for any xed bipartite graph F .
The limit value can in fact be obtained as the minimum of a certain mixed integer
program (which does depend on n). We have been able to solve the MIP when
each F i;n is a complete bipartite graph. In particular, this answers a question by
Faudree, Rousseau and Schelp [9, Problem B] who asked for the asymptotics
of Working harder on the case we prove (for all su-ciently large
n) the conjecture of Faudree, Rousseau and Sheehan [11, Conjecture 15] that
where the upper bound is obtained by considering K 3;6n
fortunately, the range on n from (1.3) is not specied in [11], although it is stated
there that ^ r(K 2;2 ; K 2;2 where the upper bound follows apparently from K 6
Unfortunately, our MIP is not well suited for practical calculations and we were
not able to compute the asymptotics for any other non-trivial forbidden graphs; in
particular, we had no progress on (1.1). But we hope that the introduced method will
produce more results: although the MIP is hard to solve, it may well be possible that,
for example, some manageable relaxation of it gives good lower or upper bounds.
Our method does not work if we allow both vertex classes of forbidden graphs to
grow with n. In these settings, in fact, we do not know the asymptotics even in the
simplest cases. For example, the best known bounds on seem to
be r < 3
(Erd}os and Rousseau [10]).
Our theorem on the existence of the limit can be extended to generalized size
Ramsey problems; this is discussed in Section 5.
2. Some Denitions. We decided to gather most of the denitions in this section
for quick reference.
We assume that bipartite graphs come equipped with a xed bipartition V
embeddings need not preserve it. We denote v i
For A  V 1
ASYMPTOTIC SIZE RAMSEY RESULTS 3
where F (v) denotes the neighbourhood of v in F . (We will write (v), etc., when
the encompassing graph F is clear from the context.) Clearly, in order to determine
F (up to an isomorphism) it is enough to have
This motivates the following denitions.
A weight f on a set V (f) a sequence (f A ) A22 V (f) of non-negative reals. A bipartite
graph F agrees with f if V 1
A sequence of bipartite graphs (Fn ) n2N is a dilatation of f (or dilates f ) if each Fn
agrees with f and
jF A
(Of course, the latter condition is automatically true for all A
Clearly, e(Fn
so we call e(f) the size
of f . Also, the order of f is and the degree of x 2 V (f) is
A3x
Clearly,
For example, given t 2 R>0 , the sequence (K s;dtne ) n2N is the dilatation of k s;t ,
where the symbol k s;t will be reserved for the weight on [s] which has value t on [s]
and zero otherwise. (We assume that V 1 (K s;dtne It is not hard to see that
any sequence of bipartite graphs described in the abstract is in fact a dilatation of
some weight.
We write F  f if for some bipartition V there is an injection
such that for any A  V 1 dominated by a vertex of V 2
is This notation is justied by the following
trivial lemma.
Lemma 2.1. Let (Fn ) n2N be a dilatation of f . If F  f , then F is a subgraph of Fn
for all su-ciently large n. Otherwise, which is denoted by F 6 f , no Fn contains F .
Let f and g be weights. Assume that v(f)  v(g) by adding new vertices to
letting g be zero on all new sets. We write f  g if there is an injection
(g) such that
This can be viewed as a fractional analogue of the subgraph relation F  G: h
embeds how much of F A  V 2 mapped into G B .
The fractional -relation enjoys many properties of the discrete one. For example,
A3x
fA
A3x
The following result is not di-cult and, in fact, we will implicitly prove a sharper
version later (with concrete estimates of ), so we omit the proof.
Lemma 2.2. Let (Fn ) n2N and (Gn ) n2N be dilatations of f and g respectively.
implies that for any  > 0 there is n 0 such that Fn  Gm for any n  n 0
)n. Otherwise, which is denoted by f 6 g, there is  > 0 and n 0 such
that Fn 6 Gm for any n  n 0 and m  (1
An r-colouring c of g is a sequence (c A1 ;:::;A r ) of non-negative reals indexed by
r-tuples of disjoint subsets of V (g) such that
c
The i-th colour subweight c i is dened by V
c
The analogy: to dene an r-colouring of G, it is enough to dene, for all disjoint
how many vertices of G A1 [[Ar are connected, for all i 2 [r], by
colour i precisely to A i . Following this analogy, there should have been the equality
sign in (2.2); however, the chosen denition will make our calculations less messy
later.
3. Existence of Limit. Let r  q  1. Consider a sequence
Assume that F i does not have an isolated vertex (that is, x
We say that a weight g arrows F (denoted by g ! F) if for any r-colouring c
of g we have F i  c i for some i 2 [r]. Dene
The denition (3.1) imitates that of the size Ramsey number and we will show
that these are very closely related indeed. However, we need a few more preliminaries.
considering k a;b which arrows F if, for example,
su-ciently large, cf. (1.2). Let l be an integer greater
lg.
Proof. Let  > 0 be any real smaller than d 0 . Let g ! F be a weight with v(g) > l
and
To prove the theorem, it is enough to construct g 0 ! F with
We have d(x)  (^r(F)
the weight g 0 on V (g) n fxg by
We claim that g 0 arrows F. Suppose that this is not true and let c 0 be an F-free
r-colouring of g 0 . We can assume that
ASYMPTOTIC SIZE RAMSEY RESULTS 5
Dene c by
c
Anfxg d i
where we denote
A if g 0
A > 0, and
The reader can check that c is an r-colouring of g.
By the assumption on g, we have F i  c i for some i 2 [r]. But this embedding
cannot use x because for we have d c i
A d i
A d i
is too small, see (2.1). But c i;A  c 0
i , which is the
desired contradiction.
Hence, to compute ^ r(F) it is enough to consider F-arrowing weights on
only.
Lemma 3.2. There exists
r(F). (And we call
such a weight extremal.)
Proof. Let gn ! F be a sequence with V (gn )  L such that e(g n ) approaches
r(F). By choosing a subsequence, assume that V (g n ) is constant and
exists for each A 2 2 L . Clearly, remains to show that g ! F.
Let c be an r-colouring of g. Let - be the smallest slack in inequalities (2.2).
Choose su-ciently large n so that jg n;A gA j < - for all A 2 2 L . We have
that is, c is a colouring of gn as well. Hence, F i  c i for some i, as required.
Now we are ready to prove our general theorem. The proof essentially takes care
of itself. We just exploit the parallels between the fractional and discrete universes,
which, unfortunately, requires messing around with various constants.
Theorem 3.3. Let be a dilatation of f i , i 2 [q]. Then, for all su-ciently
large n,
In particular, the limit lim
exists.
Proof. Let
We will prove that
By Lemma 3.2 choose an extremal weight g on L. Dene a bipartite graph
G as follows. Choose disjoint from each other (and from L) sets G A with jG A
6 OLEG PIKHURKO
In G we connect x 2 L to all of
G A if x 2 A. These are all the edges. Clearly,
A22 L
A22 L
as required. Hence, it is enough to show that G has the arrowing property.
Consider any r-colouring c : E(G) ! [r]. For disjoint sets
fy
(jC
0; otherwise,
that is, c is an r-colouring of g. Hence, F i  c i for some i 2 [r].
Suppose that i 2 [q]. By the denition, we nd appropriate
We aim at proving that F i;n  G i , where G i  G is the colour-i subgraph. Partition
F A
so that
. This is possible for any A: if w
for at least one B, then
B22 L
B22 L
i;n j:
and we have
Hence, we can extend h to the whole of V mapping [ h(A)B W A;B injectively
into B.
Suppose that i 2 [q+1; r]. The relation F i  c i means that there exist appropriate
L. We view h as a partial embedding of F i
into G i and will extend h to the whole of V
Take consecutively y There is B i  L such that c i;B i > 0 and h((y))
. The inequality c i;B i > 0 implies that there are disjoint B j 's, j 2 [r] n fig, such
that c B1 ;:::;B r > 0. Each vertex in CB1 ;:::;B r is connected by colour i to the whole of
h((y)). The inequality c B1 ;:::;B r > 0 means that jCB1 ;:::;B r
we can always extend h to y. Hence, we nd an F i -subgraph of colour i in this case.
Thus the constructed graph G has the desired arrowing property, which proves
the upper bound.
ASYMPTOTIC SIZE RAMSEY RESULTS 7
As the
lower bound, we show that, for all su-ciently large n,
Suppose on the contrary that we can nd an arrowing graph G contradicting (3.4).
Let L  V (G) be the set of vertices of degree at least d 0 n=2 in G. From d 0 njLj=4 <
e(G) < ln it follows that jLj  4l=d 0 . For A 2 2 L , dene
We have
A22 L
A22 L
Thus there is an F-free r-colouring c of g. We are going to exhibit a contradictory
r-colouring of E(G).
For each choose any disjoint sets CB1 ;:::;B r  G B (indexed by r-tuples of
disjoint sets partitioning B) such that they partition G B and
This is possible because
For colour the edge fx; yg by colour j. All the
remaining edges of G (namely, those lying inside L or inside V (G) n L) are coloured
with colour 1.
There is i 2 [r] such that G i  G, the colour-i subgraph, contains a forbidden
subgraph.
Suppose that be an embedding. If n is large, then
which implies that h(V 1
for
All other wA;B 's are set to zero. For A
B22 L
wA;B  (jF A
For
that is, h (when restricted to V (f i )) and w demonstrate that f i  c i , which is a
contradiction.
Suppose that i 2 [q +1; r]. Let V 1 consists of those vertices which are mapped
by This is a legitimate bipartition
of F i because any colour-i edge of G connects L to V (G)nL. Let y
together with c B1 ;:::;B r > 0 shows that F i  g i . This contradiction
proves the theorem.
4. Complete Bipartite Graphs. Here we will compute asymptotically the size
Ramsey number if each forbidden graph is a complete bipartite graph. More precisely,
we show that in order to do this it is enough to consider only complete bipartite graphs
having the arrowing property.
Theorem 4.1. Let r  2 and q  1. Suppose that we are given t
there exist
Proof. Let us rst describe an algorithm nding extremal s and t. Some by-product
information gathered by our algorithm will be used in the proof of the ex-
tremality of k s;t ! F.
Choose l 2 N bigger than
which is the same deni-
tion of l as that before Lemma 3.1.
We claim that l > , where
1). Indeed, take any extremal f ! F
without isolated vertices. The proof of Lemma 3.1 implies that d(x)  t 0 for any
necessarily v(f) > , which implies the claim.
For each integer s 2 [+1; l], let t 0
s > 0 be the inmum of t 2 R such that k s;t ! F.
Also, let  s be the set of all sequences a non-negative integers with
a
For a sequence a = (a and a set
A of size
a
consist of all sequences r ) of sets partitioning
A with jA
We claim that t 0
s is sol(L s ), the extremal value of the following linear program
a2s w a over all sequences (w a ) a2s of non-negative reals
such that
a2s
w a
a i
1 The weight k s;t does not arrow F for t < sol(L s ).
To prove this, let
an r-colouring c of k s;t by
s
a
other c's are zero. It is indeed a colouring:
a2s
a
a2s
We have k s i For example, for
, we have
a2s
a
a2s
w a
s
a2s
w a
s
BS
ASYMPTOTIC SIZE RAMSEY RESULTS 9
Also, K s
some
Suppose that the claim is not true and we can nd an F-free r-colouring c of k s;t .
By the denition, c A1 ;:::;A
c
so we can pick x 2 A j and set c A1 ;:::;A increasing c :::;A j nfxg;:::;A i [fxg;::: by
c. Clearly, c remains an F-free colouring. Thus, we can assume that all the c's are
zero except those of the form c A , A 2 [s]
a
for some a 2  s . Now, retracing back our
proof of Claim 1, we obtain a feasible solution w
a
a larger objective function, which is a contradiction. The claim is proved.
Thus, t 0
is an upper bound on ^ r(F).
Let us show that in fact
We rewrite the denition of ^ r(F) so that we can apply the Farkas Lemma. The
proof of the following easy claim is left to the reader.
weights g on L such that there do not exist non-negative
reals
a with the following properties
a
A22 L
a
A
c A  t
L
Let g be any feasible solution to the above problem. By the Farkas Lemma there
exist xA  0, A 2 2 L , and y i;S  0,
, such that
A
a
y i;S <
A22 L
We deduce that xA  0 (and hence considering (4.2) for
some A with jA
For each A with a := jAj >  repeat the following. Let (w a ) a2a be an extremal
solution to L a . For each a 2  a , take the average of (4.2) over all A 2 A
a
, multiply
it by w a , and add all these equalities together to obtain the following.
a2a
a
wAxA
a2a
w a
a
a
y i;S
y i;S
a2a
a
w a
a s i
a
y i;S
a2a
a
w a
a i
a
(In the last inequality we used (4.1).)
Substituting the obtained inequalities on the xA 's into (4.3) we obtain
y i;S <
A22 L
gA
s
As the y i;S 's are non-negative, some of these variables has a larger coe-cient on the
right-hand side. Let it be y i;S . We have
AS
gA
A22 L
A jAj:
The last inequality follows from the fact that for any integer a > , we have 1=t 0
a
a=m u , which in turn follows from the denition of m u . Hence, e(g) > m u as required.
Corollary 4.2. Let r  q  1, t
such that t i  s i for be an integer sequence with
Let l 2 N be larger than lim
lim
In other words, in order to compute the limit in Corollary 4.2 it is su-cient to
consider only complete bipartite graphs arrowing Fn . It seems that there is no simple
general formula, but the proof of Theorem 4.1 gives an algorithm for computing ^ r(F).
The author has realized the algorithm as a C program calling the lp solve library.
(The latter is a freely available linear programming software, currently maintained
by Michel Berkelaar [4].) The reader is welcome to experiment with our program; its
source can be found in [15].
For certain series of parameters we can get a more explicit expression. First, let
us treat the case when only the rst forbidden graph dilates with n.
We can assume that t scaling n.
Theorem 4.3. Let 2. Then for any s
s
1).
Proof. The Problem L s has only one variable w s s 0 ;s 2 1;:::;s r 1 . Trivially, t 0
s
and the theorem follows.
In the case s we obtain the following formula (with a little bit of algebra).
Corollary 4.4. For any s
have

r
ASYMPTOTIC SIZE RAMSEY RESULTS 11
Another case with a simple formula for
r(F) is
without loss of generality we can assume that t
Theorem 4.5. Let 2. Then for any s; s
with
s
s
s
with a
Proof. Let a 2 N> and let (w a ) a2a be an extremal solution to L a . (Where we
obviously dene s Excluding the constant indices in w a ,
we assume that the index set  a consists of pairs of integers (a 1 ; a 2 ) with a 1 +a
Clearly, (w 0
is also an extremal solution, where w 0
(w
Thus we can assume that w
If w then we can set w
increasing w ba 0 =2c;da 0 =2e and w da 0 =2e;ba 0 =2c by c. The easy inequality
s
s
s
a 0 b
s
a 0 b 1
implies inductively that the left-hand side of (4.1) strictly decreases while the objective
function
a2a w a does not change, which clearly contradicts the minimality of w.
Now we deduce that, for any extremal solution (w a ) a2a , we have w
unless moreover, it follows that necessarily w ba 0 =2c;da 0
which proves the theorem.
The special case r = 2 of Theorem 4.5 answers the question of Erd}os, Faudree,
Rousseau and Schelp [9, Problem B], who asked for the asymptotics of ^ r(K s;n ; K s;n ).
Unfortunately, we do not think that the formula (4.6) can be further simplied in this
case.
Finally, let us consider the case of Theorem 4.5 in more detail. It is
routine to check that Theorem 4.5 implies that ^
O(1). But we
are able to show that (1.3) holds for all su-ciently large n, which is done by showing
that a (K 2;n ; K 2;n )-arrowing graph with 18n can have at most 3 vertices
of degree at least n for all large n.
Theorem 4.6. There is n 0 such that, for all n > n 0 , we have
18n 15 and K 3;6n 5 is the only extremal graph (up to isolated vertices).
Proof. For Gn be a minimum (K 2;n ; K 2;n )-arrowing graph. We know
that e(Gn )  18n 15 so l
us assume Ln  [18].
su-ciently large n.
Suppose on the contrary that we can nd an increasing subsequence (n i ) i2N with
l n i  4 for all i. Choosing a further subsequence, assume that Ln does not
depend on i and that
exists for any A 2 2 L . The argument of
Lemma 3.2 shows that the weight g on L arrows
We have It is routine to check that at 0
a > for any a 2 [4; 18]. The
inequality (4.4) implies that, for some
jAj > 4 or A 6 S. Let J be the set of those j 2 L with g fx;y;jg > 0. We have
Consider the 2-colouring c of g obtained by letting c
disjoint
It is easy to check that neither c 1 nor c 2
contains
A22 L
Afx;yg
c i;A < (5 3:5)=2
(Recall that d g (x)  1 for all x 2 L.) This contradiction proves Claim 1.
Thus, jLn j  3 for all large n. By the minimality of Gn , spans no
edge and each x 2 sends at least 3 edges to Ln . (In particular, jLn
Thus, disregarding isolated vertices,
implies that m  6n 5, which proves the theorem.
Remark. We do not write an explicit expression for n 0 , although it should be possible
to extract this from the proof (with more algebraic work) by using the estimates of
Theorem 3.3.
5. Generalizations. If all forbidden graphs are the same, then one can generalize
the arrowing property in the following way: a graph G (r; s)-arrows F if for any
r-colouring of E(G) there is an F-subgraph that receives less than s colours. Clearly,
in the case we obtain the usual r-colour arrowing property G
This property was rst studied by Ekeles, Erd}os and Furedi (as reported in [7,
Section 9]); the reader can consult [1] for references to more recent results.
Axenovich, Furedi and Mubayi [1] studied the generalized arrowing property for
bipartite graphs in the situation when F and s are xed, G = K n;n , and r grows with
n.
We
s) to be the minimal size of a graph which (r; s)-arrows F .
Our technique extends to the case when r and s are xed whilst F grows with n (i.e.,
is a dilatation). Namely, it should be possible to show the following.
be a dilatation of a weight f and let r  s be xed. Then the limit
us denote it by
We have
weights g such
that for any r-colouring c of g there is
s
such that cS  f , where
c
where the sum is taken over all disjoint A
We omit the proof as the complete argument would not be short and it is fairly
obvious how to proceed.
Also, one can consider the following settings. Let F i be a family of graphs, i 2 [r].
We any r-colouring of E(G), there is
such that we have an F-subgraph of colour i. The task is to compute the minimum
size of a such G. Again, we believe that our method extends to this case as well. But
we do not provide any proof, so we do not present this as a theorem.
ASYMPTOTIC SIZE RAMSEY RESULTS 13

Acknowledgements

. The author is grateful to Martin Henk, Deryk Osthus,
and Gunter Ziegler for helpful discussions.



--R


On size Ramsey number of pathes

lp solve 3.2






A class of size Ramsey problems involving stars
The size-Ramsey number of trees
The size Ramsey number of trees with bounded degree
Size Ramsey results for paths versus stars
Asymptotic size Ramsey results for bipartite graphs


--TR
farkas lemma;mixed integer programming;bipartite graphs;size Ramsey number