Results 1 to 5 of 5

Thread: 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 $\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$.
    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 $\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$
    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 $\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.
    Last edited by Laurent; Sep 20th 2009 at 02: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 17th 2010, 11:00 PM
  2. set partitions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jan 22nd 2010, 10:06 AM
  3. Conjecture
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: Jun 29th 2009, 11:58 AM
  4. what is conjecture?
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: Dec 9th 2008, 09:48 AM
  5. T-Man Conjecture
    Posted in the Math Forum
    Replies: 8
    Last Post: Apr 22nd 2007, 07:22 PM

Search Tags


/mathhelpforum @mathhelpforum