A lower bound for irredundant Ramsey numbers Original Research Article

Given a graph G = (V,E), a vertex subset U ⊆ V is called irredundant if every vertex v ∈ U either has no neighbours in U or there exists a vertex w ∈ V/U such that v is the only neighbour of w in U. The irredundant Ramsey number s(m,n) is the smallest N such that any red-blue edge colouring of KN yields either an m-element irredundant subset in the blue graph or an n-element irredundant subset in the red graph. Using probabilistic methods we show that s(m,n)>Cm(nlogn(m2−m−1)[2(m−1)]