Rado.hpp File Reference

Plans regarding hypergraphs generators related to Rado's theorems. More...

Go to the source code of this file.

Detailed Description

Plans regarding hypergraphs generators related to Rado's theorems.

Basic functionality
  • Implement rado_ohg.
    1. First a basis of the solution space of Ax=0 has to be computed.
    2. Then all solutions can be enumerated, and the hyperedges extracted.
    3. Depending on the symmetries of the solution space w.r.t. set formation, the same hyperedge might be enumerated many times. Seems hard to avoid in general.
  • Implement radoi_ohg.
    1. Is there a better solution than first computing rado_ohg, and then keeping only the hyperedges of length p (wherer A is an rxp matrix)?
Checking regularity
  • A Rado parameter tuple [A_1, ..., A_r] is called "regular" for if every r-partitioning of NN there is a part P_i containing at least one hyperedge from rado_ohg(A_i,n) for suitable n.
  • As usual, via compactness this is equivalent to the condition that if n is large enough, then the corresponding (non-boolean) clause-set becomes unsatisfiable; in other words, rado_m(A_1, ..., A_m) exists.
  • Let's use "injectively regular" for the existence of radoi_m(A_1, ..., A_m).
  • In [Ramsey Theory on the Integers; Landman, Robertson] we find the following criterions for (injective) regularity:
    1. For m=1 and r=1 (just a single equation) with all coefficients being non-zero this is Theorem 9.2 (there is a non-empty subset of coefficients summing to zero).
    2. While injective regularity is characterised by Theorem 9.4 (additionally a solution x of A x = 0 must exist, where x is injective (but the entries can be arbitrary integers).
    3. Allowing more than one single equation is easy by Theorem 9.19 resp. 9.22: simply each single equation must be regular resp. injectively regular.
    4. Finally having a single matrix is handled by Theorem 9.27.
  • These conditions need to be implemented.
Known Rado numbers
  • By Theorem 9.11 in [Landman, Robertson] rado_2(matrix([a,b,-b])) is known; does this yield some interesting problem instances?
  • Section 9.2 in [Landman, Robertson] contains more cases; these should be implemented.

Definition in file Rado.hpp.