Thread: 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 be a set with elements. Let and be partitions of into parts, each having elements.

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

I conjecture that there is a subset of elements of which is a set of representatives both for and for .

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 be a set with elements. Let and be partitions of into parts, each having elements.

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

I conjecture that there is a subset of elements of which is a set of representatives both for and for .

Let , be as above such that the subsets induced by each are and respectively. W.l.o.g. we may assume that . For all there exists a such that for ohterwise There exists an such that for all , from which it would follow that which clearly can't be, and we're done since

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 be a set with elements. Let and be partitions of into parts, each having elements.

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

I conjecture that there is a subset of elements of which is a set of representatives both for and for .

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.

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.

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.

...Canadian.

Don't bother sending the check (unless you insist ). Your question gave me the occasion to leaf again through the beautiful "Proofs from the Book" ; and this is invaluable! (although the answer was not exactly in the book...)