Re: How to compute "A1 x. .. x An subset B" fast if B is fixed? Reduced maximal set of Cartesian products.
- From: William Elliot <marsh@xxxxxxxxxxxxxxxxxx>
- Date: Tue, 26 Sep 2006 01:51:27 -0700
You demand follow up to newsgroup that I don't participate in.
This is test to see if my post will show at sci.math. If it
doesn't, then I'll know for sure that there's no point in
answering posts with stipulated reply to's.
On Mon, 25 Sep 2006, sasha mal wrote:
Let d, n be natural numbers. In the following, the term "Cartesian.
product" means an element of (2^{0,...,d-1})^n.
A set of Cartesian products X is called reduced if for all unequal A, B
in X we have that A is not contained in B.
A set of Cartesian products X is called maximal if whenever a Cartesian
product C in contained in the union of X, then there is a Cartesian
product A in X so that C is contained in A.
Claim 1: Different reduced maximal sets of Cartesian products have
different unions.
Proof: trivial.
Claim 2: for n=2 and arbitrary d, there is a reduced maximal set of
Cartesian products with 2^d-2 elements.
Proof hint: Consider the whole square without a diagonal:
B = {0,...,d-1}^2 \ {(a,a) | 0 <= a < d}.
I claim that the unique reduced maximal set of Cartesian products with B
as a union has 2^d-2 Cartesian products.
Proof: Exercise.
Hypothesis: For each n>=2 and each d>=1 there is a reduced maximal set
of Cartesian products with n^d-n elements.
Please feel free to confirm or to reject it.
Regards
Sasha.
- Prev by Date: Re: On the complexity of determining whether n numbers are distinct
- Next by Date: Re: help: a O(n) algorithm to find the longest path in a tree
- Previous by thread: Best-first search metaheuristic help
- Next by thread: Re: How to compute "A1 x. .. x An subset B" fast if B is fixed? Reduced maximal set of Cartesian products.
- Index(es):
Relevant Pages
|
