Search   Memberlist   Usergroups
 Page 1 of 1 [2 Posts]
Author Message
mathlover
science forum beginner

Joined: 04 May 2005
Posts: 13

Posted: Wed Jul 19, 2006 11:30 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.
Brian M. Scott
science forum Guru

Joined: 10 May 2005
Posts: 332

Posted: Thu Jul 20, 2006 8:32 pm    Post subject: Re: A Combinatorics/Graph Theory Question

On 19 Jul 2006 16:30:16 -0700, mathlover
<immathlover@yahoo.com> wrote in
<news:1153351816.624884.222030@i3g2000cwc.googlegroups.com>
in alt.math.undergrad:

 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

X has n vertices, not "n" vertices: when you enclose the
letter in quotation marks, you're talking about the symbol
itself, not what it represents. The same goes for all of
the other places where you've used quotation marks in this
way.

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

That's backwards from the standard one-line notation, in
which n choose k is written C(n, k).

 Quote: 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)

C(n-1, k-1) here and later.

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

So X is an arbitrary set with cardinality n. Without loss
of generality Y = [X]^k, where [X]^n is a standard notation
for the set of subsets of X of cardinality k. For each x in
X and y in Y, {x, y} is an edge of the graph G iff x in y.
For each x in X, deg(x) = C(n-1, k-1), and for each y in Y,
deg(y) = k.

Say that a subset S of Y is r-dense if each x in X has at
least r neighbors in S. You want to know the minimum
cardinality of an r-dense subset of Y; I'll denote this by
p(n, k, r).

 Quote: Any help or clues are greatly appreciated.

Here's a start.

Suppose that S is r-dense. Then each element of X belongs
to at least r members of S, so |S| >= nr/k.

Now suppose that n is a multiple of k^r, say n = m*k^r.
Then without loss of generality we can take X to be
{(i_0, ..., i_r) : 1 <= i_0 <= m, 1 <= i_j <= k for j =
1, ..., r}. For each x = (i_0, ..., i_r) in X and j with
1 <= j <= r let y(x, j) be the set of points in X that
differ from x in at most the j-th coordinate; clearly
x in y(x, j) in Y. Moreover, if 1 <= j' <= r with j' != j,
then y(x, j') != y(x, j), so {y(x, j) : 1 <= j <= r} is a
collection of r members of Y, each of which contains x. Let
S = {y(x, j) : x in X & 1 <= j <= r}; we've just seen that S
is r-dense. Finally, |S| = m*r*k^(r-1) = nr/k, and it
follows that p(n, k, r) = nr/k when n is a multiple of k^r.

To answer the question completely, therefore, it suffices to
determine p(n, k, r) when n < k^r. I suspect that it's
ceil(nr/k), where ceil is the ceiling function (i.e.,
ceil(x) is the least integer greater than or equal to x),
but I've not had time to think about it seriously.

Brian
Google

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [2 Posts]
 The time now is Fri Apr 26, 2019 1:53 pm | All times are GMT
 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

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters

Powered by phpBB © 2001, 2005 phpBB Group
 [ Time: 0.0181s ][ Queries: 16 (0.0053s) ][ GZIP on - Debug on ]