$\DeclareMathOperator\MLS{MLS}$Recall that the **median operation**, on the power set $2^Y$ of subsets of a set $Y$, is the ternary law $m(A,B,C)$ mapping a triple of subsets to the set of elements belonging to at least two of them. If we view $2^Y$ as the Boolean algebra $(\mathbf{Z}/2\mathbf{Z})^Y$, this is just $m(A,B,C)=AB+BC+AC$.


There is an abstract notion of median algebra (see e.g. [Wikipedia](https://en.wikipedia.org/wiki/Median_algebra)) but it's not necessary to understand the question; it turns out that every median algebra is isomorphic to a median subalgebra of a power set (= subset of $2^Y$ closed under the ternary operation $m$).


Given a set $X$, a **maximal linked system** (ML system) is a family $\mathcal{F}$ of subsets (family in the sense: set of subsets) of $X$ with the axioms:


* $\forall A\in 2^X$, either $A$ or $A^c$ is in $\mathcal{F}$, and
* $A\cap B$ is nonempty for all $A,B\in\mathcal{F}$.


For instance, for $x\in X$, the family $\mathcal{F}\_x=\{A:A\ni x\}$ is a ML system; call it a principal ML system. Let $[X]$ be the set of principal ML systems: it is in canonical bijection with $X$.


Let $\MLS(X)\subseteq 2^{2^X}$ be the set of ML systems of $X$. This is a median subalgebra of $2^{2^X}$ (easy verification).



> 
> **Question.** Assume $X$ finite. Is $\MLS(X)$ generated, as median subalgebra of $2^{2^X}$, by the set $[X]$ of principal ML systems?
> 
> 
> 


The median subalgebra generated by $[X]$ is actually the free median algebra over $[X]$. So a positive answer to the above question actually yields a realization of this free median algebra.


For $0\le |X|\le 6$ the answer to the question is positive. The corresponding cardinal is $0$, $1$, $2$, $4$, $12$, $81$, $2646$.


In general, the cardinal $\lambda(n)$ of $\MLS(n)$ is [Sloane OEIS A001206](https://oeis.org/A001206): for $n=7,8,9$ its values are also known: $1422564$, $229809982112$, $423295099074735261880$. It grows quickly: $\log\_2(\lambda(n))\sim 2^n/\sqrt{2\pi n}$ (see Brouwer-Mills-Mills-Verbeek [DOI link](https://doi.org/10.37236/2693)). So the question amounts to asking whether this sequence $\lambda(n)$ (which has various definitions, see the OEIS link) is also the cardinal of the free median algebra on $n$ generators.


Bowditch's preprint "median algebras" ([link at Bowditch's page](http://homepages.warwick.ac.uk/%7Emasgak/papers/median-algebras.pdf)), §24.5. "*Notes on Section 5 (Free median algebras)*" asserts that $\lambda(n)$ is the cardinal of the free median algebra. This amounts to claim that the above question has a positive answer. But why is it so?


Browsing, I finally found the 1977 paper "Convexity preserving mapping in subbase convexity theory" by van Mill and van de Vel ([DOI link](https://doi.org/10.1016/1385-7258(78)90025-2)), namely Theorem 2.6, which seems to obtain a universal property for $\MLS(X)$ (in a broader setting where $X$ is a topological space). But it requires a lot of definitions, including from other papers, which makes it quite obscure to me. If it indeed specifies to the above statement (for $X$ finite discrete), I'm wondering if there is any more direct approach anywhere.


(The above question obviously has a negative answer for $X$ infinite. Indeed, nonprincipal ultrafilters, which are ML systems, are not even in the Boolean subalgebra generated by principal ultrafilters = principal ML systems.)



Free median algebras and maximal linked systems
The answer is yes. The reason is rather simple: since the median operation is a special case of a *majority* operation, that is, an operation satisfying the identities


$\forall x,y,\ m(x,x,y) = m(x,y,x) = m(y,x,x) = x,$


every median subalgebra of $2^{2^X}$ is determined by its binary projections, by the Baker-Pixley theorem. A little thought shows that each binary relation $\mathbb{R} \subseteq 2 \times 2$ is preserved by the median operation, and that the set of operations $f \in 2^{2^X}$ whose binary projections are contained in the binary projections of $[X]$ are exactly the monotone self-dual operations, which are in one-to-one correspondence with the ML systems.


A more direct argument for this was shown to me by Yuzhou Gu. We will prove that every monotone self-dual operation $f : 2^X \rightarrow 2$ can be constructed from the median operation by induction on the arity of $f$. If $f$ has arity $2$, then it's easy to see that $f$ must be a projection. For the inductive step, suppose that $f$ has arity at least $3$. Then each of the three functions


$f(x\_1,x\_2,x\_2,x\_4,...,x\_n), f(x\_3,x\_2,x\_3,x\_4,...,x\_n), f(x\_1,x\_1,x\_3,x\_4,...,x\_n)$


is a monotone self-dual function of lower arity, so it can inductively be constructed from the median operation. The claim is that we always have


$f(x\_1, ..., x\_n) = m(f(x\_1,x\_2,x\_2,x\_4,...,x\_n), f(x\_3,x\_2,x\_3,x\_4,...,x\_n), f(x\_1,x\_1,x\_3,x\_4,...,x\_n)).$


This claim follows directly from the monotonicity of $f$ and the definition of the median operation. To check this quickly, you can use a symmetry argument to assume without loss of generality that $(x\_1,x\_2,x\_3) = (0,0,1)$, in which case we need to check that


$f(0,0,1,...) = m(f(0,0,0,...), f(1,0,1,...), f(0,0,1,...)),$


which follows from


$f(0,0,0,...) \le f(0,0,1,...) \le f(1,0,1,...).$


