OKlibrary  0.2.1.6
general.hpp File Reference

Plans for the module on searching latin squares and generalisations. More...

Go to the source code of this file.

Namespaces

namespace  OKlib::LatinSquares
 

Tools for latin squares and generalisations and refinements.


namespace  OKlib
 

All components of the OKlibrary.



Detailed Description

Plans for the module on searching latin squares and generalisations.

Todo:
Update namespaces.
Todo:
Update milestones.
Todo:
Update the following todos.
Todo:
Review: Software and literature review.
Todo:
Connections to other modules
Todo:
Basic direct algorithms
Todo:
Active clause-sets
  • By combinining injectivity (bijectivity) constraints, the extension problem for latin squares and the problem of finding mutually orthogonal sets of latin squares (MOLS) shall be provided as an active clause-set.
  • Perhaps the matching techniques underlying the injectivity constraints can be generalised?!
  • Perhaps is makes sense for an array v_ij of variables to have an active clause-set LS((v_ij)), expressing that the variables form a latin square.
  • The direct implementation of LS((v_ij)) uses INJ((v_1j, ..., v_nj) and INJ(v_i1, ..., v_in).
  • Such active clause-sets do not offer poly-time performance for (e.g.) satisfiability checking, but they might be useful if it has nevertheless "special knowledge". LS(V) could offer only incomplete services (then it should be poly-time), or it might offer complete services (then it won't be poly-time).
Todo:
Completing partial latin squares
  • Every partial latin squares of order n with n-1 entries can be completed (and there exists an efficient algorithm for it): How do the various (generalised) SAT algorithms perform here?
  • Consider a partial latin square of order n with n+k entries. One could conjecture that it can be completed iff the alliance of active clause-sets given by the bijectivity-constraints is not found inconsistent by r_k reduction? (The case k = 0 follows by [Andersen, Hilton, 1983].)
Todo:
Strong hypergraph colouring
  • A latin square of dimension n is nothing else than a hypergraph G_n with 2n hyperedges of size n for the rows and columns together with the strong n-colouring problem for hypergraphs (see Hypergraphs/Colourings/plans/StrongColouring.hpp).
  • What can be done specially for latin squares, which cannot be done in general for the strong hypergraph colouring problem? (For example regarding symmetries?)
Todo:
MOLS
  • MOLS((v_ijk)) can be expressed by
    1. LS((v_ij1)), ..., LS((v_ijn))
    2. for 1 <= k1 < k2 <= k introduce variables w_{ij(k1,k2)} with domains {1,...,n}^2 and w_{ij(k1,k2)} = (v1, v2) <-> v_{ijk1} = v1 and v_{ijk2} = v2;
    3. now require INJ(w_{ij(k1,k2)}) for every pair (k1,k2).
  • The second type of active clause-sets can be captured by active clause-sets MOS((v_ij), (v'_ij)) ("mutually orthogonal squares"; note that this notion makes sense for arbitrary squares). Thus MOLS((v_ijk)) becomes the conjunction of LS for all single squares and MOS for all pairs of squares.
  • The new variables w are only necessary if we want to use INJ directly on variables; expressing INJ "by hand", we can express MOS(v, v') as a conjunction of of (n^2 over 2) * n^2 = n^4 * (n^2 - 1) / 2 4-clauses using only the variables v, v'.
  • If n is the uniform domain size (the order of the latin square), then for all 2-sets {(p,q), (p',q')}, where p,q,p',q' in {1, ..., n}, and for all eps, eps' {1, ..., n} we get the 4-clause (v_pq <> eps or v_p'q' <> eps or v'_pq <> eps' or v'_p'q' <> eps').
Todo:
Sizes
  • Thus the sizes for the direct clause representation are (using LS(n) for the clause-set expressing the condition on the existence of a latin square of order n, and MOS(n,k) for the condition on the existence of k squares of order n which are mutually orthogonal):
    1. LS(n) has 2*n*binomial(n,2)*n = n^3 * (n-1) = O(n^4) 2-clauses (using n^2 variables, each with domain size n).
    2. MOS(n, k) has binomial(k,2)*n^4*(n^2-1)/2 = k*(k-1)*n^4*(n^2-1)/4 = O(k^2 * n^6) 4-clauses (using k*n^2 variables, each with domain size n).
    3. MOLS(n,k) has k * n^3 * (n-1) = O(k * n^4) 2-clauses and k*(k-1)*n^4*(n^2-1)/4 = O(k^2 * n^6) 4-clauses (using k*n^2 variables, each with domain size n).
  • For n=10 we get that MOLS(n,k) has k * 9000 2-clauses (9000 for each LS), and k*(k-1) * 247500 4-clauses, and that with k * 100 variables of domain size 10.
  • For k=3 we get 27,000 2-clauses and 1,485,000 4-clauses with 300 variables of domain size 10, which is pretty big. In principle one can run a SAT solver on it, but likely without active clause-sets we won't have a chance.
Todo:
N(n)
  • For n >= 1 let N(n) be the maximal number of MOLS. Thus
    1. N(1) = 1
    2. N(n) <= n - 1 for n >= 2
    3. N(n) = n - 1 if n = p^k for a prime number p and a natural number k >= 1
    4. N(6) = 1
  • This determines N(n) for 1 <= n <= 9. The first open case is N(10).
  • It is known
    1. n notin {1, 2, 6} -> N(n) >= 2
    2. n >= 2: either N(n) = n - 1 or N(n) <= n - 4
    3. N(10) <> 9 (computer experiments showed that there is no projective plane of order 10).
    Thus 2 <= N(10) <= 6 (more recent results?). Can we improve this?!
  • The next case is N(12). It is known that 5 <= N(12) <= 11 (more recent results?); can we improve this?!
  • Apparently for all n >= 11 it is known N(n) >= 3 ?!
  • Two approaches possible: starting from above, showing that the problem is unsatisfiable, or starting from below, showing that the problem is satisfiable.)
  • In general we have:
    1. N(n) = n - 1 iff an affine plane of order n exists iff a projective plane of order n exists.
    2. It is stated in [Beth, Jungnickel, Lenz] that the exact value of N(n) is only known for n = p^k, p prime number, k >= 0, and for n = 6.
Todo:
Experiments
  • So we could try decide MOLS(10,3) or MOLS(10,6) --- in both cases any result SAT/UNSAT would yield a new bound (most interesting: MOLS(10,3) in UNSAT => N(10) = 3, MOLS(10,6) in SAT => N(10) = 6).
  • Not a new result, but still interesting (and publishable) would be, if a generalised SAT solver could show the unsatisfiability of some MOLS(10,k) for 7 <= k <= 9.
Todo:
Pairs of orthogonal latin squares
  • MOLS(n,2) in SAT for all n notin {1,2,6} yields interesting satisfiable problems.
Todo:
The upper bounds for N(k)
  • MOLS(n,n) in UNSAT for all n yields unsatisfiable problems, which could also be interesting (at least for active clause-sets; real clause-sets get very soon very big).

Definition in file general.hpp.