The Ramsey number R(3,K₁₀-e) and computational bounds for R(3,G)

Abstract: Using computer algorithms we establish that the Ramsey number

R (3, K_{10} - e)

is equal to 37, which solves the smallest open case for Ramsey numbers of this type. We also obtain new upper bounds for the cases of

R (3, K_{k} - e)

for

11 l e k l e 16

, and show by construction a new lower bound

55 l e R (3, K_{13} - e)

. The new upper bounds on

R (3, K_{k} - e)

are obtained by using the values and lower bounds on

e (3, K_{l} - e, n)

for

l l e k

, where

e (3, K_{k} - e, n)

is the minimum number of edges in any triangle-free graph on

n

vertices without

K_{k} - e

in the complement. We complete the computation of the exact values of

e (3, K_{k} - e, n)

for all

n

with

k l e q 10

and for

n l e q 34

with

k = 11

, and establish many new lower bounds on

e (3, K_{k} - e, n)

for higher values of

k

. Using the maximum triangle-free graph generation method, we determine two other previously unknown Ramsey numbers, namely

R (3, K_{10} - K_{3} - e) = 31

and

R (3, K_{10} - P_{3} - e) = 31

. For graphs

G

on 10 vertices, %besides

G = K_{10}

, this leaves 6 other open besides

G = K_{10}

, this leaves 6 open cases of the form

R (3, G)

. The hardest among them appears to be

G = K_{10} - 2 K_{2}

, for which we establish the bounds

31 l e R (3, K_{10} - 2 K_{2}) l e 33

.

Recommendations

Cites work

Cited in

(15)

Describes a project that uses

Uses Software

This page was built for publication: The Ramsey number \(R(3,K_{10}-e)\) and computational bounds for \(R(3,G)\)