small cut in hypercube graph In his notes on spectral graph theory Luca Trevisan writes "A $k$-dimensional hypercube with $n = 2^k$ is considerably better connected than a grid, although it is still possible to remove a vanishingly small fraction of edges (the edges of a “dimension cut,” which are a $1/k = 1/ \log_2 n$ fraction of the total number of edges) and disconnect half of the vertices from the other half" My question is, what exactly is this dimension cut? I haven't been able to Google this.

I think a dimension cut would be a cut parallel to a coordinate hyperplane.

For example in the $k=3$ case, we could cut parallel to the $yz$-plane.

This would cut the edges joining the following pairs of (previously connected) vertices in the $3$-cube:

000 and 100

001 and 101

010 and 110

011 and 111

This would disconnect the vertices 000, 001, 010, 011 from the other four.

* * *

Edited:

Note that we cut $4$ out of $12$ edges, or $\frac13$ of the edges, as predicted for dimension $3$.