Median Graph - Distributive Lattices and Median Algebras

Distributive Lattices and Median Algebras

In lattice theory, the graph of a finite lattice has a vertex for each lattice element and an edge for each pair of elements in the covering relation of the lattice. Lattices are commonly presented visually via Hasse diagrams, which are drawings of graphs of lattices. These graphs, especially in the case of distributive lattices, turn out to be closely related to median graphs.

In a distributive lattice, Birkhoff's self-dual ternary median operation

m(a,b,c) = (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) ∧ (b ∨ c),

satisfies certain key axioms, which it shares with the usual median of numbers in the range from 0 to 1 and with median algebras more generally:

• Idempotence: m(a,a,b) = a for all a and b.
• Commutativity: m(a,b,c) = m(a,c,b) = m(b,a,c) = m(b,c,a) = m(c,a,b) = m(c,b,a) for all a, b, and c.
• Distributivity: m(a,m(b,c,d),e) = m(m(a,b,e),c,m(a,d,e)) for all a, b, c, d, and e.
• Identity elements: m(0,a,1) = a for all a.

The distributive law may be replaced by an associative law:

• Associativity: m(x,w,m(y,w,z)) = m(m(x,w,y),w,z)

The median operation may also be used to define a notion of intervals for distributive lattices:

I(a,b) = {x | m(a,x,b) = x} = {x | a ∧ b ≤ x ≤ a ∨ b}.

The graph of a finite distributive lattice has an edge between vertices a and b whenever I(a,b) = {a,b}. For every two vertices a and b of this graph, the interval I(a,b) defined in lattice-theoretic terms above consists of the vertices on shortest paths from a to b, and thus coincides with the graph-theoretic intervals defined earlier. For every three lattice elements a, b, and c, m(a,b,c) is the unique intersection of the three intervals I(a,b), I(a,c), and I(b,c). Therefore, the graph of an arbitrary finite distributive lattice is a median graph. Conversely, if a median graph G contains two vertices 0 and 1 such that every other vertex lies on a shortest path between the two (equivalently, m(0,a,1) = a for all a), then we may define a distributive lattice in which a ∧ b = m(a,0,b) and a ∨ b = m(a,1,b), and G will be the graph of this lattice.

Duffus & Rival (1983) characterize graphs of distributive lattices directly as diameter-preserving retracts of hypercubes. More generally, every median graph gives rise to a ternary operation m satisfying idempotence, commutativity, and distributivity, but possibly without the identity elements of a distributive lattice. Every ternary operation on a finite set that satisfies these three properties (but that does not necessarily have 0 and 1 elements) gives rise in the same way to a median graph.