close

Вход

Забыли?

вход по аккаунту

?

326

код для вставкиСкачать
Upper Bounds for Ramsey
Numbers R(3, 3, . . ., 3) and
Schur Numbers*
Honghui Wan
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF OTTAWA
OTTAWA, ONTARIO, CANADA K1N 6N5
e-mail: [email protected]
Received November 9, 1990; revised June 15, 1993
−1
Abstract: In this paper we show that for n ≥ 4, R(3, 3, . . . , 3) < n!( e−e 2 + 3 ) + 1.
Consequently, a new bound for Schur numbers is also given. Also, for even n ≥ 6, the
−1
c 1997 John Wiley & Sons, Inc. J
Schur number Sn is bounded by Sn < n!( e−e 2 + 3 ) − n + 2. Graph Theory 26: 119–122, 1997
Keywords: upper bound, Ramsey number, Schur number
1. INTRODUCTION
For simplicity, let rn = R(3, 3, . . . , 3) (where there are n 3’s) be the least positive integer with
the property that if p ≥ rn , then for any n-coloring of the edges of Kp , the complete graph on
p vertices, there exists a monochromatic triangle. The number rn has been discussed by various
authors (e.g., [2]–[7], [9], [11]–[14]). Greenwood and Gleason [9] obtained the following upper
bound
n
X
1
+ 1 ≤ n!e + 1,
rn ≤ n!
k!
k=0
* Supported under a NSERC International Research Fellowship.
c
1997 John Wiley & Sons, Inc.
CCC 0364-9024/97/030119-04
120 JOURNAL OF GRAPH THEORY
and Whitehead [13] (see [6]) improved this to
1
+1
rn < n! e −
24
using Folkman’s [5] bound rn ≤ 65. The original proof techniques of Greenwood and Gleason
can be refined to provide a slightly better upper bound.
2. MAIN RESULTS
The following well known lemma [9] is based on the Erdös-Szekeres’ recursion; we omit the
proof.
Lemma 2.1. rn ≤ n(rn−1 − 1) + 2.
In special cases, this can be improved. The proof of the next result uses an idea similar to that
of Greenwood and Gleason’s argument for R(3, 4) ≤ 9.
Lemma 2.2. If both n and rn−1 are even, then rn ≤ n(rn−1 − 1) + 1.
Proof. Suppose n and rn−1 are even. Let m = n(rn−1 − 1) + 1 and fix a coloring ∆ :
E(Km ) → n. Let ci be the number of edges colored i, and di (x) be the number of i-colored
edges containing the vertex x.
Assume that for
P some i ∈ n, every x ∈ V (Km ) is incident with exactly rn−1 −1 edges colored
i. Then ci = 12 x di (x) = 12 m(rn−1 − 1). This is impossible since both m and rn−1 − 1 are
odd. So there exists at least one vertex x with di (x) ≥ rn−1 , in which case x together with its
neighbors induces a monochromatic triangle.
Pn
Pb n2 c 1
Lemma 2.3. Let An = n! i=0 i!1 and Bn = i=2
(2i)! . Then for n ≥ 4, rn −1 ≤ An −n!Bn .
Proof. We use induction on n. If n = 4, by the Folkman bound, r4 − 1 ≤ 64 = A4 − 4!B4 .
Now suppose that n ≥ 5 and rn−1 − 1 ≤ An−1 − (n − 1)!Bn−1 . Then for even n = 2k, let
p = An−1 − (n − 1)!Bn−1 + 1
= (n − 1)!
n−3
X
i=0
k−2
X 1
1
+ n − 1 + 1 − (n − 1)!
− (n − 1) + 1,
i!
(2i)!
i=2
which is even. By Lemma 2.2 we have
r2k − 1 ≤
=
=
=
2k(p − 1)
2k(A2k−1 − (2k − 1)!B2k−1 )
A2k − 1 − (2k)!B2k−1
A2k − (2k)!B2k .
Similarly, if n = 2k + 1, then by Lemma 2.1, we have
r2k+1 − 1 ≤
≤
=
=
(2k + 1)(r2k − 1) + 1
(2k + 1)!A2k + 1 − (2k + 1)!B2k
A2k+1 − (2k + 1)!B2k
A2k+1 − (2k + 1)!B2k+1 .
UPPER BOUNDS FOR RAMSAY NUMBERS 121
Theorem 2.4. For n ≥ 4, rn ≤ n!( e−e
Proof.
−1
2
+3
) + 1.
By Lemma 2.3,
rn − 1 ≤ An − n!B2k
 n
b2c
n
X
X
1
1

− n!
−1−
= n!
i!
(2i)!
i=0
i=0
e − e−1 + 3
.
< n!
2

1
2
3. AN APPLICATION TO SCHUR NUMBERS
In this section we give a new upper bound for Schur numbers as consequent result of the bound on
rn . The Schur number is the least number Sn such that for any n-coloring ∆ : {1, . . . , Sn } → n,
there exist x and y with ∆(x) = ∆(y) = ∆(x + y). Schur’s original proof [11] of the existence
of Sn yields Sn ≤ n!e, and a standard proof (cf. [8]) shows Sn ≤ rn − 1. This is the lowest
known upper bound (see [10] for discussion). It is known that S1 = 2, S2 = 5, S3 = 14, S4 = 45,
and S5 ≥ 158 (cf. [2], [6], [7]). A lower bound for Sn is given in [1].
The slight reduction in the known upper bound for rn already results in an improvement for
known bounds on Sn . However, for even n, we can improve further. First we need a recursive bound.
Lemma 3.1. If rn−1 is even, then Sn ≤ n(rn−1 − 2) + 2.
Proof. Assume rn −1 is even; set p = rn−1 and N = n(rn−1 −2)+2. Let ∆ : {1, . . . , N } →
n be a given n-coloring. This induces another n-coloring ∆∗ : E(Kn+1 ) → n defined by
N
= p2 − 1 + n1 , there are at least
∆∗ ({u, v}) = ∆(|u − v|). Put m = N2 + 1. Since 2n
p
N
2 distinct elements x1 , x2 , · · · xp/2 in {1, 2, . . . , 2 } colored the same, say i, under ∆. Let
H be the complete subgraph of Kn+1 induced by vertices {m ± x1 , m ± x2 , . . . , m ± xp/2 }.
Edges of Kn+1 of the form {m, m ± xj } are i-colored under ∆∗ . If H does not contain an
i-colored edge, then by the choice of p = rn−1 , H contains a monochromatic triangle. In
any case, Kn+1 contains a monochromatic triangle with vertices, say, a > b > c. Setting
x = a − b, y = b − c, ∆(x) = ∆(y) = (x + y) concludes the proof.
Theorem 3.2. For even n ≥ 6, Sn < n!( e−e
−1
2
+3
) − n + 2.
Proof. By Lemma 2.3, rn−1 ≤ An−1 − (n − 1)!Bn−1 + 1. If n is even, then An−1 −
(n − 1)!Bn−1 + 1 is even. By Lemma 3.1, Sn ≤ n(An−1 − (n − 1)!Bn−1 − 1) + 2 <
−1
n!( e−e 2 + 3 ) − n + 2.
ACKNOWLEDGMENT
The author gratefully thanks D. Gunderson, Dasong Cao, E. A. Bertram and the referees for
their kind helps, many valuable comments and suggestions which improved the presentation of
this paper.
122 JOURNAL OF GRAPH THEORY
References
[1]
H. L. Abbott and D. Hanson, A problem of Schur and its generalizations, Acta Arithmetica 20 (1972),
175–187.
[2]
L. D. Baumert and S. W. Golomb, Backtrack programming, J. Ass. Comp. Machinery 12 (1965),
516–524.
[3]
F. R. K. Chung, On the Ramsey numbers N (3, 3, . . ., 3; 2), Discrete Math. 5 (1973), 317–321.
[4]
F. R. K. Chung and C. M. Grinstead, A survey of bound for classical Ramsey numbers, J. Graph
Theory 7 (1983), 25–37.
[5]
J. Folkman, Notes on the Ramsey number N (3, 3, 3, 3). J. Combin. Theory Ser. A 16 (1974), 371–379.
[6]
H. Frdricksen, Five sum-free sets, in Congressus Numerantium 14, Proceedings of the 6th S. E.
Conference on Combinatorics, Graph Theory and Computing, eds. F. Hoffman et al. (1975), 309–314.
[7]
H. Fredricksen, Schur numbers and the Ramsey number N (3, 3, . . ., 3, 2), J. Combin. Theory A 27
(1979), 376–377.
[8]
R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey theory, Wiley–Interscience Series in
Discrete Math., New York (1980).
[9]
G. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math.
7 (1955), 1–17.
[10]
H. J. Prömel and B. Voigt, Aspects of Ramsey theory II: Arithmetic Progressions, Report No 87497,
Forschungsinstitut für Diskrete Mathematik, Institut für Ökonometrie und operations research, Universität Bonn, (Mar. 1989), 99 pages.
[11]
I. Schur, Uber die Kongruenz xm + Y m ≡ z m (mod p), Jber. Deutsch. Math.-Verein 25 (1916),
114–116.
[12]
Honghui Wan, Ramsey numbers for quasi-quadrangles and triangles, submitted.
[13]
E. G. Whitehead, Jr., Algebraic structure of chromatic graphs associated with the Ramsey number
N (3, 3, 3, 2), Discrete Math. 1 (1971), 113–114.
[14]
E. G. Whitehead, Jr., The Ramsey number N (3, 3, 3, 3, 2), Discrete Math. 4 (1973), 389–396.
Документ
Категория
Без категории
Просмотров
4
Размер файла
81 Кб
Теги
326
1/--страниц
Пожаловаться на содержимое документа