Certificates.hpp File Reference

Plans regarding van der Waerden certificates. More...

Go to the source code of this file.

Detailed Description

Plans regarding van der Waerden certificates.

DONE The notion of a "certificate"
  • A "certificate" for a pair [L,n], where L is a parameter tuple of length m and n is a natural number, corresponds to a solution of vanderwaerden_nbfclud(L,n), that is, certifies that vanderwaerden(L) > n.
  • We need a good mathematical presentation of such certificates.
    1. Reasonably seems to use a list Z of length n with numbers 1, ..., m, denoting the map {1,...,n} -> {1,...,m}.
    2. "Z" looks like a reasonable letter here: capital since it's a list, and "Z" for "Zertifikat" ("C" can not be used).
    3. More precisely these are "vdW-certificates".
    4. However, more natural seems to use a block partition P of {1,...,n} via m blocks.
    5. Given such a certificate P, via certificatevdw2list(P) the list is created, compressing multiple successive occurrences of indices i into pairs [i,k], where k counts the number of occurrences.
  • certificate_vdW_p(L,n,P) checks whether P is indeed a certificate.
Implementation certificate_vdw_p(L,n,P)
  • See ComputerAlgebra/RamseyTheory/Lisp/VanderWaerden/Hypergraphs.mac.
  • This function uses the representation of a certificate for [L,n] as a list P of the same size as L, with subsets of {1,...,n} representing a partitioning.
  • DONE Perhaps we should have a dedicated file "Certificates.mac".
  • The current check is rather slow: check_certificate_vdw([3,24],578,P) in Experimentation/Investigations/RamseyTheory/VanderWaerdenProblems/plans/3-k/24.hpp needed 82 seconds on csltok (the new laptop, not slow).
  • An alternative algorithm is to create all possible arithmetic progressions of the given lengths and to check whether each of them is not contained in the corresponding blocks of the partition.
    1. This should be faster if the block contains many elements.
    2. However otherwise it should be slower.
  • Or the current algorithm could use an array, which yields for each possible vertex its block (colour); this depends on having a linear order and "all vertices", but for that situation it is faster.
  • At the Maxima-level we consider only the fundamental algorithmic possibilities; this issue seems also very much a data-structure issue, and this can be handled properly only at C++ level. See "Checking certificates" in Applications/RamseyTheory/plans/VanderWaerden.hpp.
  • We should also use "every_s" (once it can handle multiple lists).
  • We need translations from satisfying assignments of vanderwaerden_nbfclud(L,n) to certificates and back.
    1. If a vertex i in {1,...,n} does not get a value, we can denote this by value 0 in the certificate.
    2. Or we use the maxima-value "ind".
  • It would also be useful to translate certificates to partitions and back. This can be done in general (every map induces a canonical partition on its domain).
Analysing certificates
  • We need a function to compute the Hamming-distance between two certificates.
  • Given one certificate, we need a function to find all other certificates which have at most a specified distance to the given one.
  • At least with vdw_2(3,k) it seems common that in the neighbourhoods of certificates you find other certificates; see "Analysing certificates" in Experimentation/Investigations/RamseyTheory/VanderWaerdenProblems/plans/3-k/general.hpp

Definition in file Certificates.hpp.