MATLAB Examples

Lower bound for the Ramsey number R(4)

We show that the the Ramsey number R(4) is greater than 17 by presenting a graph with 17 vertices that has clique and independence numbers equal to three. The Matgraph alpha and omega functions require the Optimization Toolbox.

Contents

The Paley graph

The graph we use is the Paley graph with n=17. The vertices of this graph correspond to the integers mod 17 with an edge between two vertices exactly when their difference is a quadratic residue mod 17. The paley function creates such a graph.

g = graph;
paley(g,17);

Maximum clique

We use omega to find the clique number and a maximum clique.

[w,S] = omega(g);
disp(['The clique number is ', int2str(w)])
notS = setdiff(1:17,S);
p = partition({S,notS});
clf;cdraw(g,p);
Optimization terminated.
The clique number is 3

Maximum independent set

We use alpha to find the independence number and a maximum independent set.

[a,S] = alpha(g);
disp(['The independence number is ', int2str(a)])
notS = setdiff(1:17,S);
p = partition({S,notS});
clf;cdraw(g,p);
Optimization terminated.
The independence number is 3

Release storage

free(g)