5
$\begingroup$

I encountered the following combinatorics problem in my research, and I'd like to know if there is a reference or an easy solution for such a problem.

Given a partially ordered set $\mathscr P$, an antichain is a subset of $\mathscr P$ such that no two elements can be compared.

Fix positive integers $n$ and $k$. Define $\mathscr A_{n,k}$ to be the set of all size-$k$ antichains taken from the poset of subsets of $[n] = \{1, \cdots n \}$. Define $A_{n,k} = \mathscr A_{n,k} / S_n$ where the permutation group $S_n$ acts on $\mathscr A_{n,k}$ by extending the natural action of $S_n$ on $[n]$; for $\sigma \in S_n$ and $\mathscr U \in \mathscr A_{n,k}$, $\sigma( \mathscr U) := \{\sigma(U) | U \in \mathscr U \}$. Alternatively, \begin{align*} & \mathscr A_{n,k} := \left\{ \{ U_1, \dots, U_k \} | \emptyset \neq U_i \subseteq [n], \forall i \neq j, U_i \not\subseteq U_j \right\} \\ & A_{n,k} := \mathscr A_{n,k} / S_n \end{align*}

Problem. Enumerate all elements of $A_n = \bigcup_{k=1}^\infty A_{n,k}$.

The problem is in data science context; I'd like to have an algorithm that computes, say, $A_{10}$ that doesn't take too long. But I'll be computing it only once, so it's fine if the computation takes a whole week (but not a whole year!). Naive enumeration and checking for all overlaps will take quite long; for example, the set of all size-5 antichains of $[10]$ has size $(2^{10})^5 \approx 10^{15}$.

Remark. One way to understand $\mathscr A_{n,k}$ is to see it as the collection of all hypergraphs on $[n]$ such that one hyperedge never includes another; it is of completely opposite nature to abstract simplicial complexes. Also, following Brendan McKay's observation, I edited the question and used the antichain terminology.

$\endgroup$
13
  • 1
    $\begingroup$ @kodlu, $|\mathscr{U}|=k$, not $|U_i|=k$. $\endgroup$
    – RobPratt
    Apr 23, 2020 at 13:00
  • 2
    $\begingroup$ For $k=1,2,\ldots$, $|A_{10,k}| = 10,95,1627,51194,2599518,170816889,\ldots$. That much took about 70 seconds but $|A_{10,7}|$ took 40 mins so far and I'm going to bed. I'll report tomorrow. I think you won't actually be able to store the full set. $\endgroup$ Apr 23, 2020 at 15:08
  • 1
    $\begingroup$ $|A_{10,7}|=11988870351$ in 80 mins. Estimate 800 billion for $A_{10,8}$ in about 130 hours -- I won't do it. Incidentally these are called antichains. $\endgroup$ Apr 23, 2020 at 15:26
  • 1
    $\begingroup$ There are 252 sets of size 5 and trivially none of them is a subset of another. There are $2^{252}-1$ ways to choose a non-empty collection of 5-sets. Moreover, the group action can reduce the number by at most $10!$. This means that $A_{10}$ is greater than $10^{69}$. $\endgroup$ Apr 24, 2020 at 0:53
  • 3
    $\begingroup$ See oeis.org/A306505 which includes the antichain with just the empty set. $\endgroup$ Apr 24, 2020 at 1:50

1 Answer 1

1
$\begingroup$

The following is basic information which should be part of an introductory combinatorics (or even computer science) course. It should help give you a good sense of scale.

It is clear that the power set of the power set of the base set contains (an inverse image of) your desired collection, and so an upper bound on the size of your collection is $2^n$ where $n=2^{10}$. As observed by Brendan McKay, quotienting out by all permutations puts a small dent in $n$, the exponent, but we still get $2^{1000}$ as a rough estimate after quotienting.

As Brendan also observed, one can take the middle sized sets and look at antichains formed from them. Here one has about $2^m$ choices, each of them mapping to part of your collection, with $m$ being the nth central binomial coefficient. Again being optimistic about the quotient map, $m$ is roughly 230 for a base set of size 10.

Finer estimates are available, but note that including a small or large set takes a good sized bite out of allowed middle sized sets for the antichain, and so the real exponent won't be much more than 230. Even if it is as high as 500, what are you going to do with it?

Gerhard "Sometimes Enough Is Too Much" Paseman, 2020.04.24.

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