8
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ isoperimetry looks very similar to that of usual hypercube graph, as distance between two vertices is half of the distance between them in hypercube $\endgroup$ Oct 27, 2011 at 15:52
  • $\begingroup$ @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. $\endgroup$
    – Seva
    Oct 27, 2011 at 17:14
  • $\begingroup$ Isn't that just the line graph of the ordinary hypercube graph? $\endgroup$ Nov 1, 2011 at 22:39
  • $\begingroup$ @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}$. $\endgroup$
    – Seva
    Nov 3, 2011 at 7:18
  • $\begingroup$ Seva: you're right, sorry. $\endgroup$ Nov 4, 2011 at 8:14

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 28, 2011 at 0:41
2
$\begingroup$

This graph is known as the half-cube.

I don't know about the other question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.