Author |
Topic: N Dimentional Cube (Read 659 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
N Dimentional Cube
« on: Dec 16th, 2003, 7:27am » |
 Quote  Modify
|
I don't know if this is the place for this problem but I hope it is:
Given a N-dimentional cube (G), a subset of its vertices (H) s.t. H's size (i.e. number of vertices) is exectly half of the size of G.
Give a lower bound on the number of edges that crosses the cut (H, G \ H) (i.e. a number of edges that for every chosen H must exist) ?
|
|
 IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender: 
Posts: 949
|
|
Re: N Dimentional Cube
« Reply #1 on: Dec 16th, 2003, 8:21am » |
Quote Modify
|
My assumption is that the optimal way to select H so that the number of edges that cross the cut is minimized is to choose one of the dimensions j, and make H the set of vertices that have coordinate 1 in dimension j. Since each point is connected to all points that differ by only one coordinate, then each point in H touches a single point in G \ H. Therefore, the number of edges that cross the cut is the size of H, which is 2N-1. The upper bound for the number of edges that cross the cut is all the edges, N*2N-1.
Interesting side-note: in 3 dimensions, no matter how you pick H, H and G \ H are are topologically identical. This means that minimizing the number of edges that cross the cut is the same as maximizing the number of edges inside H. In higher dimensions they're not always the same, and they don't always have the same number of edges inside them.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: N Dimentional Cube
« Reply #2 on: Dec 17th, 2003, 11:00pm » |
Quote Modify
|
on Dec 16th, 2003, 8:21am, James Fingas wrote:| My assumption is that the optimal way to select H so that the number of edges that cross the cut is minimized is to choose one of the dimensions j... |
|
James hi,
Your assumption is correct !
Can you think of a more formal way to prove this (I know how to prove it in a fairly complicated combinatorial way and I wonder if there can be a more easy way) ?
Thanks...
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: N Dimentional Cube
« Reply #3 on: Jun 17th, 2004, 7:45am » |
Quote Modify
|
on Dec 17th, 2003, 11:00pm, Dudidu wrote:
James hi,
Your assumption is correct !
Can you think of a more formal way to prove this (I know how to prove it in a fairly complicated combinatorial way and I wonder if there can be a more easy way) ?
Thanks...
|
|
Let f(x) = (x logx)/2, the log being taken base 2.
Let S be a subgraph of any hypercube.
(By a subgraph I mean consider a subset V of the vertices and consider a subset E of edges of the hypercube with each endpoint of each edge of E being in V)
I think we can show that, for any subgraph S(V,E) of a hypercube, |E| [le] f(|V|)
i.e the number of edges in S is [le] (|V|log|V|)/2
where |V| is the number of vertices in S.
I think we can show that:
f(x) + f(y) + min{x,y} [le] f(x+y) [forall] x,y [ge] 1. - (1)
LHS being equal to RHS iff x = y.
Assume x <= y. Let y = tx where t [ge] 1.
Now f(x) + f(y) + x [le] f(x+y) iff
4xxxyy [le] (x+y)(x+y)
Setting y = tx we get the equivalent inequality
4tt [le] (1+t)(1+t)
i.e.
4/t [le] (1+1/t)(1+t) - (*)
Using (1 +h)x [ge] 1 + hx + x(x-1)h[sup2]/2 we can prove (*)
Now a hypercube H of dimension D+1 is composed of 2 hypercubes (say H1 and H2) of dimension D, with each vertex of H1 connected to exactly one vertex of H2 and vice versa. -(2)
Given |V|, Let S be a subgraph of H with |V| vertices and |E| edges. Suppose for any other subgraph S' of H with |V| vertices, the number of edges in S' [le] |E| (i.e S is maximal with respect to number of edges)
We can prove by induction that |E| [le] f(|V|) using (1) and (2)
Using this we can show that the minimum cut (with each vertex set being 1/2 the total) is at least 2n-1 for an n dimensional cube. (as any subgraph of 2n-1 vertices of the cube has no more than (n-1)2n-2
edges. (using the upper bound we just showed))
I have given up on finding a combinatorial proof...
I am curious to know what proof you came up with. If it is not a bother, can you please post the proof (or at least a hint) here?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: N Dimentional Cube
« Reply #4 on: Aug 9th, 2004, 10:52am » |
Quote Modify
|
I found the following in a combinatorics book.
Harper, Bernstein and Hart proved the following:
Let h(i) be the sum of digits in the binary representation of i.
for 0 [le] l < m define
f(l,m) = [sum] l [le] i < m h(i)
Then, the edge maximum subgraph of m vertices of the nD hypercube has exactly f(0,m) edges.
i.e any m vertex subgraph of the nD hypercube has no more than f(0,m) edges and there is a subgraph which has exactly f(0,m) edges.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print