24.5. Summary of Key Concepts

So, imagine you are given an arbitrary poset less than equal to relationship. This is not again a numerical less than equal to, this is an arbitrary relation, R, which is reflexive, anti symmetric and transitive. Then if I take a pair of elements x,y then the element y is called the cover of element x if the following two conditions hold. The element x should be related to the element y and of course x ≠ y, that is why the less than symbol. And there should not exist any intermediate element ∃z,x ≤ z ≤ y.

In a partially ordered set (poset), an element ‘y’ is considered a cover of another element ‘x’ if two specific conditions are met: First, there must be a direct relationship such that 'x is less than or equal to y' (this is represented in relation R). Second, there can be no element that is between ‘x’ and ‘y’. This means that you cannot find any other element 'z' such that 'x is related to z' and 'z is related to y'. This relationship is visually represented in a Hasse diagram where if you can go from ‘x’ to ‘y’ without encountering any intervening elements, then ‘y’ covers ‘x’.

Consider a hierarchy in a company. If 'Manager' is at a higher level than 'Employee', and there are no other roles in between like 'Team Lead' or 'Supervisor', we can say 'Manager' covers 'Employee'. However, if there is 'Team Lead' between 'Manager' and 'Employee', then 'Manager' does not cover 'Employee'.

Let us next define what we call as the maximal and minimal element in a poset. An element a is called as the maximal element if it is on the top most layer informally, or if it has no cover. More formally, a maximal element P is such that ∃Q ∈ S, Q < P, there is no element B on top of A. Similarly, an element is called a minimal element if it occurs at the lower level of your Hasse diagram or has no element that it covers.

In the context of a poset, a maximal element is one that does not have any other element above it; it cannot be covered by any other element. This means that you can't find an element that is related to it (higher in the hierarchy) that is not itself. Conversely, a minimal element is positioned at the lowest level in the Hasse diagram, having no elements that it covers—that is, there are no elements below it in the order. If you visualize this in a Hasse diagram, the maximal elements are at the top, and the minimal elements are at the bottom.

Think of a stack of blocks where the highest blocks represent maximal elements (nothing can be placed on top of them), and the lowest block in the stack represents a minimal element (no blocks stacked underneath it). An example can be seen in a family tree: the oldest generation is the maximals because no one else is older, while the youngest child can be seen as the minimal since they don't have younger siblings.

Now finally let us define what we call as the greatest element and the least element of a poset. If you have an element a of the set S, a is called the greatest element if every element b is related to the element a as per the relation R. The element a is called the least element if it is related to every other element b.

In a poset, a greatest element is one to which every other element in the set is related; that means they are all lesser than or equal to this element. In contrast, a least element is related to every element in the poset in such a way that it is always lesser than or equal to those elements. In mathematical terms, if we say element 'a' is the greatest, then for all other elements 'b' in the poset, 'b ≤ a' holds true. For least elements, 'a ≤ b' holds true for every element 'b'.

Imagine a leaderboard in a competition: the greatest element here is the winner, as they have beaten or have a better score than everyone else. The least element could be represented by a participant who has not won any points or prizes; they are at the bottom rank since they have not surpassed any other participant.

Using all the concepts that we have discussed in, now we will now do a very interesting exercise here, which we call as topological sorting.

Topological sorting is a method used to order elements of a poset based on their dependencies. When tasks or elements are given with relations that dictate certain prerequisites, topological sorting arranges them into a sequence where each task or element appears before all its dependent tasks in the ordering. The result is a linear ordering of the tasks that respects their dependencies. This method applies to directed acyclic graphs (DAGs) and helps in scheduling tasks with given prerequisites effectively.

Consider a cooking recipe where certain steps must be achieved before others, e.g., preparation of ingredients must come before cooking, which must then come before plating. Topological sorting will help you determine the order to follow to complete the recipe efficiently, ensuring you do not start cooking before preparing the ingredients.

--