# Thread: 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 $\displaystyle S$ be a set with $\displaystyle mn$ elements. Let $\displaystyle P_1$ and $\displaystyle P_2$ be partitions of $\displaystyle S$ into $\displaystyle m$ parts, each having $\displaystyle n$ elements.

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

I conjecture that there is a subset of $\displaystyle m$ elements of $\displaystyle S$ which is a set of representatives both for $\displaystyle P_1$ and for $\displaystyle 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 $\displaystyle S$ be a set with $\displaystyle mn$ elements. Let $\displaystyle P_1$ and $\displaystyle P_2$ be partitions of $\displaystyle S$ into $\displaystyle m$ parts, each having $\displaystyle n$ elements.

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

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

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

I conjecture that there is a subset of $\displaystyle m$ elements of $\displaystyle S$ which is a set of representatives both for $\displaystyle P_1$ and for $\displaystyle P_2$.
Canadian or US dollars?

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.