# A conjecture about set partitions

• September 20th 2009, 10:38 AM
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$.
• September 20th 2009, 11:42 AM
Jose27
Quote:

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$
• September 20th 2009, 02:40 PM
Laurent
Quote:

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.
• September 20th 2009, 03:09 PM
Bruno J.
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. (Giggle)