Ramsey's theorem

Ramsey's theorem is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The task is to find a graph with 17 Nodes such that any clique of 4 Nodes is neither totally connected nor totally unconnected.

C

For 17 nodes, (4,4) happens to have a special solution: arrange nodes on a circle, and connect all pairs with distances 1, 2, 4, and 8. It's easier to prove it on paper and just show the result than let a computer find it (you can call it optimization). <lang c>#include <stdio.h>

int main() { int a[17][17] = Template:0; int i, j, k; char *mark = "01-";

for (i = 0; i < 17; i++) a[i][i] = 2;

for (k = 1; k <= 8; k <<= 1) { for (i = 0; i < 17; i++) { j = (i + k) % 17; a[i][j] = a[j][i] = 1; } }

for (i = 0; i < 17; i++) { for (j = 0; j < 17; j++) printf("%c ", mark[a[i][j]]); putchar('\n'); } return 0; }</lang>output (17 x 17 connectivity matrix):

- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 
1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 
1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 
0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 
1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 
0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 
0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 
0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 
1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 
1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 
0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 
0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 
0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 
1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 
0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 

Mathprog

An example in Mathprog may be found on this page http://rosettacode.org/wiki/Execute_Ramsey_Mathprog.

This may be run:

glpsol --math R_4_4_17.mprog --output R_4_4_17.sol (see page http://rosettacode.org/wiki/Category:Mathprog)

The solution may be viewed on this page http://rosettacode.org/wiki/Solution_Ramsey_Mathprog

In the mprog file each clique is named as st<xxxxxx>. A corresponding entry in the solution file identifies the number of nodes connected in this clique. In the second part of the solution the status of each arc in the graph, connected=1 unconnected=0 is shown.