Connectivity

From Polytope Wiki
(Redirected from Connected graph)
Jump to navigation Jump to search
A regular compound of two triangles
A regular octagram
The hexagram is not connected but the octagram is.

Connectivity or connectedness is a property of polytope like object with several closely related formulations.

Abstract Polytopes[edit | edit source]

The hexagram is not connected since proper elements on the left of the dotted line are incomparable to proper elements on the right of the dotted line.

Abstract polytopes are typically required to be strongly connected. This condition may be relaxed to allow for compounds, but it also allows for additional shapes that are not compounds, such as polyhedra with compound faces.

Connectivity[edit | edit source]

A bounded poset is said to be connected if it is rank 1 or if for any two proper elements F  and G , there exists a sequence of proper elements such that , , and any are comparable.[1] The special concession that rank 1 polytopes are connected ensures that the dyad is connected and thus an abstract polytope.

Strong connectivity[edit | edit source]

Strong connectivity is a version of connectivity used in the definition of abstract polytope. A bounded poset is strongly connected iff every section is connected.

Note that this requires every section not just every proper section to be connected. In general every proper section of a poset being connected does not imply that the poset itself is connected.[1] Polytope compounds are exactly those posets such that every proper section is connected but the poset is not connected.

Strong connectivity is desired for abstract polytopes since we want sections of abstract polytopes to be themselves abstract polytopes. Strong connectivity ensures not only that the poset itself is not a compound but also that it doesn't have compound faces, edges etc.

Example[edit | edit source]

Although degenerate in euclidean space the described polyhedron can be thought of as a tiling of the 2-sphere. It's two faces are colored in red and blue respectively.

A dihedron with tetragramal faces ({4/2,2}) is connected but not strongly connected. If we draw its Hasse diagram we can see that the section highligted in red is a tetragram and thus is not connected.

This obeys the other requirements of an abstact polytope (it is dyadic, ranked and bounded) thus if the strongly connected requirement was weakened to only require posets to be connected this would be an abstract polytope.

Flag connectivity[edit | edit source]

Two flags are said to be adjacent iff they differ by exactly one element. A ranked bounded poset is flag connected iff for any two flags and , there exists a sequence of flags such that , , and any pair of flags and are adjacent.

Flag connectivity is a stronger condition than connectivity. However flag connectivity can only be applied to ranked posets whereas connectivity can be applied to any bounded poset. In practice however abstract polytopes are required to be ranked and even weaker notions generally maintain this requirement. Any ranked poset that is flag connected is also connected.

Strong flag connectivity[edit | edit source]

A ranked bounded poset is strongly flag connected iff every section is flag connected. On ranked bounded posets strong flag connectivity is equivalent to strong connectivity.[2]

Graphs[edit | edit source]

A graph is connected if for any two vertices v  and v'  there is a sequence of vertices such that:

  • For every i , is adjacent to . that is there is an edge between the two.

Intuitively this is the same as saying you can get from any one vertex to any other simply by following edges.

Flag graphs[edit | edit source]

The flag graph of the hexagram is not connected.

The flag graph of a ranked poset is connected iff the poset is flag connected.

The graph based definitions of complex and maniplex, which generalize the idea of a flag graph, both require the graph to be connected.

References[edit | edit source]

Sources[edit | edit source]

  • McMullen, Peter; Schulte, Egon (December 2002), Abstract Regular Polytopes (1st ed.), Cambridge University Press, ISBN 0-521-81496-0