general.hpp File Reference

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

Go to the source code of this file.


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.

Update namespaces.
Update milestones.
Update the following todos.
Review: Software and literature review.
Connections to other modules
Basic direct algorithms
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).
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].)
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?)
  • 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').
  • 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.
  • 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.
  • 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.
Pairs of orthogonal latin squares
  • MOLS(n,2) in SAT for all n notin {1,2,6} yields interesting satisfiable problems.
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.