Results 1 to 4 of 4

Math Help - Size of the intersection set

  1. #1
    Member
    Joined
    Mar 2006
    Posts
    125

    Size of the intersection set

    Hello guys

    I am thinking about a problem involving intersection of sets.

    If I have for example a two sets A and B, and |A| is the number of elements in A and |B| the number of elements in B, then |A \cap B| is the number of elements in the intersection set A \cap B.

    Now, if I add a third set C, with |C| elements, the number of elements in A \cap B \cap C will be naturally smaller (or equal) than in A \cap B. And if I'll add more sets, the number of elements in the intersection will keep decreasing.

    Are there any researches / theorems about the rate of decrements ? I mean, if I take sets with numbers that are chosen by random, and I keep adding them, how strongly will the number of elements in the intersection converge to zero ?

    Any insights / references will be most appreciated...


    /cap means intersection, couldn't make latex work, don't know why...apologies...
    Last edited by WeeG; July 1st 2012 at 11:52 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Size of the intersection set

    Well it depends on what elements C and |A \cap B| have in common. You can't show that the intersection converges to zero, because each additional set might as well be equal to the intersection of A and B.

    If A and B are fixed and are subsets of a universal set U, and if C, D, ... are subsets of fixed size, that's an entirely different question. Try small cases first.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2006
    Posts
    125

    Re: Size of the intersection set

    What I am trying to prove is slightly different.

    Let's say I have a set U which is a subset of the integers set Z. U contains around 10,000 elements.

    Now I take a subset of U, let's call it A, and it has (just for illustration) 3000 elements. In the next step I will take another subset B, and it will have 2700 elements. I choose the elements of the subsets by random (!). Now I look at the intersection of A and B, it will contain (for example) 300 elements. In the next step I will take another random subset, C, and will look at the intersection of A, B and C. My intuition say that if I'll keep doing that, eventually the generalized intersection will converge to the empty set.

    In the real world problem from which I took this challenge, I have seen the size of the generalized intersection decreases fast to 25 elements for 3 sets only. I do not have the 4th just yet, but I am trying to find a mathematical explanation to my intuition.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Size of the intersection set

    Ohh I see...one way to think of it, if any element n appears in the intersection of sets A,B,C, it must be contained in sets A,B,C. What is the probability of that happening?

    I haven't thought about this for much time, but it looks like you'll probably get some sort of probability distribution based on the number and size of your subsets, and the size of the universal set U. Yes, intuitively, the intersection should "converge" to the empty set.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Maximum size of G
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 6th 2012, 05:48 AM
  2. Bin size for 3d histogram
    Posted in the Statistics Forum
    Replies: 1
    Last Post: January 10th 2011, 11:55 PM
  3. Max size of..
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2010, 08:09 AM
  4. Size!
    Posted in the Math Challenge Problems Forum
    Replies: 4
    Last Post: November 16th 2009, 04:40 PM
  5. Replies: 2
    Last Post: October 19th 2009, 03:47 AM

Search Tags


/mathhelpforum @mathhelpforum