1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Set theory question!

  1. Sep 25, 2012 #1
    1. The problem statement, all variables and given/known data
    Hi everyone, i have the following problem, that for the moment i couldn't find the solution or even how to search about...

    This is it, we have a family of subsets F ={F_1,...,F_p} of the set {1,2,...,k}.

    We know that, for every i != j, F_i !=F_j
    and for every pair of elements a, b \in {1,2,...k} there exists one F_i
    such that a belongs to F_i but b does not.
    (this is, no pair of elements belong to exactly the same sets)

    Notice that with this restriction, at most one element can be outside every F_i.

    it is clear that p should be at least ceiling ( log_2 ( k ) ).

    First question. Does this family of sets have any name in the literature?

    Second question:
    Consider now the maximal sets S_1,S_2,...S_s such that
    S_i is a subset of F and the intersection of every F_j \in S_i is non-empty.
    The maximality means that there is no S_i subset of S_j with exactly
    the same intersection, i.e., the intersection of F_x \in S_i != intersection of F_x \in S_j
    for S_i subset of S_j.

    I want to prove that s >= k-1

    Thank you all for any answer :)

    2. Relevant equations

    3. The attempt at a solution
    No idea how to solve but just in particular cases, for example for p = k-1
    and F_i ={i}....
  2. jcsd
  3. Sep 26, 2012 #2
    mmh nothing...? :(
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook