$\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) 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: 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). 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), §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), 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.)
Best Answer
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,...).$