OKlibrary  0.2.1.6
Ramsey.hpp File Reference

Plans regarding generators for Ramsey-hypergraphs. More...

Go to the source code of this file.


Detailed Description

Plans regarding generators for Ramsey-hypergraphs.

Bug:
ramseyrv_ohg handles r=0 incorrectly
  • ramseyrv_ohg(0,0,0) should return [[rv()],[{rv()}]], not [[rv()],[{{}}]].
Todo:
Ramsey hypergraphs
  • We should always have that standardisation should not change the order of vertices or hyperedges, however this seems to be the case here?
  • Perhaps we should use complete_hg and variations.
  • Compare with ComputerAlgebra/Hypergraphs/Lisp/Generators/GreenTao.mac (so that we arrive at a certain standardisation of generator-facilities).
  • One needs to revise the extreme cases; compare "Ramsey problems" in ComputerAlgebra/Satisfiability/Lisp/Generators/RamseyTheory/plans/RamseyProblems.hpp.
  • Providing a standardised vertex set:
    1. DONE We only need to consider lexicographical ordering of the vertex names. Actually, in order to preserve monotonicity, we better use colexicographical ordering.
    2. This standardised hypergraph has then a canonical order-preserving isomorphism to ramsey_ohg(q,r,n).
      1. For this to hold (for the vertices) we needed ramsey_ohg to use colexicographical ordering.
      2. Perhaps this is a sensible thing to do; however it seems we don't need to do something on the hyperedges (i.e., we continue to use lexicographical order there).
      3. Currently we use the lexicographical order of ramsey_ohg on vertex set and hyperedge set, but using colexicographical ranking.
      4. This has the advantage that ramsey_ohg is easy to compute and isomorphic to ramsey_stdohg.
      5. But for n' >= n we don't have that ramsey_stdohg(q,r,n') is an extension of ramsey_stdohg(q,r,n) --- we only have that ramsey_stdhg(q,r,n) is a subhypergraph of ramsey_stdhg(q,r,n').
    3. The same numbering should also be used in the C++ generator (see Ramsey.cpp).
    4. So that we can easily create additional clauses with Maxima, added then to the C++-generated files.
  • Accompanying statistics are needed.
    1. See okltest_ramsey_hg for the formula for the number of hyperedges.
    2. Likely only basic statistics should be computed, while for example the size of the automorphism group etc. is handled in module. RamseyTheory/Lisp/Ramsey.
Todo:
Generalised Ramsey hypergraphs
  • We can define Ramsey hypergraphs for arbitrary hypergraphs G (ramsey_hg uses the complete r-graph).
    1. The vertices are the hyperedges of G.
    2. Hyperedges are sets of hyperedges of G which are the hyperedge-set of a complete q-graph.
    3. If G is a graph, then we are considering the hypergraph of "cliques", restricted to cliques of size q, and where the clique is viewed as a collection of edges.
    4. We need to check whether this is the common point of view.

Definition in file Ramsey.hpp.