OKlibrary  0.2.1.6
Certificates.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 15.7.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 
00022 oklib_include("OKlib/ComputerAlgebra/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/RamseyTheory/Lisp/Schur/Certificates.mac")$
00024 
00025 kill(f)$
00026 
00027 
00028 /* *****************
00029    * Basic notions *
00030    *****************
00031 */
00032 
00033 okltest_certificate_schur_p(f) := (
00034   assert(f(1,0,[{}]) = true),
00035   assert(f(1,1,[{}]) = false),
00036   assert(f(1,1,[{1,2}]) = false),
00037   assert(f(1,1,[{1},{1}]) = false),
00038   assert(f(1,1,[{1}]) = true),
00039   assert(f(2,2,[{},{1}]) = false),
00040   assert(f(2,2,[{2},{1}]) = true),
00041   assert(f(2,2,[{1,2},{}]) = false),
00042   assert(f(2,4,[{1,2},{3,4}]) = false),
00043   assert(f(2,4,[{1,4},{2,3}]) = true),
00044   assert(f(3,13,[{1,4,7,10,13},{5,6,8,9},{2,3,11,12}]) = true),
00045   true)$
00046 
00047 okltest_certificate_wschur_p(f) := (
00048   assert(f(1,0,[{}]) = true),
00049   assert(f(1,1,[{}]) = false),
00050   assert(f(1,1,[{1,2}]) = false),
00051   assert(f(1,1,[{1},{1}]) = false),
00052   assert(f(1,1,[{1}]) = true),
00053   assert(f(1,2,[{1,2}]) = true),
00054   assert(f(2,2,[{},{1}]) = false),
00055   assert(f(2,2,[{2},{1}]) = true),
00056   assert(f(2,2,[{1,2},{}]) = true),
00057   assert(f(2,4,[{1,2},{3,4}]) = true),
00058   assert(f(2,4,[{1,4},{2,3}]) = true),
00059   assert(f(2,8,[{1,2,4,8},{3,5,6,7}]) = true),
00060   assert(f(3,13,[{1,4,7,10,13},{5,6,8,9},{2,3,11,12}]) = true),
00061   assert(f(3,23,[{1,2,4,8,11,16,22},{3,5,6,7,19,21,23},{9,10,12,13,14,15,17,18,20}]) = true),
00062   true)$
00063 
00064 okltest_certificate_pdschur_p(f) := (
00065   assert(f(1,0,[{}]) = true),
00066   assert(f(1,1,[{}]) = false),
00067   assert(f(1,1,[{1,2}]) = false),
00068   assert(f(1,1,[{1},{1}]) = false),
00069   assert(f(1,1,[{1}]) = true),
00070   assert(f(2,2,[{},{1}]) = false),
00071   assert(f(2,2,[{1,2},{}]) = false),
00072   assert(f(2,2,[{2},{1}]) = true),
00073   assert(f(2,3,[{1,3},{2}]) = true),
00074   assert(f(2,3,[{1},{2,3}]) = false),
00075   assert(f(2,4,[{1,2},{3,4}]) = false),
00076   assert(f(2,4,[{1,4},{2,3}]) = true),
00077   assert(f(3,5,[{1,3,5},{2},{4}]) = true),
00078   assert(f(3,6,[{1,6},{3,4},{2,5}]) = true),
00079   assert(f(3,6,[{1},{3,4},{2,5,6}]) = false),
00080   assert(f(3,9,[{1,3,7,9},{2,5,8},{4,6}]) = true),
00081   assert(f(3,13,[{1,4,7,10,13},{5,6,8,9},{2,3,11,12}]) = true),
00082   true)$
00083 
00084 okltest_certificate_pdwschur_p(f) := (
00085   assert(f(1,0,[{}]) = true),
00086   assert(f(1,1,[{}]) = false),
00087   assert(f(1,1,[{1,2}]) = false),
00088   assert(f(1,1,[{1},{1}]) = false),
00089   assert(f(1,1,[{1}]) = true),
00090   assert(f(1,2,[{1,2}]) = true),
00091   assert(f(2,2,[{},{1}]) = false),
00092   assert(f(2,2,[{1,2},{}]) = true),
00093   assert(f(2,2,[{2},{1}]) = false),
00094   assert(f(2,3,[{1,3},{2}]) = true),
00095   assert(f(2,3,[{1},{2,3}]) = false),
00096   assert(f(2,4,[{1,2},{3,4}]) = false),
00097   assert(f(2,4,[{1,4},{2,3}]) = true),
00098   assert(f(2,5,[{1,3,5},{2,4}]) = true),
00099   assert(f(3,5,[{1,3,5},{2},{4}]) = false),
00100   assert(f(3,6,[{1,6},{3,4},{2,5}]) = true),
00101   assert(f(3,6,[{1},{3,4},{2,5,6}]) = false),
00102   assert(f(3,13,[{1,4,7,10,13},{5,6,8,9},{2,3,11,12}]) = true),
00103   assert(f(3,14,[{1,4,6,9,11,14},{2,5,10,13},{3,7,8,12}]) = true),
00104   true)$
00105 
00106 okltest_certificate_schurfsb_p(f) := (
00107   assert(f(1,0,[]) = false),
00108   assert(f(1,0,[{}]) = true),
00109   assert(f(1,1,[{}]) = false),
00110   assert(f(1,1,[{1,2}]) = false),
00111   assert(f(1,1,[{1},{1}]) = false),
00112   assert(f(1,1,[{1}]) = true),
00113   assert(f(2,2,[{},{1}]) = false),
00114   assert(f(2,2,[{2},{1}]) = false),
00115   assert(f(2,2,[{1},{2}]) = true),
00116   assert(f(2,2,[{1,2},{}]) = false),
00117   assert(f(2,4,[{1,2},{3,4}]) = false),
00118   assert(f(2,4,[{1,4},{2,3}]) = true),
00119   assert(f(2,4,[{2,3},{1,4}]) = false),
00120   assert(f(3,4,[{1,4},{2,3},{}]) = true),
00121   assert(f(3,4,[{2,3},{1,4},{}]) = false),
00122   assert(f(3,13,[{1,4,7,10,13},{5,6,8,9},{2,3,11,12}]) = false),
00123   assert(f(3,13,[{1,4,7,10,13},{2,3,11,12},{5,6,8,9}]) = true),
00124   true)$
00125 
00126 okltest_certificate_wschurfsb_p(f) := (
00127   assert(f(1,0,[]) = false),
00128   assert(f(1,0,[{}]) = true),
00129   assert(f(1,1,[{}]) = false),
00130   assert(f(1,1,[{1,2}]) = false),
00131   assert(f(1,1,[{1},{1}]) = false),
00132   assert(f(1,1,[{1}]) = true),
00133   assert(f(1,2,[{1,2}]) = true),
00134   assert(f(2,2,[{},{1}]) = false),
00135   assert(f(2,2,[{2},{1}]) = false),
00136   assert(f(2,2,[{1},{2}]) = true),
00137   assert(f(2,2,[{1,2},{}]) = true),
00138   assert(f(2,4,[{1,2},{3,4}]) = true),
00139   assert(f(2,4,[{3,4},{1,2}]) = false),
00140   assert(f(2,4,[{1,4},{2,3}]) = true),
00141   assert(f(2,4,[{2,3},{1,4}]) = false),
00142   assert(f(2,8,[{1,2,4,8},{3,5,6,7}]) = true),
00143   assert(f(2,8,[{3,5,6,7},{1,2,4,8}]) = false),
00144   assert(f(3,8,[{1,2,4,8},{3,5,6,7},{}]) = true),
00145   assert(f(3,8,[{1,2,4,8},{},{3,5,6,7}]) = false),
00146   assert(f(3,13,[{1,4,7,10,13},{5,6,8,9},{2,3,11,12}]) = false),
00147   assert(f(3,13,[{1,4,7,10,13},{2,3,11,12},{5,6,8,9}]) = true),
00148   assert(f(3,23,[{1,2,4,8,11,16,22},{3,5,6,7,19,21,23},{9,10,12,13,14,15,17,18,20}]) = true),
00149   assert(f(3,23,[{3,5,6,7,19,21,23},{1,2,4,8,11,16,22},{9,10,12,13,14,15,17,18,20}]) = false),
00150   true)$
00151 
00152 okltest_certificate_pdschurfsb_p(f) := (
00153   assert(f(1,0,[]) = false),
00154   assert(f(1,0,[{}]) = true),
00155   assert(f(1,1,[{}]) = false),
00156   assert(f(1,1,[{1,2}]) = false),
00157   assert(f(1,1,[{1},{1}]) = false),
00158   assert(f(1,1,[{1}]) = true),
00159   assert(f(2,2,[{},{1}]) = false),
00160   assert(f(2,2,[{1,2},{}]) = false),
00161   assert(f(2,2,[{2},{1}]) = false),
00162   assert(f(2,2,[{1},{2}]) = true),
00163   assert(f(2,3,[{1,3},{2}]) = true),
00164   assert(f(2,3,[{2},{1,3}]) = false),
00165   assert(f(2,3,[{1},{2,3}]) = false),
00166   assert(f(2,4,[{1,2},{3,4}]) = false),
00167   assert(f(2,4,[{1,4},{2,3}]) = true),
00168   assert(f(2,4,[{2,3},{1,4}]) = false),
00169   assert(f(2,4,[{2,3},{1,4}]) = false),
00170   assert(f(3,5,[{1,3,5},{2},{4}]) = true),
00171   assert(f(3,6,[{1,6},{3,4},{2,5}]) = false),
00172   assert(f(3,6,[{1,6},{2,5},{3,4}]) = true),
00173   assert(f(3,6,[{1},{3,4},{2,5,6}]) = false),
00174   assert(f(3,9,[{1,3,7,9},{2,5,8},{4,6}]) = false),
00175   assert(f(3,13,[{1,4,7,10,13},{5,6,8,9},{2,3,11,12}]) = false),
00176   assert(f(3,13,[{1,4,7,10,13},{2,3,11,12},{5,6,8,9}]) = true),
00177   true)$
00178 
00179 okltest_certificate_pdwschurfsb_p(f) := (
00180   assert(f(1,0,[]) = false),
00181   assert(f(1,0,[{}]) = true),
00182   assert(f(1,1,[{}]) = false),
00183   assert(f(1,1,[{1,2}]) = false),
00184   assert(f(1,1,[{1},{1}]) = false),
00185   assert(f(1,1,[{1}]) = true),
00186   assert(f(1,2,[{1,2}]) = true),
00187   assert(f(2,2,[{},{1}]) = false),
00188   assert(f(2,2,[{1,2},{}]) = true),
00189   assert(f(2,2,[{2},{1}]) = false),
00190   assert(f(2,3,[{1,3},{2}]) = true),
00191   assert(f(2,3,[{1},{2,3}]) = false),
00192   assert(f(2,4,[{1,2},{3,4}]) = false),
00193   assert(f(2,4,[{1,4},{2,3}]) = true),
00194   assert(f(2,4,[{2,3},{1,4}]) = false),
00195   assert(f(2,5,[{1,3,5},{2,4}]) = false),
00196   assert(f(3,5,[{1,3,5},{2},{4}]) = false),
00197   assert(f(3,5,[{1,5},{3},{2,4}]) = true),
00198   assert(f(3,6,[{1,6},{3,4},{2,5}]) = true),
00199   assert(f(3,6,[{2,5},{1,6},{3,4}]) = false),
00200   assert(f(3,6,[{1},{3,4},{2,5,6}]) = false),
00201   assert(f(3,13,[{1,4,7,10,13},{5,6,8,9},{2,3,11,12}]) = false),
00202   assert(f(3,13,[{1,4,7,10,13},{2,3,11,12},{5,6,8,9}]) = true),
00203   assert(f(3,14,[{1,4,6,9,11,14},{2,5,10,13},{3,7,8,12}]) = false),
00204   assert(f(3,14,[{1,4,6,9,11,14},{3,7,8,12},{2,5,10,13}]) = true),
00205   true)$
00206 
00207 
00208 /* *******************
00209    * Transformations *
00210    *******************
00211 */
00212 
00213 okltest_uncompresss_schurpalindromic_subsets(f) := (
00214   assert(f(0,[]) = []),
00215   assert(f(0,[{}]) = [{}]),
00216   assert(f(0,[{},{}]) = [{},{}]),
00217   assert(f(1,[{1}]) = [{1}]),
00218   assert(f(1,[{},{1}]) = [{},{1}]),
00219   assert(f(2,[{1},{2}]) = [{1},{2}]),
00220   assert(f(2,[{1,2},{}]) = [{1,2},{}]),
00221   assert(f(3,[{1},{2}]) = [{1,3},{2}]),
00222   assert(f(4,[{1,2}]) = [{1,2,3,4}]),
00223   assert(f(4,[{1},{2},{}]) = [{1,4},{2,3},{}]),
00224   assert(f(5,[{1},{2},{3},{4}]) = [{1,5},{2},{3},{4}]),
00225   true)$
00226 
00227 okltest_uncompresss_wschurpalindromic_subsets(f) := (
00228   assert(f(0,[]) = []),
00229   assert(f(0,[{}]) = [{}]),
00230   assert(f(0,[{},{}]) = [{},{}]),
00231   assert(f(1,[{1}]) = [{1}]),
00232   assert(f(1,[{},{1}]) = [{},{1}]),
00233   assert(f(2,[{1},{}]) = [{1,2},{}]),
00234   assert(f(2,[{1,2},{}]) = [{1,2},{}]),
00235   assert(f(3,[{1},{2}]) = [{1,3},{2}]),
00236   assert(f(4,[{1,2}]) = [{1,2,3,4}]),
00237   assert(f(4,[{1},{2},{}]) = [{1,4},{2,3},{}]),
00238   assert(f(5,[{1},{2},{3},{4}]) = [{1,5},{2,4},{3},{2,4}]),
00239   assert(f(5,[{1},{2},{3}]) = [{1,5},{2,4},{3}]),
00240   true)$
00241 
00242 
00243 /* **************************
00244    * Analysing certificates *
00245    **************************
00246 */
00247 
00248 okltest_depth_partition(f) := (
00249   assert(f([]) = minf),
00250   assert(f([{}]) = inf),
00251   assert(f([{1},{2},{3}]) = 3),
00252   assert(f([{1,4},{2,3},{5,1}]) = 2),
00253   true)$
00254 
00255 okltest_edepth_partition(f) := (
00256   assert(f([{1}]) = 1),
00257   assert(f([{1,2}]) = 1),
00258   assert(f([{1},{2}]) = 2),
00259   assert(f([{1,3},{2}]) = 2),
00260   assert(f([{1,4},{2,3}]) = 2),
00261   assert(f([{1,3,5},{2},{4}]) = 4),
00262   assert(f([{1,6},{3,4},{2,5}]) = 3),
00263   assert(f([{1,3,7,9},{2,5,8},{4,6}]) = 4),
00264   assert(f([{1,4,7,10,13},{5,6,8,9},{2,3,11,12}]) = 5),
00265   /* XXX */
00266   true)$
00267