1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics: Complementary Pair

  1. Apr 29, 2015 #1
    1. The problem statement, all variables and given/known data

    My book repeatedly uses the phrase "contains one of each complementary pair of sets" and I am wondering what do they mean by that exactly?

    2. Relevant equations

    None

    3. The attempt at a solution

    For example, when it proves that an intersecting family of subsets of ##\{1,...,n\}## satisfies ##|F|\le2^{n-1},## it says the ##2^n## subsets of ##X## can be divided into ##2^{n-1}## complementary pairs ##\{A,X \A\}##.

    I am not sure what the mean by complementary pairs when referring to an intersecting family.
     
  2. jcsd
  3. Apr 29, 2015 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    The notation {A,X\A} tells you what they mean by complementary pairs. Each pair consists of a subset A and its complement X\A (the set of all elements of X that aren't in A). The sets A and X\A have empty intersection. So if F is an intersecting family of sets then for each pair you can select at most one of A and X\A to belong to F. If you pick both then F is not intersecting. So the number of elements in F is less than or equal to the number of complementary pairs.
     
    Last edited: Apr 29, 2015
  4. Apr 30, 2015 #3
    Thank you very much for clarifying.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Combinatorics: Complementary Pair
Loading...