7
$\begingroup$

$\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.)

$\endgroup$
4
  • 1
    $\begingroup$ Just as in any variety generated by a finite algebra, the free median algebra on $n$ generators can be realized as the algebra of all term operations in $n$ variables, which in this case are exactly the monotone self-dual Boolean operations $f\colon\{0,1\}^n\to\{0,1\}$. These can be identified with $f^{-1}(1)$, which are the families $F$ of subsets of $[n]$ such that (1) for each $A$, either $A$ or $A^c$ is in $F$, and (2) $F$ is upwards closed. Is this the same as a ML system? $\endgroup$ Oct 22, 2022 at 15:32
  • 1
    $\begingroup$ Yes, I think this is an equivalent condition. $\endgroup$ Oct 22, 2022 at 15:38
  • $\begingroup$ @EmilJeřábek you probably mean in (1) that exactly one of $A,A^c$ is in $F$. As stated, e.g., the subsets of cardinal $\ge 4$ in a 17-element set would form such a family, and we don't want this. $\endgroup$
    – YCor
    Oct 22, 2022 at 16:02
  • $\begingroup$ I meant "either ... or ..." literally, i.e., as exclusive or. $\endgroup$ Oct 22, 2022 at 16:08

1 Answer 1

7
$\begingroup$

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,...).$

$\endgroup$
7
  • 3
    $\begingroup$ The fact that all monotone self-dual Boolean operations can be generated from the ternary majority operation is at least as old as the description of Post's lattice. $\endgroup$ Oct 22, 2022 at 15:53
  • 2
    $\begingroup$ Old, but not as widely known as it should be. I'd be interested in seeing the original proof, if you can track it down. $\endgroup$
    – zeb
    Oct 22, 2022 at 16:05
  • $\begingroup$ Post's proof should be in the 1941 monograph; I don't know what proof it is. $\endgroup$ Oct 22, 2022 at 16:11
  • $\begingroup$ Thank you! I could already follow Gu's argument. It even shows, by induction, that $\le n-2$ iterations of $m$ are enough to obtain an operation of arity $n\ge 2$ from projections. $\endgroup$
    – YCor
    Oct 22, 2022 at 16:39
  • 2
    $\begingroup$ @EmilJeřábek I'd like to see Post's paper (I don't have access to it). I'd also be interested in a reference where the correspondence with free median algebra is explicit — it would indeed be nice to mention cardinal of free median algebras in the OEIS sequence oeis.org/A001206 $\endgroup$
    – YCor
    Oct 22, 2022 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.