OKlibrary  0.2.1.6
PdNumbers.hpp File Reference

Plans regarding palindromic van der Waerden numbers. More...

Go to the source code of this file.


Detailed Description

Plans regarding palindromic van der Waerden numbers.

Todo:
Palindromic numbers
  • As discussed in "Palindromic versions" in Experimentation/Investigations/RamseyTheory/VanderWaerdenProblems/plans/general.hpp we should provide the smallest n_1 such that for n' >= n_1 no palindromic solution exists, and the largest n_0, such that for all n' <= n_0 palindromic solutions do exist.
  • So the "palindromic number" is actually a pair of numbers (namely (n_0,n_1)).
  • Naming:
    1. pdvanderwaerden(t)
    2. How to access the parts (sat- resp. unsat-related)? At Maxima-level we could simply use pdvanderwaerden(t)[1 / 2]. It works, however it is not very expressive.
    3. DONE (palindromic versions are something special, a kind of "universal variation", and so they deserve their own treatmeant) Or perhaps we should provide g_vanderwaerden(t,p), where p is some parameter, perhaps a string, which selects which form of a generalised vdW-number is considered.
    4. DONE (not chosen) Or perhaps vanderwaerden_g(t,p), in this case vanderwaerden_g(t,"pd"). This seems best.
  • How to name this quantity in mathematical formulas?
    1. DONE (not chosen) "pdvdw_m(t)"
    2. "vdw_m^{pd}(t)": this seems better, since it is a variation on vdW-numbers; and in general variations of Ramsey-type numbers are indicated by an upper index.
    3. Note that this "number" is actually a pair.
    4. How to access the two components of the pairs? Lower and upper index are already used. One could write "vdw_m^{pd}(t)_{1 / 2}" (index 1 for the sat-part, index 2 for the unsat-part) ? Correct, but not very expressive.
    5. In a context where "w(m; t_1,..., t_m)" is used for "vdw_m(t)", one can use "w^{pd}(m; t_1,...,t_m)" for vdw_m^pd(t), and "w^{pd}_{1 / 2}(m; t_1,...,t_m)" for the sat- resp. unsat-component.
    6. Again, indices "1", "2" are not much telling. "0", "1" for "unsat", "sat" would be better, however then we have a clash with the ordering of the components (and their real indices).
  • From a solution for n a solution for n-2 can be derived by removing vertices n and 1, and then subtracting 1 from the remaining vertices.
  • Thus the sequence of bits for n=1,... (always for a given tuple t) is first all 1's, then 0 and 1 strictly alternating, and then all 0,s (where the lenght of the alternating sequence could be zero).
  • DONE (integrated) Dual versions (regarding satisfiability):
    1. So we also need to consider the largest n such that all n' <= n yield satisfiable problems.
    2. At the Maximap-level we could name that vanderwaerden_g(t,"pdsat").
    3. In mathematical formulas we could use "svdw_m^{pd}(t)".
    4. The two numbers svdw_m^{pd}(t), vdw_m^{pd}(t) completely determine satisfiability for all n (for this t).

Definition in file PdNumbers.hpp.