4
$\begingroup$

John Isbell defined a notion of a median algebra (although the original idea is due to Birkhoff). A median algebra is a set $S$ with a ternary operation $[x,y,z]$ satisfying a set of axioms. The example to have in mind comes from lattice theory. Suppose $(L, \wedge, \vee, 0, 1)$ is a lattice. Then, we can define $[x, y, z] = (x \vee y) \wedge (y \vee z) \wedge (x \vee z)$ (with a little work, you can show it satisfies said axioms). The intuition is clear: if, for example $x \preceq y \preceq z$, then $[x,y,z] = y$. More interesting things can happen if $x, y, z$ do not lie in a chain.

My question is this: is there a nice notion of median of a) a finite subset of elements of a lattice or b) and arbitrary subset of a complete lattice. In order for said notion to be considered a median, it must, at the bare minimum, satisfy the property that if $C$ is a chain, then $\mathrm{median} (C)$ is a median (maybe there are two) of the chain.

$\endgroup$
7
  • 1
    $\begingroup$ To define a median algebra form a lattice, the lattice needs to be distributive. $\endgroup$ Commented Sep 28, 2021 at 23:13
  • $\begingroup$ why is that? consider the pentagon lattice $N_5$. the median of the length 3 chain should still be the middle element, right? $\endgroup$
    – Hans
    Commented Sep 29, 2021 at 3:27
  • $\begingroup$ In a median algebra $X$, define $[a,b]=\{[a,b,x]\mid x\in X\}$. Then $[a,b]$ is a distributive lattice where $x\wedge y=[a,x,y],x\vee y=[b,x,y]$, and these new lattice operations will agree with the old lattice operations as long as $a\leq b$. In particular, $x\wedge y=[0,x,y],x\vee y=[1,x,y]$ whenever the lattice produces a median algebra. $\endgroup$ Commented Sep 29, 2021 at 3:35
  • 1
    $\begingroup$ Here are some terms that are essentially medians for lattices $s_{n,k}(x_{1},\dots,x_{n})=\bigwedge_{R\subseteq[n],|R|=k}(\bigvee_{r\in R}x_{r}),t_{n,k}(x_{1},\dots,x_{n})=\bigvee_{R\subseteq[n],|R|=k}(\bigwedge_{r\in R}x_{r})$ $\endgroup$ Commented Sep 29, 2021 at 3:38
  • 1
    $\begingroup$ You may mention comedian algebras in a talk. But I found a recent dissertation about algebraic structures dual for median algebras known as poc sets. I think the term comedian algebras is better (and funnier too). arxiv.org/ftp/arxiv/papers/1607/1607.07747.pdf $\endgroup$ Commented Oct 4, 2021 at 3:33

1 Answer 1

5
$\begingroup$

Yes. There is a nice notion of an $n$-ary median term in a distributive lattice and in a median algebra as long as $n$ is odd.

Proposition: Suppose that $1\leq k\leq n$.

  1. There is a term $t$ in the language of lattices such that if $x_{1}\leq\dots\leq x_{n}$, then $t(x_{1},\dots,x_{n})=x_{k}$ and where $t$ satisfies the identity $t(z_{1},\dots,z_{n})=t(z_{\sigma(1)},\dots,z_{\sigma(n)})$ for each permutation $\sigma\in S_{n}$.

  2. If $s,t$ are terms in the language of lattices such that if $x_{1}\leq\dots\leq x_{n}$, then $s(x_{1},\dots,x_{n})=t(x_{1},\dots,x_{n})=x_{k}$ and where $s(z_{1},\dots,z_{n})=s(z_{\sigma(1)},\dots,z_{\sigma(n)})$ and $t(z_{1},\dots,z_{n})=t(z_{\sigma(1)},\dots,z_{\sigma(n)})$ for each permutation $\sigma\in S_{n}$, then $s(u_{1},\dots,u_{n})=t(u_{1},\dots,u_{n})$ whenever $u_{1},\dots,u_{n}$ are elements of some distributive lattice.

For example, suppose that $m_{n,k}^{+}(z_{1},\dots,z_{n})=\bigwedge_{R\in[n]^{k}}(\bigvee_{r\in R}z_{r})$, and suppose that $m_{n,k}^{-}(z_{1},\dots,z_{n})=\bigvee_{R\in[n]^{n+1-k}}(\bigwedge_{r\in R}z_{r})$. Then the terms $m_{n,k}^{-},m_{n,k}^{+}$ satisfy $1$ in the above proposition.

To prove $2$, we observe that $2$ holds for the $2$ element distributive lattice, and that the variety of all distributive lattices is generated by the $2$ element distributive lattice.

For distributive lattices, we may just write $m_{n,k}$ for $m_{n,k}^{-}$ or $m_{n,k}^{+}$ since $m_{n,k}^{-}$ and $m_{n,k}^{+}$ are logically equivalent for distributive lattices.

By the next proposition, we see that the for distributive lattice, the medians $m_{n,k}$ are precisely the terms which are symmetric with respect to all permutations in $S_{n}$.

Proposition: If $t$ is a term in the language of distributive lattices such that $t(z_{1},\dots,z_{n})=t(z_{\sigma(1)},\dots,z_{\sigma(n)})$ for each permutation $\sigma$, then there is some $k$ with $1\leq k\leq n$ such that $t(z_{1},\dots,z_{n})=m_{n,k}(z_{1},\dots,z_{n})$ whenever $z_{1},\dots,z_{n}$ belong to some distributive lattice.

If $t$ is a term in the language of all distributive lattices, then let $t^{d}$ be the term obtained from $t$ by replacing every instance of $\wedge$ with $\vee$ and every instance of $\vee$ with $\wedge$.

Proposition: If $n=2r-1$, then the median $m_{2r-1,r}$ is (up-to-logical equivalence) the only $2r-1$-ary term $t$ in the language of Boolean algebras where $t(z_{1},\dots,z_{n})=t(z_{\sigma(1)},\dots,z_{\sigma(n)})$ for each permutation $\sigma$ and where $t=t^{d}$.

The term $m_{2r-1,r}(x_{1},\dots,x_{2r-1})$ can actually be defined in terms of the ternary median operator. The theory of $2r-1$ median operations has been studied in the paper "The algebra of majority consensus" by Hans-Jorgen Bandelt and Gerasimos C. Meletiou.

Define terms $$(w_{1},\dots,w_{i+1},x^{i})=m(m(m(w_{1},w_{2},x),w_{3},x),\dots,w_{i+1},x).$$

The following proposition reconstructs the $2r-1$-ary median $m_{2r-1,r}$ from the $2r-3$-ary median $m_{2r-3,r-1}$ and the ternary median $m$.

Proposition: In a distributive lattice, we have $$m_{2r-1,r}(x_{1},\dots,x_{2r-1})$$ $$=m_{2r-3,r-1}(x_{1},\dots,x_{r-2},(x_{r-1},x_{r},x_{r+1}),(x_{r-1},x_{r},x_{r+1},x_{r+2}^{2}))\dots(x_{r-1}\dots,x_{2r-2},x_{2r-1}^{r-1})).$$

There are other ways of constructing the $2r-1$-median operator from the ternary median. The $2r-1$-median operator is the only $2r-1$-ary term $t$ up to logical equivalence in the language of ternary median algebras such that $t(z_{1},\dots,z_{2r-1})=t(z_{\sigma(1)},\dots,z_{\sigma(2r-1)})$ for all permutations $\sigma\in S_{2r-1}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .