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

Authors Jan Goedgebeur, Stanisław P. Radziszowski

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.0038, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p19

zbMATH Keywords

almost-complete graphs computation Ramsey number triangle-free graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Generalized Ramsey theory (05C55) Graph theory (including graph drawing) in computer science (68R10)

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

.

Review text

Summary: 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 \leq k \leq 16\), and show by construction a new lower bound \(55 \leq 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 \leq 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 \leq 10\) and for \(n \leq 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 open cases of the form \(R(3,G)\). The hardest among them appears to be \(G=K_{10}-2K_2\), for which we establish the bounds \(31 \leq R(3,K_{10}-2K_2) \leq 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)\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396940)