erdős #986

← #985 · #987 → (packet.json; erdosproblems.com)

For any fixed $s \geq 3$ , $R (s, k) ≫ \frac{k ^{s - 1}}{( lo g k ) ^{c}}$ for some constant $c = c (s) > 0$ .

Worked, still open.

graph theory · open · 0 attempts

use this record

vela registry pull vfr_37aec80d874a0239

vela reproduce examples/erdos-problems

evidence

unverified AI candidates (2)

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

Interpreting $R(k,n)$ as the usual **off‑diagonal graph Ramsey number** (r(k,n)=r(K_k,K_n)):

candidate solution ↗

llm-hunter · gpt pro 5.2 · unverified

1 LLM attack(s) recorded (gpt pro 5.2); unverified.

candidate solution ↗

oeis

A000791 — Ramsey numbers R(3,n).1,3,6,9,14,18,23,28,36 A059442 — Array of Ramsey numbers R(n,k) (n >= 2, k >= 2) read by antidiagonals.2,3,3,4,6,4,5,9,9,5,6,14,18,14,6,7,18,25,25,18,7,8,23

links

#6 in Ramsey Theory · link

Create a formalisation here · link

#77If

R (k)

is the Ramsey number for

K_{k}

, the minimal

n

such that every

2

-colouring of the edges of

K_{n}

contains a monochromatic copy of

K_{k}

, then find the value of

k \to \infty lim R (k)^{1/ k} .

A059442 #78Let

R (k)

be the Ramsey number for

K_{k}

, the minimal

n

such that every

2

-colouring of the edges of

K_{n}

contains a monochromatic copy of

K_{k}

.Give a constructive proof that

R (k) > C^{k}

for some constant

C > 1

.A059442 #87Let

ϵ > 0

. Is it true that, if

k

is sufficiently large, then

R (G) > (1 - ϵ)^{k} R (k)

for every graph

G

with chromatic number

χ (G) = k

? Even stronger, is there some

c > 0

such that, for all large

k

R (G) > c R (k)

for every graph

G

with chromatic number

χ (G) = k

?A059442 #165Give an asymptotic formula for

R (3, k)

.A000791 #166Prove that

R (4, k) ≫ \frac{k ^{3}}{( lo g k ) ^{O (1)}} .

A059442 #544Show that

R (3, k + 1) - R (3, k) \to \infty

k \to \infty

. Similarly, prove or disprove that

R (3, k + 1) - R (3, k) = o (k) .

A000791 #545Let

G

be a graph with

m

edges and no isolated vertices. Is the Ramsey number

R (G)

maximised when

G

is 'as complete as possible'? That is, if

m = (2 n) + t

edges with

0 \leq t < n

then is

R (G) \leq R (H),

where

H

is the graph formed by connecting a new vertex to

t

of the vertices of

K_{n}

?A059442 #553Let

R (3, 3, n)

denote the smallest integer

m

such that if we

3

-colour the edges of

K_{m}

then there is either a monochromatic triangle in one of the first two colours or a monochromatic

K_{n}

in the third colour. Define

R (3, n)

\frac{R ( 3 , 3 , n )}{R ( 3 , n )} \to \infty

n \to \infty

.A000791 #812Is it true that

\frac{R ( n + 1 )}{R ( n )} \geq 1 + c

for some constant

c > 0

, for all large

n

? Is it true that

R (n + 1) - R (n) ≫ n^{2} ?

A059442 #1029If

R (k)

is the Ramsey number for

K_{k}

, the minimal

n

such that every

2

-colouring of the edges of

K_{n}

contains a monochromatic copy of

K_{k}

, then

\frac{R ( k )}{k 2 ^{k /2}} \to \infty.

A059442 #1030Let

R (k, l)

be the usual Ramsey number: the smallest

n

such that if the edges of

K_{n}

are coloured red and blue then there exists either a red

K_{k}

or a blue

K_{l}

.Prove the existence of some

c > 0

such that

k \to \infty lim \frac{R ( k + 1 , k )}{R ( k , k )} > 1 + c .

A000791

status

open

evidence

oeis

links

status

Search Vela