Plans regarding hypergraphs generators related to Hindman's theorems and conjectures.
More...
Go to the source code of this file.
Detailed Description
Plans regarding hypergraphs generators related to Hindman's theorems and conjectures.
 Todo:
 Implement iteratorforms

Implement the form of a hypergraph generator, where not the hyperedges are produced, but just a "range" (in the C++ sense) is computed, where then iterators are used to create the hyperedges one after another.

Using the general concepts in ComputerAlgebra/AbstractDataTypes/Lisp/plans/general.hpp we have the following natural implementation of a forward iterator:
hindman_a1k2_ohg_ver(n) := create_list(i,i,1,n)$
hindman_a1k2_ohg_hypit(n) := if n<=1 then [done] else
buildq([n,s:floor(sqrt(n))],
[1,
lambda([it], block([x:it[4], y:it[5]], {x,y,x+y,x*y})),
lambda([it], block([x:it[4], y:it[5]],
it[1] : it[1]+1,
if x=1 then
if y < n1 then it[5]:y+1
elseif s=1 then it[1]:done
else (it[4]:2, it[5]:2)
elseif y+1<=n/x then it[5]:y+1
elseif x<s then (it[4]:x+1, it[5]:x+1)
else it[1]:done)),
1,1])$
 Todo:
 Implement general functionality (arbitrary k)

hindman_ohg_0(a,k,n) and hindmani_ohg_0(a,k,n) need to improved.

Not all tuples [x_1, ..., x_k] have their sums and products in {1, ..., n}  actually most won't.

Perhaps we solve first the problem with "all products" (only; see 'Implement "all products"' below), since except of trivial cases the product dominates the sum.

And then we add the summands to the hyperedges, filtering out the unsuitable ones.

stable_unique is rather slow.

DONE (achieved by all_ord_tuples) We need a function producing all tuples [x_1, ..., x_k] over {1, ..., m} with x_1 <= ... <= x_k (while x_1 < ... < x_k is obtained by computing all ksubsets and listifying the result).

Simplest is to compute all ktuples, and then to sort the results.

This is obtained by setify(map(sort,all_tuples_l(setn(m),k))).

This is wasteful, but a simple solution, and it yields the canonical order.

DONE A simple first implementation ignores all efficiency considerations.

First a "generic" hyperedge is constructed, e.g. for k=3 the hyperedge {x1,x2,x3,x1+x2,x1+x3,x2+x3,x1+x2+x3,x1*x2,x1*x3,x2*x3,x1*x2*x3}.

This is likely best achieved as a union of the sumsonly and the productsonly case:
union(
map(sum_l,map(listify,disjoin({},powerset({x1,x2,x3})))),
map(prod_l,map(listify,disjoin({},powerset({x1,x2,x3}))))
);
{x1,x2,x1*x2,x2+x1,x3,x1*x3,x3+x1,x2*x3,x3+x2,x1*x2*x3,x3+x2+x1}

Then [x1,x2,x3] runs through all possibilities, and the substitution is performed.
 Todo:
 Implement "all products"

As with Folkmanhypergraphs, but now using "all products" instead of "all sums".
Definition in file Hindman.hpp.