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