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.

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.