Author 
Message 
sasha mal science forum beginner
Joined: 05 May 2005
Posts: 21

Posted: Wed Mar 15, 2006 12:48 pm Post subject:
Minimal union of cartesian products



Dear newsgroupers!
1.
Let X and Y be finite sets. The algorithm for the following problem is
needed.
Given a subset Q of the cross product X x Y, find the smallest natural
number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k>  Q is a union of k (or less) Cartesian products}.
2. We generalize the problem to more dimensions.
Let X1,..., Xn be finite sets. The algorithm for the following problem
is needed.
Given a subset Q of the cross product X1 x ... x Xn, find the smallest
natural number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k>  Q is a union of k (or less) Cartesian products}.
Could anyone help?
Regards,
sasha 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Thu Mar 16, 2006 5:29 am Post subject:
Re: Minimal union of cartesian products



sasha mal wrote:
Quote:  Dear newsgroupers!
1.
Let X and Y be finite sets. The algorithm for the following problem is
needed.
Given a subset Q of the cross product X x Y, find the smallest natural
number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k>  Q is a union of k (or less) Cartesian products}.
[...]
Could anyone help?

You might want to look at bipartite graphs; given Q,X, and Y, define a
bipartite graph G(Q) by V(G) = X union Y, and (x,y) is in E(G) iff
(x,y) is in Q. Then you'll want to partition G into the fewest number
of complete bipartite graphs.
 Christopher Heckman 

Back to top 


sasha mal science forum beginner
Joined: 05 May 2005
Posts: 21

Posted: Thu Mar 16, 2006 11:38 am Post subject:
Re: Minimal union of cartesian products



Proginoskes wrote:
Quote:  sasha mal wrote:
Dear newsgroupers!
1.
Let X and Y be finite sets. The algorithm for the following problem is
needed.
Given a subset Q of the cross product X x Y, find the smallest natural
number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k>  Q is a union of k (or less) Cartesian products}.
[...]
Could anyone help?
You might want to look at bipartite graphs; given Q,X, and Y, define a
bipartite graph G(Q) by V(G) = X union Y, and (x,y) is in E(G) iff
(x,y) is in Q. Then you'll want to partition G into the fewest number
of complete bipartite graphs.

Not quite. Almost. The word "partition" usually means that the sets of
vertices (or edges) of the complete bipartite graphs are disjoint.
However, the Cartesian products are allowed to have common elements.
But nevertheless, it's a very nice view of the problem.
Regards,
sasha. 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Fri Mar 17, 2006 8:55 am Post subject:
Re: Minimal union of cartesian products



sasha mal wrote:
Quote:  Proginoskes wrote:
sasha mal wrote:
Dear newsgroupers!
1.
Let X and Y be finite sets. The algorithm for the following problem is
needed.
Given a subset Q of the cross product X x Y, find the smallest natural
number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k>  Q is a union of k (or less) Cartesian products}.
[...]
Could anyone help?
You might want to look at bipartite graphs; given Q,X, and Y, define a
bipartite graph G(Q) by V(G) = X union Y, and (x,y) is in E(G) iff
(x,y) is in Q. Then you'll want to partition G into the fewest number
of complete bipartite graphs.
Not quite. Almost. The word "partition" usually means that the sets of
vertices (or edges) of the complete bipartite graphs are disjoint.
However, the Cartesian products are allowed to have common elements.

But if you have common elements in X and Y, they are differentiated in
X x Y by whether they're in the first component or the second. If X =
{1,2,3} and Y={1,2,4}, the ordered pair (1,2) (as an element of X x Y)
indicates that the 1 is from X and the 2 from Y. So the 1's in X and Y
are actually different, when you consider the cross product
X x Y.
 Christopher Heckman 

Back to top 


sasha mal science forum beginner
Joined: 05 May 2005
Posts: 21

Posted: Fri Mar 17, 2006 5:17 pm Post subject:
Re: Minimal union of cartesian products



Proginoskes wrote:
Quote:  sasha mal wrote:
Proginoskes wrote:
sasha mal wrote:
Dear newsgroupers!
1.
Let X and Y be finite sets. The algorithm for the following problem is
needed.
Given a subset Q of the cross product X x Y, find the smallest natural
number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k>  Q is a union of k (or less) Cartesian products}.
[...]
Could anyone help?
You might want to look at bipartite graphs; given Q,X, and Y, define a
bipartite graph G(Q) by V(G) = X union Y, and (x,y) is in E(G) iff
(x,y) is in Q. Then you'll want to partition G into the fewest number
of complete bipartite graphs.
Not quite. Almost. The word "partition" usually means that the sets of
vertices (or edges) of the complete bipartite graphs are disjoint.
However, the Cartesian products are allowed to have common elements.
But if you have common elements in X and Y, they are differentiated in
X x Y by whether they're in the first component or the second. If X =
{1,2,3} and Y={1,2,4}, the ordered pair (1,2) (as an element of X x Y)
indicates that the 1 is from X and the 2 from Y. So the 1's in X and Y
are actually different, when you consider the cross product
X x Y.
You are right, but that's not what I mean. 
I mean that two Cartesian products are allowed two have common pairs.
For instance, let X={a,b,c}, Y={1,2,3},
Q={(a,1),(a,2),(b,2),(b,3),(c,1),(c,2),(c,3)}.
Then Q={a,c}x{1,2} union {b,c}x{2,3}. This representation is a minimal
one. The pair (c,2) belongs both to
C1 = {a,c}x{1,2} and to C2 = {b,c}x{2,3}.
Howevewr, if you view Q as a bipartite graph, then the complete
subgraphs C1 and C2 do have a common edge. So C1 union C2 is not a
"partition". 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Sat Mar 18, 2006 7:26 am Post subject:
Re: Minimal union of cartesian products



sasha mal wrote:
Quote:  Proginoskes wrote:
sasha mal wrote:
Proginoskes wrote:
sasha mal wrote:
Dear newsgroupers!
1.
Let X and Y be finite sets. The algorithm for the following problem is
needed.
Given a subset Q of the cross product X x Y, find the smallest natural
number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k>  Q is a union of k (or less) Cartesian products}.
[...]
Could anyone help?
You might want to look at bipartite graphs; given Q,X, and Y, define a
bipartite graph G(Q) by V(G) = X union Y, and (x,y) is in E(G) iff
(x,y) is in Q. Then you'll want to partition G into the fewest number
of complete bipartite graphs.
Not quite. Almost. The word "partition" usually means that the sets of
vertices (or edges) of the complete bipartite graphs are disjoint.
However, the Cartesian products are allowed to have common elements.
But if you have common elements in X and Y, they are differentiated in
X x Y by whether they're in the first component or the second. If X =
{1,2,3} and Y={1,2,4}, the ordered pair (1,2) (as an element of X x Y)
indicates that the 1 is from X and the 2 from Y. So the 1's in X and Y
are actually different, when you consider the cross product
X x Y.
You are right, but that's not what I mean.
I mean that two Cartesian products are allowed two have common pairs.
For instance, let X={a,b,c}, Y={1,2,3},
Q={(a,1),(a,2),(b,2),(b,3),(c,1),(c,2),(c,3)}.
Then Q={a,c}x{1,2} union {b,c}x{2,3}. This representation is a minimal
one. The pair (c,2) belongs both to
C1 = {a,c}x{1,2} and to C2 = {b,c}x{2,3}.
Howevewr, if you view Q as a bipartite graph, then the complete
subgraphs C1 and C2 do have a common edge. So C1 union C2 is not a
"partition".

Okay; I see what you mean. Yes, "partition" should be replaced with
"union" in my response from so long ago ...
 Christopher Heckman 

Back to top 


Google


Back to top 



The time now is Wed Mar 21, 2018 10:37 am  All times are GMT

