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

Posted: Wed Jul 19, 2006 11:02 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. 

Back to top 


Robert B. Israel science forum Guru
Joined: 24 Mar 2005
Posts: 2151

Posted: Thu Jul 20, 2006 2:00 am Post subject:
Re: A Combinatorics/Graph Theory Question



In article <1153350177.809822.112810@m79g2000cwm.googlegroups.com>,
mathlover <immathlover@yahoo.com> wrote:
Quote:  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.

Put another way:
What is the largest family S of kelement subsets of X = {1,...,n}
such that there are at most r1 members of S containing 1?
Clearly you could take all C(n1,k) kelement subsets of X that don't
contain 1, plus min(r1, C(n1,k1) of the C(n1,k1) kelement
subsets of X that do contain 1, and you can't do better than that.
So your answer is p = C(n1,k) + min(r1, C(n1,k1)) + 1.
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Thu Jul 20, 2006 7:02 am Post subject:
Re: A Combinatorics/Graph Theory Question



mathlover wrote:
Quote:  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.

Your question seems to have been answered elsewhere. HOWEVER:
In the future, if you are going to post the same thing to more than
newsgroup, post it to both at once (this is called "crossposting").
That way, people who read one newsgroup can see replies that the people
who read the other newsgroup have made.
 Christopher Heckman 

Back to top 


Google


Back to top 



The time now is Wed Sep 26, 2018 4:24 am  All times are GMT

