๐ฎ
๐ฎ
The Ethereal
Decidability of well quasi-order and atomicity for equivalence relations under embedding orderings
January 26, 2023 ยท The Ethereal ยท ๐ Order
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
V. Ironmonger, N. Ruskuc
arXiv ID
2301.11048
Category
math.CO: Combinatorics
Cross-listed
cs.IT
Citations
2
Venue
Order
Last Checked
3 months ago
Abstract
We consider the posets of equivalence relations on finite sets under the standard embedding ordering and under the consecutive embedding ordering. In the latter case, the relations are also assumed to have an underlying linear order, which governs consecutive embeddings. For each poset we ask the well quasi-order and atomicity decidability questions: Given finitely many equivalence relations $ฯ_1,\dots,ฯ_k$, is the downward closed set Av$(ฯ_1,\dots,ฯ_k)$ consisting of all equivalence relations which do not contain any of $ฯ_1,\dots,ฯ_k$: (a) well-quasi-ordered, meaning that it contains no infinite antichains? and (b) atomic, meaning that it is not a union of two proper downward closed subsets, or, equivalently, that it satisfies the joint embedding property?
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Combinatorics
๐ฎ
๐ฎ
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
๐ฎ
๐ฎ
The Ethereal
Generalized Twisted Gabidulin Codes
๐ฎ
๐ฎ
The Ethereal
Tables of subspace codes
๐ฎ
๐ฎ
The Ethereal
Classification of weighted networks through mesoscale homological features
๐ฎ
๐ฎ
The Ethereal