Dtjytyk

How do pianists reach extremely loud dynamics?

First console to have temporary backward compatibility

How to deal with a team lead who never gives me credit?

Is the Standard Deduction better than Itemized when both are the same amount?

What would be the ideal power source for a cybernetic eye?

Where are Serre’s lectures at Collège de France to be found?

Amount of permutations on an NxNxN Rubik's Cube

If u is orthogonal to both v and w, and u not equal to 0, argue that u is not in the span of v and w. (

Is it a good idea to use CNN to classify 1D signal?

Why are both D and D# fitting into my E minor key?

Is "Reachable Object" really an NP-complete problem?

Can you use the Shield Master feat to shove someone before you make an attack by using a Readied action?

Did MS DOS itself ever use blinking text?

What does "lightly crushed" mean for cardamon pods?

What font is "z" in "z-score"?

What causes the direction of lightning flashes?

When a candle burns, why does the top of wick glow if bottom of flame is hottest?

If a contract sometimes uses the wrong name, is it still valid?

Using audio cues to encourage good posture

8 Prisoners wearing hats

Is there a kind of relay only consumes power when switching?

What does the "x" in "x86" represent?

Is grep documentation wrong?

Do I really need to have a message in a novel to appeal to readers?

Renumerating partitioned sets [duplicate]

0

$begingroup$

This question already has an answer here:

• 
  Partition of a set and Hall's theorem
  
  1 answer
  
  

This is a problem in my graph theory class and I'm unsure about how to solve it..

Let $X$ be the set ${1,2,dots,mn}$. Suppose we partition $X$ into $m$ sets $P_1,dots,P_m$, each of size $n$.

Suppose we choose another partition $Q_1,dots,Q_m$, each of size $n$.

Show that the sets $P_i$ can be renumbered so that $P_i cap Q_i$ is non-empty for every $i$.

Thanks in advance!

Edit: I'm attempting to use Hall's Marriage theorem to solve this but I'm struggling with formulating the solution in a way that would get me to my answer.

combinatorics graph-theory set-partition

share|cite|improve this question

edited Mar 25 at 4:38

MarianD

2,2761619

asked Mar 24 at 20:40

Davyd RickmannDavyd Rickmann

263

$endgroup$

marked as duplicate by Gibbs, Cesareo, darij grinberg, mrtaurho, Javi Mar 25 at 11:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

add a comment | 

0

$begingroup$

This question already has an answer here:

• 
  Partition of a set and Hall's theorem
  
  1 answer
  
  

This is a problem in my graph theory class and I'm unsure about how to solve it..

Let $X$ be the set ${1,2,dots,mn}$. Suppose we partition $X$ into $m$ sets $P_1,dots,P_m$, each of size $n$.

Suppose we choose another partition $Q_1,dots,Q_m$, each of size $n$.

Show that the sets $P_i$ can be renumbered so that $P_i cap Q_i$ is non-empty for every $i$.

Thanks in advance!

Edit: I'm attempting to use Hall's Marriage theorem to solve this but I'm struggling with formulating the solution in a way that would get me to my answer.

combinatorics graph-theory set-partition

share|cite|improve this question

edited Mar 25 at 4:38

MarianD

2,2761619

asked Mar 24 at 20:40

Davyd RickmannDavyd Rickmann

263

$endgroup$

marked as duplicate by Gibbs, Cesareo, darij grinberg, mrtaurho, Javi Mar 25 at 11:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

add a comment | 

$begingroup$

This question already has an answer here:

• 
  Partition of a set and Hall's theorem
  
  1 answer
  
  

This is a problem in my graph theory class and I'm unsure about how to solve it..

Let $X$ be the set ${1,2,dots,mn}$. Suppose we partition $X$ into $m$ sets $P_1,dots,P_m$, each of size $n$.

Suppose we choose another partition $Q_1,dots,Q_m$, each of size $n$.

Show that the sets $P_i$ can be renumbered so that $P_i cap Q_i$ is non-empty for every $i$.

Thanks in advance!

Edit: I'm attempting to use Hall's Marriage theorem to solve this but I'm struggling with formulating the solution in a way that would get me to my answer.

combinatorics graph-theory set-partition

share|cite|improve this question

edited Mar 25 at 4:38

MarianD

2,2761619

asked Mar 24 at 20:40

Davyd RickmannDavyd Rickmann

263

$endgroup$

share|cite|improve this question

edited Mar 25 at 4:38

MarianD

2,2761619

asked Mar 24 at 20:40

Davyd RickmannDavyd Rickmann

263

share|cite|improve this question

edited Mar 25 at 4:38

MarianD

2,2761619

asked Mar 24 at 20:40

Davyd RickmannDavyd Rickmann

263

edited Mar 25 at 4:38

MarianD

2,2761619

edited Mar 25 at 4:38

MarianD

2,2761619

asked Mar 24 at 20:40

Davyd RickmannDavyd Rickmann

263

asked Mar 24 at 20:40

Davyd RickmannDavyd Rickmann

263

1 Answer
1

active

oldest

votes

1

$begingroup$

Hall's Marriage Theorem is the right way to go. To put it in terms of graphs, consider a bipartite graph, where The $P_k$ form one of the bipartition sets, and the $Q_k$ form the other. Make $P_i$ adjacent to $Q_j$ if and only if $P_icap Q_jneq emptyset.$ Then you want to show that there is a complete matching, so if you can show that Hall's condition holds, you are done.

That is, you must show that if $P_{i_1},dots,P_{i_k}$ are given, for some $1leq kleq m,$ then there exist $Q_{i_1},dots,Q_{i_k}$ that each have at least one element in common with at least one of the $P_{i_j}.$

This is quite easy when you think about it.

share|cite|improve this answer

answered Mar 24 at 21:01

saulspatzsaulspatz

17.5k31536

$endgroup$

add a comment | 

1

$begingroup$

Hall's Marriage Theorem is the right way to go. To put it in terms of graphs, consider a bipartite graph, where The $P_k$ form one of the bipartition sets, and the $Q_k$ form the other. Make $P_i$ adjacent to $Q_j$ if and only if $P_icap Q_jneq emptyset.$ Then you want to show that there is a complete matching, so if you can show that Hall's condition holds, you are done.

That is, you must show that if $P_{i_1},dots,P_{i_k}$ are given, for some $1leq kleq m,$ then there exist $Q_{i_1},dots,Q_{i_k}$ that each have at least one element in common with at least one of the $P_{i_j}.$

This is quite easy when you think about it.

share|cite|improve this answer

answered Mar 24 at 21:01

saulspatzsaulspatz

17.5k31536

$endgroup$

add a comment | 

1

$begingroup$

Hall's Marriage Theorem is the right way to go. To put it in terms of graphs, consider a bipartite graph, where The $P_k$ form one of the bipartition sets, and the $Q_k$ form the other. Make $P_i$ adjacent to $Q_j$ if and only if $P_icap Q_jneq emptyset.$ Then you want to show that there is a complete matching, so if you can show that Hall's condition holds, you are done.

That is, you must show that if $P_{i_1},dots,P_{i_k}$ are given, for some $1leq kleq m,$ then there exist $Q_{i_1},dots,Q_{i_k}$ that each have at least one element in common with at least one of the $P_{i_j}.$

This is quite easy when you think about it.

share|cite|improve this answer

answered Mar 24 at 21:01

saulspatzsaulspatz

17.5k31536

$endgroup$

add a comment | 

$begingroup$

Hall's Marriage Theorem is the right way to go. To put it in terms of graphs, consider a bipartite graph, where The $P_k$ form one of the bipartition sets, and the $Q_k$ form the other. Make $P_i$ adjacent to $Q_j$ if and only if $P_icap Q_jneq emptyset.$ Then you want to show that there is a complete matching, so if you can show that Hall's condition holds, you are done.

That is, you must show that if $P_{i_1},dots,P_{i_k}$ are given, for some $1leq kleq m,$ then there exist $Q_{i_1},dots,Q_{i_k}$ that each have at least one element in common with at least one of the $P_{i_j}.$

This is quite easy when you think about it.

share|cite|improve this answer

answered Mar 24 at 21:01

saulspatzsaulspatz

17.5k31536

$endgroup$

share|cite|improve this answer

answered Mar 24 at 21:01

saulspatzsaulspatz

17.5k31536

answered Mar 24 at 21:01

saulspatzsaulspatz

17.5k31536

answered Mar 24 at 21:01

saulspatzsaulspatz

17.5k31536