 Forum index » Science and Technology » Math » Combinatorics
Author Message
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 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 Mon Mar 18, 2019 5:29 pm | All times are GMT Forum index » Science and Technology » Math » Combinatorics
 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