Subject: Re: How Many Edges Hath a Hypercube? (fwd)

From: Tom Banchoff <[email-masked]>
Date: Sat, 27 Jan 1996 17:02:27 -0500 (EST)

---------- Forwarded message ----------
Date: Sat, 27 Jan 1996 17:02:10 -0500 (EST)
From: Tom Banchoff <tfb@budge>
To: Keith Adams <[email-masked]>
Subject: Re: How Many Edges Hath a Hypercube?

Dear Keith,
        Good show.  You have given a good description of a recursive 
definition of the number of edges in an n-cube, meaning that you can 
figure out the answer for a specific n if you know the values of vertices 
and edges for the previous integers (when n > 0 anway).  Can you find a 
"closed form" expression for the number of edges in an n-cube, i.e. a 
straight formula depending only on n?  
        It will be interesting to see how the technology improves for the 
transmission of formulas and images in geometry.
        By the way, could you send subsequent messages to the address
[email-masked]?  That way they go directly to my 
Macintosh where I am keeping Math 8 things until our new page is set up.
Thanks.

        Prof. B. 

On Fri, 26 Jan 1996, Keith Adams wrote:

>                 How Many Edges Hath a Hypercube?
> 
> What is really asked when one asks for the number of edges of a
> hypercube? First off, let us say what we mean by a hypercube. Given a
> length k, a cube of n dimensions, where n is a positive integer, is
> the figure formed by two congruent cubes of n-1 dimensions and line
> segments of length k connecting the corresponding vertices of the two
> congruent cubes of n-1 dimensions such that each of these line
> segments is perpendicular to each line segment in the cube of n-1
> dimensions which connects one of its endpoints with another vertex of
> the cube. We also define the special case where n=0, in which case the
> cube of zero dimensions is a point, which point is its only vertex.
> Each line segment which connects two vertices of the cube of n
> dimensions is an edge. A hypercube is a cube of four dimensions.
> Notice that not all vertices are connected by edges. Also notice that
> for ease of definition, I am defining cubes as wire frames; wind blows
> through them. Finally, for ease of notation I will sometimes write
> "n-cube" to mean the cube of n dimensions.
> 
> Let's see some applications of this. First, the cube of 0 dimensions,
> by definition:
> 
>                                 .
> 
> 
> Next, we follow the definition's recipe for finding a 1-cube. What we
> need is a figure where two 0-cubes, or points, which are congruent (as
> are all points) are connected with a line segment of length k, such
> that all other edges blah blah blah, but there are no other edges, so
> it's just a line segment, basically. Let's name our endpoints P and Q.
> 
> 
>                         *--------------*
>                          P              Q
> 
> PQ=k, because we said so.
> 
> Things really get interesting when it comes time to look a a 2-cube,
> because for the first time the cube of n-1 dimensions has edges, and
> the perpendicularity of our new edges comes into play. The definition
> tells us that we will need two congruent 1-cubes:
> 
>                         *--------------*
>                          P              Q
> 
> 
> 
> 
> 
> 
>                         *--------------*
>                          R              S
> 
> RS=PQ=k, because that's what congruency of line segments means. Now we
> connect the corresponding vertices (P to R and Q to S) such that PR
> and QS are perpendicular to all segments connecting vertices in the
> original n-1-cube. In our case, there aren't that man
> perpendicularities to account for.
> 
>                         *--------------*
>                         |P           |_|Q
>                         |              |
>                         |              |
>                         |              |
>                         |              |
>                         |_            _|
>                         | |          | |
>                         *--------------*
>                          R              S
> 
> Due to the limitations of ASCII email, we can stop here, having gotten
> the flavor of the definition I'm working with without unwisely
> overstepping the rendering power of this medium.
> 
> Now, in order to actually tackle the problem of edge-counting, let's
> first look at the issue of vertex-counting. We know that the only new
> vertices introduced in each successive dimension are in a copy of the
> cube of n-1 dimensions. We can reasonably conclude that the following
> function V() will return the correct number of vertices for a cube of
> n dimensions.
> 
>              _
>             / n>=1:  2 * V(n-1)
>             |
>     V(n) = <
>             |
>             \ n=0: 1
>              -
> 
> This is an overblown way of saying that V(n) = 2^n.
> 
> So, now we are ready to directly concern ourselves with the problem of
> edge-counting. First of all, what has our definition to tell us about
> edges? Well, we know that contained in the new figure are two copies
> of the old figure. Intuitively, it seems reasonable then to assume
> that the number of edges is greater than or equal to the number of
> edges for an n-1 cube. Also, we know that there are some new edges
> added for each dimension. How many? Well, the definition stated it in
> a round about way, but since corresponding vertices of the n-1-cube
> are the ones connected by these edges, those added edges are equal in
> number to the number of vertices of the n-1-cube. So, we can define a
> function E to give the number of edges for a cube of n dimensions:
> 
>              _
>             / n>1:  2 * E(n-1) + V(n-1)
>             |
>     E(n) = <
>             |
>             \ n<=1: n
>              -
> 
> For a hypercube, ie a 4-cube, E(4) = 32.
> 
> 
> Keith Adams
> 
> 
>