# A hypercube-related graph

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?

Thanks!

• isoperimetry looks very similar to that of usual hypercube graph, as distance between two vertices is half of the distance between them in hypercube – Fedor Petrov Oct 27 '11 at 15:52
• @Fedor: The isoperimetric problem for a given graph is to determine, for every given $n$, the maximum possible number of edes of an induced subgraph of order $n$. I cannot see any immediate relation between the isoperimitric problem for the hypercube and the graph I am interested in. – Seva Oct 27 '11 at 17:14
• Isn't that just the line graph of the ordinary hypercube graph? – Zsbán Ambrus Nov 1 '11 at 22:39
• @Zsban: certainly, not! To begin with, the line graph of the hypercube has order $n\cdot 2^n$ (the number of edges of the hypercube), while the graph in question has order $2^{n-1}$. – Seva Nov 3 '11 at 7:18
• Seva: you're right, sorry. – Zsbán Ambrus Nov 4 '11 at 8:14

## 2 Answers

Conway & 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.

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 http://en.wikipedia.org/wiki/Demihypercube, and various dimension specific pages there.

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.

• For $n=5$ it's the configuration of $16$ lines on a generic Del Pezzo surface of degree $4$ (complete intersection of two quadrics in 4-space): two lines meet iff the corresponding vertices are disjoint. [The induced graph on the 10-vertex co-neighborhood is Petersen.] This generalizes to higher odd $n$; apprently this was first shown in Miles Reid's thesis. – Noam D. Elkies Oct 28 '11 at 0:41

This graph is known as the half-cube.

I don't know about the other question.