connected poset


Let P be a poset. Write ab if either ab or ba. In other words, ab if a and b are comparablePlanetmathPlanetmath. A poset P is said to be connectedPlanetmathPlanetmathPlanetmath if for every pair a,bP, there is a finite sequencePlanetmathPlanetmath a=c1,c2,,cn=b, with each ciP, such that cici+1 for each i=1,2,,n-1.

For example, a poset with the property that any two elements are either bounded from above or bounded from below is a connected poset. In particular, every semilattice is connected. A fence is always connected. If P has more than one element and contains an element that is both maximal and minimalPlanetmathPlanetmath, then it is not connected. A connected componentMathworldPlanetmathPlanetmath in a poset P is a maximal connected subposet. In the last example, the maximal-minimal point is a component in P. Any poset can be written as a disjoint unionMathworldPlanetmath of its components.

It is true that a poset is connected if its corresponding Hasse diagramMathworldPlanetmath is a connected graph. However, the converseMathworldPlanetmath is not true. Before we see an example of this, let us recall how to construct a Hasse diagram from a poset P. The diagram so constructed is going to be an undirected graph (since this is all we need in our discussion). Draw an edge between a,bP if either a covers b or b covers a. Let us denote this relationMathworldPlanetmathPlanetmath between a and b by ab. Let E be the collectionMathworldPlanetmath of all these edges. Then G=(P,E) is a graph where elements of P serve as vertices and E as the constructed edges. From this construction, one sees that a finite path exists between a,bV(G)=P if there is a finite sequence a=d0,d1,,dm=b, with each diV(G), such that didi+1 for i=1,,m-1. In other words, a and b can be “joined” by a finite number of edges, such that a is a vertex on the first edge and b is the vertex on the last edge.

As promised, here is an example of a connected poset whose underlying Hasse diagram is not connected. take the real line with adjoined to the right (meaning every element r is less than or equal to ). Then the resulting poset is connected, but its underlying Hasse diagram is not, since no element in can be joined to by a finite path.

Title connected poset
Canonical name ConnectedPoset
Date of creation 2013-03-22 17:08:31
Last modified on 2013-03-22 17:08:31
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 6
Author CWoo (3771)
Entry type Definition
Classification msc 06A07
Related topic ConnectedGraph
Defines connected
Defines connected component