Binary Order Thinning of Finite Posets: Homology, Collapses, and Sharp Limits

Extracted text · reading copy 3 · 16 PDF pages

Read the source-based HTML + MathML instead · Read the original PDF · Download the extracted text

Binary Order Thinning of Finite Posets:
Homology, Collapses, and Sharp Limits
Brian Theory
27 September 2026
Abstract
Let P be a finite poset, letb :P→{0,1}, and thin the order by retainingx≤P y exactly
when b(x)≤b(y). We study the inclusion of order complexes∆(Q)↪→∆(P ). When ht(P )≤2,
the one-bit relative boundaryC2(∆P,∆Q; Z)→C1(∆P,∆Q; Z) is a reduced oriented graph-
incidence matrix. This gives the complete integral relative homology, proves torsion-freeness, and
yields an exact recognition theorem: vanishing relative homology overF2, over every field, or over
Z is equivalent to a rooted-forest condition, to a perfect acyclic matching of the relative cells, and
to an actual simplicial collapse∆(P)↘∆(Q). The rigidity is sharp in two independent directions.
At height two, two simultaneous Boolean coordinates already admit a seven-element example
whose relative integral boundary has determinant−1 and whose endpoints are contractible, but
for which no relative elementary collapse can even begin; an exhaustive enumeration verifies
that no such two-bit example exists on at most six vertices. With unrestricted height, a one-bit
cone–whisker construction realizes the homotopy type of an arbitrary nonempty finite poset
inside a contractible coarse space and produces relative torsion already in height three. The
graph-incidence and total-unimodularity ingredients are standard, as are rooted-forest/fitting-
orientation methods and the general discrete-Morse mechanism linking appropriate acyclic
matchings to collapse. The contribution isolated here is the exact incidence recognition forced
by Boolean order thinning at height two, its coefficient-independent forest criterion, and the
identification of the two sharp boundaries.
Keywords. finite posets; order complexes; relative homology; simplicial collapse; graph incidence;
rooted forests; Boolean observations; discrete Morse theory.
1 Introduction
A simple operation on a finite poset already exhibits a useful boundary between rigid low-dimensional
topology and more general cancellation phenomena. LetP be a finite poset and let
b :P−→{0,1}.
Define a same-vertex suborderQ by
x≤Qy ⇐⇒x≤P y and b(x)≤b(y). (1)
Thus precisely the1→0 comparisons are deleted. The central question of this paper is when the
inclusion
∆(Q)↪→∆(P )
1

is topologically harmless, and when homological harmlessness is already strong enough to force an
explicit collapse.
Finite posets and their order complexes are classical, as are the links between finite spaces
and posets due to McCord and subsequent developments [16, 1, 2]. Relative homology, graph
incidence, total unimodularity, elementary collapse, and discrete Morse theory are also standard
tools [13, 12, 15, 10]. The point here is not to repackage these theories. It is that the Boolean rule
(1), together with the height-two restriction, forces a very special relative boundary which can be
recognized exactly.
Two closer antecedents deserve explicit separation from the contribution claimed here. Mukherjee
developed the topology of rooted forests and, in particular, collapse and relative-homology results for
triangulated closed manifolds [17, 18], and Contreras–Tawfeek proved for rooted forests of arbitrary
simplicial complexes that correspondence to a discrete gradient is equivalent to simplicial collapse
onto the root [6]. Accordingly, the matching-to-collapse mechanism used below is not claimed
as new; a short direct proof is retained because in the present two-layer setting it is elementary
and makes the relative-collapse order explicit. A different nearby use of Boolean functions and
order complexes is due to Björner–Goresky–MacPherson [5]: their complex is the induced order
complex on the true states of a Boolean function, whereas(1) keeps the carrier and deletes order
relations. The claim here is therefore narrower: the thinning rule at height two forces a reduced
graph-incidence boundary, and that forced form yields the exact equivalences and sharp failure
regimes proved below.
Our main positive result is the following. Height is counted by strict inequalities, soht(P )≤2
means that no chain has four elements, equivalentlydim ∆(P)≤2. LetK = ∆(P ) and L = ∆(Q).
All vertices survive the thinning. IfE and T are the deleted edges and deleted triangles, then the
only nonzero part of the integral relative chain complex is
B :C2(K,L; Z) = ZT−→C1(K,L; Z) = ZE.
For one bit, every column ofB has either one nonzero entry or two opposite nonzero entries.
After adjoining one formal root for each coarse connected component,B is exactly an oriented
graph-incidence matrix with the root rows removed.
This observation has three consequences. First, the entire integral relative homology is explicit
and torsion-free. Second, coefficient choice becomes irrelevant. Third, homological neutrality is
equivalent to a rooted forest, and leaf pruning of that forest is literally an elementary simplicial
collapse. In particular, for a single Boolean coordinate at height at most two,
H∗(K,L; F2) = 0 ⇐⇒H∗(K,L; Z) = 0 ⇐⇒K↘L.
The theorem also includes homotopy and simple-homotopy equivalence, a perfect acyclic matching
of the relative cells, and homology over an arbitrary field.
The equivalence is sharp on two independent axes. The first is bit count. With two coordinates,
the relative boundary need no longer be an ordinary graph incidence matrix. We give a seven-element
height-two poset and a mapα: P→{0,1}2 for which the relative7×7 integral boundary has
determinant−1, yet no deleted edge is initially free. The support graph has three perfect matchings
whose signed determinant contributions cancel to−1. Both endpoint posets beat-reduce to a
point, so the inclusion of order complexes is nevertheless a homotopy equivalence. A separate
exhaustive computation over all height-two naturally labelled posets and all two-bit labels through
six vertices finds no counterexample. Thus the seven-element example is vertex-minimal subject to
that exhaustive certificate.
2

The second sharpness axis is height. For any nonempty finite posetR, adding a new greatest
element and choosing one Boolean label in a particular way makes the coarse order complex a cone
while the thinned order complex is∆(R) with one collapsible whisker. Consequently unrestricted
one-bit thinning contains arbitrary finite-poset homotopy types and arbitrary corresponding reduced
homology shifts. In particular, one bit already produces relative torsion in height three. The height-
two hypothesis therefore does real mathematical work; it is not merely a convenient dimension
cutoff.
The paper is deliberately narrower than the broader logical-topology program from which the
problem arose. We use general finite-poset language first. Section 9 returns to the observation-
refinement interpretation only after the structural results are complete. We do not develop a separate
observation-dimension theory, generic persistence constructions, formula-level exact sequences, or
other branches that do not support the theorem above.
2 Order thinning, deleted cells, and relative chains
2.1 Finite-poset conventions
For a finite posetP, write ∆(P ) for its order complex: its vertices are the elements ofP, and a
k-simplex is a strict chain
x0<x 1<···<x k.
The heightht(P ) is the largest number of strict inequalities in a chain. Thusht(P ) = dim ∆(P ).
Connected components ofP mean connected components of its undirected comparability graph,
equivalently of∆(P ).
Givenb :P→{0,1}, defineQ =Qb by (1). Since the Boolean order is transitive,Q is a partial
order on the same ground set. We set
K = ∆(P ), L = ∆(Q).
BecauseQ andP have the same vertices,L is a spanning subcomplex ofK. A simplexx0<···<x k
of K lies inL exactly when
b(x0)≤b(x1)≤···≤b(xk).
Equivalently, it is deleted exactly when its Boolean word contains a1→0 descent.
More generally, for a block ofr Boolean coordinates
α:P−→{0,1}r,
we writeQαfor the coordinatewise thinning
x≤Qαy ⇐⇒x≤P y and α(x)≤α(y) (2)
where the last order is coordinatewise. The one-bit case isr = 1.
2.2 The relative complex
The inclusionL⊆K gives the usual relative chain complexC∗(K,L;R) over a coefficient ring
R [13]. SinceL contains all vertices,C0(K,L;R) = 0. If ht(P )≤2, there are no simplices above
dimension two, so withE the deleted edges andT the deleted triangles,
0−→RT BR
−−→RE−→0 (3)
3

is the complete relative complex. In particular,
H2(K,L;R) = kerBR, H 1(K,L;R) = cokerBR, H 0(K,L;R) = 0. (4)
This is a homology calculation, not by itself a homotopy test. The one-bit theorem below explains
why the special Boolean incidence structure supplies the missing homotopical information at height
two.
3 One bit at height two: an incidence theorem
Assume throughout this section thatht(P )≤2 and b :P→{0,1}. Orient every simplex by the
poset order. Forx<y <z ,
∂[x,y,z] = [y,z]−[x,z] + [x,y]. (5)
There are eight Boolean words on a three-chain. Four are nondecreasing and hence survive. The
four deleted words have the following relative boundaries.
wordb(x)b(y)b(z) deleted edges integral coefficients in ∂rel
010 yz +1
101 xy +1
100 xy,xz +1,−1
110 xz,yz −1,+1
In particular, a deleted triangle contains exactly one or two deleted edges, never zero and never
three.
Definition 3.1 (rooted incidence graph). Let E be the deleted edges. For every connected
component C of P, introduce a formal root∗C. The multigraphGb(P ) has vertex set
V (Gb(P )) =E⊔{∗C :C∈π0(P )}.
Each deleted triangleτcontributes one graph edge. Ifτhas two deleted edgese,f, join the vertices
e andf. If it has one deleted edgee, joine to the root of the coarse component containingτ. Orient
each graph edge so that, after deleting the root rows, its incidence column agrees with the signs in
(5).
Parallel graph edges are allowed. Every connected component ofGb(P ) contains at most one
formal root: all of its deleted-edge vertices and triangle edges lie inside a single connected component
of P, for which only one formal root was introduced.
Proposition 3.2 (integral incidence recognition). With the ordered deleted edges as rows and
deleted triangles as columns, the integral relative boundary
B :C2(K,L; Z)−→C1(K,L; Z)
is the oriented vertex-edge incidence matrix ofGb(P ) with all formal-root rows deleted.
Proof. A 010 or 101 column has one coefficient+1. It is the reduced incidence column of an edge
directed from the component root to the unique deleted-edge vertex. A100 or 110 column has two
coefficients +1 and−1, so it is the ordinary oriented incidence column of an edge between the two
deleted-edge vertices. These are all deleted three-chain patterns.
4

∗C e1 e2
τa τb
Figure 1: The two possible incidence types for a deleted triangle in the one-bit, height-two regime.
A triangle with one deleted edge is represented by an edge to the formal component root; a triangle
with two deleted edges is represented by an ordinary edge between their vertices. Deleting the root
rows recovers the relative boundary columns.
The proposition turns the complete relative homology into elementary graph topology. For a
finite graphG, letc(G) be its number of connected components and put
β1(G) =|E(G)|−|V (G)|+c(G).
Let c0(Gb(P )) be the number of connected components containing no formal root. Isolated roots
are permitted and contribute neither a relative chain generator nor a homology generator.
Theorem 3.3(complete integral relative homology). For one-bit thinning of a finite poset of height
at most two, the relative boundary matrixB is totally unimodular and
H2(K,L; Z)∼= Zβ1(Gb(P )), (6)
H1(K,L; Z)∼= Zc0(Gb(P )), (7)
H0(K,L; Z) = 0. (8)
Consequently all integral relative homology groups are torsion-free, and for every fieldk,
dimkH2(K,L; k) =β1(Gb(P )), dimkH1(K,L; k) =c0(Gb(P )).
Proof. An oriented graph-incidence matrix is totally unimodular. One elementary proof is by
induction on a square submatrix: a column with at most one nonzero reduces the determinant to a
smaller minor, while if every column has two nonzeros then the opposite signs make the row sum
zero. Deleting rows preserves total unimodularity. Thus Proposition 3.2 gives the first claim. This
is the ordinary graph-incidence phenomenon; more general relations between total unimodularity
and relative torsion are well established [10].
Consider one connected component ofGb(P ). If it contains a root, deleting the root row from its
incidence matrix gives full row rank. More is needed overZ to identify the cokernel: a spanning tree
of the component gives a square maximal minor of the reduced incidence matrix with determinant
±1. Hence the image is all ofZV−1, so the cokernel is zero; its kernel is the integral cycle space.
If the component contains no root, the matrix is the ordinary incidence matrix of a connected
graph, whose cokernel isZ and whose kernel is again its cycle space. Taking direct sums over graph
components gives(6)–(8). The universal coefficient theorem for homology of the pair gives, for every
field k, a short exact sequence
0−→Hk(K,L; Z)⊗Z k−→Hk(K,L; k)−→TorZ
1 (Hk−1(K,L; Z),k)−→0.
The integral relative groups above are free, so the Tor term vanishes and the stated field dimensions
follow.
Remark 3.4 (novelty boundary). The graph-incidence matrix, its total unimodularity, and the
formulas for graph cycle and component spaces are standard. The candidate contribution is the
recognition that the particular Boolean thinning rule forces the relative simplicial boundary into
precisely this reduced-incidence form. No new general matrix-tree theorem is claimed.
5

4 The exact forest/collapse theorem
CallGb(P ) a rooted forestif it is acyclic and every connected component contains exactly one formal
root. This includes isolated roots.
For later use, letL⊆K be any same-vertex simplicial inclusion withdimK≤2. Its relative
support graphΓ(K,L) is the bipartite graph whose left vertices are the deleted edgesE =K1\L1,
whose right vertices are the deleted trianglesT = K2\L2, and in whiche∈E is adjacent to
τ∈T exactly whene⊂τ. A perfect matching M ={(ei,τi)}is acyclic if the directed graph
on the matched pairs, with an arrowi→j whenever i̸= j and ei⊂τj, is acyclic. This is the
usual acyclicity condition for the corresponding matching of the relative face poset in this two-layer
setting.
Lemma 4.1 (two-layer matching–collapse lemma). LetL⊆K be as above. This is the present
two-layer specialization of the standard acyclic-matching/collapse principle when the unmatched cells
form the target subcomplex; compare Forman [12], Kozlov [15], and the rooted-forest formulation of
Contreras–Tawfeek [6]. The following are equivalent:
(i) K collapses simplicially ontoL using only deleted edge–triangle pairs;
(ii) Γ(K,L) has an acyclic perfect matching;
(iii) the poset of relative cellsK\L, ordered by inclusion, has a perfect acyclic matching.
Proof. A relative collapse sequence pairs every deleted triangle with the deleted edge removed with
it. If the pair(ei,τi) is removed at stepi and ei⊂τj with j̸=i, thenτj must already have been
removed before stepi; otherwiseei would not be free. Thus every arrow in the matched-pair digraph
points strictly backward in collapse order, so the resulting perfect matching is acyclic.
Conversely, letM ={(ei,τi)}be an acyclic perfect matching. Its matched-pair digraph has a
sink i. By definition of sink,ei lies in no remaining deleted triangle exceptτi. No retained triangle
can contain a deleted edge, becauseL is a subcomplex, and there are no simplices above dimension
two. Henceei is a free face ofτi. Collapse this pair and restrictM to the remaining relative cells.
The restricted matched-pair digraph is still acyclic, so iteration removes all relative cells. This proves
(ii)⇒(i); condition (iii) is the same matching condition expressed in the relative face poset.
Theorem 4.2(one-bit height-two recognition theorem). LetP be a finite poset withht(P )≤2, let
b :P→{0,1}, defineQ by (1), and putK = ∆(P ) and L = ∆(Q). The following are equivalent.
(i) H∗(K,L; F2) = 0.
(ii) H∗(K,L; k) = 0 for every fieldk.
(iii) H∗(K,L; Z) = 0.
(iv) Gb(P ) is a rooted forest.
(v) the poset of relative cellsK\L admits a perfect acyclic matching (equivalently,Γ(K,L) has
an acyclic perfect matching);
(vi) K collapses simplicially ontoL by deleted edge–triangle pairs;
(vii) the inclusionL↪→K is a simple-homotopy equivalence;
(viii) the inclusionL↪→K is a homotopy equivalence.
When these conditions hold and deleted cells are nonempty,B is square and detB =±1 after
compatible row and column orderings.
Proof. Theorem 3.3 makes (i)–(iv) equivalent: vanishing is exactlyβ1(Gb(P )) = 0 andc0(Gb(P )) = 0,
which says that every graph component is a tree containing its unique possible root.
6

Assume (iv). Any nontrivial rooted tree has a nonroot leaf. The corresponding deleted edgee
lies in exactly one currently remaining deleted triangleτ. No retained triangle can contain a deleted
edge, becauseL is a subcomplex, and there are no cells above dimension two. Thuse is a free face
of τin the current complex. Delete the pair(e,τ). OnGb(P ) this is exactly pruning a nonroot leaf
and its incident graph edge, leaving a rooted forest. Iteration removes all deleted cells and proves
(vi). Recording the pairs in the pruning order yields an acyclic perfect matching of the relative cells,
proving (v) as well.
Lemma 4.1 gives the converse (v)⇒(vi) directly in this two-layer situation. This step is a
transparent specialization of standard discrete-Morse collapse theory, not a new matching-to-collapse
theorem. A simplicial collapse gives a simple-homotopy equivalence and therefore a homotopy
equivalence, so (vi)⇒(vii)⇒(viii). Finally a homotopy equivalence induces an integral homology
equivalence, giving (viii)⇒(iii) and closing the cycle.
In the neutral nonempty case,(3) has zero kernel and cokernel, so|E|=|T|and B is an integral
isomorphism. Total unimodularity then forces determinant±1.
Corollary 4.3(greedy collapse algorithm). After the deleted edges and triangles have been con-
structed, homotopy neutrality of a one-bit height-two thinning can be decided in time linear in the
size of the defect incidence data: repeatedly remove a deleted edge incident to exactly one remaining
deleted triangle together with that triangle. The procedure succeeds exactly when all deleted cells are
exhausted.
Proof. This is nonroot-leaf pruning inGb(P ). Equivalently, one may test directly that each graph
component is a tree with exactly one root.
Remark 4.4. The theorem is stronger than a matrix-rank test for a particular coefficient field. The
extra force comes from the one-bit incidence structure, not from homology alone. Section 7 gives
a unimodular relative boundary for which direct collapse fails as soon as a second coordinate is
allowed.
5 Structural sufficient conditions and logical examples
The exact theorem above is specific to height two, but constructive sufficient conditions are available
in arbitrary height. We record only the forms that will be useful for interpreting Boolean observations.
Proposition 5.1(repair maps). LetP be any finite poset andb :P→{0,1}.
(a) If there is an order-preservingρ:P→P such thatρ(p)≤p and b(ρ(p)) = 0 for everyp, then
∆(Qb)↪→∆(P ) is a homotopy equivalence.
(b) Dually, if there is an order-preservingλ:P→P such thatp≤λ(p) and b(λ(p)) = 1 for every
p, the same conclusion holds.
Proof. In (a), ρis also monotone as a mapP →Qb, and iρ≤idP and ρi≤idQb. Pointwise
comparable monotone maps induce homotopic maps on order complexes, soi and ρare homotopy
inverses; see, for example, the comparable-map machinery in Barmak [1]. Part (b) is dual.
Let F =b−1(0) and T =b−1(1). Proposition 5.1 immediately gives the following closure-system
criteria.
7

Corollary 5.2 (floors, ceilings, and semilattice closure). Each of the following is sufficient for
homotopy preservation.
(a) For everyp∈P, F∩↓p has a greatest element.
(b) For everyp∈P, T∩↑p has a least element.
(c) P is a finite join-semilattice,F is join-closed, andF∩↓p̸= ∅ for everyp.
(d) P is a finite meet-semilattice,T is meet-closed, andT∩↑p̸= ∅ for everyp.
In (c) the repair isρ(p) = ⋁(F∩↓p); in (d) it isλ(p) = ⋀(T∩↑p).
Corollary 5.3(Horn-type specialization). Suppose a realized-signature poset is a meet-subsemilattice
of a Boolean cube and the truth states ofb are the models of a Horn CNF in the old coordinates. If
every realized signature lies below at least one such model, then the thinning preserves homotopy type.
Dually, on a join-subsemilattice, a union-closed false region that is lower cofinal gives a down-repair.
Remark 5.4. The closure properties of Horn and dual-Horn relations are classical [14, 19]. The
corollary is only their use as an explicit repair certificate; no blanket claim that every Horn-defined
observation is homotopy-neutral is intended. The cofinality and semilattice hypotheses are essential
parts of the statement.
Example 5.5 (the Boolean diamond). Let P be the Boolean diamond onD = ∅, A ={X},
C ={Y}, andB ={X,Y}. ThusD<A<B and D<C <B . The following four one-bit profiles
illustrate the criteria and the exact graph formula.
observation profile on (D,A,C,B) certificate effect
X∨Y 0,1,1,1 isotone Q =P
X XORY 0,1,1,0 rooted tree proper thinning;
homotopy-neutral
X⇔Y 1,0,0,1 rooted tree / true ceiling proper thinning;
homotopy-neutral
¬(X∨Y ) 1 ,0,0,0 one rootless component topology changes
For XOR the two deleted edgesA<B and C <B are each anchored by a one-deletion triangle,
giving a rooted two-leaf tree. XNOR is dual. For NOR the root is isolated and the three deleted-edge
vertices form an unrooted path; Theorem 3.3 givesH1(K,L; Z)∼= Z.
6 A controlled chain corollary
The complete one-bit classification for a coarse chain is included only as a compact order-theoretic
corollary. IfP =Cn, two positionsi<j are incomparable in the thinned order exactly whenbi = 1
and bj = 0. Hence the incomparability graph ofQ is a bipartite Ferrers graph (the neighborhoods
of the 1-vertices are nested), WritingInc(Q) for this incomparability graph, pairwise comparable
sets in a poset are chains, so
∆(Q) = Ind(Inc(Q)),
the independence complex of that Ferrers graph. Dochtermann–Engström give the corresponding
contractible-versus-two-point homotopy dichotomy for independence complexes of Ferrers graphs [9,
Proposition 3.7]; related Ferrers-graph topology is also developed by Claesson–Kitaev–Ragnarsson–
Tenner [8]. We therefore retain the result for its explicit Boolean-word formulation and elementary
beat-point proof, not as a novelty claim.
8

Theorem 6.1(binary chain trichotomy). Letn≥1, letP =Cn be then-element chain, and write
bi =b(i). Exactly one of the following occurs.
(a) The wordb1···bn is nondecreasing. ThenQ =P.
(b) The word is nonconstant and nonincreasing, hence1a0n−a for some 1 ≤a < n. Then
Q∼=Ca⊔Cn−a; in particular the thinning changesH0.
(c) In every other case,Q is beat-contractible and∆(Q)↪→∆(P ) is a homotopy equivalence.
Consequently there aren + 1 profiles withQ =P, n−1 profiles for which the thinning changesH0,
and 2n−2n remaining profiles withQ̸=P for which ∆(Q)↪→∆(P ) is nevertheless a homotopy
equivalence.
Proof. Case (a) is immediate from(1). In case (b), all comparisons inside the initial1-block and
final 0-block survive, while every comparison from the first block to the second is deleted, giving
the stated disjoint union.
For case (c), ifb1 = 0 then the first chain element remains a global minimum ofQ; ifbn = 1
the last remains a global maximum. Either condition makes∆(Q) a cone. The only remaining
endpoint pattern isb1 = 1, bn = 0. Since the word is not nonincreasing, some0 occurs before a
later 1. Remove the initial1-vertices one at a time: for each such vertex, the first later1 is the
least element of its strict upper set in the current poset, so it is an up-beat point. After these
removals the first remaining vertex has label0 and is a global minimum. ThusQ beat-reduces to a
point. The coarse chain is also contractible, and any map between nonempty contractible spaces is
a homotopy equivalence. Counting binary words gives the final formula.
7 Sharpness I: two bits already fail
For a general block thinning at height two, the relative complex still has the form(3), but its
columns need not be graph-incidence columns. The relative support graphΓ(K,L) introduced
before Lemma 4.1 is therefore the natural combinatorial object. Perfect matchings are thefitting
orientations of higher-dimensional rooted-forest theory in this special dimension [4, 11].
Proposition 7.1(direct collapse and unique fitting orientation). For any same-vertex block thinning
Q⊆P with ht(P )≤2, the following are equivalent:
(i) ∆(P ) collapses directly to∆(Q) by deleted edge–triangle pairs;
(ii) the relative support graph has an acyclic perfect matching;
(iii) the relative support graph has exactly one perfect matching.
The empty support graph has its unique empty matching and represents the identity collapse.
Proof. Lemma 4.1 gives (i)⇐⇒(ii). For a perfect matching, a directed cycle in the matched-pair
digraph is exactly an alternating cycle of the bipartite support graph. Flipping an alternating
cycle gives a second perfect matching. Conversely, the symmetric difference of two distinct perfect
matchings is a nonempty disjoint union of alternating cycles. Thus a perfect matching is acyclic
exactly when it is unique, proving (ii)⇐⇒(iii). The matching/fitting-orientation viewpoint is
standard [12, 4, 6]; the uniqueness argument above is only the bipartite two-layer form needed
here.
We now give the sharp counterexample. It is stated completely so that the existence claim does
not depend on the exhaustive search used later for minimality.
9

Theorem 7.2(seven-element two-bit counterexample). There is a seven-element posetP of height
two and a mapα:P→{0,1}2 such that, for the coordinatewise thinned suborderQ,
∆(Q)↪→∆(P )
is an integral homology equivalence and a homotopy equivalence, but∆(P )̸↘∆(Q) by a relative
elementary-collapse sequence.
Proof. Let P be the transitive closure of the cover relations
0< 2,0< 3,0< 4,1< 2,1< 4,
2< 5,2< 6,3< 5,3< 6,4< 5. (9)
Every maximal chain has three elements, soht(P ) = 2. Define
x 0 1 2 3 4 5 6
α(x) 10 01 01 00 11 00 01
The retained strict comparisons inQ are
(0,4),(1,2),(1,4),(1,6),(2,6),(3,5),(3,6). (10)
Order the deleted edges as
e1 = (0,2), e2 = (0,3), e3 = (0,5), e4 = (0,6),
e5 = (1,5), e6 = (2,5), e7 = (4,5),
and the deleted triangles as
t1 = (0,2,5), t2 = (0,2,6), t3 = (0,3,5), t4 = (0,3,6),
t5 = (0,4,5), t6 = (1,2,5), t7 = (1,4,5).
With the order orientation, the relative integral boundary is
B =


1 1 0 0 0 0 0
0 0 1 1 0 0 0
−1 0 −1 0 −1 0 0
0 −1 0 −1 0 0 0
0 0 0 0 0 −1 −1
1 0 0 0 0 1 0
0 0 0 0 1 0 1


, detB =−1. (11)
ThusB is an integral isomorphism and the relative integral homology vanishes in all degrees. Hence
the inclusion is an integral homology equivalence (and is a homology equivalence over every field).
The support graph has exactly three perfect matchings. As permutations assigning to rowei the
column tp(i), they are
(1,4,3,2,7,6,5),
(2,3,1,4,7,6,5),
(2,3,5,4,6,1,7),
10

e1 t1
e2 t2
e3 t3
e4 t4
e5 t5
e6 t6
e7 t7
deleted edges deleted triangles
Figure 2: Relative support graph of the seven-state two-bit example. Every deleted edge has degree
at least two, so no relative elementary collapse can start. The graph nevertheless has three perfect
matchings, listed in the text, whose signed determinant contributions sum to−1.
where the displayed indices are one-based. Their determinant contributions are, respectively,
−1,+1,−1, summing to−1. This is precisely the kind of cancellation among fitting orientations
already present in the general higher-dimensional rooted-forest framework [4]; the point here is that
two Boolean coordinates can realize it inside this order-thinning problem.
More directly, the seven deleted-edge degrees into deleted triangles are
(2,2,3,2,2,2,2).
No deleted edge is initially free. Since every vertex is retained and there are no simplices above
dimension two, a relative elementary collapse would have to start by pairing a deleted edge with its
unique incident deleted triangle. No such first move exists. ThereforeK̸↘L. Proposition 7.1 gives
the same conclusion from the existence of three perfect matchings.
It remains to check homotopy equivalence. Both endpoint posets beat-reduce to a point. One
valid reduction forP is
3↓0, 4↑5, 0↑2, 1↑2, 5↓2, 2↑6,
and forQ it is
0↑4, 2↓1, 4↓1, 1↑6, 5↓3, 3↑6.
Herex↓y means thatx is removed as a down-beat point with the indicated extremal lower neighbor,
and similarly for↑. Thus both order complexes are nonempty and contractible. Their inclusion is
therefore a homotopy equivalence.
The preceding theorem is a finite explicit proof. Vertex minimality is a separate, computer-assisted
statement.
Proposition 7.3 (computer-assisted vertex minimality). No height-two two-bit counterexample
of the type in Theorem 7.2 exists on at most six vertices. Consequently the seven-element example
is vertex-minimal, conditional only on the correctness of the exhaustive checker and its stated
enumeration model.
Exhaustive certificate.For eachn≤6, the checker enumerates every naturally labelled transitive
relation on{0,...,n−1}of height at most two and every one of the4n maps to{0,1}2. Every finite
11

poset admits a linear extension, so natural labellings cover all isomorphism types, with harmless
duplication. For each pair it constructs the coordinatewise thinned order, the deleted edges and
triangles, and the relative matrix overF2. Relative acyclicity requires a square full-rank matrix. For
each such neutral case, the program tests uniqueness of a perfect matching of the support graph and
uses Proposition 7.1: a neutral example fails direct collapse exactly when the perfect matching is
not unique. The search intentionally testsF2-neutrality rather than the stronger integral-homology
and endpoint-homotopy conditions in Theorem 7.2. This enlarges the candidate class: integral
relative acyclicity impliesF2-relative acyclicity, so any smaller counterexample of the theorem’s type
would necessarily be detected by this weaker filter. Therefore failure to find a noncollapsible case in
the larger F2-neutral class suffices for the stated lower bound; no separate homotopy test is needed
for exclusion.
A fresh independent rerun on 27 September 2026 produced
n posets two-bit profiles square cases F2-neutral max. matrix dim.
1 1 4 4 4 0
2 2 32 25 25 0
3 7 448 256 256 1
4 39 9,984 4,174 4,174 2
5 330 337,920 104,114 103,562 4
6 4,117 16,863,232 3,865,228 3,767,044 8
No neutral case throughn = 6 had more than one perfect matching. The independent bounded-check
script, its recorded output, and the fixed seven-state rerun are available in the website certificate
package; they are not embedded in this PDF. Section 10 records the distinction between this
exhaustive evidence and the analytic proof of Theorem 7.2.
Theorem 7.4(sharp two-bit failure with certified minimality). There exists a seven-element poset
P of height two and a mapα:P→{0,1}2 such that, for the coordinatewise thinned suborderQ,
the inclusion ∆(Q)↪→∆(P ) is an integral homology equivalence and a homotopy equivalence but
∆(P )̸↘∆(Q) by a relative elementary-collapse sequence. No such two-bit example exists on at
most six vertices.
The existence assertion is the explicit mathematical construction of Theorem 7.2. The vertex-
minimality sentence is computer-assisted and is exactly Proposition 7.3; it is not being presented as
a separate noncomputational proof.
Corollary 7.5(bit-count sharpness). At height two, one bit is the maximal universal regime in
which homology neutrality forces direct collapse. For every block sizer≥2, there are height-two
r-coordinate thinnings that are homology-neutral but do not collapse directly.
Proof. The one-bit assertion is Theorem 4.2, and the two-bit failure is Theorem 7.2. For anyr> 2,
append r−2 constant coordinates to the seven-state two-bit labeling. Coordinatewise comparability
is unchanged, so the thinned suborder and the same noncollapse certificate persist.
8 Sharpness II: greater height destroys one-bit rigidity
The height hypothesis is independently sharp. The following construction is elementary but strong
enough to show why no unrestricted one-bit analogue of Theorem 4.2 can hold.
12

Theorem 8.1(cone–whisker realization). LetR be any nonempty finite poset and choose a minimal
element z∈R. Adjoin a new greatest elementt to formP =R∪{t}. Define
b(z) =b(t) = 0, b (x) = 1 ( x∈R\{z}).
Then the one-bit thinningQ retains all comparisons ofR and precisely one new comparison involving
t, namelyz <t. Therefore
∆(P ) = cone(∆R), ∆(Q) = ∆(R)∪{z}[z,t], (12)
and ∆(Q) collapses onto ∆(R). In particular,
∆(Q)↪→∆(P ) is a homotopy equivalence ⇐⇒∆(R) is contractible, (13)
and fork≥1,
Hk(∆P,∆Q; Z)∼= ˜Hk−1(∆R; Z). (14)
Proof. Every comparison internal toR survives: it is either0→1 (when it starts atz) or 1→1,
apart from identities. Forx∈R\{z}, the new comparisonx < tis 1→0 and is deleted, while
z <t is 0→0 and survives. Sincet is greatest inP, ∆(P ) is a cone. In∆(Q) the edge [z,t] is a
whisker andt is a free vertex, so deleting it leaves∆(R). Equation (13) follows because the coarse
complex is contractible, and(14) follows from the long exact sequence of the pair together with
(12).
Corollary 8.2 (arbitrary refined homotopy type). Within a contractible coarse order complex,
one Boolean coordinate of unrestricted height can realize, up to a single collapsible whisker, the
order-complex homotopy type of any nonempty finite poset.
Corollary 8.3 (torsion in height three). There are one-bit height-three thinnings with relative
integral torsion. In particular, taking a height-two finite-poset model ofRP2 as R in Theorem 8.1
gives
H2(∆P,∆Q; Z)∼= Z/2.
A 13-point projective-plane finite model is standard prior art [7], so this yields a 14-state example.
More generally, choosingR with torsion in reduced homology transfers that torsion one degree
upward to the relative pair.
Remark 8.4. Theorem 8.1 also shows that integral homology neutrality need not imply homotopy
neutrality beyond height two: choose an acyclic but noncontractible finite complex and take its
face poset forR. This is exactly the separation that the rooted incidence structure rules out in
Theorem 4.2.
9 Positioning and the logical-observation interpretation
9.1 What is standard and what is specific here
The mathematical ingredients used in the proofs have substantial prior art. Finite-poset/order-
complex methods and finite-space realization are classical [16, 1, 2]. Elementary collapse and
acyclic matchings belong to standard simple-homotopy and discrete-Morse theory [12, 15]. Higher-
dimensional rooted forests, fitting orientations, determinant weights, and cancellation among several
13

fitting orientations are established in the work of Bernardi–Klivans and related higher-dimensional
tree theory [4, 11]. Mukherjee developed topological and collapse/homology criteria for rooted
forests, including triangulated closed manifolds [17, 18], and Contreras–Tawfeek characterized, for
rooted forests in arbitrary simplicial complexes, when the forest corresponds to a discrete gradient
in terms of simplicial collapse to its root [6]. Thus neither the generic rooted-forest language nor
the matching-to-collapse mechanism is a novelty claim of this paper. Total-unimodularity and
torsion questions for simplicial boundary matrices likewise have a broader established setting [10].
The Horn closure statements in Section 5 rely on classical closure properties rather than a new
classification of Horn logic [14, 19]. Finally, Björner–Goresky–MacPherson attach order complexes
to the true-state subposet of a Boolean function in their study of circuit complexity [5]. That
construction is topically close but mathematically different from the same-carrier relation thinning
studied here.
The narrower contribution claimed by this paper is the exact recognition theorem for the
particular Boolean order-thinning rule: one coordinate plus height at most two forces the defect into
an ordinary reduced graph-incidence matrix. Combining this forced incidence form with the standard
collapse machinery makes coefficient independence, rooted forests, perfect acyclic matchings of the
relative cells, and actual collapse equivalent for this thinning problem. The seven-element two-bit
example and the cone–whisker construction then identify clean limits of that recognition theorem.
We make no claim that the underlying graph, matching, or rooted-forest theories are new.
9.2 Propositional logical topology interpretation
In an observation-generated finite logical topology, one may pass to the Kolmogorov quotient
and regard the specialization structure as a finite poset of realized observation signatures. The
same-carrier thinning model applies literally when the new Boolean observationfactors through
the currentT0 quotient: equivalently, it is constant on every current observational-equivalence
class and therefore does not split a quotient point into several newly distinguishable states. Under
this hypothesis, the new observation retains a coarse comparison exactly when its truth value is
nondecreasing along that comparison. A single new observation is then precisely the thinning(1),
and a simultaneous block that factors through the current quotient is (2).
If a new observation separates worlds that were identified in the current quotient, the refinedT0
carrier itself gains points; that operation is not merely a same-carrier order thinning and is outside
the literal scope of the theorems proved here.
This statement should not be confused with McCord’s theorem. McCord’s canonical map from
the order-complex realization to a finiteT0 space is a weak homotopy equivalence [16]; it is not
an assertion that every such realization map is an ordinary homotopy equivalence. Our main
theorems are statements about the order complexes∆(Q)⊆∆(P ). Beat-point reductions are
used only where they explicitly contract the relevant finite posets/order complexes, and relative
homology computations are never presented as homotopy tests without an additional theorem such
as Theorem 4.2.
For the logical program, the operational message is correspondingly narrow. A single Boolean
observation on a height-two current signature poset admits an exact, integral, combinatorial safety
test and an explicit collapse certificate. Simultaneous observation blocks do not inherit that
equivalence automatically, and higher-height models require genuinely stronger hypotheses such as
the repair maps of Section 5.
14

10 Reproducibility and proof status
The manuscript is accompanied by areproducibility/ directory. The principal files are:
• verify_two_bit_height_two_counterexample.py, an exact checker for Theorem 7.2;
• two_bit_height2_exhaustive.cpp, the exhaustive checker used for Proposition 7.3, with
supplied and rerun outputs throughn = 6;
• retained one-bit verifiers for the height-two matrix criterion, repair-map sufficient conditions,
chain classification, and repair-forest equivalence;
• a reproducibility README and SHA-256 manifest.
There are two logically different kinds of claims. The one-bit incidence theorem, Theorem 4.2, the
explicit seven-element construction, and the cone–whisker theorem have mathematical proofs in the
text. The statement that seven vertices are minimal for the two-bit failure is computer-assisted: the
program exhausts the finite search space through six vertices, but the paper does not disguise that
enumeration as a noncomputational proof. For the exclusion step it is enough to enumerate the larger
class of F2-neutral cases: every integral-homology-neutral candidate of the target type isF2-neutral,
so a smaller target counterexample could not be filtered out by omitting an endpoint-homotopy
test. The exact seven-state verifier independently reconstructs the orders, the relative matrix, its
determinant andF2 rank, the matching count, the deleted-edge degrees, and the two beat reductions.
The retained one-bit checks are supplementary regression tests rather than foundations for the
proof. In the post-audit rerun, the repair-forest verifier checked all height-at-most-two naturally
labelled posets through six vertices (4,117 posets atn = 6, 263,488 one-bit cases there) and reported
all assertions passed. The independent height/homology and chain scripts likewise passed their
stated ranges. These finite checks help guard transcription and implementation errors but are not
substituted for the proofs in Sections 3–4.
11 Conclusion
A one-bit observation on a height-two finite poset has an exactly classifiable incidence defect. The
relative integral boundary is a reduced graph-incidence matrix, so relative homology is torsion-free
and determined by graph cycles and rootless components. In this regime, homology neutrality is
not merely necessary for topological neutrality: it forces a rooted forest and therefore an explicit
simplicial collapse.
Both hypotheses are sharp. Keeping height two but allowing two Boolean coordinates already
permits determinant cancellation among several fitting orientations; the seven-element example is
homology- and homotopy-neutral but admits no direct relative collapse, and exhaustive computation
certifies that six vertices do not suffice. Keeping one bit but dropping the height bound allows
arbitrary finite-poset homotopy types inside a contractible coarse cone and relative torsion in height
three. These two failures isolate the precise scope in which the one-bit forest theorem should be
used.
References
[1] J. A. Barmak, “On Quillen’s Theorem A for posets,”Journal of Combinatorial Theory, Series
A 118 (2011), 2445–2453.https://arxiv.org/abs/1005.0538.
15

[2] J. A. Barmak,Algebraic Topology of Finite Topological Spaces and Applications, Lecture Notes
in Mathematics 2032, Springer, 2011.
[3] J. A. Barmak and E. G. Minian, “Simple homotopy types and finite spaces,”Advances in
Mathematics 218 (2008), 87–104.
[4] O. Bernardi and C. J. Klivans, “Directed rooted forests in higher dimension,”Electronic Journal
of Combinatorics23(4) (2016), P4.35. DOI: 10.37236/5819.
[5] A. Björner, M. Goresky, and R. MacPherson, “Topological aspects of Boolean
functions,” Pure and Applied Mathematics Quarterly 20(3) (2024), 1029–1063. DOI:
10.4310/PAMQ.2024.v20.n3.a1.
[6] I. Contreras and A. R. Tawfeek, “On discrete gradient vector fields and Laplacians of simplicial
complexes,”Annals of Combinatorics28(1) (2024), 67–91. DOI: 10.1007/s00026-023-00655-1.
[7] N. Cianci and M. Ottina, “Poset splitting and minimality of finite models,”Journal of
Combinatorial Theory, Series A157 (2018), 120–161. DOI: 10.1016/j.jcta.2018.02.010.
[8] A. Claesson, S. Kitaev, K. Ragnarsson, and B. E. Tenner, “Boolean complexes for Ferrers
graphs,”Australasian Journal of Combinatorics48 (2010), 159–173.
[9] A. Dochtermann and A. Engström, “Algebraic properties of edge ideals via combinatorial
topology,”Electronic Journal of Combinatorics16(2) (2009), R2. DOI: 10.37236/68.
[10] T. K. Dey, A. N. Hirani, and B. Krishnamoorthy, “Optimal homologous cycles, total uni-
modularity, and linear programming,”SIAM Journal on Computing40(4) (2011), 1026–1044.
https://arxiv.org/abs/1001.0338.
[11] A. M. Duval, C. J. Klivans, and J. L. Martin, “Simplicial and cellular trees,” inRecent Trends
in Combinatorics, IMA Volumes in Mathematics and its Applications 159, Springer, 2016,
713–752.
[12] R. Forman, “Morse theory for cell complexes,”Advances in Mathematics134 (1998), 90–145.
DOI: 10.1006/aima.1997.1650.
[13] A. Hatcher,Algebraic Topology, Cambridge University Press, 2002.
[14] P. Jeavons, D. Cohen, and M. Gyssens, “Closure properties of constraints,”Journal of the
ACM 44(4) (1997), 527–548. DOI: 10.1145/263867.263489.
[15] D. Kozlov,Combinatorial Algebraic Topology, Algorithms and Computation in Mathematics
21, Springer, 2008.
[16] M. C. McCord, “Singular homology groups and homotopy groups of finite topological spaces,”
Duke Mathematical Journal33 (1966), 465–474. DOI: 10.1215/S0012-7094-66-03352-7.
[17] S. K. Mukherjee, “On the topology of rooted forests in higher dimensions,”Topology and its
Applications 247 (2018), 50–56. DOI: 10.1016/j.topol.2018.07.013.
[18] S.K.Mukherjee, “Ontherootedforestsintriangulatedclosedmanifolds,” Linear and Multilinear
Algebra 68(10) (2020), 2034–2043. DOI: 10.1080/03081087.2019.1570066.
[19] M. Wild, “The joy of implications, aka pure Horn formulas: Mainly a survey,”Theoretical
Computer Science658 (2017), 264–292.
16