FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
Minimal union of cartesian products
Post new topic   Reply to topic Page 1 of 1 [6 Posts] View previous topic :: View next topic
Author Message
sasha mal
science forum beginner


Joined: 05 May 2005
Posts: 21

PostPosted: Wed Mar 15, 2006 12:48 pm    Post subject: Minimal union of cartesian products Reply with 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}.

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

PostPosted: Thu Mar 16, 2006 5:29 am    Post subject: Re: Minimal union of cartesian products Reply with quote

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

PostPosted: Thu Mar 16, 2006 11:38 am    Post subject: Re: Minimal union of cartesian products Reply with quote

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

PostPosted: Fri Mar 17, 2006 8:55 am    Post subject: Re: Minimal union of cartesian products Reply with quote

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

PostPosted: Fri Mar 17, 2006 5:17 pm    Post subject: Re: Minimal union of cartesian products Reply with quote

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

PostPosted: Sat Mar 18, 2006 7:26 am    Post subject: Re: Minimal union of cartesian products Reply with quote

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
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [6 Posts] View previous topic :: View next topic
The time now is Fri Jun 23, 2017 1:44 pm | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Maplesoft is committed to providing the highest level of ... Vladimir Bondarenko Math 21 Fri Jul 07, 2006 5:11 am
No new posts Alimentary products Nicolas DELFAU Chem 5 Fri Jun 30, 2006 7:46 am
No new posts union convex set is not convex Ismail Math 9 Tue Jun 20, 2006 12:06 pm
No new posts Minimal set of linear constraints Alec.Edgington@blueyonder num-analysis 3 Wed Jun 14, 2006 10:21 am
No new posts minimal anisomorphism SysTom Math 0 Mon Jun 12, 2006 3:19 am

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0222s ][ Queries: 16 (0.0037s) ][ GZIP on - Debug on ]