Results 1 to 5 of 5

Math Help - A conjecture about set partitions

  1. #1
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    From
    México
    Posts
    721
    Quote Originally Posted by Bruno J. View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Bruno J. View Post
    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.
    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.
    Last edited by Laurent; September 20th 2009 at 03:57 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Bruno J. View Post
    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...)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. ABC conjecture
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: May 18th 2010, 12:00 AM
  2. set partitions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 22nd 2010, 11:06 AM
  3. Conjecture
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: June 29th 2009, 12:58 PM
  4. what is conjecture?
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: December 9th 2008, 10:48 AM
  5. T-Man Conjecture
    Posted in the Math Forum
    Replies: 8
    Last Post: April 22nd 2007, 08:22 PM

Search Tags


/mathhelpforum @mathhelpforum