OKlibrary  0.2.1.6
BasicNotions.mac
Go to the documentation of this file.
```00001 /* Oliver Kullmann, 6.8.2008 (Swansea) */
00002 /* Copyright 2008 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/CombinatorialMatrices/Lisp/Basics.mac")\$
00023
00024 /* *****************
00025    * Basic notions *
00026    *****************
00027 */
00028
00029 ics_p(S) := listp(S) and is(length(S) = 3) and com_p([S[2],S[3],S[1]])\$
00030
00031
00032 /* *********************
00033    * Checking equality *
00034    *********************
00035 */
00036
00037 ics_equalp(S1,S2) := com_equalp(ics2com(S1),ics2com(S2))\$
00038
00039
00040 /* ***************
00041    * Conversions *
00042    ***************
00043 */
00044
00045 /* The point-block incidence matrix: */
00046 ics2com(S) := [S[2],S[3],S[1]]\$
00047 /* Interpreting combinatorial matrices as incidence structures: */
00048 com2ics(M) := [M[3],M[1],M[2]]\$
00049
00050 /* The point-adjacency matrix: */
00051 ics2scom_p(S) := block([IM : ics2com(S)],
00052   prod_com(IM, IM))\$
00053 /* The block-adjacency matrix: */
00054 ics2scom_b(S) := block([IM : trans_com(ics2com(S))],
00055   prod_com(IM, IM))\$
00056
00057 /* The associated general hypergraph: */
00058 ics2ghg(S) := [S[2],S[3],buildq([S],lambda([H],subset(S[2],lambda([v],is(S[3](v,H)=1)))))]\$
00059 /* Remark: ics2ghg(S) = com2ghg(ics2com(S)). */
00060 /* General hypergraphs as incidence structures: */
00061 ghg2ics(G) := [lambda([p,b], if elementp(p,b) then 1 else 0), G[1], G[2]]\$
00062 /* Remark: ghg2ics(G) = com2ics(trans_com(edge_vertex_com_hyp(G))). */
00063
00064
00065 /* *******************
00066    * Main parameters *
00067    *******************
00068 */
00069
00070 balanced_ics_p(S,t,index) := every_s(
00071   lambda([T], is(
00072     length(subset(S[3], lambda([b],
00073       every_s(lambda([p], is(S[1](p,b) = 1)), T)))))
00074     = index),
00075   powerset(S[2],t))\$
00076 /* If balanced_ics_p(S,t,i) is true, then S is a "t-balanced design (with
00077    index i)".
00078 */
00079
00080 /* The special case for t=0 (the number of blocks): */
00081 blockcount_ics_p(S,b) := is(length(S[3]) = b)\$
00082 /* Remark: blockcount_ics_p(S,b) = balanced_ics_p(S,0,b). */
00083
00084 /* The special case for t=1 (regularity ("repetition number")): */
00085 regular_ics_p(S,r) := block([reg : true],
00086   for p in S[2] while reg do
00087     reg : is(sum_l(map(lambda([b], S[1](p,b)), S[3])) = r),
00088   return(reg))\$
00089 /* Remark: regular_ics_p(S,r) = balanced_ics_p(S,1,r). */
00090 /* Also: regular_ics_p(S,r) is true iff all diagonal entries of
00091    ics2scom_p(S) are equal to r.
00092 */
00093
00094 /* The special case for t=2 ("pairwise balanced designs"): */
00095 pairwisebalanced_p(S,index) := every_ndiagc_scom_p(ics2scom_p(S), index)\$
00096 /* Remark: pairwisebalanced_p(S,index) = balanced_ics_p(S,2,index). */
00097
00098 /* The dual cases: */
00099
00100 /* The number of points: */
00101 pointcount_ics_p(S,v) := is(length(S[2]) = v)\$
00102 /* Remark: pointcount_ics_p(S,v) = balanced_ics_p(dual_ics(S),0,v). */
00103
00104 /* The block size (uniformity): */
00105 uniform_ics_p(S,k) := block([unif : true],
00106   for b in S[3] while unif do
00107     unif : is(sum_l(map(lambda([p], S[1](p,b)), S[2])) = k),
00108   return(unif))\$
00109 /* Remark: uniform_ics_p(S,k) = balanced_ics_p(dual_ics(S),1,k). */
00110 /* Also: uniform_ics_p(S,k) is true iff all diagonal entries of
00111    ics2scom_b(S) are equal to k.
00112 */
00113
00114 /* The block-intersection sizes (for pairs of different blocks): */
00115 dual_pairwisebalanced_p(S,index) := every_ndiagc_scom_p(ics2scom_b(S), index)\$
00116 /* Remark: dual_pairwisebalanced_p(S,index) = balanced_ics_p(dual_ics(S),2,index). */
00117
00118
00119 /* Generalisations for regularity and uniformity (given by sets
00120    of possible values): */
00121 degree_set_ics_p(S,D) := block([reg : true],
00122   for p in S[2] while reg do
00123     reg : elementp(sum_l(map(lambda([b], S[1](p,b)), S[3])), D),
00124   return(reg))\$
00125 /* Remark: regular_ics_p(S,r) = degree_set_ics_p(S,{r}). */
00126 blocksize_set_ics_p(S,K) := block([unif : true],
00127   for b in S[3] while unif do
00128     unif : elementp(sum_l(map(lambda([p], S[1](p,b)), S[2])), K),
00129   return(unif))\$
00130 /* Remark: uniform_ics_p(S,k) = blocksize_set_ics_p(S,{k}). */
00131
00132
00133 /* Generalisations for index and dual index (given by sets of
00134    possible values): */
00135 pairwisebalanced_set_p(S,I) := every_ndiag_scom_p(lambda([x],elementp(x,I)),ics2scom_p(S))\$
00136 /* Remark: pairwisebalanced_p(S,index) = pairwisebalanced_set_p(S,{index}). */
00137 dual_pairwisebalanced_set_p(S,I) := every_ndiag_scom_p(lambda([x],elementp(x,I)),ics2scom_b(S))\$
00138 /* Remark: dual_pairwisebalanced_p(S,index) = dual_pairwisebalanced_set_p(S,{index}). */
00139
00140
00141 /* ***********************
00142    * Basic constructions *
00143    ***********************
00144 */
00145
00146 dual_ics(S) := [buildq([S],lambda([p,b],S[1](b,p))),S[3],S[2]]\$
00147
00148
00149 /* ********************
00150    * Basic properties *
00151    ********************
00152 */
00153
00154 square_design_p(S) := is(length(S[2]) = length(S[3]))\$
00155
00156 /* Geometries: */
00157
00158 partial_geometry_p(S) := pairwisebalanced_set_p(S,{0,1})\$
00159 linear_design_p(S) := pairwisebalanced_p(S,1)\$
00160 projective_incidence_plans_p(S) := linear_design_p(S) and
00161   linear_design_p(dual_ics(S))\$
00162
00163 /* Steiner-Systems and generalisations: */
00164
00165 regular_balanced_p(S,t,index,r) := balanced_ics_p(S,t,index) and regular_ics_p(S,r)\$
00166
00167 uniform_balanced_p(S,t,index,k) := balanced_ics_p(S,t,index) and uniform_ics_p(S,k)\$
00168 /* Remark: Uniform balanced designs are also regular. */
00169 design_p(S,t,k,v,index) := uniform_balanced_p(S,t,index,k) and pointcount_ics_p(S,v)\$
00170
00171 steiner_p(S,t,k,v) := design_p(S,t,k,v,1)\$
00172
00173 /* Steiner triple system: */
00174 sts_p(S,v) := steiner_p(S,2,3,v)\$
00175 /* Steiner quadruple system: */
00176 sqs_p(S,v) := steiner_p(S,3,4,v)\$
00177
```