Thiagarajan Grid-Free Decidability Conjecture

Definitions and mathematical statement

Let $\mathcal T$ denote the class called trace-regular event structures in the supplied record. For $E\in\mathcal T$, write $\operatorname{MSO}_{\mathrm{src}}(E)$ for the monadic second-order theory intended by that source, and let $\operatorname{Grid}_{\mathrm{src}}(E)$ mean that $E$ contains a grid event structure in the source's sense. Thus grid-free means $\neg\operatorname{Grid}_{\mathrm{src}}(E)$. A theory is decidable if an algorithm determines, for every sentence in its specified language, whether that sentence belongs to the theory. The supplied record does not specify that language, its relational structure, the range of its set quantifiers, the definition of trace regularity, or the precise grid-containment relation. These source-dependent notions must be recovered before the formulas below constitute a fully specified mathematical problem.

The proposed equivalence is \[ \forall E\in\mathcal T,\qquad \operatorname{MSO}_{\mathrm{src}}(E)\text{ is decidable} \quad\Longleftrightarrow\quad \neg\operatorname{Grid}_{\mathrm{src}}(E). \] The original passage reports that containing a grid implies undecidability, and also reports a counterexample to the converse implication. Consequently, the unrestricted equivalence is presented here as a conjecture reported to be false, rather than as an unresolved assertion.

More precisely, the passage reports the existence of a nonpositively curved square complex $Z$ with one vertex, four edges, and three squares. It states that $Z$ is virtually special and that every principal filter of its universal cover is the domain of a trace-regular event structure $E_Z$. For a partially ordered set $(P,\leq)$ and $v\in P$, a principal filter is \[ \mathord{\uparrow}v=\{x\in P:v\leq x\}. \] The ordering or directed structure needed to interpret this definition on the universal cover is not supplied. The passage further states that the graph of $E_Z$ has infinite treewidth and bounded hyperbolicity, using the former to conclude undecidability of $\operatorname{MSO}_{\mathrm{src}}(E_Z)$ and the latter to conclude grid-freeness. These are claims of the supplied passage; its graph convention and the hypotheses supporting these implications are not specified here.

The remaining characterization request can therefore be written as follows: identify mathematically specified subclasses $\mathcal C\subseteq\mathcal T$ for which \[ \forall E\in\mathcal C,\qquad \neg\operatorname{Grid}_{\mathrm{src}}(E) \ \Longrightarrow\ \operatorname{MSO}_{\mathrm{src}}(E)\text{ is decidable}. \] Within any such subclass, the source-reported grid obstruction would give the proposed equivalence. The record particularly requests consideration of domains arising as principal filters of universal covers of finite special cube complexes. It does not specify additional restrictions on this family or a criterion by which its subclasses are to be characterized.

There is a material qualification concerning this requested family. Before discussing MSO decidability, the original passage says that "Thiagarajan's conjecture" was proved for event structures with domains arising as principal filters of universal covers of finite special cube complexes, referring to [1]. It then separately introduces the MSO conjecture and its counterexample, referring to [2]. The record does not state the earlier conjecture or identify these numbered references unambiguously. Its dated assessment treats that earlier result as a positive partial result, but this does not establish that it is a positive result for the MSO implication displayed above. No such identification is made in this draft.

Short English statement

The source reports that grids obstruct MSO decidability and that a grid-free trace-regular event structure with undecidable MSO theory exists. The remaining request is to characterize subclasses where grid-freeness does imply decidability. The intended MSO language, grid notion, and relationship to the earlier theorem about special cube complexes require clarification.

Sources

• Local registry: data/unsolvedmath/problems.json, supplied permanent UnsolvedMath ID $30006604$, title "Thiagarajan Grid-Free Decidability Conjecture," exact source problem code catalogue entry. The supplied record labels the status partially_solved and the statement corrected_verified; these are registry labels, not independent mathematical verification.
• Supplied report citation: Median Geometry and Applications (2026), Oberwolfach Reports, DOI 10.4171/owr/2026/8, pp. 487--540. Source URL and literature-source link: https://doi.org/10.4171/owr/2026/8. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature-source attribution: Chalopin--Chepoi, "counterexample to Thiagarajan's conjecture," https://arxiv.org/abs/1605.08288. This supplied label does not by itself identify the conjecture with the MSO conjecture.
• Supplied literature-source attribution: Chalopin--Chepoi, "1-Safe Petri nets and special cube complexes," https://arxiv.org/abs/1810.03395.
• The original passage attributes the definition of the relevant MSO theory for an event-structure unfolding $E_N$ of a net system $N$, and the grid obstruction, to Thiagarajan and Yang (2014). No complete bibliographic citation for that work is supplied. The passage's references [1] and [2] are not explicitly mapped to the supplied literature links, and its first-person authorship is not identified.
• Literature assessment checked at 2026-08-22: the supplied curation labels the problem partially solved, describes a positive theorem for principal filters of universal covers of finite special cube complexes, and says the unrestricted Thiagarajan conjecture is false. This is supplied dated curation, not independently verified. The background expressly requests independent verification of time-sensitive status and cited claims.