most recent 30 from http://mathoverflow.net 2013-06-20T12:46:11Z http://mathoverflow.net/feeds/question/79270 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/79270/a-hypercube-related-graph Seva 2011-10-27T14:37:15Z 2011-10-28T04:21:29Z

<p>For integer $n\ge 3$, consider the graph on the set of all even vertices of the $n$-dimensional hypercube $\{0,1\}^n$ in which two vertices are adjacent whenever they differ in exactly two coordinates. This is an $(n(n-1)/2)$-regular graph on $2^{n-1}$ vertices. Is there any standard name / notation for this graph? Is there a way to construct it from some "basic" graphs using standard graph operations (like products of graphs)? Has anybody ever studied the isoperimetric problem for this graph?</p> <p>Thanks!</p>

http://mathoverflow.net/questions/79270/a-hypercube-related-graph/79328#79328 gordon-royle 2011-10-27T22:46:24Z 2011-10-27T22:46:24Z

<p>This graph is known as the half-cube.</p> <p>I don't know about the other question.</p>

http://mathoverflow.net/questions/79270/a-hypercube-related-graph/79338#79338 Zack Wolske 2011-10-28T00:33:36Z 2011-10-28T04:21:29Z

<p>Conway &amp; Sloane's "Sphere Packings, Lattices and Groups" references Coxeter's "Regular Polytopes" for the phrase "halfcube", but Coxeter only uses the notation $h\Pi_n$, saying $h$ can be taken to stand for half- or hemi-, for an arbitrary polytope $\Pi_n$ {$p, q, \ldots, w$} with even $p$ (in your case, {$4,3,3,\ldots, 3$}) This construction is section 8.6 in Coxeter. Since then, halfcube seems to have lost favour, and hemi-cube has become the name for a construction of quotienting out vertices, while the term demicube (or demihypercube if you want to be explicit about using hypercubes and not cubes) is reserved for the construction of deleting vertices of a hypercube. See Conway, Burgiel and Goodman-Strass's "Symmetries of Things." Chapter 26 covers this, where they call them hemicubes, and draw some lovely pictures.</p> <p>Specific dimensional cases have different names. Your $n=3$ case is the complete $K_4$. $n=4$ is the 16-cell, also called a hexadecachoron in older books, and happens to be a cross-polytope (this does not continue in higher dimensions). By $n=5$, the polytopes begin to take shape as their own specific family and no longer have multiple names. See <a href="http://en.wikipedia.org/wiki/Demihypercube" rel="nofollow">http://en.wikipedia.org/wiki/Demihypercube</a>, and various dimension specific pages there.</p> <p>I do not know anything about the isoperimetric problem for these graphs, but there has likely been work done on the $n \leq 4$ cases, since those graphs also show up as other constructions.</p>