3
$\begingroup$

Let’s call a collection $\mathcal{F} \subseteq \mathcal{P}(X)$ satisfying:

  • $\emptyset, X \in \mathcal{F}$
  • For all $U, V \in \mathcal{F}$ it holds that $U \cap V \in \mathcal{F}$.

special.

We can evaluate the number of special collections on a finite labeled set of n elements via the following code:

    Table[Length[
  Select[Subsets[Subsets[Range[n]]], 
   And[MemberQ[#, {}], MemberQ[#, Range[n]], 
     SubsetQ[#, Intersection @@@ Tuples[#, 2]]] &]], {n, 0, 4}]

Let us introduce the following three conditions that special collection may satisfy:

($\mathrm S_2$) For all $x,y \in X, \ x\neq y$ there exists $H \in \mathcal{F}$ such that $X \setminus H \in \mathcal{F}$ and $x \in H$ and $y \in X \setminus H $.

($\mathrm S_3$) For all $x \in X$ and $U \in \mathcal{F}, x \notin U$ there exists $H \in \mathcal{F}$ such that $X \setminus H \in \mathcal{F}$ and $x \in H$ and $U \subseteq X \setminus H $.

Let us thus by $a_2(n)$, $a_3(n)$, respectively, denote the denote the number of $\mathrm S_2$, that is, $\mathrm S_3$ special collections on a finite labeled set of n elements.

However, I am not sure how to alter the code such that the condition $\mathrm S_2$, that is, $\mathrm S_3$ is satisfied as well

Can someone help me to write a code to enumerate the sequences $a_2(n)$, $a_3(n)$?

I would like to offer my sincere graditude in advance!

$\endgroup$
4
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Kuba
    Nov 1, 2022 at 22:30
  • $\begingroup$ Been a while but… condition S_2 makes it a Haussdorf topology? $\endgroup$ Jun 25, 2023 at 15:22
  • $\begingroup$ Not quite. But I get the association you are having. These families are not topologies, but the statement of the axiom is similar to the Hausdorff ($T_2$) axiom. $\endgroup$
    – user227351
    Jun 25, 2023 at 15:45
  • $\begingroup$ This is a matroid, correct? It might be speedier to just compute the set of bases, and verify the basis exchange axiom on those. $\endgroup$ Jun 25, 2023 at 19:43

1 Answer 1

2
+100
$\begingroup$

Solution for $S_2$.

Here is a partial answer (for $S_2$ only), to give you some inspiration.

First, we'll define a function special[n] that generates all special collections (and $a(n)$, of course, is just the length of special[n]):

special[n_] :=
  Select[
   Subsets[Subsets[Range[n]]],
   And[
     MemberQ[#, {}],
     MemberQ[#, Range[n]],
     SubsetQ[#, Intersection @@@ Tuples[#, 2]]] &
   ];
a[n_] := Length@special[n];

Table[a[n], {n, 4}] (* {1, 4, 45, 2271} *)

Let's write your $S_2$ condition on $x$, $y$, and $F$:

s2[x_, y_, F_, n_] :=
 MemberQ[F,
  _?(H |-> With[{H1 = Complement[Range[n], H]},
      MemberQ[F, H1] && MemberQ[H, x] && MemberQ[H1, y]])]

Some comments on what's going on:

  1. MemberQ[list, _?f] returns true if at least one member of list satisfies the predicate f - similar to Length@Select[list, f]>0 but faster since it doesn't need to calculate f on every element of list.

  2. We use a handy |-> shortcut to define a function with a named argument $H$. With defines a shortcut for the complement of $H$, and the rest is a straightforward translation of your condition.

  3. Note that we need $n$ as an explicit argument to $s_2$ in order to calculate the complement.

We can check how $s_2$ works with specific arguments $x=1$ and $y=2$ in special[2]:

Column@special[2]
(*
{{{}, {1, 2}}},
{{{}, {1}, {1, 2}}},
{{{}, {2}, {1, 2}}},
{{{}, {1}, {2}, {1, 2}}}
 *)

Select[special[2], s2[1, 2, #, 2] &] (* {{{}, {1}, {2}, {1, 2}}} *)

Indeed, it's easy to see that only one family - all subsets of $\{1,2\}$ - satisfies $s_2$.

Now, for a given family $F$, we'll check whether it satisfies $s_2$ for all possible pairs $x, y$ (we only need to check for the subsets of length 2 given that the condition is symmetrical on $x, y$). Note that we can re-use the symbol $s_2$ as the function below has arity of 2 and the one defined before has arity of 4:

s2[F_, n_] := AllTrue[
  Subsets[Range[n], {2}],
  s2[#[[1]], #[[2]], F, n] &]

Finally,

a2[n_] := Length@Select[special[n], s2[#, n] &]

Here is a table for the values of $a_2(n)$ for $n=1\dots4$:

Table[a2[n], {n, 4}] (* {1, 1, 4, 167} *)

Answer for $S_3$.

I also wrote the code for $a_3(n)$, and the answer is $1,2,8,121$ for $n=1,\dots,4$.

It was pretty straightforward to do. But in general, I'm not a big fan of answering questions of the type "please write some code for me" :). You would get much bigger mileage from learning some programming basics and showing the places where you got stuck, as opposed to just asking strangers to solve a problem for you.

(Update) Solution for $S_3$.

After some consideration, I decided that's it would be too cruel to not share the solution. So here it is.

The $S_3$ condition is very similar to $S_2$:

s3[x_, U_, F_, n_] :=
 MemberQ[F,
  _?(H |-> With[{H1 = Complement[Range[n], H]},
      MemberQ[F, H1] && MemberQ[H, x] && SubsetQ[H1, U]])]

The somewhat tricky part is to generate all pairs $(x,U)$ for a given $F$. I suggest you to meditate on the following piece of code - most of the ingredients are as described above, FreeQ is the opposite of MemberQ, and Flatten[_, 1] can be looked up in the documentation.

allPairs[F_, n_] := 
 Flatten[(x |-> ({x, #} & /@ Select[F, FreeQ[#, x] &])) /@ Range[n], 
  1]

After this, the s3[F,n] definition is very similar to $s_2$:

s3[F_, n_] := AllTrue[
  allPairs[F, n],
  s3[#[[1]], #[[2]], F, n] &
  ]

And we are ready to calculate $a_3(n)$:

a3[n_] := Length@Select[special[n], s3[#, n] &]
Table[a3[n], {n, 4}] (* {1, 2, 8, 121} *)
$\endgroup$
11
  • $\begingroup$ Thank you so much! I completely understand how such straightforward answers deprive individuals of programming skills. However, I truly needed some values of those sequences for my ongoing research, and I don’t have time to invest in programming. $\endgroup$
    – user227351
    Oct 31, 2022 at 11:14
  • $\begingroup$ Would you mind providing the solution for $\mathrm I$ also since it is an unrelated condition? $\endgroup$
    – user227351
    Oct 31, 2022 at 11:15
  • $\begingroup$ You are welcome! To set your expectation, I’m unlikely to work on the last part - it’s slightly more involved and technical, and I have already satisfied my curiosity by working on the first two parts. $\endgroup$
    – Victor K.
    Oct 31, 2022 at 23:21
  • 1
    $\begingroup$ Re: “I don’t have time to invest in programming” - my friendly advice would be to find some time to invest, esp. given that with WL is extremely useful tool for a mathematician. “An Elementary Introduction” by S. Wolfram is a good start: wolfram.com/language/elementary-introduction/2nd-ed $\endgroup$
    – Victor K.
    Oct 31, 2022 at 23:25
  • 1
    $\begingroup$ Well then, I think this concludes it and that your answer deserves the bounty (@thorimur) :) ! $\endgroup$
    – user227351
    Nov 1, 2022 at 17:35

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.