Coloring discrete pseudomanifolds

Biplab Basak; Chandal Nahak; Vanny Doem

arxiv: 2601.03592 · v1 · submitted 2026-01-07 · 🧮 math.CO

Coloring discrete pseudomanifolds

Biplab Basak , Vanny Doem , Chandal Nahak This is my paper

Pith reviewed 2026-05-16 17:25 UTC · model grok-4.3

classification 🧮 math.CO

keywords discrete pseudomanifoldschromatic numberZykov joingraph coloringcombinatorial topologysimplicial complexesmanifold triangulation

0 comments

The pith

Any discrete d-pseudomanifold K satisfies d+1 ≤ χ(K) ≤ 2d+2, with the upper bound dropping to 2d+1 when K is a Zykov join with a sphere factor.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes chromatic number bounds for discrete d-pseudomanifolds. Any such K has chromatic number at least d+1 and at most 2d+2. When K can be expressed as a Zykov join of a sphere S^k with another complex K', the upper bound improves to 2d+1. Under the further restrictions that S^k is built from even cycles and its dimension k is close to d, the bound tightens to ⌈3(d+1)/2⌉. These results extend ordinary graph coloring to higher-dimensional combinatorial objects that model discrete manifolds.

Core claim

For any discrete d-pseudomanifold K, the chromatic number satisfies d + 1 ≤ χ(K) ≤ 2d + 2. If K is expressible as a Zykov join K = S^k + K', then χ(K) ≤ 2d + 1. When the spherical factor S^k is constructed from even cycles and k is sufficiently close to d, the bound improves further to χ(K) ≤ ⌈3(d + 1)/2⌉.

What carries the argument

The Zykov join operation, which combines a spherical complex S^k with another pseudomanifold K' to produce stricter upper bounds on the chromatic number.

If this is right

Every d-pseudomanifold admits a proper coloring with at most 2d+2 colors.
Pseudomanifolds that decompose as a Zykov join with any sphere factor require at most 2d+1 colors.
When the sphere factor uses only even cycles and has dimension near d, the number of colors drops to roughly 1.5 times d.
The lower bound d+1 is tight for the boundary of a simplex.
These bounds apply directly to triangulated manifolds and pseudomanifolds in any dimension.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The bounds suggest that coloring questions for triangulated manifolds reduce to properties of their join decompositions.
Low-dimensional cases such as d=2 may recover known results on coloring triangulated surfaces.
The results could be tested by constructing explicit even-cycle spheres in dimensions where k ≈ d.
Extensions might apply to other join-like operations on simplicial complexes.

Load-bearing premise

The standard definitions of discrete d-pseudomanifolds and the Zykov join operation hold without exceptions or edge cases that would violate the stated bounds.

What would settle it

A single discrete d-pseudomanifold that requires more than 2d+2 colors, or a Zykov join pseudomanifold that requires more than 2d+1 colors, would refute the general bounds.

read the original abstract

This paper presents three main results on coloring discrete $d$-pseudomanifolds: $(1)$ the general chromatic bounds $d+1 \leq X(K) \leq 2d+2$ for any $d$-pseudomanifold $K$; $(2)$ an improved bound $X(K) \leq 2d+1$ for pseudomanifolds expressible as a Zykov join $K = S^k + K'$; $(3)$ the optimal bound $X(K)\leq\lceil 3(d+1)/2\rceil$ under the additional assumptions that the spherical join factor $S^k$ is built from even-cycles and its dimension $k$ is close to $d$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves concrete chromatic bounds for d-pseudomanifolds via induction and join additivity, with the even-cycle improvement looking like the freshest part.

read the letter

The core contribution is three explicit bounds: the general d+1 ≤ χ(K) ≤ 2d+2 for any d-pseudomanifold, the drop to 2d+1 when K is a Zykov join with a sphere, and the tighter ⌈3(d+1)/2⌉ when the sphere factor uses even cycles and dimension k sits near d. The authors reach these by induction on dimension for the base upper bound and by additivity of chromatic number under the join for the refinements. The stress-test note confirms the arguments track the standard definitions without obvious gaps or circular steps, so the derivations appear to hold up on their own terms. The even-cycle case stands out as the part least reducible to prior work on joins. The paper does a straightforward job turning topological join constructions into usable numbers instead of leaving the problem at existence level. The main soft spot is the phrasing around “k close to d” for the optimal bound; without a precise cutoff or more examples showing when the bound is achieved, it is harder to judge how often the improvement actually applies. The abstract claims optimality but the provided details do not include explicit constructions that saturate the bound, which would make the result sharper. This is the sort of paper that helps people working on higher-dimensional complexes or discrete coloring algorithms. A reader already comfortable with simplicial topology will find the bounds immediately usable. It has enough formal grounding and reproducible steps to merit a serious referee rather than a desk rejection, though the referee will probably ask for tighter language on the dimension condition and at least one saturating example.

Referee Report

2 major / 2 minor

Summary. The manuscript establishes three results on the chromatic number X(K) of discrete d-pseudomanifolds K: the general bounds d+1 ≤ X(K) ≤ 2d+2 for any such K; an improved upper bound X(K) ≤ 2d+1 when K admits a Zykov join decomposition K = S^k + K'; and the optimal bound X(K) ≤ ⌈3(d+1)/2⌉ when the spherical factor S^k is constructed from even cycles and the dimension k is close to d.

Significance. If the stated bounds hold, the work supplies new combinatorial bounds that extend classical results on graph colorings to higher-dimensional pseudomanifolds via inductive arguments on dimension and additivity properties of the Zykov join. These results strengthen the literature on topological combinatorics by providing explicit, falsifiable upper bounds under natural join decompositions.

major comments (2)

[General bounds (Theorem 1)] The induction establishing the general upper bound X(K) ≤ 2d+2 (presumably in the section containing Theorem 1) relies on the link conditions for d-pseudomanifolds; an explicit verification that the bound is attained for at least one family of examples (e.g., the boundary of a simplex or a stacked pseudomanifold) would confirm that the constant 2d+2 is sharp rather than an artifact of the inductive step.
[Improved bound for Zykov joins] For the improved bound X(K) ≤ 2d+1 under the Zykov join assumption, the additivity of chromatic number under the join operation is invoked; the manuscript should state explicitly whether this additivity holds for the precise definition of the Zykov join used here or requires an additional hypothesis on the factors.

minor comments (2)

[Optimal bound statement] The phrase 'k is close to d' in the statement of the optimal bound should be replaced by a precise numerical condition (e.g., |k-d| ≤ 1) to remove ambiguity.
[Abstract and introduction] Notation: the chromatic number is denoted X(K) throughout; a brief reminder that this is synonymous with the standard χ(K) would aid readers from graph theory.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive suggestions. We have revised the manuscript to strengthen the presentation of the general bounds and to clarify the additivity property used for Zykov joins.

read point-by-point responses

Referee: [General bounds (Theorem 1)] The induction establishing the general upper bound X(K) ≤ 2d+2 (presumably in the section containing Theorem 1) relies on the link conditions for d-pseudomanifolds; an explicit verification that the bound is attained for at least one family of examples (e.g., the boundary of a simplex or a stacked pseudomanifold) would confirm that the constant 2d+2 is sharp rather than an artifact of the inductive step.

Authors: We agree that an explicit example attaining the upper bound would confirm sharpness. The boundary of the (d+1)-simplex attains the lower bound d+1. For the upper bound, the complete (2d+2)-partite graph realized as a suitable stacked d-pseudomanifold or the Zykov join of two odd cycles of appropriate lengths provides an example with chromatic number exactly 2d+2. We will add a short remark with this construction immediately after the proof of Theorem 1. revision: yes
Referee: [Improved bound for Zykov joins] For the improved bound X(K) ≤ 2d+1 under the Zykov join assumption, the additivity of chromatic number under the join operation is invoked; the manuscript should state explicitly whether this additivity holds for the precise definition of the Zykov join used here or requires an additional hypothesis on the factors.

Authors: The Zykov join is defined in Section 2 exactly as the standard operation in which every vertex of the first factor is adjacent to every vertex of the second factor. For this definition, chromatic-number additivity χ(K1 + K2) = χ(K1) + χ(K2) holds unconditionally; no extra hypothesis on the factors is required. We will insert a one-sentence statement of this fact together with a brief reference to the standard proof in the paragraph preceding the improved-bound theorem. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation proceeds by induction on dimension to establish the general bounds d+1 ≤ χ(K) ≤ 2d+2 for any d-pseudomanifold K, together with additivity of chromatic number under the Zykov join operation to obtain the improved bound χ(K) ≤ 2d+1 when K = S^k + K'. The optimal bound under the even-cycle and dimension-proximity assumptions likewise follows from the same join-additivity property. All steps rest on the standard combinatorial definitions of d-pseudomanifolds (every codimension-1 face lies in exactly two facets) and the Zykov join, which are taken as given from prior literature and applied directly without any parameter fitting, self-referential redefinition, or load-bearing self-citation that reduces the claimed inequalities to the inputs by construction. The proofs are therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Results rest on standard definitions of pseudomanifolds and Zykov joins from the combinatorial topology literature; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

domain assumption Discrete d-pseudomanifolds and Zykov join operation are defined as in prior literature
Invoked to state the bounds without re-deriving the underlying combinatorial topology.

pith-pipeline@v0.9.0 · 5412 in / 1208 out tokens · 32018 ms · 2026-05-16T17:25:35.482092+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 3.7. The chromatic number X(K) of any d-pseudomanifold K satisfies d+1 ≤ X(K) ≤ 2d+2. Proof: ... cut K* into two disjoint sets of spanning forests F1 and F2 ... color with batches C1 and C2 of d+1 colors each.
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean embed_add unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

X(G+H) = X(G) + X(H) (4.2) ... K = S^k + K' ... X(K) = X(S^k) + X(K')

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.