A Combinatorics/Graph Theory Question

There is a problem I have exposed to but, though being badly in need of an answer, I have not yet been able to solve it. I am not quite sure if it is better classified as a graph theory problem or a combinatorial one; anyway, here is the problem:

Assume we have a bipartite graph with X and Y as its two parts. X has "n" vertices and Y has C(k,n) vertices where "k" is a natural number less than "n" and by C(k,n) I denote the number of k-element subsets of an n-element set. The edges of the graph are formed as below: we correspond each k-element subset of X with a vertex in Y and put an edge between that vertex of Y and each member of the corresponding k-element subset of X.

Now it is clear that for every vertex of X there are C(k-1, n-1) vertices in Y that have an edge to that vertex. That is every vertex in X has exactly C(k-1, n-1) number of neighbors in Y. Now the problem is as follows: assuming "r" is a natural number not larger than C(k-1, n-1) (I am specially interested in the case r=2) determine the minimum number "p" (or at least a non-trivial upper bound on it) such that for every p-element subset, like S, of Y the following property holds: for every node in X, like "v", it has at least "r" neighbors which are members of S.

Any help or clues are greatly appreciated.

Thanks. Received on Thu Jul 20 2006 - 01:33:51 CEST