Concertina Hypercubes

The graph of a concertina n-cube is the Hasse diagram of implications between n-place formulas in predicate logic.

The concertina n-cube is the geometric interpretation of this graph as a truncation of the n-cube.
Each of its pairs of opposite vertices corresponds to a face of the permutohedron of order n.

The cocoon concertina hypercube is a version with additional internal vertices and edges.

Names

These structures seemed to be unnamed, so I named the solid for its similarity to a concertina, and the variant with substructures for its similarity to a cocoon. For the sake of brevity the convex concertina n-cube is also called n-concertina and the cocoon concertina n-cube is called n-cocoon.

Geometry

Hasse diagram of 3-place formulas...	interpreted as a convex polyhedron	... called concertina cube

The red hexagons in the 3-concertina are 2-concertinas. The blue edges are 1-concertinas.

The image gives an idea how the coordinates of an n-concertina are constructed from the next smaller one:
The (n−1)-place coordinate tuples of the (n−1)-concertina are used to create the lower half of the n-place tuples of the n-concertina by inserting 0s in all n possible places of every tuple.

For n = 3 this means that from the 6 points of the concertina square 13 points are created,
which belong to 3 concertina squares between the 3 pairs of axes.

The upper half of the points is created by point reflection through the center.
(All coordinates of the top vertex are n+1, so all coordinates of the center are (n+1)/2.)

This inductive calculation of the coordinates is realized in old_to_new_points. A similar calculation of the formulas is realized in old_to_new_formulas. Here the equivalent to point reflection is complement.

The coordinates, abbreviated formulas and pseudo-octal strings for n = 2..6 can be found here: 2, 3, 4, 5, 6
The edges of n-concertinas for n = 2..5 can be found here: 2, 3, 4, 5

Cocoon concertina hypercube

When variables are allowed to coincide (like in ∃x L(x, x) for "Someone loves himself.") the resulting Hasse diagram becomes rather messy. There seems to be no reasonable interpretation as a polytope — let alone a convex one.

For n ≥ 3 this poset is not graded. But it seems to be possible to force each inner vertex on a rank level of the convex polytope (see ranks 1 / 5, 2 / 4 and 3 for n = 3). The reason is that there are many substructures with (real or assigned) ranks. Apart from the convex solid these are smaller cocoons (like this 2- in a 3-cocoon) and Hasse diagrams of set partitions (like this one for a 4-set). One for a 3-set with Bell(3) = 5 vertices can be seen in the 3-cocoon between the origin and the lower orange vertex.

There is no obvious way to find coordinates for the inner vertices.

Cocoon concertina square with 8 vertices and 13 edges		Cocoon concertina cube with 46 vertices and 139 edges

The similarity of the 2-cocoon with the cube (just one edge more) is rather misleading. But labeling its vertices from 0 to 7 like those of a cube (edge where bitwise ≤) is handy in the pseudo-octal representation of longer formulas.

The edges of n-cocoons for n = 2..5 can be found here: 2, 3, 4, 5

Logic

Note that the abbreviation counts from 1 while the code representation counts from 0.
The formula and its abbreviation read the visualisation vertically.

formula	abbr.	oct.	vis.	code representation
∀y ∃x P(x, y)	a2 e1	3		vert = [False, True] horz = [1, 0]
∃x P(x, x)	e(12)	5		vert = [True] horz = [0, 0] partitions_dict = {0: [[0, 1]]}
∀y ∃x ∀z P(x, y, z)	a2 e1 a3	31-0		vert = [False, True, False] horz = [1, 0, 2]
∀y ∀z ∃x P(x, y, z)	a23 e1	33-0		vert = [False, True] horz = [1, 0, 0]
∃x ∃z ∀y P(x, y, z)	e13 a2	17-4		vert = [True, False] horz = [0, 1, 0]
∃x ∀y P(x, y, x)	e(13) a2	15-4		vert = [True, False] horz = [0, 1, 0] partitions_dict = {0: [[0, 2]]}
∀y ∃x ∀z ∃w P(w, x, y, z)	a3 e2 a4 e1	733-31-0		vert = [False, True, False, True] horz = [3, 1, 0, 2]
∃z ∀x ∀y P(x, y, z, x)	e3 a(14)2	042-40-1		vert = [True, False] horz = [1, 1, 0, 1] partitions_dict = {1: [[0, 3], [1]]}

Formulas with parentheses in the abbreviations (and white dots in the visualisations) have coinciding variables,
so they are not found in the convex but only in the cocoon concertina hypercubes.

The formula a2 e1 a3 implies a23 e1. The pseudo-octal strings make this easy to see: 31-0 is bitwise ≤ 33-0.
As there are no formulas between them, a2 e1 a3 --> a23 e1 is an edge of the concertina cube.

The implication is realized in octal_implies. It checks if corresponding digits of two pseudo-octal strings are bitwise ≤ (an edge of the cube) or if they are 2 and 5 (the one edge of the 2-cocoon that is not in the cube). The pseudo-octal string of a formula is generated by octal. An explanation how it works can be found here.

Integer sequences

This project was created to calculate some integer sequences describing concertina hypercubes.
They are found in the OEIS. Currently there are no formulas, and the calculations take too long for n ≥ 6.

Convex

ID	description	n = 3	calculation
A300700	(n−k)-faces	1, 18, 42, 26	faces.sage
A300701	sum of k-faces (row sums of A300700)	87	faces.sage
A000629	vertices (column 0 of A300700, row sums of A300699)	26
A300693	edges (column 1 of A300700)	42	coordinates_hasse.py
A300699	vertices by rank	1, 3, 6, 6, 6, 3, 1	ranks_convex.py
A300697 A300698	volumes half volumes	52 26	volume.py

For n ≥ 1 the number of vertices is twice an ordered Bell number (A000670) in the n-concertina,
and twice the number of preferential arrangements (A083355) in the n-cocoon.

Cocoon

ID	description	n = 3	calculation
A300695	vertices by rank	1, 6, 13, 6, 13, 6, 1	cocoon.py
A300696	vertices (row sums of A300695)	46
A300694	edges	139	cocoon.py

Concertina tesseract details

A closer look at the geometric properties of the 4-concertina can be found in this subfolder, especially in variables.py.

Requirements

Libraries that were installed in Virtualenv are in requirements.txt.
Sage 8.1 was installed globally.