The edge-isoperimetric problem on the 600-vertex regular solid (Q1399246)

The edge boundary of a subset \(S\) of the set of vertices \(V\) of a graph is the number of edges from \(S\) to \(V\setminus S\). The edge-isoperimetric problem (EIP) seeks, for a given positive integer \(k\), the smallest edge boundary among all sets of \(k\) vertices. The authors report on their solution to the EIP on a certain four dimensional polytope with 600 vertices. The EIP had previously been solved for all other regular convex polytopes. The method of solution is to convert the EIP to a maximum weight ideal problem on the stability order of the polytope. From there, a morphism is used to reduce the problem to a size which can be handled by a computer.