Ramsey for complete graphs with dropped cliques

Abstract

Let $K\_[k,t]$ be the complete graph on $k$ vertices from which a set of edges, induced by a clique of order $t$, has been dropped. In this note we give two explicit upper bounds for $R(K\_[k\_1,t\_1],\dots ,K\_[k\_r,t\_r])$ (the smallest integer $n$ such that for any $r$-edge coloring of $K\_n$ there always occurs a monochromatic $K\_[k\_i,t\_i]$ for some $i$). Our first upper bound contains a classical one in the case when $k\_1=\cdots =k\_r$ and $t\_i=1$ for all $i$. The second one is obtained by introducing a new edge coloring called {\em $\chi \_r$-colorings}. We finally discuss a conjecture claiming, in particular, that our second upper bound improves the classical one in infinitely many cases.

arXiv comment10 pages, 2 figures, 1 table