R (3,3,3,3)
R (3,3,3,3)
R (3,3,3,3)
(u)| = |S
(u) S
(v) is referred to
as an attaching set. The structure of a potential attaching set is quite limited.
The section ends with a statement, given without proof, of Theorem 2.5, which
gathers together the results of the local arguments into a single theorem, This
theorem limits the structure of potential attaching sets. More specically, it
states that every attaching set has cardinality 0, 1, 2 or 5. It further states that
the structure of attaching sets of cardinality 5 are severely restricted. In 3, we
give the global arguments, that is, arguments which require the consideration
of multiple attaching sets at the same time. There we assume Theorem 2.5 for
every attaching set in a given good coloring of K
62
with four colors, and use
that fact to derive a contradiction, thus proving that no such good coloring on
K
62
exists. This is the main result, Theorem 3.4, that is, R(3, 3, 3, 3) 62.
2. Preliminaries
Notation 2.1. For convenience, we dene
[i
1
, . . . , i
n
] =
i
f(1)
, . . . , i
f(n)
f is a permutation on 1, . . . , n
.
We also write u
v, where u and v are vertices in some edge colored graph
and is a color, to indicate that the edge connecting u and v is of color .
R(3, 3, 3, 3) 62: THE GLOBAL ARGUMENTS 3
Denition 2.2. Let V be the vertex set of an edge colored complete graph. Let
be a color and let v V . Then we dene
S
(v) = x V [ x
v .
Denition 2.3. Let v
0
, . . . , v
15
be vertices of an edge coloring of a complete
graph, and let , , and be colors. We dene the following predicates:
(1) P
,
(v
1
, . . . , v
5
) iff
df
v
1
v
2
v
3
v
4
v
5
v
1
and v
1
v
3
v
5
v
2
v
4
v
1
. (See Figure 1.)
v
1
v
2
v
3
v
4
v
5
Figura 1. P
,
(v
1
, . . . , v
5
)
(2) A
0
,,
(v
1
, . . . , v
10
) iff
df
P
,
(v
1
, v
2
, v
3
, v
4
, v
5
) and P
,
(v
6
, v
7
, v
8
, v
9
, v
10
) and v
1
v
6
and v
2
v
7
and v
3
v
8
and v
4
v
9
and v
5
v
10
and v
1
v
8
v
5
v
7
v
4
v
6
v
3
v
10
v
2
v
9
v
1
and
v
1
v
7
v
3
v
9
v
5
v
6
v
2
v
8
v
4
v
10
v
1
.
(3) A
1
,,
(v
1
, . . . , v
10
) iff
df
P
,
(v
1
, v
2
, v
3
, v
4
, v
5
) and P
,
(v
6
, v
7
, v
8
, v
9
, v
10
) and v
1
v
6
and v
2
v
7
and v
3
v
8
and v
4
v
9
and v
5
v
10
and v
1
v
8
v
5
v
7
v
4
v
10
v
3
v
6
v
2
v
9
v
1
and
v
1
v
7
v
3
v
9
v
5
v
6
v
4
v
8
v
2
v
10
v
1
.
(4) C
0
,,
(v
1
, . . . , v
15
) iff
df
A
0
,,
(v
11
, v
12
, v
13
, v
14
, v
15
, v
1
, v
2
, v
3
, v
4
, v
5
) and A
0
,,
(v
1
, v
2
, v
3
, v
4
, v
5
, v
6
,
v
7
, v
8
, v
9
, v
10
) and A
0
,,
(v
6
, v
7
, v
8
, v
9
, v
10
, v
11
, v
12
, v
13
, v
14
, v
15
).
(5) C
1
,,
(v
1
, . . . , v
15
) iff
df
A
1
,,
(v
11
, v
12
, v
13
, v
14
, v
15
, v
1
, v
2
, v
3
, v
4
, v
5
) and A
1
,,
(v
1
, v
2
, v
3
, v
4
, v
5
, v
6
,
v
7
, v
8
, v
9
, v
10
) and A
1
,,
(v
6
, v
7
, v
8
, v
9
, v
10
, v
15
, v
14
, v
13
, v
12
, v
11
).
(6) B
0
,,
(v
0
, . . . , v
15
) iff
df
C
0
,,
(v
1
, . . . , v
15
) and v
0
v
1
, v
2
, v
3
, v
4
, v
5
and v
0
v
6
, v
7
, v
8
, v
9
, v
10
and v
0
v
11
, v
12
, v
13
, v
14
, v
15
. (See Figure 2.)
(7) B
1
,,
(v
0
, . . . , v
15
) iff
df
C
1
,,
(v
1
, . . . , v
15
) and v
0
v
1
, v
2
, v
3
, v
4
, v
5
and v
0
v
6
, v
7
, v
8
, v
9
, v
10
and v
0
v
11
, v
12
, v
13
, v
14
, v
15
. (See Figure 3.)
4 RICHARD L. KRAMER
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
v
12
v
13
v
14
v
15
v
11
v
12
v
13
v
14
v
15
v
0
Figura 2. B
0
,,
(v
1
, . . . , v
15
)
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
15
v
14
v
13
v
12
v
11
v
11
v
12
v
13
v
14
v
15
v
0
Figura 3. B
1
,,
(v
1
, . . . , v
15
)
Lemma 2.1. Let U be the vertex set of a complete graph with a good edge
coloring, colored with the pairwise distinct colors , , and . If |U| = 16, then
there exist x
0
, . . . , x
15
U and some i 0, 1 such that B
i
,,
(x
0
, . . . , x
15
)
Demostracion. See Kalbeisch and Stanton [6].
Lemma 2.3. Let U be the vertex set of a complete graph with a good edge
coloring, colored with the pairwise distinct colors , , and . If |U| = 15, then
there exist x
1
, . . . , x
15
U and some i 0, 1 such that C
i
,,
(x
1
, . . . , x
15
)
Demostracion. See Heinrich [5].
Remark 2.1. In Lemma 2.1 and Lemma 2.3, i = 0 if the coloring is untwisted,
and i = 1 if the coloring is twisted.
Proposition 2.4. Let V be the vertex set of a complete graph with a good edge
coloring, colored with the pairwise distinct colors , , , and . Suppose that
|V | = 62 and let x V . Then
|S
(x)|, |S
(x)|, |S
(x)|, |S
(x)|
[16, 16, 16, 13] [16, 16, 15, 14] [16, 15, 15, 15].
Demostracion. It is clear that
62 = |V |
= | x S
(x) S
(x) S
(x) S
(x)|
= 1 +|S
(x)| +|S
(x)| +|S
(x)| +|S
(x)|.
Also, for any , , , , we see that the induced good edge coloring on
the complete graph with vertex set S
(x)|, |S
(x)|, |S
(x)|, |S
The following theorem summarizes the results of the local arguments of [7],
that is, arguments that proceed by consideration of a single attaching set. In
these arguments, all potential attaching sets of cardinalities other than 0, 1, 2,
and 5 are eliminated, and the structure of any attaching sets of cardinality 5
are severely restricted. This theorem is used repeatedly in the global arguments
of the next section.
6 RICHARD L. KRAMER
Theorem 2.5. Let V be the vertex set of a complete graph with a good edge
coloring with four colors. Suppose that |V | = 62 and let u, v V with u ,= v
be such that |S
(u)| = |S
(u) S
(v)|
0, 1, 2, 5 . In addition, if |S
(u) S
(u) and y
0
, . . . , y
15
S
(v) with x
i
= y
i
for all i 11, 12, 13, 14, 15 and
some j 0, 1 and colors , , and , such that B
j
,,
(x
0
, . . . , x
15
) and
B
j
,,
(y
0
, . . . , y
15
) with
S
(u) S
(v) = x
11
, x
12
, x
13
, x
14
, x
15
= y
11
, y
12
, y
13
, y
14
, y
15
.
Furthermore, if |S
(u) S
(u) S
(v), we have
|S
(w) and S
(w), S
(w) 15 for ,= , ,
by Proposition 2.4, so that by Lemma 2.1, Lemma 2.3 and Remark 2.1, it
makes sense to say that S
(w) and S
(z)| 15.
Demostracion. Suppose not. Then |S
(x) S
(x) S
(x) S
(y)| = 5.
Next, we show that |S
(u)S
(v)| = |S
(u)S
(w)| = |S
(v)S
(w)| = 5.
Suppose not. Then we may, without loss of generality, suppose that |S
(u)
S
(u) S
(v)| 2. But,
x, y S
(u) S
(u) S
(v) = x, y S
(w).
R(3, 3, 3, 3) 62: THE GLOBAL ARGUMENTS 7
But then we have
S
(u) S
(w)
(v) S
(w)
(u) S
(v) S
(w) S
(x) S
(y)
(x) S
(y)
(y) S
(x)
(x) S
(y)
(u) S
(w)
(v) S
(w)
(w)
(x) S
(y)
(y) S
(x)
(x) S
(y)
(u) S
(w)
(v) S
(w)
(w)
= 11 + 11 + 5 +
(u) S
(w)
(v) S
(w)
+ 16
11 + 11 + 5 + 11 + 11 + 16
= 65,
which is a contradiction. Thus, we have
|S
(u) S
(v)| = |S
(u) S
(w)| = |S
(v) S
(w)| = 5,
as desired.
We may now apply Theorem 2.5 to each pair in u, v, w to see that there
exist colors ,
,= such that
S
(u) S
(x)| 14,
S
(u) S
and |S
(x)| 14,
and
S
(v) S
and |S
(x)| 14.
By Proposition 2.4, we see that =
.
Thus, there exists some ,= , such that |S
(x)| 14 and
= (S
(u) S
(x)) (S
(v) S
(x))
= (S
(u) S
(x)) (S
(w) S
(x))
= (S
(v) S
(x)) (S
(w) S
(x)).
Next, we show that |S
(z) S
(z) S
z{ u,v,w}
(z) S
(x)
(x),
we must have 5 + 5 + 5 14, which is impossible.
8 RICHARD L. KRAMER
Thus, we may suppose, without loss of generality, that |S
(u) S
(x)| 4.
Let and be the two other colors. Then, since u
x, we must have
16 =
(u)
(u) S
(x)
(u) S
(x)
(u) S
(x)
(u) S
(x)
(u) S
(x)
(u) S
(x)
1 + 5 + 5 + 4
= 15,
which is impossible.
The proof is complete.
Theorem 3.2. Let V be the vertex set of a complete graph with a good ed-
ge coloring, colored with the pairwise distinct colors , , , and . Suppose
that u, v V with S
(u) = x
0
, . . . , x
15
and S
(v) = y
0
, . . . , y
15
with
B
1
,,
(x
0
, . . . , x
15
) and B
1
,,
(y
0
, . . . , y
15
) such that S
(u) S
(v) = a, b, c, d,
e where a = x
13
= y
13
, b = x
14
= y
14
, c = x
15
= y
15
, d = x
11
= y
11
,
and e = x
12
= y
12
. Suppose further that |V | = 62. If |S
(b)| = |S
(e)| = 15. If |S
(d)| = |S
(c)| = 15.
Demostracion. First, note that the hypotheses of the theorem are preserved by
the following symmetry :
u u
v v
a a
b c e d b
x
0
x
0
x
3
x
8
x
3
x
1
x
7
x
5
x
9
x
1
x
2
x
10
x
4
x
6
x
2
y
0
y
0
y
3
y
8
y
3
y
1
y
7
y
5
y
9
y
1
y
2
y
10
y
4
y
6
y
2
Note that the symmetry acts on the colors as follows:
First, we show that if |S
(a)| = 16 but |S
(b)| = |S
(a)| = 16.
Applying Theorem 2.5 once again, this time to a and b, and using the fact that
x
5
, y
5
, d S
(a) S
(a) S
(b)| = 5.
Furthermore, note that x
5
y
5
, since x
5
, y
5
S
(a) S
(c) S
(d). Note
also that d
x
5
, y
5
. Thus, by Theorem 2.5, applied to a and b, we see that
|S
(d)| 14.
But by Theorem 2.5, applied to u and v, we see that
|S
(d)| 14,
which is impossible, by Proposition 2.4.
Thus, we have shown that
if |S
(b)| = 15.
Repeated applications of the symmetry give
if |S
(c)| = 15,
if |S
(e)| = 15,
and
if |S
(d)| = 15.
The proof is complete.
Theorem 3.3. Let V be the vertex set of a complete graph with a good edge
coloring, colored with four colors. Then there exists some color and vertices
u, v V , such that |S
(u)| = |S
(v)| = 16 and |S
(u) S
(v)| = 5 with
both S
(u) and S
(v) twisted.
Demostracion. By Proposition 2.4, for each z V there exists some color
such that |S
(z, )
|S
(z)| = 16
62.
Thus, there must exist some color such that
|S
(z)| = 16
16.
Let z
0
, z
1
, z
2
, z
3
, z
4
, z
5
V be pairwise distinct vertices such that |S
(z
i
)| = 16
for all i 0, 1, 2, 3, 4, 5 .
10 RICHARD L. KRAMER
First, we show that |S
(z
i
) S
(z
j
)| = 5 for some i, j 0, 1, 2, 3, 4, 5 .
Suppose not. Then, by Theorem 2.5, we see that |S
(z
i
) S
(z
j
)| 2 for any
distinct i, j 0, 1, 2, 3, 4, 5 . Thus, we have
62 =
(z
0
) S
(z
1
) S
(z
2
) S
(z
3
) S
(z
4
) S
(z
5
)
16 + 14 + 12 + 10 + 8 + 6
= 66,
which is impossible. Thus, we see that there exist some i, j 0, 1, 2, 3, 4, 5 ,
such that |S
(z
i
) S
(z
j
)| = 5. Let x = z
i
and y = z
j
.
Thus, we have |S
(x)| = |S
(y)| = 16 and |S
(x) S
(y)| = 5. By Theo-
rem 2.5, applied to x and y, we see that there exist colors , , and , such that
|S
(x)S
(u)S
(v)
are colored with the colors and .
By Proposition 2.4, we see that for any w S
(u) S
(w)| = 16 or |S
(x)S
(x) S
(u)| =
|S
(v)| = |S
(w)| = 16 or |S
(u)| = |S
(v)| = |S
(u)| = |S
(v)| = |S
(w)| = 16.
Since u, v, w S
(x) S
(x) S
u, v and that w
1
is the only such element of S
(x) S
(y).
Since |S
(x)| = |S
(x) S
(y) S
(u)S
(u)| = |S
(u) S
(u) and S
(x)| = |S
(y)| = 16 and
|S
(x) S
(x) S
(u)| = |S
(v)| =
16 and |S
(u) S
(u) and S
(v) twisted.
By Theorem 2.5, there exist x
0
, . . . , x
15
S
(u) and y
0
, . . . , y
15
S
(v)
with x
i
= y
i
for all i 11, 12, 13, 14, 15 and colors , , and , such that
B
1
,,
(x
0
, . . . , x
15
) and B
1
,,
(y
0
, . . . , y
15
) with S
(u) S
(v) = a, b, c, d, e ,
where a = x
13
= y
13
, b = x
14
= y
14
, c = x
15
= y
15
, d = x
11
= y
11
, and
e = x
12
= y
12
.
First, note that the entire situation so far is preserved by the following
symmetry :
u u
v v
a a
b c e d b
x
0
x
0
x
3
x
8
x
3
x
1
x
7
x
5
x
9
x
1
x
2
x
10
x
4
x
6
x
2
y
0
y
0
y
3
y
8
y
3
y
1
y
7
y
5
y
9
y
1
y
2
y
10
y
4
y
6
y
2
Note that the symmetry acts on the colors as follows:
By Theorem 2.5, applied to u and v, we see that |S
(b)| = |S
(b)| = |S
(b)| = |S
(e)| = |S
(b)| = |S
(e)| = 16.
Since b, e, a
u, v, we see, by Theorem 3.1, that |S
(a)| = |S
(c)| = 16,
thus giving a contradiction.
12 RICHARD L. KRAMER
Thus, we have shown that
|S
(a)| 15.
An application of the symmetry to this gives
|S
(a)| 15.
Since |S
Referencias
[1] F. R. H. Chung, On the Ramsey Numbers N(3, 3, . . . , 3; 2), Discrete Mathema-
tics, 5 (1973), 317321.
[2] S. E. Fettes, R. L. Kramer & S. P. Radziszowski, An Upper Bound of 62
on the Classical Ramsey Number R(3, 3, 3, 3), Ars Combinatoria, LXXII (2004)
4163.
[3] J. Folkman, Notes on the Ramsey Number N(3, 3, 3, 3), Journal of Combinato-
rial Theory, Series A 16 (1974), 371379.
[4] R. E. Greenwood & A. M. Gleason, Combinatory Relations and Chromatic
Graphs, Canadian Journal of Mathematics, 7 (1955), 17.
[5] K. Heinrich, Proper Colorings of K
15
, Journal of the Austrailian Mathematical
Society, 24 (1977), 465495.
[6] J. K. Kabfleisch & R. G. Stanton, On the Maximal Triangle-Free Edge-
Chromatic Graphs in Three Colors, Journal of Combinatorial Theory, 5 (1968),
920.
[7] R. L. Kramer The Classical Ramsey Number R(3, 3, 3, 3) is No Greater Than
62 Preprint, 1108
[8] C. Laywine & J. P. Mayberry, A Simple Construction Giving the Two Non-
Isomorphic Triangle-Free 3-Colored K
16
s, Journal of Combinatorial Theory, Se-
ries B 45 (1988), 120124.
[9] S. P. Radziszowski, Small Ramsey Numbers, Electronic Journal of Combinato-
rics, (1999), 1-35.
[10] A. Sanchez-Flores, An Improved Upper Bound For the Ramsey Number
N(3, 3, 3, 3; 2), Discrete Mathematics, 140 (1995), 281286.
(Recibido en abril de 2006)
department of Mathematics
Iowa State University
Ames, Iowa, USA
e-mail: ricardo@iastate.edu