\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{latexsym}

\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newcommand{\Proof}{ \noindent{\bf Proof.}\quad }
\newcommand{\qed}{\hfill$\Box$\medskip}
\newcommand{\Ff}{{\mathbb F}}
\newcommand{\maysplit}{\discretionary{}{}{}}
\newcommand{\mayhyph}{\discretionary{-}{}{}}

\title{Counting families of mutually intersecting sets}
\author{A. E. Brouwer, C. F. Mills, W. H. Mills \& A. Verbeek}
% W. H. Mills (1921-2007)
% C. F. Mills (1951-2000)
% A. Verbeek (1946-1990)
\date{2012-08-21}

\begin{document}
\maketitle

\begin{center}
{\it To Cecile, on the occasion of her 65th birthday}
\end{center}

\begin{abstract}
We show that the number of maximal intersecting families on a 9-set
% (the ninth Ho\c{s}ten-Morris number)
equals 423295099074735261880,
that the number of independent sets of the Kneser graph
$K(9,4)$ equals 366996244568643864340,
and that the number of intersecting families on an 8-set and on a 9-set is
14704022144627161780744368338695925293142507520
and
12553242487940503914363982718112298267975272720808010757809032705650-\\591023015520462677475328
(roughly $1.255 \cdot 10^{91}$), respectively.
\end{abstract}

\section{Introduction}
Let $X$ be a finite set, and ${\cal F}$ a collection of subsets of $X$.
We call ${\cal F}$ {\em linked} (or {\em intersecting})
when any two (not necessarily distinct) members of ${\cal F}$
have nonempty intersection.
We call ${\cal F}$ a {\em maximal linked system} (mls) when ${\cal F}$
is linked, but no strictly larger collection of subsets of $X$ is linked.
Let $|X|=n$. If $n > 0$, then a maximal linked system has size $2^{n-1}$
(since it contains precisely one of $A$, $X\setminus A$ for each subset
$A$ of $X$).

For a family ${\cal F}$ of subsets of $X$,
let ${\cal F}^{\rm min}$ be the collection
of inclusion-wise minimal elements of ${\cal F}$.
Then ${\cal F}^{\rm min}$ is an antichain.
Let ${\cal F}^{\,\uparrow}$ be the collection of subsets of $X$
containing some element of ${\cal F}$.
If ${\cal F}$ is an mls, then
${\cal F} = {\cal F}^{\,\rm min}{}^{\uparrow}$.

The Kneser graph $K(n,r)$ is the graph with as vertices the
$r$-subsets of a fixed $n$-set, two vertices being adjacent
when they are disjoint. It follows that a coclique (independent set)
in $K(n,r)$ is a collection of mutually intersecting $r$-subsets
of the given $n$-set.

\medskip
Let $\lambda(n)$ and $\Lambda(n)$ be the number of
maximal linked systems and linked systems on $n$ points, respectively.
In this note we determine $\lambda(9)$, $\Lambda(8)$ and $\Lambda(9)$.
The numbers $\lambda(n)$ (and, to a lesser degree, $\Lambda(n)$)
play a r\^{o}le in various areas of mathematics.
The description in terms of maximal linked systems is from topology
(giving the size of the superextension of a finite space).
In this setting, $\lambda(n)$ with $n \le 6$ was determined by G.~A.~Jensen
% see Verbeek, thesis, page 27
in 1966, $\lambda(7)$ was found in \cite{BV}, and $\lambda(8)$ in \cite{MM}.
An equivalent formulation comes from the area of Boolean functions
(see below) where $\lambda(n)$ is the number of self-dual monotone
Boolean functions of $n$ variables. Knuth \cite{Kn} computes $\lambda(n)$
for $n \le 8$.
% Knuth fasc0b page 33, Table 7.1.1-3
% Knuth fasc0c page 57, answer 7.1.2-88
% Knuth fasc1b page 89, answer 7.1.4-74.
Ho\c{s}ten \& Morris~\cite{HM} found that the order
dimension of the complete graph $K_n$ is the smallest $t$ for which
$\lambda(t-1) \ge n$, and computed $\lambda(n)$ for $n \le 6$.
Conway and Loeb studied $\lambda(n)$ in the context of multi-player
coalitions and determined $\lambda(n)$ for $n \le 8$, cf.~\cite{L,LC}.
The value of $\Lambda(n)$ for $n \le 7$ was found in \cite{PMN}.
The sequences $\lambda(n)$ and $\Lambda(n)$ are given in Sloane's
Encyclopedia of Integer Sequences under A001206 and A051185, respectively.

\subsection{Description in terms of Boolean functions}
A {\em Boolean function} in $n$ variables is a function
$f : \{0,1\}^n \to \{0,1\}$. There is a 1-1 correspondence
between Boolean functions $f$ and set systems ${\cal F}$
obtained by letting $f$ be the characteristic function of ${\cal F}$.
The Boolean function $f$ is called {\em monotone} when it cannot
decrease (become false) when some variables are increased (made true).
The equivalent property for ${\cal F}$ is that ${\cal F}^\uparrow = {\cal F}$.
The Boolean function $f$ is called {\em self-dual} when
$f(1-x_1,...,1-x_n) = 1-f(x_1,...,x_n)$. The equivalent property
for ${\cal F}$ is that ${\cal F}$ contains precisely one element
from every complementary pair $\{A,X\setminus A\}$.
Counting maximal linked systems is therefore equivalent to
counting self-dual monotone Boolean functions.

\subsection{Counting}
Erd\H{o}s \cite{E} (p. 79) writes: {\it It does not seem easy to determine}
$\lambda(n)$. {\it We could not even get an asymptotic formula}.
It is an easy exercise to give asymptotic formulas for $\log_2 \lambda(n)$
and $\log_2 \Lambda(n)$.

\begin{Proposition}\label{asymp} {\rm (\cite{BV})}

(i) Let $\alpha(n)$ be the number of antichains on $n$ points. Then
$$
\log_2 \lambda(n) \sim \log_2 \alpha(n-1) \sim {2^n \over \sqrt {2\pi n}} .
$$

(ii) Let $i(n)$ be the number of families on $n$ points
with nonempty intersection. Then
$$
\log_2 \Lambda(n) \sim \log_2 i(n) \sim 2^{n-1} .
$$
\end{Proposition}

(A proof is given in the next section.)

The currently known values of $\lambda(n)$ and $\Lambda(n)$ are as follows.

\begin{Proposition}
The values of $\lambda(n)$ and $\Lambda(n)$ for $n \le 9$
are as given in the table below.

{\rm \begin{center}\begin{tabular}{ccc}
$n$ & $\lambda(n)$ & $\Lambda(n)$ \\
\hline
0 & 1 & 1 \\
1 & 1 & 2 \\
2 & 2 & $2 \cdot 3$ \\ % 6
3 & 4 & $2^3 \cdot 5~$ \\ % 40
4 & 12 & $2^5 \cdot 43$ \\ % 1376
5 & 81 & $2^{12} \cdot 321$ \\ % 1314816
6 & 2646 & $2^{22} \cdot 217633$ \\ % 912818962432
7 & 1422564 & $2^{49} \cdot 517277329$ \\
% 291201248266450683035648
8 & 229809982112 & $2^{93} \cdot 1484726812083249435$ \\
% 14704022144627161780744368338695925293142507520
9 & 423295099074735261880 &
$2^{200} \cdot 7811901978914936479242384764953$
% 12553242487940503914363982718112298267975272720808010757809032705650591023015520462677475328
\end{tabular}\end{center}}
\end{Proposition}

That is, the sequence $\Lambda(n)$ starts out
1, 2, 6, 40, 1376, 1314816, 912818962432,
{\footnotesize 291201248266450683035648,
14704022144627161780744368338695925293142507520,

}{\tiny

\vskip 0.7mm\noindent
12553242487940503914363982718112298267975272720808010757809032705650591023015520462677475328, ...

}

\section{Easy bounds}
Before one starts counting, it helps to have some idea about
the size of the result, so that one can pick a suitable algorithm.
Below we give some rough estimates.

\begin{Lemma} Let $n \ge 1$. Then
$\log_2 \lambda(n) \ge {n-1 \choose [n/2]-1}$.
\end{Lemma}
\Proof
If $n$ is even, say $n = 2m$, then pick arbitrarily one element
from each pair $\{A,X\setminus A\}$ of complementary sets of size $m$.
This gives $2^e$ linked systems, where
$e = \frac{1}{2}{n \choose m} = {n-1 \choose m-1}$.
Extend each of these linked systems to a maximal linked system.
The mls's obtained will be pairwise distinct.

If $n$ is odd, say $n=2m+1$, then pick arbitrarily one element
from each pair $\{A,X\setminus A\}$ of complementary sets
where $A$ has size $m$ and contains a fixed element $x_0 \in X$.
This gives $2^e$ linked systems, where
$e = {2m \choose m-1}$, and the same conclusion follows.
\qed

\begin{Lemma} Let $n \ge 1$. Then $\lambda(n) < \alpha(n-1)$.
\end{Lemma}
\Proof
Fix $x_0 \in X$.
The map ${\cal F} \mapsto \{ A \in {\cal F}^{\rm min} \mid x_0 \notin A \}$
is a bijection from mls's on $n$ points to linked antichains on $n-1$ points
(and $\{\emptyset\}$ is an antichain that is not linked).
\qed

Since Kleitman \cite{K} shows that $\log_2 \alpha(n) \sim {n \choose [n/2]}$,
these two lemmas imply part (i) of Proposition \ref{asymp}.
More precise results were given by Korshunov~\cite{Korshunov}.

For small $n$ the value of $\alpha(n)$ was determined by various authors.
One finds 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998,
56130437228687557907788 for $0 \le n \le 8$ (\cite{W}).
This is Sloane's sequence A000372.

\begin{Lemma} Let $n \ge 1$. Then

(i)
$$\lambda(n)\, 2^{2^{n-1} - {n \choose [n/2]}} \le
\Lambda(n) \le \lambda(n)\, 2^{2^{n-1}} ,$$

(ii)
$$n 2^{2^{n-1}}(1-{n-1 \over 2 \cdot 2^{2^{n-2}}}) \le
\sum_{k=1}^n (-1)^{k+1} {n \choose k} 2^{2^{n-k}} = i(n) \le
\Lambda(n) .$$
\end{Lemma}
\Proof
(i) Let ${\cal F}$ be an mls. Then ${\cal F}$ has size $2^{n-1}$, and
hence contains $2^{2^{n-1}}$ linked subfamilies. This shows that
$\Lambda(n) \le \lambda(n).2^{2^{n-1}}$.
Next, ${\cal F}^{\rm min}$ is an antichain,
and, by Sperner's Lemma, has size at most ${n \choose [n/2]}$.
Each of the at least $2^{2^{n-1} - {n \choose [n/2]}}$ linked families
${\cal G}$ with ${\cal F}^{\rm min} \subseteq {\cal G} \subseteq {\cal F}$
determines ${\cal F} = {\cal G}^\uparrow$.

(ii) Since a family with nonempty intersection is linked,
$i(n) \le \Lambda(n)$. The formula for $i(n)$ follows by inclusion-exclusion.
Since ${n \choose k} 2^{2^{n-k}}$ decreases with $k$, the first two terms
give a lower bound for the sum.
\qed

This lemma implies part (ii) of Proposition \ref{asymp}.

\medskip
Finally, let us note a 1-1 correspondence.
Above we saw a 1-1 correspondence between mls's on $n$ points
and linked antichains on $n-1$ points. There is also a \mbox{1-1}
correspondence between linked antichains on $n-1$ points
and linked antichains on $n$ points `in the bottom half ${\cal H}$
of the Boolean lattice', where ${\cal H}$ consists of the subsets of $X$
of size less than $n/2$, together with an arbitrary choice of precisely one
element from each complementary pair $\{A,X\setminus A\}$ of sets of size
$n/2$ (in case $n$ is even). Indeed, we can let ${\cal F}$ correspond with
$({\cal F} \cap {\cal H}) \cup \{X\setminus A \mid A \in
{\cal F} \setminus {\cal H}\}$.

\section{Computation of $\lambda(8)$}
In Section \ref{L8}, $\lambda(8)$ is found as a side result of the
computation of $\Lambda(8)$. The algorithm used in \cite{MM}
enumerated upwardly closed linked systems ${\cal L}$ of sets of size at most 3,
and for each ${\cal L}$ counted the number $a$ of complementary pairs
$\{A,X\setminus A\}$ of 4-sets, such that both $A$ and $X\setminus A$
meet all elements of ${\cal L}$. Now ${\cal L}$ is contained in precisely
$2^a$ mls's. One finds $\lambda(8) = \sum_{\cal L} 2^{a({\cal L})} =
229809982112$.

\section{Computation of $\lambda(9)$}\label{l9}
We count linked antichains ${\cal A}$ on 9 points, of which all
elements have size at most 4. Let ${\cal A}'$ be the subcollection
of ${\cal A}$ consisting of the sets of size at most 3.

Classifying all linked antichains ${\cal B}$ on 9 points,
of which all elements have size at most 3, under the action of
the symmetric group Sym(9) shows that there are 15952 orbits.
For each orbit, pick a representative ${\cal B}$ and count extensions
to linked antichains ${\cal A}$ for which ${\cal A}' = {\cal B}$.
For example, if ${\cal B}$ contains a singleton $\{x\}$,
then it contains nothing else, and ${\cal A} = {\cal B}$. (There are
9 such ${\cal A}$.) A similar conclusion holds when ${\cal B}$ contains
three pairs $\{x,y\}$, $\{x,z\}$ and $\{y,z\}$. For largish ${\cal B}$
it is very easy to find all extensions ${\cal A}$. The worst case is
that where ${\cal B}$ is empty, so that ${\cal A}$ is a coclique
in the Kneser graph $K(9,4)$.

\subsection{Counting independent sets in a sparse graph}
Counting independent sets in a sparse graph is a popular topic.
People mostly prove complexity results: for regular graphs of degree
at most 4, approximate counting is easy, for degree at least 6
it is difficult (cf.~\cite{DFJ}).
Here we have degree 5, and we want the exact count.

A recursive algorithm that keeps a current set of vertices $S$,
and when $S$ contains an edge $xy$ calls itself with $S\setminus\{x\}$
and with $S\setminus (\{x\} \cup N(x))$, where $N(x)$ is the set of
neighbours of $x$, can count $2^{|S|}$ independent sets
when $S$ is independent.
This is good, but too slow.

A better version of the algorithm will go down the recursion
when some vertex $x$ has degree at least 2 in $S$, and count
$2^a 3^b$ when $S$ contains $a$ isolated points and $b$ isolated edges.
This is still too slow.

The algorithm used in practice uses recursion when some vertex $x$ has degree
at least 3 in $S$, and counts the proper number when all vertices in $S$
have degree at most 2, so that $S$ induces a union of paths and cycles.
(Let $p(n)$ be the number of cocliques in the path $P_n$ on $n$ vertices,
and $c(n)$ the number of cocliques in the cycle $C_n$ on $n$ vertices.
Then $p(0) = 1$, $p(1) = 2$, $p(m) = p(m-1)+p(m-2)$ for $m \ge 2$, and
$c(m) = p(m-1)+p(m-3)$ for $m \ge 3$. The proper number is the product
of numbers $p(m)$ and $c(m)$, one for each connected component
$P_m$ or $C_m$.)

The result of doing this on the Kneser graph $K(9,4)$
was 366996244568643864340,
and together with the 56298854506091397540 extensions of nonempty
${\cal B}$ we find that $\lambda(9) = 423295099074735261880$.

\section{Computation of $\Lambda(8)$}\label{L8}
We follow the setup of Pogosyan, Miyakawa \& Nozaki \cite{PMN}.
Let $2^X$ be the power set of $X$, of size $2^n$, where $n \ge 1$.
If $n$ is even, fix an element $x_0 \in X$.
Let ${\cal H}$, the bottom half of $2^X$, consist of the subsets of $X$
of size less than $n/2$, or of size precisely $n/2$ and not containing $x_0$.
Then for each complementary pair $\{A,X\setminus A\}$ precisely one
element is in ${\cal H}$.
Let there be $k(r,n)$ linked antichains of size $r$ contained in ${\cal H}$.
Let $m = {n-1 \choose [n/2]-1}$.

\begin{Theorem} \label{LL} {\rm (\cite{PMN})}
$\lambda(n) = \sum_{r=0}^m k(r,n)$ and
$\Lambda(n) = \sum_{r=0}^m 2^{2^{n-1}-r} k(r,n)$.
The precise power of $2$ that divides $\Lambda(n)$ is
$2^{2^{n-1}-m}$.
\end{Theorem}
%
\Proof
The largest intersecting antichain in ${\cal H}$ for even $n$ is
the collection of elements of ${\cal H}$ of size $n/2$.
(This collection is linked since the sets do not contain $x_0$.)
For odd $n$ the largest intersecting antichains are the collections
of sets of size $(n-1)/2$ containing some fixed element $x \in X$.
In both cases the size of a largest intersecting antichain equals
$m := {n-1 \choose [n/2]-1}$.

Since each mls ${\cal F}$ is uniquely determined by the linked
antichain ${\cal F}^{\rm min} \cap {\cal H}$, we see that
$\lambda(n) = \sum_r k(r,n)$.

For a linked system ${\cal F}$, consider the linked antichain
${\cal G} = {\cal F}^{\rm min} \cap {\cal H}$ and put $r = |{\cal G}|$.
The number of ${\cal F}$ giving rise to the same ${\cal G}$ equals
$2^{2^{n-1}-r}$. Indeed, there are $2^{n-1}-r$ pairs $\{A,X\setminus A\}$
with $A \in {\cal H} \setminus {\cal G}$.
For such a pair, it possible that $A \in {\cal F}$ only if there is
a $B \in {\cal G}$ with $B \subset A$. In this case
$(X\setminus A) \cap B = \emptyset$, so $X\setminus A \notin {\cal F}$,
while we can freely choose whether $A \in {\cal F}$.
On the other hand, if there is no such $B$, then $A \notin {\cal F}$
while we can freely choose whether $X\setminus A \in {\cal F}$.
(Note that $2^X \setminus {\cal H}$ is linked, and adding sets that
properly contain a set that is present already cannot invalidate the
property of being linked.)
This shows that $\Lambda(n) = \sum_{r=0}^m 2^{2^{n-1}-r} k(r,n)$.

Since $k(m,n) = 1$ if $n$ is even, and $k(m,n) = n$ if $n$ is odd,
so that $k(m,n)$ is odd in all cases, it follows that the precise
power of 2 that divides $\Lambda(n)$ is $2^{2^{n-1}-m}$.
\qed

For $n=8$ we found the following values:

\begin{center}{\footnotesize
\begin{tabular}{@{}c@{~}|@{~}c@{~~}c@{~~}c@{~~}c@{~~}c@{~~}c@{}}
\hline\rule{0pt}{8pt}
$r$ & 0 & 1 & 2 & 3 & 4 & 5 \\
$k(r,8)$ & 1 & 127 & 5103 & 110901 & 1442910 & 12564636 \\
\hline\rule{0pt}{10pt}
$r$ & 6 & 7 & 8 & 9 & 10 & 11 \\
$k(r,8)$ & 78501094 & 365924948 & 1302838180 &
3609216800 & 7932407952 & 14155324680 \\
\hline\rule{0pt}{10pt}
$r$ & 12 & 13 & 14 & 15 & 16 & 17 \\
$k(r,8)$ & 21054328876 & 26807793040 & 29932703320 &
29875293476 & 27014411074 & 22319717630 \\
\hline\rule{0pt}{10pt}
$r$ & 18 & 19 & 20 & 21 & 22 & 23 \\
$k(r,8)$ & 16932275290 & 11821639550 & 7598222786 &
4489816356 & 2432135090 & 1202614280 \\
\hline\rule{0pt}{10pt}
$r$ & 24 & 25 & 26 & 27 & 28 & 29 \\
$k(r,8)$ & 539687680 & 218192464 & 78745884 &
25082260 & 6952300 & 1647520 \\
\hline\rule{0pt}{10pt}
$r$ & 30 & 31 & 32 & 33 & 34 & 35 \\
$k(r,8)$ & 326312 & 52416 & 6545 & 595 & 35 & 1 \\
\hline
\end{tabular}}\end{center}

In this particular case we see
that the numbers given add up to $\lambda(8) = 229809982112$, a good check.
% The values $k(0,n) = 1$ and $k(1,n) = 2^{n-1}-1$ are obvious.
%
% We see k(35,8) = (m choose 0), k(34,8) = (m choose 1),
% k(33,8) = (m choose 2), k(32,8) = (m choose 3),
% k(31,8) = (m choose 4) + 56
% The additional 56 are antichains containing a triple ijk.
% If ijk does not contain 0, it excludes the four 4-sets ijkl
% and replaces its complement, so get size 31.
% If ijk contains 0, it excludes the five disjoint 4-sets, agina size 31.
%
It follows that $\Lambda(8) = \sum_r 2^{128-r} k(r,8) =
2^{93} \cdot 1484726812083249435 {\kern -0.55pt} = {\kern -0.55pt}
14704022144627161780744368338695925293142507520$.


\section{Computation of $\Lambda(9)$}
Combining the ideas used for $\Lambda(8)$ and $\lambda(9)$
yields a computation of $\Lambda(9)$. We briefly sketch the procedure.
Let $n = 9$.
Let $f(x) := \sum_{r=0}^m k(r,n) x^r$ be the polynomial where the
coefficient of $x^r$ is the number of linked antichains of size $r$
(in ${\cal H}$, which here is the collection of all subsets of $X$
of size at most 4). By Theorem \ref{LL} we have $\lambda(9) = f(1)$
and $\Lambda(9) = 2^{256} f(\frac12)$. The polynomial $f(x)$ is
computed just like the number $\lambda(9)$ was earlier, but this
time with added bookkeeping of the size of the linked antichains found.

Again consider the graph in which the linked antichains are the cocliques.
If, after fixing $s$ vertices of the future coclique, the part of the
graph that is compatible with the chosen subset has maximum degree
at most two, so that it decomposes into a number of paths and cycles,
then the contribution of this choice will be $x^s$ times the product
of factors $p_m(x)$ and $c_m(x)$, one for each connected component
that is a path $P_m$ or a cycle $C_m$ respectively.
The polynomials $p_m(x)$ and $c_m(x)$ are given by
$p_0(x)=1$, $p_1(x)=x+1$, $p_m(x)=xp_{m-2}(x)+p_{m-1}(x)$ for $m \ge 2$,
and $c_m(x)=xp_{m-3}+p_{m-1}$ for $m \ge 3$.

As before (in \S\ref{l9}) classify all linked antichains ${\cal B}$ on 9 points
of which all elements have size at most 3. There are 15952 orbits.
The contribution to $f(x)$ of the 15951 orbits with nonempty ${\cal B}$
equals

\smallskip{\footnotesize
$g(x) = 129x + 15750x^2 + 912450x^3 + 31596495x^4 + 746247600x^5
+ 12916236186x^6 + \cdots
% 171069930630x^7 + 1784733288174x^8 + 14988489949608x^9 +
% 103135310500698x^{10} + 590266964879046x^{11} + 2846098214272341x^{12} +
% 11686321357101300x^{13} + 41222686429050354x^{14} + 125786616678088770x^{15}
% + 333798296901132987x^{16} + 773421395297815782x^{17}
% + 1569287289913667352x^{18} + 2794306321944654888x^{19}
% + 4373520248001406761x^{20} + 6024826013184807090x^{21}
% + 7313914057515899778x^{22} + 7835028140289993426x^{23}
% + 7419316109162849073x^{24} + 6224819312102237532x^{25}
% + 4642111393729916526x^{26} + 3090492519450586740x^{27}
% + 1847567608050583593x^{28} + 999312770017922202x^{29}
% + 493543325532562956x^{30} + 224917558838503650x^{31}
% + 95614085826689220x^{32} + 38295259008791148x^{33}
% + 14560109580300858x^{34} + 5275698332696676x^{35} + 1821455376154731x^{36}
% + 596914843924182x^{37} + 184466426431266x^{38} + 53315581460400x^{39}
% + 14279164274802x^{40} + 3508319871252x^{41} + 782104041378x^{42}
% + 156246577074x^{43} + 27569760120x^{44}
 + 4221415800x^{45}
 + 548449482x^{46} + 58674672x^{47} + 4953060x^{48} + 308700x^{49}
 + 12600x^{50} + 252x^{51}$},

\smallskip\noindent
and we find $g(1) = 56298854506091397540$ (as we found before), and
$2^{256}g(\frac12) = 2^{200} \cdot 3002198881528317355134735632256$.

% \medskip\noindent{\footnotesize
% 4824347599159642336830254752905562805454456304949368420149946320864930225978277771666784256}.\kern-50pt

\smallskip\noindent
It remains to handle cocliques in $K(9,4)$. Let $h(x)$ be their contribution.
Then $h(x) = 1 + 126j(x)$, where $x j'(x)$ is the contribution of the
cocliques that contain a fixed chosen vertex. We found

\smallskip{\footnotesize
$j'(x) = 1 + 120x + 6850x^2 + 247740x^3 + 6379125x^4 + 124596364x^5 +
1920563240x^6 + \cdots + 121602100x^{49} + 14255452x^{50} +
1377740x^{51} + 105205x^{52} + 5940x^{53} + 220x^{54} + 4x^{55}$,
}

\smallskip\noindent
so that

\smallskip{\footnotesize
$h(x) = 1 + 126x + 7560x^2 + 287700x^3 + 7803810x^4 + 160753950x^5 +
2616523644x^6 + \cdots + 306437292x^{50} + 35219352x^{51} + 3338370x^{52} + 250110x^{53} +
13860x^{54} + 504x^{55} + 9x^{56}$,}

\smallskip\noindent
and it follows that $h(1) = 366996244568643864340$ (as we found before), and
$2^{256}h(\frac12) = 2^{200} \cdot 4809703097386619124107649132697$.

% \smallskip\noindent{\footnotesize
% 7728894888780861577533727965206735462520816415858642337659086384785660797037242691010691072}.\kern-50pt

\smallskip
Altogether, this yields $f(x) = g(x)+h(x) = $
{\footnotesize $1 + 255x + 23310x^2 + 1200150x^3 + 39400305x^4 +
907001550x^5 + 15532759830x^6 + 205640068950x^7 + \,\cdots\, +
% 14559448155x^{48} +
2265891210x^{49} + 306449892x^{50} + 35219604x^{51} + 3338370x^{52} +
250110x^{53} + 13860x^{54} + 504x^{55} + 9x^{56}$.\kern-50pt}

\smallskip\noindent
It follows that $\lambda(9) = f(1) = 423295099074735261880$
(as we found before), and
$\Lambda(9) = 2^{256} f(\frac12) = 2^{200} \cdot 7811901978914936479242384764953$.

% \smallskip\noindent{\footnotesize
% 12553242487940503914363982718112298267975272720808010757809032705650591023015520462677475328}.\kern-50pt

\section{History}
\def\thefootnote{\fnsymbol{footnote}}
\setcounter{footnote}{1}
Parts of the above are from \cite{BV} and \cite{MM}.
These four authors had agreed to submit a joint paper,
but nothing came of it. Today my three coauthors\footnote{
W. H. Mills (1921-2007), C. F. Mills (1951-2000), A. Verbeek (1946-1990)}
are no longer alive,
and the results of \cite{BV,MM} have been published by others.
The present note improves all previous results known to me.

\section*{Acknowledgment}
The referee suggested to add a computation of $\Lambda(9)$.

\begin{thebibliography}{99}

\bibitem{BV}
A. E. Brouwer \& A. Verbeek,
{\it Counting families of mutually intersecting sets},
internal report ZN 41, Afd. Zuivere Wiskunde,
Math. Centrum, Amsterdam, March 1972.
% \hfill{\tt http://oai.cwi.nl/oai/asset/7461/7461A.pdf}

\bibitem{DFJ}
M. Dyer, A. Frieze \& M. Jerrum,
{\it On counting independent sets in sparse graphs},
SIAM J. Comput. {\bf 31} (2002) 1527--1541.

\bibitem{E}
P. Erd\H{o}s,
{\it Problems and results in combinatorial analysis},
Proc. Symp. Pure Math. AMS {\bf 19} (1971) 77--89.

% \bibitem{FMSS}
% R. Fidytek, A. W. Mostowski, R. Somla \& A. Szepietowski,
% {\it Algorithms counting monotone Boolean functions},
% Information Processing Letters {\bf 79} (2001) 203--209.
%% have typo in alpha(7), nothing new after Wiedemann

\bibitem{HM}
Serkan Ho\c{s}ten \& Walter D. Morris, Jr.,
{\it The order dimension of the complete graph},
Discr. Math. {\bf 201} (1999) 133--139.

\bibitem{K}
D. Kleitman,
{\it On Dedekind's problem: the number of monotone Boolean functions},
Proc. Amer. Math. Soc. {\bf 21} (1969) 677--682.

\bibitem{Kn}
D. E. Knuth,
{\it The Art of Computer Programming}, Vol. 4A,
{\it Combinatorial Algorithms, Part 1}, Addison-Wesley, 2011.
% Section 7.1.1, p. 79. [2008]

\bibitem{Korshunov}
A. D. Korshunov,
{\it Families of subsets of a finite set and closed class of
Boolean functions}, pp. 375--396 in:
``Extremal Problems for Finite Sets'', Proc. Visegrad (Hungary),
Bolyai Society Mathematical Studies, Vol. 3, 1991.

\bibitem{L}
D. E. Loeb,
{\it Stable winning coalitions},
pp. 451--471 in:
R. J. Nowakowski,
{\it Games of no chance},
Cambridge Univ. Pres, 1998.

\bibitem{LC}
D. E. Loeb \& A. R. Conway,
{\it Voting fairly: transitive maximal intersecting families of sets},
J. Comb. Th. (A) {\bf 91} (2000) 386--410.

\bibitem{MM}
C. F. Mills \& W. H. Mills,
{\it The calculation of $\lambda(8)$},
preprint, July 1979.
% that is, received by aeb July 1979.

\bibitem{PMN}
G. Pogosyan, M. Miyakawa \& A. Nozaki,
{\it On the number of clique Boolean functions},
RIMS K\^{o}ky\^{u}roku {\bf 666} (1988) 302--315.
% http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/666.html
% http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0666-31.pdf
%
% There is also
% Grant Pogosyan, Masahiro Miyakawa, Akihiro Nozaki \& Ivo G. Rosenberg,
% The Number of Clique Boolean Functions,
% IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and
% Computer Sciences Vol. E80-A (1997) No.8 pp. 1502-1507
% http://search.ieice.org/bin/summary.php?id=e80-a_8_1502
% but unavailable to me.

\bibitem{W}
D. Wiedemann,
{\it A computation of the eighth Dedekind number},
Order {\bf 8} (1991) 5--6.

\end{thebibliography}

\end{document}