|
|
|
|
connected poset
|
(Definition)
|
|
|
Let be a poset. Write if either or . In other words, if and are comparable. A poset is said to be connected if for every pair , there is a finite sequence
, with each , such that
for each
.
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 has more than one element and contains an element that is both maximal and minimal, then it is not connected. A connected component in a poset is a maximal connected subposet. In the last example, the maximal-minimal point is a component in . Any poset can be written as a disjoint union of its components.
It is true that a poset is connected if its corresponding Hasse diagram is a connected graph. However, the converse is not true. Before we see an example of this, let us recall how to construct a Hasse diagram from a poset . The diagram so constructed is going to be an undirected graph (since this is all we need in our discussion). Draw an edge between if either covers or covers . Let us denote this relation between and by
. Let be the collection of all these edges. Then is a graph where elements of serve as vertices and as the constructed edges. From this construction, one sees that a finite path exists between
if there is a finite sequence
, with each
, such that
for
. In other words, and can be “joined” by a finite number of edges, such that is a vertex on the first edge and 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
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.
|
"connected poset" is owned by CWoo. [ full author list (2) ]
|
|
(view preamble)
Cross-references: right, line, real, vertex, path, finite, vertices, collection, relation, covers, edge, graph, converse, Hasse diagram, disjoint union, point, minimal, contains, fence, semilattice, bounded from below, bounded from above, property, finite sequence, comparable, poset
There are 31 references to this entry.
This is version 3 of connected poset, born on 2007-05-23, modified 2007-05-23.
Object id is 9449, canonical name is ConnectedPoset.
Accessed 823 times total.
Classification:
| AMS MSC: | 06A07 (Order, lattices, ordered algebraic structures :: Ordered sets :: Combinatorics of partially ordered sets) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|