wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> N Dimentional Cube 
        
(Message started by: Dudidu on Dec 16^th, 2003, 7:27am)

Title: N Dimentional Cube
Post by Dudidu on Dec 16^th, 2003, 7:27am

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) ?

Title: Re: N Dimentional Cube
Post by James Fingas on Dec 16^th, 2003, 8:21am

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. [hide] 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 2^N-1. The upper bound for the number of edges that cross the cut is all the edges, N*2^N-1. [/hide]

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.

Title: Re: N Dimentional Cube
Post by Dudidu on Dec 17^th, 2003, 11:00pm

on 12/16/03 at 08:21:55, 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...

Title: Re: N Dimentional Cube
Post by Aryabhatta on Jun 17^th, 2004, 7:45am

on 12/17/03 at 23:00:57, Dudidu wrote:

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
4^xx^xy^y [le] (x+y)^(x+y)

Setting y = tx we get the equivalent inequality
4t^t [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 2^n-1 for an n dimensional cube. (as any subgraph of 2^n-1 vertices of the cube has no more than (n-1)2^n-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?

Title: Re: N Dimentional Cube
Post by Aryabhatta on Aug 9^th, 2004, 10:52am

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.