Timeline for Reference request: Representing posets by integer divisibility
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 25, 2019 at 13:30 | comment | added | Richard Stanley | The least integer $r$ for which a finite poset $P$ is a subposet of the poset $D_n$ of divisors of some integer $n$ with $r$ distinct prime factors is the (order) dimension of $P$. This concept goes back to Dushnik and Miller (1941). Dimension is usually defined in terms of subposets of $\mathbb{Z}^r$, which is clearly equivalent to the definition in terms of $D_n$. | |
| Apr 25, 2019 at 5:40 | comment | added | David Eppstein | I agree that it's trivial. I did say "very easy" in my question. But I would still like a reference. | |
| Apr 25, 2019 at 2:08 | comment | added | Richard Stanley | It is trivial that every finite poset (indeed, every poset) $P$ can be represented by a collection of sets with the subset relation. (Let $x\in P$ correspond to $\{y\in P\,|\,y\leq x\}$.) The divisors of a squarefree integer with $r$ prime factors is isomorphic to the lattice of subsets of an $r$-element set. Thus I don't see the point of representing posets by integer divisibility. | |
| Apr 25, 2019 at 1:33 | comment | added | Todd Trimble | Feynman on trivial theorems: e-reading.club/chapter.php/71262/21/… | |
| Apr 25, 2019 at 1:20 | comment | added | Sam Hopkins | This seems like such a trivial fact that I'm not sure it would be stated anywhere. | |
| Apr 24, 2019 at 23:36 | history | asked | David Eppstein | CC BY-SA 4.0 |