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

Posted: Wed Jul 19, 2006 10:58 pm Post subject:
A Combinatorics/Graph Theory Question



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 kelement subsets of
an nelement set. The edges of the graph are formed as below: we
correspond each kelement subset of X with a vertex in Y and put an
edge between that vertex of Y and each member of the corresponding
kelement subset of X.
Now it is clear that for every vertex of X there are C(k1, n1)
vertices in Y that have an edge to that vertex. That is every vertex in
X has exactly C(k1, n1) number of neighbors in Y. Now the problem is
as follows: assuming "r" is a natural number not larger than C(k1,
n1) (I am specially interested in the case r=2) determine the minimum
number "p" (or at least a nontrivial upper bound on it) such that for
every pelement 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. 
