A lower bound for the number of vertices of some Ramsey graphs

Abstract

A subset $v_1,..v_p$ of vertices of graph is called da $p$-clique if any two of them are adjacent. The graph $G$ is called a $(p_1,..,p_s)$-Ramsey graph, for some set of integers $p_1,...p_s$ if for every colouring of the edges of $G$ there exist an $i,1\leq i \leq s$, such that $G$ contains monochromatic $p_i$-clique of the $i$-colour. The symbol $R(p_1,..p_s)$ denotes the minimal natural number $n$ such that the complete graph with $n$ vertices is $(p_1,..,p_s)$-Ramsey graph and the symbol $N(R(p_1,...,p_s))$-the minimal natural number $n$ such that there exists a $(p_1,..,p_s)$-Ramsey graph with $n$ vertices and without $R(p_1,..,p_s)$-clique. In this paper it is proved a lowe bound for the numbers $N(R(p_1,..p_s))$