Numbers.hpp File Reference

Plans regarding Ramsey numbers. More...

Go to the source code of this file.

Detailed Description

Plans regarding Ramsey numbers.

Incorrect parameter checking
  • The current implementation of ramsey_p is obviously incorrect.
  • DONE The parameter transformations should be informative, and thus should not use ramsey_p (they should be understandable on their own, and should exactly specify the case).
  • DONE All implementations of parameter-transformers (like "ramseytrivle_a") are incorrect: Every such function must work on every possible list.
  • DONE Before performing the correction, first the tests need to be updated to detect the errors (as usual).
Weak specifications
  • There are often no explanations about the meaning of the different cases.
  • The "_a"-functions need a general explanation about their usage, and then their specification should just state (as clearly as possible) the special case handled.
Write docus
Add known Ramsey bounds
  • Some bounds are in the current system but all bounds known should be represented in the system.
  • See the running report of [Radziszowski, Small Ramsey Numbers].
  • Also in the eis-database we should find Ramsey-numbers.
  • References for the bounds; compare "Bibtex-database" in OKlib/plans/Annotations.hpp.
Proofs of numbers
  • The question here is how to provide a method of extracting a proof of the given bounds, as there are various different methods:
    1. Trivial bounds based on reasoning regarding small parameter values
    2. Proven bounds with references.
    3. Bounds (not implemented).
  • How to handle annotation with references for bounds?
Ramsey numbers
  • DONE The following needs to be updated according to the general naming conventions discussed in "Systematic notations for the numbers in %Ramsey theory" in ComputerAlgebra/RamseyTheory/plans/general.hpp.
    1. For a "Ramsey parameter tuple" as below, the number of "colours" is not mentioned, while the size of the hyperedges comes last.
    2. Perhaps we should just put the size of the hyperedges as first component, but leave it otherwise.
    3. So the tuple of clique-sizes is always written out (while the redundant information on the number of colours then is not needed).
    4. Or should be provide the (redundant) number of colours? Then it would use the same conventions as the function-arguments?
    5. Should we then also allow the hyperedge-size to be left out (which implies the value 2)?
    6. The current tuple [[3,3,3],2] would then become [3,2,[3,3,3]] or [3,[3,3,3]]. But there such defaults seem useless, so perhaps we should just use the full version.
    7. Leaving out the number of colours yields [2,[3,3,3]]; perhaps this is best.
  • DONE A "Ramsey parameter tuple" is a tuple [r, [q_1,...,q_s]], where s is the number of colours (all q_i and r are natural numbers).
  • The function ramsey([r, par_tuple]) computes a pair, consisting of a lower and an upper bound on the Ramsey number for this tuple.
  • This function is now available, but needs to be improved:
    • The known general upper and lower bounds need to be integrated:
      1. The system must be extensible.
      2. Perhaps one "bound function" delivers:
        • the function which from the given parameter tuple computes the other parameter tuple for which bounds are needed
        • and the function which from these other bounds computes the bounds.
        Then ramsey recursively invokes all registered bound functions, and uses minimum resp. maximum.
      3. Either we provide pairs [lower bound, upper bound], or precise values (just integers).
      4. DONE (ramsey_hm has been removed) The system needs to general enough, so that also the values given by ramsey_hm can be checked (possibly improved).
        1. It might be good to extend the hash-map ramsey_hm to contain information on how currently the best bounds are obtained.
        2. One possibility is for the interesting small parameter values just to use comments.
  • Important that the system developed here can later be generalised to yield bounds on all sorts of combinatorial parameters.
    1. Compare ComputerAlgebra/Satisfiability/Lisp/MinimalUnsatisfiability/plans/uhit_def.hpp for another catalogue of data (and instances).
DONE Incorrect handling of Ramsey parameter tuples
  • DONE The superfluous parameter r needs to be removed everywhere (except, of course, where explicitly diagonal-versions are treated).
  • DONE It is actually not clear at all what "r" stands for: standardisation of the names used ("k" and "r"; perhaps others?) is needed.
  • DONE At this time also the testobjects-file needs a make-over: The editorial structure of tests- and testobjects-files should always be the same as the basic file (for which tests are provided).
  • DONE And specifications for most functions in ComputerAlgebra/RamseyTheory/Lisp/Ramsey/Numbers.mac are missing.
  • DONE The function "ramsey" should take as parameter exactly a Ramsey parameter tuple.
  • DONE The predicate "ramsey_p" is needed.

Definition in file Numbers.hpp.