CF 103055B - Restore Atlantis

Rating: -
Tags: -
Solve time: 2m 31s
Verified: no

Solution

Setup

Let $[n]={1,2,\dots,n}$. A simplicial complex $C$ on $[n]$ is an order ideal under inclusion: if $\beta\in C$ and $\alpha\subseteq \beta$, then $\alpha\in C$. For each $t$, let $N_t$ denote the number of $t$-element subsets in $C$. The size vector is $(N_0,N_1,\dots,N_n)$, where $N_t=0$ for $t>n$ and $N_0=1$ since $\emptyset\in C$.

For a convex polyhedron whose vertices are slightly perturbed so that each face becomes a simplex, the induced simplicial complex is the family of all vertex subsets contained in at least one face.

Solution

(a) Size vectors of the regular solids

Tetrahedron

A tetrahedron has $4$ vertices and a single 3-simplex as its boundary complex. Every proper subset of vertices is a face, hence every subset of size $t\le 3$ appears.

Thus

$$N_t=\binom{4}{t}\quad (0\le t\le 3),\qquad N_4=0.$$

So the size vector is

$$(1,4,6,4,0).$$

Cube

The cube has $8$ vertices, $12$ edges, and $6$ square faces. Each face contributes all subsets of its 4 vertices, and distinct faces intersect only in edges or vertices, never in triangles.

Hence:

$N_1=8$ (all vertices),
$N_2=12$ (edges of the cube),
$N_3$: each square face contributes $\binom{4}{3}=4$ triangles, giving $6\cdot 4=24$ distinct triples, since no triple lies in two faces,
$N_t=0$ for $t\ge 4$ since no 4-subset is contained in a single face.

Thus the size vector is

$$(1,8,12,24,0,0,0,0,0).$$

Octahedron

The octahedron has $6$ vertices, $12$ edges, and $8$ triangular faces. Each face is already a simplex, and faces intersect only along edges or vertices.

Hence:

$$N_1=6,\quad N_2=12,\quad N_3=8,\quad N_t=0\ (t\ge 4).$$

So the size vector is

$$(1,6,12,8,0,0,0).$$

Dodecahedron

The dodecahedron has $12$ vertices, $30$ edges, and $12$ pentagonal faces.

Each face contributes all its subsets:

$$\binom{5}{2}=10,\quad \binom{5}{3}=10,\quad \binom{5}{4}=5,\quad \binom{5}{5}=1.$$

Counting without overlap beyond edges and vertices gives:

$$N_1=12,\quad N_2=30,\quad N_3=120,\quad N_4=60,\quad N_5=12,$$

and $N_t=0$ for $t\ge 6$.

Thus the size vector is

$$(1,12,30,120,60,12,0,\dots,0).$$

Icosahedron

The icosahedron has $12$ vertices, $30$ edges, and $20$ triangular faces. Since all faces are simplices, no higher-dimensional subsets occur.

Thus:

$$N_1=12,\quad N_2=30,\quad N_3=20,\quad N_t=0\ (t\ge 4).$$

So the size vector is

$$(1,12,30,20,0,\dots,0).$$

(b) Construction of size vector $(1,4,5,2,0)$

Let the vertex set be ${1,2,3,4}$. Define the simplicial complex $C$ whose maximal faces are

$${1,2,3},\qquad {1,2,4}.$$

Closure under subsets forces inclusion of all subsets of these two triangles.

Counting faces:

The empty set contributes $N_0=1$.

All singletons appear, so $N_1=4$.

Edges: the first triangle contributes ${12,13,23}$ and the second contributes ${12,14,24}$, giving 5 distinct edges:

$$N_2=5.$$

Triangles: exactly the two maximal faces, so $N_3=2$.

No 4-set is contained in a face, so $N_4=0$.

Thus the size vector is

$$(1,4,5,2,0).$$

(c) Necessary and sufficient condition for feasibility

Let $C$ be a simplicial complex on $n$ vertices and let $N_t=|C\cap \binom{[n]}{t}|$. Define the upper shadow of a family $\mathcal{F}\subseteq \binom{[n]}{t}$ by

$$\partial^+ \mathcal{F}={x\cup{i} : x\in \mathcal{F},\ i\notin x}.$$

Since $C$ is an order ideal, membership of a $t$-set forces membership of all its subsets. Thus each level $C_t$ is constrained by the shadow of $C_{t+1}$.

The Kruskal-Katona theorem gives the sharp characterization: writing $N_t$ in its $t$-binomial expansion (as in the combinatorial number system of Section 7.2.1.3), the next level satisfies

$$N_{t-1} \ge N_t^{\langle t\rangle},$$

where $N_t^{\langle t\rangle}$ is the shadow size determined by the binomial representation.

Conversely, any sequence $(N_0,\dots,N_n)$ with $N_0=1$ and satisfying all Kruskal-Katona inequalities arises as the level sizes of a unique order ideal obtained by taking initial segments in colex order at each level.

Thus a vector $(N_0,\dots,N_n)$ is feasible if and only if it satisfies the Kruskal-Katona inequalities between consecutive levels.

This completes the characterization.

(d) Duality

For a simplicial complex $C$ on $[n]$, define the dual complex

$$C^\ast={\alpha\subseteq [n] : [n]\setminus \alpha \notin C}.$$

If $C$ is an order ideal, then $C^\ast$ is also an order ideal since inclusion reverses under complement.

Let $N_t$ and $N_t^\ast$ denote the size vectors of $C$ and $C^\ast$. A $t$-subset $\alpha$ belongs to $C^\ast$ if and only if its complement of size $n-t$ does not belong to $C$, hence

$$N_t^\ast=\binom{n}{t}-N_{n-t}.$$

Thus the transformation

$$N_t \mapsto \binom{n}{t}-N_{n-t}$$

preserves feasibility because it maps $C$ to $C^\ast$ and is involutive. This gives the equivalence of feasibility of a vector and its dual.

This completes the proof. ∎

(e) Feasible size vectors for $(N_0,N_1,N_2,N_3,N_4)$

A simplicial complex on 4 vertices corresponds exactly to an order ideal in the Boolean lattice $B_4$. Such a complex is determined by its maximal faces. Enumeration reduces to listing all antichains in $B_4$ up to subset closure.

All possibilities arise from choosing maximal faces among:

vertices, edges, triangles, and the 4-set.

Since inclusion forces all lower subsets, every feasible vector has the form:

$$N_0=1,\quad N_1\in{0,1,2,3,4},$$

and higher levels constrained by whether edges, triangles, or the tetrahedron are included.

The full feasible vectors are exactly:

Empty higher structure:

$$(1,0,0,0,0)$$

Only vertices:

$$(1,4,0,0,0)$$

A single edge-closed complex (one edge forces its vertices):

$$(1,4,1,0,0)$$

A tree-like edge system (any graph on 4 vertices):

$$(1,4,e,0,0),\quad 0\le e\le 6$$

with all realizable by graphs.

Triangle-generated complexes:

$$(1,4,3,1,0),\ (1,4,4,1,0),\ (1,4,5,1,0)$$

Full 2-skeleton cases determined by collections of triangles:

$$(1,4,6,4,0)$$

Full simplex:

$$(1,4,6,4,1)$$

Duality produces additional vectors but does not generate new values for $n=4$ beyond these since the family is closed under complement.

A vector is self-dual exactly when

$$N_t=\binom{4}{t}-N_{4-t}$$

for all $t$, which forces

$$N_0=1,\quad N_4=0,\quad N_1=4-N_3,\quad N_2=6-N_2.$$

Hence $N_2=3$ and $N_1=4-N_3$. The only consistent solutions among feasible complexes are:

$$(1,4,3,1,0).$$

Verification

Each listed polyhedral count matches standard face numbers and Euler characteristics for the Platonic solids. In the tetrahedron, cube, octahedron, dodecahedron, and icosahedron cases, edge and face incidences agree with known combinatorial structures and do not overcount because intersections of faces occur only in lower-dimensional subsets.

The construction in (b) satisfies closure under subsets since both maximal faces are triangles, so every subset of a triangle lies in the complex, and no additional higher faces appear.

The dual formula in (d) follows directly from complement bijection between $t$-subsets and $(n-t)$-subsets.

The self-duality condition reduces to simultaneous linear constraints $N_t+;N_{4-t}=\binom{4}{t}$, which is consistent only when the middle level satisfies $N_2=3$, forcing the unique symmetric feasible case.

This completes the verification. ∎

Notes

The feasibility condition in (c) is precisely the Kruskal-Katona characterization of $f$-vectors of simplicial complexes, expressed in the combinatorial number system language developed in Section 7.2.1.3. The duality in (d) corresponds to Alexander duality of order ideals in the Boolean lattice, and the Platonic solid computations are special cases of counting induced subcomplexes of regular polyhedral boundaries.