2
$\begingroup$

Let's fix a finite set $E, \#E = n$. I am interested in families $\cal S$ of subsets of $E$ with the property that if $A \in {\cal S}$ and $B \subset A$ then $B \in {\cal S}$. My question is: How many such families are there? I'd be happy with a reasonable upper estimate. Bonus if you can estimate the number of such $\cal S$ with fixed $\#{\cal S}$.

(By the way, does this property have a name? It occurs in one possible definition of a matroid but being a matroid is a stronger condition. Do we know how many matroids with a fixed ground set are there?)

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ en.wikipedia.org/wiki/Dedekind_number $\endgroup$
    – Sam Hopkins
    Jun 24, 2021 at 22:14
  • 1
    $\begingroup$ You are just counting simplicial complexes on $n$ elements... $\endgroup$
    – Sam Hopkins
    Jun 24, 2021 at 22:14
  • 1
    $\begingroup$ One way to say the number of such $\mathcal{S}$ with $\#\mathcal{S}=k$ is the number of elements of rank $k$ in the free distributive lattice on $n$ elements: see en.wikipedia.org/wiki/…. Anyways these kinds of questions are well-studied but the numbers become intractable immediately (at least that is my impression) $\endgroup$
    – Sam Hopkins
    Jun 24, 2021 at 22:37
  • 2
    $\begingroup$ For the "bonus question," see the OEIS: oeis.org/A269699 $\endgroup$
    – Sam Hopkins
    Jun 24, 2021 at 23:37
  • 1
    $\begingroup$ In particular the reference (doi.org/10.1016/0012-365X(80)90156-9) shows that for fixed $k$, the number of such $\mathcal{S}$ as a function of $n$ is given by a polynomial in $n$. $\endgroup$
    – Sam Hopkins
    Jun 24, 2021 at 23:39

1 Answer 1

Reset to default
3
$\begingroup$

This is Dedekind's Problem. The best asymptotic estimate is due to Korshunov, but his paper is about 100 pages long. Someone spent almost $2,000 getting it translated to English, but that translation is not publically available. Sapozhenko's proof seems to be about half as long. I believe some of the papers one might need to understand his proof have also been translated into English and the same person I referred to has those translations. You can also look at Kleitman and Markowsky.

Improve this answer
$\endgroup$

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.