Asymptotic Bounds for CO-irredundant and Irredundant Ramsey Numbers

Abstract

A set of vertices $X\subseteq V$ in a simple graph $G(V,E)$ is irredundant (CO-irredundant) if each vertex $x\in X$ is either isolated in the induced subgraph $G[X]$ or else has a private neighbor $y\in V\setminus X$ ($y\in V$) that is adjacent to $x$ and to no other vertex of $X$. The irredundant Ramsey number $s(t_1,\dots ,t_l)$, CO-irredundant Ramsey number $s_{\mathrm{CO}}(t_1,\dots ,t_l)$, is the minimum $N$ such that every $l$-coloring of the edges of the complete graph $K_N$ on $N$ vertices has a monochromatic irredundant set, a monochromatic CO-irredundant set, of size $t_i$ for some $1\le i\le l$, respectively. In this paper, firstly, we establish a lower bound for the irredundant Ramsey number $s(t_1,\dots ,t_l)$ by a random and probabilistic method. Secondly, we improve an upper bound for $s(3,9)$ such that $24\le s(3,9)\le 26$. Thirdly, using Krivelevich's lemma, we establish an asymptotic lower bound for the $\mathrm{CO}$-irredundant Ramsey number $s_{\mathrm{CO}}(m,n)$.

19 pages,2 figures