Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Measuring the non-totalness of an order

Nathaniel Virgo (Aug 03 2024 at 04:50):

I'd like some way to "measure" the extent to which a partially ordered set departs from being a totally ordered set.

In my case the partial orders are always lattices, and I'm fine with either making use of that or just treating them as preorders.

"Measure" here can be interpreted liberally - it could be numerical, but it could also be something that lets us say one preorder is "more total" than another (given that they might not have the same set of objects), or it could be something that gives us a set of "obstructions" to a partial order being total.

I know that's kind of vague, but I'm wondering if anyone has anything they think might help?

Nathaniel Virgo (Aug 03 2024 at 04:55):

The reason I'm asking is that I'm interested in measuring the "complicatedness" of a relation between two sets. Formal concept analysis is a way to take a relation and turn it into a lattice, and I have an intuition that the kind of "complicatedness" I'm interested in has to do with how this lattice departs from being a total order. I guess I'm also interested in other notions of "complicatedness of a relation" if anyone has one to hand.

Chris Grossack (they/them) (Aug 03 2024 at 05:23):

One idea is to count how many total orders refine the partial orders you started with. In case you started with something already a total order, there's only one total refinement (the one you started with) and in case you start with something "totally unordered" (where nothing is above or below anything else) then there's $n!$ many total refinements (since they can be ordered however you like)

Chris Grossack (they/them) (Aug 03 2024 at 05:25):

Other posets on $n$ elements will have some number of refinements between $1$ and $n!$, and this number will give some measure of how far from totally ordered it is... I'm not sure if it's a good measure, though, this is just the first thing I came up with. I guess it's possible there could be a "rigid" partial order without many total order refinements, but which is still qualitatively quite far from being total? But I can't quickly think of one

Chris Grossack (they/them) (Aug 03 2024 at 05:27):

Anyways, the total orders extending a partial order are called the linear extensions, and they're very well studied by combinatorialists, so there might be literature related to what you want

Chris Grossack (they/them) (Aug 03 2024 at 05:30):

You could also count the largest antichain. This is another measure of how "wide" the poset is, and thus of how far it is from being a total order. This is also very well studied by combinatorialists

Joshua Meyers (Aug 03 2024 at 05:33):

Another possible measure of this, for a partial order $P$, is the length of the smallest chain $P=P_0\subset P_1\subset P_2\subset\cdots P_n$ where $P_n$ is a total order, all inclusions are proper, all $P_i$ have the same elements, and there is no $i$ and $Q$ with proper inclusions $P_i\subset Q \subseteq P_{i+1}$.

Joshua Meyers (Aug 03 2024 at 05:35):

A quick way of saying this whole thing is "the length of the smallest maximal chain in the poset of refinements of $P$"

David Egolf (Aug 03 2024 at 05:37):

Is there any adjunction between the category of total orders and the category of partial orders? My hope is that, if there is such an adjunction, it would allow us to associate to a given partial order some corresponding "canonical" total order. Then one could try to measure how different the starting partial order is from the total order it induces via the adjunction.

Joshua Meyers (Aug 03 2024 at 06:02):

I can say that the forgetful functor from total orders to partial orders does not have a left or a right adjoint. This can be seen by checking the universal properties that a left or right adjoint would have to satisfy, and then finding posets which serve as counterexamples.

So such an adjunction could not involve the forgetful functor.

Oscar Cunningham (Aug 03 2024 at 06:33):

Chris Grossack (they/them) said:

One idea is to count how many total orders refine the partial orders you started with. In case you started with something already a total order, there's only one total refinement (the one you started with) and in case you start with something "totally unordered" (where nothing is above or below anything else) then there's $n!$ many total refinements (since they can be ordered however you like)

If you define the function as the number of refinements divided by $n!$, then it respects the coproduct nicely: $f(P+Q)=f(P)f(Q)$.

Rémy Tuyéras (Aug 03 2024 at 06:51):

What about simplicial homology?

Take a preorder $P$ and define $C_n(P) = \mathbb{Z}[\{[x_0,x_1,\dots,x_n]~|~x_0\leq x_1 \leq \dots \leq x_n\}]$

You have a chain complex $\partial_n:C_n(P) \to C_{n-1}(P)$ given by the singular homology derivative, namely:

$\partial_n [x_0,x_1,\dots,x_n] = \sum_{k=0}^n (-1)^k [x_0,x_1,x_{k-1},x_{k+1},\dots,x_n]$

If we take $Q = \{0 \leq 1\leq 2\textrm{ and }0 \leq 1' \leq 2\}$ (the commutative square), then we have:

• $C_2(P) = \mathbb{Z}[(0,1,2), (0,1',2), \dots]$
• $C_3(P) = \mathbb{Z}[(0,1,2,2),(0,0,1,2),\dots]$
• and without formally checking it, we would probably get something like this:
  $H_2(P) = H_2(\{0 \leq 1\leq 2\}) \oplus_{H_2(\{0 \leq 2\})} H_2(\{0 \leq 1'\leq 2\})$.

Clémence Chanavat (Aug 03 2024 at 09:54):

Rémy Tuyéras said:

What about simplicial homology?

Take a preorder $P$ and define $C_n(P) = \mathbb{Z}[\{[x_0,x_1,\dots,x_n]~|~x_0\leq x_1 \leq \dots \leq x_n\}]$

You have a chain complex $\partial_n:C_n(P) \to C_{n-1}(P)$ given by the singular homology derivative, namely:

$\partial_n [x_0,x_1,\dots,x_n] = \sum_{k=0}^n (-1)^k [x_0,x_1,x_{k-1},x_{k+1},\dots,x_n]$

If we take $Q = \{0 \leq 1\leq 2\textrm{ and }0 \leq 1' \leq 2\}$ (the commutative square), then we have:

• $C_2(P) = \mathbb{Z}[(0,1,2), (0,1',2), \dots]$
• $C_3(P) = \mathbb{Z}[(0,1,2,2),(0,0,1,2),\dots]$
• and without formally checking it, we would probably get something like this:
  $H_2(P) = H_2(\{0 \leq 1\leq 2\}) \oplus_{H_2(\{0 \leq 2\})} H_2(\{0 \leq 1'\leq 2\})$.

It seems that you are describing the poset homology, which measures the "topological holes" in the realisation of the nerve of the poset. If I'm not mistaken, the simplicial complex of your example is a disc, whose homology is 0, so it doesn't really measure how far the poset is from being a total order?

If the poset is finite, I would suggest instead taking the graph homology of the covering (=Hasse) diagram. If $x$ and $y$ are not comparable, then (since we are in a lattice) there is always a cycle in the covering diagram $x \wedge y \to \ldots \to x \to \ldots \to x \vee y \to \ldots \to y \to \ldots \to x \wedge y$, which give a generator of the $H^1$

Graham Manuell (Aug 03 2024 at 10:35):

I think the order dimension should also work for this purpose.

Todd Trimble (Aug 03 2024 at 14:38):

It seems that you are describing the poset homology, which measures the "topological holes" in the realisation of the nerve of the poset. If I'm not mistaken, the simplicial complex of your example is a disc, whose homology is 0, so it doesn't really measure how far the poset is from being a total order?

When people talk about the homology of a lattice, they typically remove the top and bottom elements and then take the nerve of that poset.

Rémy Tuyéras (Aug 03 2024 at 19:02):

Clémence Chanavat said:

It seems that you are describing the poset homology, which measures the "topological holes" in the realisation of the nerve of the poset. If I'm not mistaken, the simplicial complex of your example is a disc, whose homology is 0, so it doesn't really measure how far the poset is from being a total order?

When I created my example, I mostly focused on $H_0$ (which is the quotient of a free group over an image). Further tinkering with the example, particularly in trying to intuitively detect the "obstructions," led me to $H_2$. However, I forgot that it was a kernel over an image.

As you mentioned, @Clémence Chanavat, the original intuition was to use the underlying graph, ignoring what could be seen as the faces between the paths. Overall, $C_n(P)$ aims to count the linear suborders in the preorder $P$, but the homotopy relation should be factorizations of squares:

The path $x \leq y \leq z$ is equivalent to the path $x \leq y' \leq z$ if we have relations $y \leq y'$ or $y' \leq y$.

This appears to be related to @Todd Trimble's comment about forgetting the top and bottom elements and focusing only on the path between $y$ and $y'$.

It also seems connected to the use of linear extensions suggested by @Chris Grossack (they/them). If we have a non-linear partial order with $x \leq y \leq z$ and $x \leq y' \leq z$, then making it into a linear extension would mean imposing $y \leq y'$ or $y' \leq y$.

Initially, I considered using a homological measure to quotient $[x,y,z]$ and $[x,y',z]$ with paths $[x,y,y',z]$ or $[x,y',y,z]$ if they existed. However, this seems more homotopy-like than homology-like.

If such a homotopy existed, I wonder whether linear extensions serve as a sort of (co)fibrant replacement construction of some sort and whether the order dimension suggested by @Graham Manuell indicates the "order" at which this (co)fibrant replacement construction converges (whatever that might mean).

Rémy Tuyéras (Aug 03 2024 at 19:17):

The homotopy relation should probably be something like this: take $X \to P$ and $Y \to P$ to be two sublinear orders in $P$. We define a homotopy between $X$ and $Y$ as a factorization of the morphism $X+Y \to P$ into

$X+Y \to I(X,Y) \to P$

where $I(X,Y) \to P$ defines a linear extension of $X+Y$ in $P$.

Rémy Tuyéras (Aug 03 2024 at 19:39):

Transitiveness for this homotopy relation may require that we impose a "direction" to the extension encoded by $I(X,Y)$

Rémy Tuyéras (Aug 03 2024 at 19:44):

and the generating cofibrations would copy the topological intuition by considering morphisms as follows (turning partial orders to linear ones)

$\underbrace{\{0 \leq 1 \leq 2, 0 \leq 1' \leq 2\}}_{\mathbb{S}^1} \to \underbrace{\{0 \leq 1 \leq 2, 0 \leq 1' \leq 2,1\leq 1'\}}_{\mathbb{D}^2}$