A Combinatorics/Graph Theory Question

mathlover · science forum beginner Joined: 04 May 2005 Posts: 13

Hi every body,

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.

Google