OKlibrary  0.2.1.6
Ramsey.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 5.8.2012 (Swansea) */
00002 /* Copyright 2012 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00023 /* ********************
00024    * Ramsey's theorem *
00025    ********************
00026 */
00027 
00028 /* We now consider the underlying hypergraphs for Ramsey problems, that is,
00029    for r-graphs with n vertices we consider q-cliques, and a counter-example
00030    showing that ramsey_s^r(q,q,...,q) > n, where the list of q's has length s,
00031    is a hypergraph colouring using s colours of the following hypergraph.
00032    In other words, ramsey_hg(q,r,n) has as vertices the r-subsets
00033    of {1,...,n}, while a hyperedge is given by the set of r-subsets
00034    of any q-subset of {1,...,n}.
00035    Prerequisites: q,r,n >= 0.
00036 */
00037 ramsey_hg(q,r,n) := block([V0 : setn(n), V],
00038  V : powerset(V0,r),
00039  if q>n then [V,{}]
00040  elseif r>q then [V,{}]
00041  else
00042   [V, map(lambda([T],powerset(T,r)),powerset(V0,q))])$
00043 /* The ordered version, using lexicographical ordering on the vertices
00044    as well as on the hyperedges (considered as q-subsets):
00045 */
00046 ramsey_ohg(q,r,n) := block([V0 : setn(n), V],
00047  V : listify(powerset(V0,r)),
00048  if q>n then [V,[]]
00049  elseif r=0 then [V,[{{}}]]
00050  elseif r>q then [V,[]]
00051  else
00052   [V, map(lambda([T],powerset(T,r)), listify(powerset(V0,q)))])$
00053 
00054 /* Now using vertices e.g. "rv(1,2,3)" instead of "{1,2,3}". */
00055 
00056 kill(rv)$
00057 declare(rv,noun)$
00058 rv_var([L]) := apply(nounify(rv),L)$
00059 set_rv(s) := apply(rv_var,listify(s))$
00060 
00061 ramseyrv_ohg(q,r,n) := block([V0 : setn(n), V],
00062  V : map(set_rv,listify(powerset(V0,r))),
00063  if q>n then [V,[]]
00064  elseif r=0 then [V,[{{}}]]
00065  elseif r>q then [V,[]]
00066  else
00067   [V, map(lambda([T],map(set_rv,powerset(T,r))), listify(powerset(V0,q)))])$
00068 
00069 /* Standardised Ramsey hypergraphs, now using colexicographical ordering of
00070    the vertices (as r-subsets of {1,...,n}) to convert them into natural
00071    numbers (while keeping the lexicographical order of hyperedges, as in
00072    ramseyrv_ohg):
00073 */
00074 ramsey_stdohg(q,r,n) :=
00075  ev(ramseyrv_ohg(q,r,n), rv([L]):=rank_colex_ksubsets(setify(L)), rv)$
00076 /* Note that the vertex list is ordered in such a way to keep the
00077    correspondence to the lexicographical ordering of the vertices.
00078 */
00079 
00080 
00081 /* Statistics functions: */
00082 
00083 nver_ramsey_hg(q,r,n) := binomial(n,r)$
00084 nver_ramsey_ohg(q,r,n) := binomial(n,r)$
00085 nver_ramsey_stdohg(q,r,n) := binomial(n,r)$
00086 
00087 nhyp_ramsey_hg(q,r,n) :=
00088   if q > n then 0
00089   elseif r > n then 0
00090   else if r > q then 0
00091   elseif r = 0 then 1
00092   else binomial(n,q)$
00093 nhyp_ramsey_ohg(q,r,n) :=
00094   if q > n then 0
00095   elseif r > n then 0
00096   else if r > q then 0
00097   elseif r = 0 then 1
00098   else binomial(n,q)$
00099 
00100