- #1
juanchoba
- 2
- 0
Homework Statement
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 :)
Juan!
Homework Equations
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}...