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

<lang> /*Ramsey 4 4 17

 This model finds a graph with 17 Nodes such that no clique of 4 Nodes is either fully
 connected, nor fully disconnected

 Nigel_Galloway
 January 18th., 2012

• /

param Nodes := 17; var Arc{1..Nodes, 1..Nodes}, binary;

clique{a in 1..(Nodes-3), b in (a+1)..(Nodes-2), c in (b+1)..(Nodes-1), d in (c+1)..Nodes} : 1 <= Arc[a,b] + Arc[a,c] + Arc[a,d] + Arc[b,c] + Arc[b,d] + Arc[c,d] <= 5;

end; </lang>

This may be run:

glpsol --minisat --math R_4_4_17.mprog --output R_4_4_17.sol

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

In the solution file the first section 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.