OKlibrary  0.2.1.6
Numbers.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 27.7.2008 (Swansea) */
00002 /* Copyright 2008, 2009, 2010, 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 
00022 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00023 
00024 
00025 /* ******************
00026    * Ramsey numbers *
00027    ******************
00028 */
00029 
00030 /* A "Ramsey parameter tuple" is a pair [r,L], where r is the length of the
00031    hyperedges considered, the length of L is the number of colours/parts, and 
00032    each entry of L specifies the size of the complete r-hypergraph, whose 
00033    existence as (subgraph) the Ramsey numbers shall guarantee.
00034 */
00035 
00036 /* Bounds for Ramsey numbers are given as integers if the exact bound is known.
00037  * and pairs [lower bounds, upper bounds] otherwise (which must be correct).
00038 */
00039 
00040 /* Returns the current bounds known for the given Ramsey parameter tuple.
00041    In the case nothing is known, unknown is returned. */
00042 ramsey(param_tuple) := 
00043   if ramseyr0_a(param_tuple)#[] then
00044     apply(ramseyr0,ramseyr0_a(param_tuple))
00045   elseif ramseytrivle_a(param_tuple)#[] then 
00046     apply(ramseytrivle,ramseytrivle_a(param_tuple))
00047   elseif ramseytriveq_a(param_tuple)#[] then 
00048     apply(ramseytriveq,ramseytriveq_a(param_tuple))
00049   elseif ramseytrivk_a(param_tuple)#[] then 
00050     apply(ramseytrivk,ramseytrivk_a(param_tuple))
00051   elseif ramseyg2_3_a(param_tuple)#[] then 
00052     apply(ramseyg2_3,ramseyg2_3_a(param_tuple))
00053   elseif ramseyg2_4_a(param_tuple)#[] then 
00054     apply(ramseyg2_4,ramseyg2_4_a(param_tuple))
00055   elseif ramseyg2_5_a(param_tuple)#[] then 
00056     apply(ramseyg2_5,ramseyg2_5_a(param_tuple))
00057   elseif ramseyg2_6_a(param_tuple)#[] then 
00058     apply(ramseyg2_6,ramseyg2_6_a(param_tuple))
00059   elseif ramseyg2_7_a(param_tuple)#[] then 
00060     apply(ramseyg2_7,ramseyg2_7_a(param_tuple))
00061   elseif ramseyg2_8_a(param_tuple)#[] then 
00062     apply(ramseyg2_8,ramseyg2_8_a(param_tuple))
00063   elseif ramseyg2_9_a(param_tuple)#[] then 
00064     apply(ramseyg2_9,ramseyg2_9_a(param_tuple))
00065   elseif ramseyg2_10_a(param_tuple)#[] then 
00066     apply(ramseyg2_10,ramseyg2_10_a(param_tuple))
00067   elseif ramseyg3_3_3_a(param_tuple)#[] then 
00068     apply(ramseyg3_3_3,ramseyg3_3_3_a(param_tuple))
00069   elseif ramseyhg3_2_4_a(param_tuple)#[] then 
00070     apply(ramseyhg3_2_4,ramseyhg3_2_4_a(param_tuple))
00071   else unknown$
00072 
00073 /* Checking whether L is a valid Ramsey parameter tuple: */
00074 ramsey_p(L) := 
00075   listp(L) and length(L) > 1 and
00076   integerp(L[1]) and L[1] >= 0 and 
00077   listp(L[2]) and length(L[2]) > 0 and every_s(integerp,L[2]) and
00078   every_s(lambda([a], is(a >= 0)), L[2])$
00079 
00080 /*
00081   There are numerous different "cases" for the known Ramsey number and so the
00082   lookup or computation of these number is split into many functions, which are
00083   then combined in "ramsey".
00084 
00085   For each case, there are two functions "ramseyXXX_a" and "ramseyXXX" where 
00086   XXX is a short abbreviation for the name/concept associated with the case.
00087 
00088   The "ramseyXXX_a" function takes an arbitrary Ramsey parameter tuple and 
00089   returns either [], in which case this "case" does not apply to the given 
00090   tuple, or it returns a list of arguments for ramseyXXX, in which case it does
00091   and ramseyXXX, given these arguments will return the Ramsey number for that
00092   tuple.
00093 
00094   These "cases" are split into 4 main groups.
00095 
00096   The "trivial cases" are those which can be computed directly, based on the
00097   definition of the Ramsey numbers.
00098 
00099   The "two-colour graph cases" are those which are associated with Ramsey
00100   problems with tuples of the form [2,[p,q]], and their associated functions
00101   are "ramseyg2_p_a" and "ramseyg2_p", where "ramseyg2_p" takes q as an
00102   argument.
00103 
00104   The "multi-colour graph cases" are those which are associated with Ramsey
00105   problems with tuples of the form [2,[p1,...,pn], and their associated 
00106   functions are "ramseyg2_p1_..._p(n-1)_a" and "ramseyg2_p1_..._p(n-1)", where 
00107   "ramseyg2_p1_..._p(n-1)" takes "pn" as an argument.
00108   
00109   The "hypergraph cases" are those which are associated with Ramsey
00110   problems with tuples of the form [r,[p1,...,pn], and their associated 
00111   functions are "ramseygr_p1_..._p(n-1)_a" and "ramseygr_p1_..._p(n-1)", where 
00112   "ramseygr_p1_..._p(n-1)" takes "pn" as an argument.
00113 
00114 */
00115 
00116 /* *****************
00117    * Trivial cases *
00118    *****************
00119 */
00120 
00121 /* If L[1] = 0 then the set of all 0-subsets of any set is {{}}, 
00122    and so as soon as */
00123 
00124 /* Given a Ramsey parameter tuple L, returns [0] if L[1] = 0 and 
00125    length(L[2]) > 0, otherwise it returns []. */
00126 ramseyr0_a(L) :=
00127   if length(L) = 2 and listp(L[2]) and length(L[2]) > 0 and 
00128      L[1] = 0 then [last(L[2])]
00129   else []$
00130 ramseyr0(z) := z$
00131 
00132 /* If min(L[2]) < L[1] then the set of all L[1]-subsets of {1,..,min(L)} is 
00133    empty, and the Ramsey number is simply min(L).  */
00134 
00135 /* Given a Ramsey parameter tuple L, returns a list with the minimum 
00136    element of L[2] if min(L[2]) < L[1], otherwise it returns []. */
00137 ramseytrivle_a(L) :=
00138   if length(L) = 2 and listp(L[2]) and length(L[2]) > 0 and 
00139      integerp(L[1]) and integerp(first(L[2])) and
00140      L[1] >= 0 and L[2][1] >= 0 and
00141      first(L[2]) < L[1] then [first(L[2])]
00142   else []$
00143 /* Given the minimum element "q" of a Ramsey parameter tuple's L[2], and
00144    assuming "q < L[2]", return the Ramsey number for this tuple. */
00145 ramseytrivle(min_qi) := min_qi$
00146 
00147 
00148 /* If min(L[2]) = L[1] then that part can not be used without making an 
00149    L[1]-clique, so there is simply the remaining Ramsey problem without that 
00150    part. */
00151 
00152 /* Given a Ramsey parameter tuple L, returns the original L with the minimum
00153    element of L[2] removed if min(L[2]) = L[1], otherwise it returns []. */
00154 ramseytriveq_a(L) := 
00155   if length(L) = 2 and listp(L[2]) and length(L[2]) > 0 and 
00156      integerp(L[1]) and integerp(first(L[2])) and
00157      L[1] >= 0 and L[2][1] >= 0 and
00158      first(L[2]) = L[1] then [[L[1],rest(L[2])]]
00159   else []$
00160 /* Given a Ramsey parameter tuple L, returns the Ramsey number for this
00161    tuple. 
00162    
00163    The assumption is that this L has had a value removed from L[2] based
00164    on ramseytriveq_a. */
00165 ramseytriveq(L) := ramsey(L)$
00166 
00167 
00168 /* If length(L[2]) < 2 then the Ramsey number is simply the first time there 
00169    are enough vertices for a L[2][1]-clique, as there is only one part. */
00170 
00171 /* Given a Ramsey parameter tuple L, returns a list with the first element
00172    of L[2] if length(L[2]) = 1, otherwise it returns []. */
00173 ramseytrivk_a(L) := 
00174   if length(L) = 2 and listp(L[2]) and length(L[2]) = 1 and 
00175      integerp(L[1]) and integerp(first(L[2])) and
00176      L[1] >= 0 and L[2][1] >= 0 then [first(L[2])]
00177   else []$
00178 /* Given an element "q" of a Ramsey parameter tuple whose L[2] contains only 
00179    "q" returns the Ramsey number for this tuple. */
00180 ramseytrivk(q) := q$
00181 
00182 
00183 /* *********************
00184    * Two-colour graphs *
00185    *********************
00186 */
00187 
00188 /* Given a Ramsey parameter tuple L, returns a list with "q" as the only 
00189    element if L is of the form [2,[3,q]], otherwise returns []. */
00190 ramseyg2_3_a(L) := 
00191   if length(L) = 2 and listp(L[2]) and length(L[2]) = 2 and 
00192      L[1] = 2 and first(L[2]) = 3 and integerp(second(L[2])) and
00193      second(L[2]) >= 0 then [last(L[2])]
00194   else []$
00195 /* Returns the Ramsey number for a Ramsey parameter tuple of the form 
00196    [2,[3,q]].*/
00197 ramseyg2_3(q) := 
00198   if q <= 15 then
00199     [1,3,6,9,14,18,23,28,36,
00200      [40,43],[46,51],[52,59],[59,59],[66,78],[73,88]][q]
00201   else unknown$
00202 
00203 
00204 /* Given a Ramsey parameter tuple L, returns a list with "q" as the only 
00205    element if L is of the form [2,[4,q]], otherwise returns []. */
00206 ramseyg2_4_a(L) := 
00207   if length(L) = 2 and listp(L[2]) and length(L[2]) = 2 and 
00208      L[1] = 2 and first(L[2]) = 4 and integerp(second(L[2])) and
00209      second(L[2]) >= 0 then [last(L[2])]
00210   else []$
00211 /* Returns the Ramsey number for a Ramsey parameter tuple of the form 
00212    [2,[4,q]].*/
00213 ramseyg2_4(q) := 
00214   if q <= 15 then
00215     [1,4,9,18,25,
00216      [35,41],[49,61],[56,84],[73,115],[92,149],[97,191],[128,238],[133,291],
00217      [141,349],[153,417]][q]
00218   else unknown$
00219 
00220 
00221 /* Given a Ramsey parameter tuple L, returns a list with "q" as the only 
00222    element if L is of the form [2,[5,q]], otherwise returns []. */
00223 ramseyg2_5_a(L) := 
00224   if length(L) = 2 and listp(L[2]) and length(L[2]) = 2 and 
00225      L[1] = 2 and first(L[2]) = 5 and integerp(second(L[2])) and
00226      second(L[2]) >= 0 then [last(L[2])]
00227   else []$
00228 /* Returns the Ramsey number for a Ramsey parameter tuple of the form 
00229    [2,[5,q]].*/
00230 ramseyg2_5(q) := 
00231   if q <= 15 then
00232     [1,5,14,25,[43,49],
00233      [58,87],[80,143],[101,216],[125,316],[143,442],[159,inf],[185,848],[209,inf],
00234      [235,1461],[265,inf]][q]
00235   else unknown$
00236 
00237 /* Given a Ramsey parameter tuple L, returns a list with "q" as the only 
00238    element if L is of the form [2,[6,q]], otherwise returns []. */
00239 ramseyg2_6_a(L) := 
00240   if length(L) = 2 and listp(L[2]) and length(L[2]) = 2 and 
00241      L[1] = 2 and first(L[2]) = 6 and integerp(second(L[2])) and
00242      second(L[2]) >= 0 then [last(L[2])]
00243   else []$
00244 /* Returns the Ramsey number for a Ramsey parameter tuple of the form 
00245    [2,[6,q]].*/
00246 ramseyg2_6(q) := 
00247   if q <= 15 then
00248     [1,6,18,[35,41],[58,87],
00249      [102,165],[113,298],[127,495],[169,780],[179,1171],[253,inf],[262,2566],[317,inf],
00250      [0,5033],[401,inf]][q]
00251   else unknown$
00252 
00253 /* Given a Ramsey parameter tuple L, returns a list with "q" as the only 
00254    element if L is of the form [2,[7,q]], otherwise returns []. */
00255 ramseyg2_7_a(L) := 
00256   if length(L) = 2 and listp(L[2]) and length(L[2]) = 2 and 
00257      L[1] = 2 and first(L[2]) = 7 and integerp(second(L[2])) and
00258      second(L[2]) >= 0 then [last(L[2])]
00259   else []$
00260 /* Returns the Ramsey number for a Ramsey parameter tuple of the form 
00261    [2,[7,q]].*/
00262 ramseyg2_7(q) := 
00263   if q <= 15 then
00264     [1,7,23,[49,61],[80,143],
00265      [113,298],[205,540],[216,1031],[233,1713],[289,2826],[405,4553],[416,6954],[511,10581],
00266      [0,15263],[0,22116]][q]
00267   else unknown$
00268 
00269 
00270 /* Given a Ramsey parameter tuple L, returns a list with "q" as the only 
00271    element if L is of the form [2,[8,q]], otherwise returns []. */
00272 ramseyg2_8_a(L) := 
00273   if length(L) = 2 and listp(L[2]) and length(L[2]) = 2 and 
00274      L[1] = 2 and first(L[2]) = 8 and integerp(second(L[2])) and
00275      second(L[2]) >= 0 then [last(L[2])]
00276   else []$
00277 /* Returns the Ramsey number for a Ramsey parameter tuple of the form 
00278    [2,[8,q]].*/
00279 ramseyg2_8(q) := 
00280   if q <= 15 then
00281     [1,8,28,[56,84],[101,216],
00282      [127,495],[216,1031],[282,1870],[317,3583],[0,6090],[0,10630],[0,16944],[817,27490],
00283      [0,41525],[861,63620]][q]
00284   else unknown$
00285 
00286 
00287 /* Given a Ramsey parameter tuple L, returns a list with "q" as the only 
00288    element if L is of the form [2,[9,q]], otherwise returns []. */
00289 ramseyg2_9_a(L) := 
00290   if length(L) = 2 and listp(L[2]) and length(L[2]) = 2 and 
00291      L[1] = 2 and first(L[2]) = 9 and integerp(second(L[2])) and
00292      second(L[2]) >= 0 then [last(L[2])]
00293   else []$
00294 /* Returns the Ramsey number for a Ramsey parameter tuple of the form 
00295    [2,[9,q]].*/
00296 ramseyg2_9(q) := 
00297   if q <= 14 then
00298     [1,9,36,[73,115],[125,316],
00299      [169,780],[233,1713],[317,3583],[565,6588],[580,12677],[0,22325],[0,39025],[0,64871],
00300      [0,89203]][q]
00301   else unknown$
00302 
00303 
00304 /* Given a Ramsey parameter tuple L, returns a list with "q" as the only 
00305    element if L is of the form [2,[10,q]], otherwise returns []. */
00306 ramseyg2_10_a(L) := 
00307   if length(L) = 2 and listp(L[2]) and length(L[2]) = 2 and 
00308      L[1] = 2 and first(L[2]) = 10 and integerp(second(L[2])) and
00309      second(L[2]) >= 0 then [last(L[2])]
00310   else []$
00311 /* Returns the Ramsey number for a Ramsey parameter tuple of the form 
00312    [2,[10,q]].*/
00313 ramseyg2_10(q) := 
00314   if q <= 15 then
00315     [1,10,[40,43],[92,149],[143,442],
00316      [179,1171],[289,2826],[0,6090],[580,12677],[798,23556],unknown,[0,81200],unknown,
00317      unknown,[1265,inf]][q]
00318   else unknown$
00319 
00320 /* **********
00321    * Graphs *
00322    **********
00323 */
00324 
00325 /* Given a Ramsey parameter tuple L, returns a list with "q" as the only 
00326    element if L is of the form [2,[3,3,q]], otherwise returns []. */
00327 ramseyg3_3_3_a(L) := 
00328   if length(L) = 2 and listp(L[2]) and length(L[2]) = 3 and 
00329      L[1] = 2 and first(L[2]) = 3 and second(L[2]) = 3 and 
00330      integerp(third(L[2])) and third(L[2]) >= 0 then [last(L[2])]
00331   else []$
00332 /* Returns the Ramsey number for a Ramsey parameter tuple of the form 
00333    [2,[3,3,q]].*/
00334 ramseyg3_3_3(q) := 
00335   if q <= 3 then 
00336     [1,6,17][q] 
00337   else unknown$
00338 
00339 
00340 /* ***************
00341    * Hypergraphs *
00342    ***************
00343 */
00344 
00345 /* Given a Ramsey parameter tuple L, returns a list with "q" as the only 
00346    element if L is of the form [3,[4,q]], otherwise returns []. */
00347 ramseyhg3_2_4_a(L) := 
00348   if length(L) = 2 and listp(L[2]) and length(L[2]) = 2 and 
00349      L[1] = 3 and first(L[2]) = 4 and integerp(second(L[2])) and 
00350      second(L[2]) >= 0 then [last(L[2])]
00351   else []$
00352 /* Returns the Ramsey number for a Ramsey parameter tuple of the form 
00353    [3,[4,q]].*/
00354 ramseyhg3_2_4(q) := 
00355   if q = 4 then 13 else unknown$
00356 
00357 
00358 /* ***********
00359    * Bounds  *
00360    ***********
00361 */
00362 
00363 /* Returns the upper bound given the result of a call to "ramsey": */
00364 ramsey_ub(n) := if listp(n) then last(n) else n$
00365 /* Returns the upper bound given the result of a call to "ramsey" safely,
00366    i.e. if the value is unknown, then infinity is returned (so this can be
00367    used without checking the return value). */
00368 ramsey_ub_s(n) := block([ret],
00369   ret : if listp(n) then last(n) else n,
00370   return(if ret = unknown then inf else ret))$
00371 
00372 
00373 /* Returns the lower bound given the result of a call to "ramsey": */
00374 ramsey_lb(n) := if listp(n) then first(n) else n$
00375 /* Returns the lower bound given the result of a call to "ramsey" safely,
00376    i.e. if the value is unknown, then 0 is returned (so this can be
00377    used without checking the return value). */
00378 ramsey_lb_s(n) := block([ret],
00379   ret : if listp(n) then first(n) else n,
00380   return(if ret = unknown then 0 else ret))$
00381