 Forum index » Science and Technology » Math » Combinatorics
Author Message
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 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 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 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". 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 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 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 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. 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 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 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 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 is a union of k (or less) Cartesian products}. Could anyone help? Regards, sasha  Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 The time now is Tue Mar 19, 2019 5:13 pm | All times are GMT Forum index » Science and Technology » Math » Combinatorics
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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