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 02:36:07 -0700
Well my test failed. When a follow up to another newsgroup is demanded,
then my post doesn't appear. Does this then mean as you insist follow ups
to be at comp.theory, that I will not, can be be participant of the
discussion, unless I connect into comp.theory, which I will not do as I
already participate in too many groups.
So how are you going to answer this or answer a well thought out reply?
Do I have to be in comp.theory? Unless I hear from you via sci.math, I
will conclude that all posts demending reply to another newsgroups are of
no note.
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: help: a O(n) algorithm to find the longest path in a tree
- Next by Date: Re: On the complexity of determining whether n numbers are distinct
- Previous 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
|
