Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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.
share|improve this answer
    
where can I read this paper? –  a boy Aug 26 '10 at 4:53

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.