# Math Help - A conjecture about set partitions

1. ## A conjecture about set partitions

I offer $1 for a proof of the following conjecture of mine, and$0.50 for a counter-example.

Let $S$ be a set with $mn$ elements. Let $P_1$ and $P_2$ be partitions of $S$ into $m$ parts, each having $n$ elements.

A subset of $S$ is called a "set of representatives" for a partition $P$ if each part of $P$ contains exactly one representative.

I conjecture that there is a subset of $m$ elements of $S$ which is a set of representatives both for $P_1$ and for $P_2$.

2. Originally Posted by Bruno J.
I offer $1 for a proof of the following conjecture of mine, and$0.50 for a counter-example.

Let $S$ be a set with $mn$ elements. Let $P_1$ and $P_2$ be partitions of $S$ into $m$ parts, each having $n$ elements.

A subset of $S$ is called a "set of representatives" for a partition $P$ if each part of $P$ contains exactly one representative.

I conjecture that there is a subset of $m$ elements of $S$ which is a set of representatives both for $P_1$ and for $P_2$.
Let $P_1$, $P_2$ be as above such that the subsets induced by each are $A_i$ and $B_i$ $i=1,...,m$ respectively. W.l.o.g. we may assume that $A_i \neq B_j$ $i,j=1,...,m$. For all $i$ there exists a $j$ such that $A_i \cap B_j \neq \emptyset$ for ohterwise There exists an $i$ such that for all $j$ $A_i \cap B_j = \emptyset$, from which it would follow that $A_i= \emptyset$ which clearly can't be, and we're done since $A_i \neq B_j$

3. Originally Posted by Bruno J.
I offer $1 for a proof of the following conjecture of mine, and$0.50 for a counter-example.

Let $S$ be a set with $mn$ elements. Let $P_1$ and $P_2$ be partitions of $S$ into $m$ parts, each having $n$ elements.

A subset of $S$ is called a "set of representatives" for a partition $P$ if each part of $P$ contains exactly one representative.

I conjecture that there is a subset of $m$ elements of $S$ which is a set of representatives both for $P_1$ and for $P_2$.
This is known as König's theorem, and seems to be a consequence of Hall's marriage theorem. Your problem is stated in the very first paragraph of this article (but you need to pay for the article (more than $1)...). You can also find (for free) the statement of the version generalizing both König's theorem and the marriage theorem here or there. To Jose27: you didn't prove that two different indices i lead to different indices j, in other words that no part of P2 contains none or more than one representative. 4. Awesome! I'll check it out. You are very knowledgeable. I can send you a check for$1 if you wish. When I become famous it will be worth at least $2. ...Canadian. 5. Originally Posted by Bruno J. I can send you a check for$1 if you wish. When I become famous it will be worth at least \$2.