Fan-complete Ramsey numbers

Abstract: We consider Ramsey numbers

r (G, H)

with tight lower bounds, namely, �egin{align*} r(G,H) geq (chi(G)-1)(|H|-1)+1, end{align*} where

c h i (G)

denotes the chromatic number of

G

and

| H |

denotes the number of vertices in

H

. We say

H

is

G

-good if the equality holds. In this paper, we prove that the fan-graph

F_{n} = K_{1} + n K_{2}

is

K_{p}

-good if

n g e q 27 p^{2}

, improving previous tower-type lower bounds for

n

due to Li and Rousseau (1996). The join graph

G + H

is defined by adding all edges between the disjoint vertex sets of

G

and

H

. Let

n H

denote the union graph of

n

disjoint copies of

H

. We show that

K_{1} + n H

is

K_{p}

-good if

n

is sufficiently large. We give a stronger lower bound inequality for Ramsey number

r (G, K_{1} + F)

for the case of

G = K_{p} (a_{1}, a_{2}, d o t s, a_{p})

, the complete

p

-partite graph with

a_{1} = 1

and

a_{i} l e q a_{i + 1}

. In particular, using a stability-supersaturation lemma by Fox, He and Wigderson (2021), we show that for any fixed graph

H

, �egin{align*} r(G,K_1+nH) = left{ �egin{array}{ll} (p-1)(n |H|+a_2-1)+1 & extrm{if

n | H | + a_{2} - 1

or

a_{2} - 1

is even,}\ (p-1)(n |H|+a_2-2)+1 & extrm{otherwise,} end{array} ight. end{align*} where

G = K_{p} (1, a_{2}, d o t s, a_{p})

with

a_{i}

's satisfying some mild conditions and

n

is sufficiently large. The special case of

H = K_{1}

gives an answer to Burr's question (1981) about the discrepancy of

r (G, K_{1, n})

from

G

-goodness for sufficiently large

n

. All bounds of

n

we obtain are not of tower-types.

This page was built for publication: Fan-complete Ramsey numbers