# A conjecture about set partitions

• Sep 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 \$\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\$.
• Sep 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 \$\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\$
• Sep 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 \$\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\$.

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.
• Sep 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)