 Forum index » Science and Technology » Math
Author Message
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 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.

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 "cross-posting").
That way, people who read one newsgroup can see replies that the people
who read the other newsgroup have made.

--- Christopher Heckman 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 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 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.

Put another way:
What is the largest family S of k-element subsets of X = {1,...,n}
such that there are at most r-1 members of S containing 1?

Clearly you could take all C(n-1,k) k-element subsets of X that don't
contain 1, plus min(r-1, C(n-1,k-1) of the C(n-1,k-1) k-element
subsets of X that do contain 1, and you can't do better than that.
So your answer is p = C(n-1,k) + min(r-1, C(n-1,k-1)) + 1.

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada 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 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.  Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 The time now is Tue Mar 26, 2019 3:53 am | All times are GMT Forum index » Science and Technology » Math
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Question about Life. socratus Probability 0 Sun Jan 06, 2008 10:01 pm Probability Question dumont Probability 0 Mon Oct 23, 2006 3:38 pm Probabilistic Combinatorics Notes Help Sundus Math 0 Fri Jul 21, 2006 11:27 am Question about exponention WingDragon@gmail.com Math 2 Fri Jul 21, 2006 8:13 am question on solartron 1260 carrie_yao@hotmail.com Electrochem 0 Fri Jul 21, 2006 7:11 am