# Quasi-Ramsey Graphs

A graph with number of vertices less than R(n,n)-1, is called quasi-Ramsey of case n, if it has no complete graph Kn in itself or its complementary graph, and if added another vertex, no matter how it is lined to the graph, the derived graph will have Kn in itself or its complementary. When the number of vertices is R(n,n)-1, call it a Ramsey graph. There is a simple example to show the existence of quasi-Ramsey graph. First R(n,n)>(n-1)(n-1). Second, choose n-1 (n-1)-complete graphs Kn-1, without any lines between any two vertices from two distinct Kn-1. This graph with (n-1)(n-1) vertices is a quasi-Ramsey graph. Furthermore, there are a series of questions about it. For example, if there could be non-isomorphic quasi-Ramsey graphs with same number of vertices, if they are all completely symmetrical (vertex transitive)and how many quasi-Ramsey graphs there are. If all the quasi-Ramsey graphs can be cleared out, we will get a deeper understanding of the structure of Ramsey graphs. Then we are more likely to obtain better estimates of Ramsey numbers.

-
$R(2,2)=2$ and $R(3,3)=6$ –  Aaron Meyerowitz Dec 9 '11 at 6:18
Yes, correct. What's your point? –  Zhipeng Lu Dec 9 '11 at 6:33
It is a minor point but it is not always the case that $R(n,n) \gt n(n-1)$ –  Aaron Meyerowitz Dec 9 '11 at 6:37
If the inequality is obvious from the construction, why is it false for $n=3$? –  Yemon Choi Dec 9 '11 at 6:54
Sorry, minor fault, R(n+1,n+1)>n*n from another construction. –  Zhipeng Lu Dec 9 '11 at 7:00

In the case of $R(4,4)$, there is a unique graph $G$ of order 17 and two non-isomorphic graphs $G_1, G_2$ of order 16. You can find the graphs here. The three graphs $G,G_1,G_2$ are each isomorphic to their own complements.

In the case of $R(5,5)$, the largest known graphs are on 42 vertices, even though the best proven upper bound on their size is 48. All of the 656 known graphs of order 42 are available on the same page, and the paper explaining their construction is B. D. McKay and S. P. Radziszowski, Subgraph counting identities and Ramsey numbers, J. Combinatorial Theory, Ser. B, 69 (1997) 193-209 PDF.

In general I don't think much is known about the Ramsey graphs slightly below the maximal graphs, and it is hopeless at the current state of knowledge to find general constructions for them.

ADDED: Thanks for your reply, I didn't notice you wanted vertex-maximal Ramsey graphs. The second of the (4,4)-graphs of order 16 is one. There are 634 of order 15, 126010 of order 14, 693270 of order 13, 136834 of order 12, 4124 of order 11, 76 of order 10, 6 of order 9, none of smaller order. The great majority of these are not regular. The 6 of order 9 include your example $3K_3$ (three triangles).

-
Thanks for your information. I just believe the socalled quasiRamsey graph are easier to find out. –  Zhipeng Lu Dec 11 '11 at 2:00
A Quasi-Ramsey graph is simply an R(n,n) graph (which has less than the maximum number of vertices for such a graph) yet is not a subgraph of any R(n,n) graph. Brendan gives you a link to descriptions (in graph6 format) of several R(n,n) graphs for $n=4,5$ and this with some work (once one masters the graph6 format, which I have not) gives several explicit Quasi-Ramsey graphs. Sails.ee my amended answer for slightly more det –  Aaron Meyerowitz Dec 11 '11 at 4:27

The complement of a quasi-Ramsey graph will still be quasi-Ramsey so that answers the question about non-isomorphic with the same number of variables (together with your construction).

$R(4,4)=18$ and there is a unique 17 vertex graph (a Paley graph) with no $K_4$ subgraph or 4 vertex independent set.It is self dual and regular of degree 8. It is vertex transitive which means that except for one 16 vertex graph every other either contains 4 independent vertices or a $K_4$ or is quasiRamsey. This should make it easy to find some irregular 16 vertex quasiRamsey graphs.

later Thanks to the answer from Brendan McKay (who would know!) I can say a bit more. I'll allow myself an editorial moment to say that the description of the graph6 format is not the most welcoming to the casual (windows based) curious reader who just wants to see the (adjacency matrix of) a particular graph or two. Hence I will state that the data pages he links to give descriptions of certain graphs but I have seen them. An R(4,4) graph is one which has neither 4 vertices with all 6 edges between them nor 4 vertices with 0 edges between them. Of course any subgraph of such a graph is also R(4,4). The definition in the question of a Quasi-Ramsey graph (for $n=4$) is an R(4,4) graph (on 16 vertices or less) so that no extension by adding one vertex and some edges on it is also R(4,4)

As Brendan says (with a link to a page with the descriptions) there is a single 17 vertex R(4,4) graph. It has only one 16 vertex subgraph . There is exactly one other 16 vertex R(4,4) graph so it fits the given description of Quasi-Ramsey. Between them these two graphs have no more that 32 vertex subgraphs (probably somewhat less.) In all there are evidently 640 15-vertex R(4,4) graphs so at least 608 of them are Quasi-Ramsey. Between all 640 there at most 640*15=9600 14-vertex subgraphs. Evidently there are 130816 14-vertex R(4,4) graphs so at least 130816-9600= 121216 of them are Quasi-Ramsey. Most likely some of those are not regular (let alone vertex transitive).

All this leads me to suspect that there are a very very large number of Quasi-Ramsey graphs for each $n \ge 5$ and that plenty of them are not regular. Perhaps someone can give an explicit description of at least one for $n=4$, however I can not at the moment.

-
Yes, I know, but this is not essential improvement. –  Zhipeng Lu Dec 9 '11 at 6:38
Zhipeng, it seems that Aaron has answered one of the questions you asked. If that's not the question you wanted to ask, then perhaps you should edit the question? –  Yemon Choi Dec 9 '11 at 6:56
I have corrected the minor fault in my question. Itself and its complement has no essential difference if you see it as a two-colored graph. –  Zhipeng Lu Dec 9 '11 at 7:15
Your answer gives no explication. The 17 vertex Paley graph is obviously not quasiRamsey. And generally, a Ramsey graph contains no quasiRamsey subgraph. How to find an irregular 16 vertex quasiRamsey graph? –  Zhipeng Lu Dec 9 '11 at 8:54
It is not a complete answer but I thought it relevant. There is at least one 16 vertex graph that is $K_4$ free (including the complement) , the Paley graph with a deleted vertex. Are there any others? If so, they are all Quasi-Ramsey. I agree that it is not easy to find one. If in fact there are no others then note that the Payley graph has only 2 15 vertex sugraphs so look for a 15 graph other than one of those which is $K_4$ free any of those would be Quasi-Ramsey. –  Aaron Meyerowitz Dec 9 '11 at 17:33