5
$\begingroup$

Lets denote by $a(n)$ the number of families $\mathcal{F} \subseteq \mathcal{P}(X)$ on a finite set $X$ with $n$ elements satisfying:

  • $\emptyset, X \in \mathcal{F}$
  • For all $U, V \in \mathcal{F}$ it holds that $U \cap V \in \mathcal{F}$.
  • For all nonempty disjoint $U, V \in \mathcal{F}$ there exists $H \in \mathcal{F}$ such that $X \setminus H \in \mathcal{F}$ and $U \subseteq H$ and $V \subseteq X \setminus H $.

If we were to drop the last restriction, I understand the brute force approach would be the following:

a'(n)=Length[
  Select[Subsets[Subsets[Range[n]]],
   And[MemberQ[#, {}], MemberQ[#, Range[n]],
     SubsetQ[#, Intersection @@@ Tuples[#, 2]]&]]

However, I am not sure how to alter the code such that the third condition is satisfied as well. Can someone help me and write a code to enumerate the sequence $a(n)$?

This sequence has a very significant mathematical interpretation, namely in that it is related to convexity spaces.

Note that I am hoping to calculate $a(n)$ at least up to $a(4)$.

$\endgroup$
5
  • $\begingroup$ No, the third condition is different and I can’t quite relate the code to this problem. $\endgroup$
    – user227351
    Aug 5, 2022 at 18:26
  • $\begingroup$ Unless I'm missing something, isn't the last condition impossible to satisfy? Let $U,V=X\in\mathcal{F}$. Then $V=X\subseteq X\setminus H$ implies $H=\varnothing$, but $U=X\not\subseteq\varnothing$? $\endgroup$
    – Lukas Lang
    Aug 7, 2022 at 21:09
  • $\begingroup$ You are right. I corrected my question. $\endgroup$
    – user227351
    Aug 7, 2022 at 21:41
  • $\begingroup$ You are interested in matroids? $\endgroup$ Aug 20, 2022 at 12:43
  • $\begingroup$ @PerAlexandersson, do you perhaps mean antimatroids? $\endgroup$
    – user227351
    Oct 4, 2022 at 9:17

1 Answer 1

4
+150
$\begingroup$

Here's a naive brute-force approach using lists. First, let's take advantage of the fact that in Subsets[X], {} always appears first and X appears last; and that in Subsets[PX], the order of elements in PX is preserved. That means we can just check the first and last element to see if {} and X are members:

bounded[F_, X_] := Cases[F, {{}, ___, X}]

Then we test for intersections as you do, except we use Subsets; while Tuples is faster, this lets us perform fewer Intersections:

intersectionClosedQ[F_] := 
 SubsetQ[F, Intersection @@@ Subsets[F, {2}]]

For the third condition, we break it up into several steps. First we get the pairs of nonempty disjoint sets. We'll do this readably by filtering the length-2 subsets of $\mathcal{F}$—we can optimize later! (In particular, if we had kept track of information about which elements were formed as intersections of which other elements in the previous step, we could look at the preimage of {}. Maybe we should have also hung onto Subsets[F].) We can also take advantage of the fact that we know the first element of any family will be {}, so we can just drop the first element as a way to consider only nonempty sets, instead of writing something like DeleteCases[F, {}].

disjointPairs[F_] := Select[Subsets[Drop[F, 1], {2}], Apply[DisjointQ]]

Then we create the weak closure-under-complementation condition. "There exists" translates into Or or AnyTrue, and Complement implements the set complement. (The f[a][b] syntax just makes mapping a little more convenient via when we're ready to do it (via AllTrue), but we could just as well use a function with two arguments instead.) I'm guessing it's better computationally to compute the set of all pairs of complemented sets in $\mathcal{F}$ first. We also preserve "duplicates"—pairs of the form $(H, \bar{H})$ and $(\bar{H}, H)$ are both included—so that comparing is easy later.

complementedPairs[F_, X_] := Select[{#, Complement[X, #]} & /@ F, MemberQ[F, #[[2]]] &]

weaklyComplementedPairQ[cpF_][disjointpair_] := AnyTrue[cpF,
  And @@ MapThread[SubsetQ, {#, disjointpair}] &]

(* A potential optimization would be to compute disjointPairs[F]
   first, and only proceed if nonempty. *)

weaklyComplementedQ[F_, X_] := AllTrue[disjointPairs[F], 
      weaklyComplementedPairQ[complementedPairs[F, X]]]

Putting it all together:

validFamilies[n_Integer?Positive] := With[{X = Range[n]},
 Select[bounded[Subsets@Subsets@X, X],
   F |-> intersectionClosedQ[F] && weaklyComplementedQ[F, X]
  ]]

bruteForceA[n_Integer?Positive] := Length[validFamilies[n]]

With these definitions, we find that Table[bruteForceA[n], {n,1,4}] is {1, 4, 35, 857}. Evaluating bruteForceA[5] takes up over 25 GB of temporary storage and then crashes my kernel. So, some optimization is required to proceed further. I recommend inspecting validFamilies[n] for small values of n to make sure it works as expected! This computation can be optimized far more than it currently is, so perhaps bruteForceA[5] is not totally intractable; also, there's the (admittedly small) chance of a closed-form solution. Even "carving out" certain spaces of valid families, getting a closed form for those, then counting the rest manually might help.

If I have time, I'd like to try to optimize this! We might Compile to C code and represent subsets as integers. Also, instead of building all families and then filtering, we could try to find a way to only build valid families in the first place.

$\endgroup$
8
  • $\begingroup$ It seems to work as far as checking valid families. Thank you! $\endgroup$
    – user227351
    Aug 11, 2022 at 0:49
  • $\begingroup$ It would truly appreciate if you tried to optimise this so that $a(5)$ can be computed. I would be prepared to award another bounty. $\endgroup$
    – user227351
    Aug 11, 2022 at 0:50
  • $\begingroup$ @TianVlašić it's a fun problem! there might be some interesting mathematical structure too. I'll comment if I update my solution. also note: the optimization to skip an empty set of disjoint pairs was incorrect, but did not affect the computation results. $\endgroup$
    – thorimur
    Aug 11, 2022 at 1:03
  • $\begingroup$ I have awarded the bounty to you since nobody answered. I think it would be appropriate for you to also answer the edited part of the question. I would be very grateful! $\endgroup$
    – user227351
    Oct 8, 2022 at 14:38
  • $\begingroup$ @user227351 Sorry, but I don't really have the time right now. I may want to come back to this in the future, but I'm not really comfortable promising that I will—so, it's probably best to assume I won't come back to it, unfortunately. Please rescind the bounty. $\endgroup$
    – thorimur
    Oct 14, 2022 at 21:40

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.