- #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}...