general.hpp File Reference

Plans regarding Ramsey problems. More...

Go to the source code of this file.

Detailed Description

Plans regarding Ramsey problems.

Relations to other modules
Automorphisms of Ramsey hypergraphs
  • First the natural operation of S_n on ramsey_hg(q,r,n) needs to be made available.
    1. Implemented in ComputerAlgebra/RamseyTheory/Lisp/Ramsey/Hypergraphs.mac.
    2. Easiest first to consider the elements of S_n as lists.
  • The operation of S_n should be faithful (in most cases), and we need to extract the induced automorphisms of ramsey_hg(q,r,n).
  • Then we need to find out whether these automorphisms cover all.
    1. For small parameters values (including q=3,r=2) we can enumerate all automorphisms by brute force.
    2. What tools are available for hypergraph automorphisms?
  • It would also be interesting here to try apply some of the symmetry breaking ideas discussed in Satisfiability/Lisp/Generators/RamseyTheory/plans/RamseyProblems.hpp and then consider the number and character of the remaining symmetries.
Automorphisms of Ramsey clause-sets
  • The obvious automorphisms of diagonal Ramsey clause-sets are given by the inner product of automorphisms for the underlying Ramsey hypergraph and the S_s when using s colours.
  • So at least we have S_n x S_s (translated).
  • Are there more?
    1. It seems that by brute force (enumerating all clause-set automorphisms we cannot process any non-trivial example?
    2. We need stronger tools for computing automorphisms of clause-sets.
  • And what about non-diagonal Ramsey clause-sets? One would guess that in "most" cases there are no other automorphisms than given by the underlying S_n ?
Representing counter-examples

Definition in file general.hpp.