Decidability of well quasi-order and atomicity for equivalence relations under embedding orderings

January 26, 2023 ยท The Ethereal ยท ๐Ÿ› Order

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"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 shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Combinatorics

๐Ÿ”ฎ ๐Ÿ”ฎ The Ethereal

Tables of subspace codes

Daniel Heinlein, Michael Kiermaier, ... (+2 more)

math.CO ๐Ÿ› arXiv ๐Ÿ“š 94 cites 10 years ago