3
$\begingroup$

Ramsey number $R(3,6)=18$. How to construct a graph of $17$ nodes which does not contain neither a clique of order $3$ or an independent set of order $6$. could you show me the tactics or the adjacency matrix?

2 Answers 2

6

Look at http://cs.anu.edu.au/~bdm/data/ramsey.html for the R(3,6)'s with less than 18 vertices. The ones with 17 are:

alt text

Apartently, an example is constructed by hand in

  • J. G. Kalbfleish, Chromatic graphs and Ramsey's theorem, Ph. D. thesis, University of Waterloo, January 1966.
  • 0
    where can I read this paper?2010-08-26
0

Here is an explicit example that is very concrete, but a near miss: a graph $G$ with 16 vertices containing no triangle and no independent set with six elements. I think that it is not possible to extend the graph $G$ by a single vertex preserving this property, but I would be interested if I could be proved wrong! For those who are interested and know about these things, the graph $G$ is the graph of configurations of the exceptional curves on a del Pezzo surface of degree four. None of this will be needed.

Construction of $G$. Start with a circle $C$ in the plane, five distinct points $p_1,\ldots,p_5$ on the circle $C$ and the 10 lines $\{\ell_{ij}\}_{1 \leq i < j \leq 5}$ through the five points. The graph has as vertices the circle $C$, the points $\{p_i\}$ and the lines $\{\ell_{ij}\}$, for a total of $1+5+10=16$ vertices. The edges are as follows:

  1. the vertex $C$ is joined to each point $p_1,\ldots,p_5$, but to no line;

  2. the vertex $p_i$ is joined to each line through itself and to the circle, but nothing else (for instance, there is no edge between different points and no edge between $p_1$ and $\ell_{23}$);

  3. the vertex $\ell_{ij}$ is joined to the points $p_i$ and $p_j$, as well as all the lines $\ell_{kl}$ for $i,j\neq k,l$;

where, of course, $i$ and $j$ range in $\{1,\ldots,5\}$, and $i$<$j$ when both appear.

You can now check that there are no triangles and no independent sets with six elements in $G$. The checks are easier once you realize that there is a large group of symmetries acting on $G$ (the group is larger than the obvious permutations of the indices: it has order 1920).

Unfortunately, this graph has 16 vertices! As I mentioned above, I think that any extension of this graph will have either a triangle or an independent set of size six, but I am not sure: anyone can confirm this? One way to go about this would be to see if this graph appears as a subgraph in one of the examples that Mariano gives in his answer. My argument was not this one, and I would prefer a more conceptual argument.