A326853 -id:A326853 - cp's OEIS frontend

A327037 Number of pairwise intersecting set-systems covering n vertices where every two vertices appear together in some edge (cointersecting).

1, 1, 3, 21, 913, 1183295, 909142733955, 291200434282476769116160

Offset: 0

Gus Wiseman, Aug 17 2019

A set-system is a finite set of finite nonempty sets. Its elements are sometimes called edges. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. This sequence counts pairwise intersecting, covering set-systems that are cointersecting, meaning their dual is pairwise intersecting.

			The a(0) = 1 through a(3) = 21 set-systems:
  {}  {{1}}  {{1,2}}      {{1,2,3}}
             {{1},{1,2}}  {{1},{1,2,3}}
             {{2},{1,2}}  {{2},{1,2,3}}
                          {{3},{1,2,3}}
                          {{1,2},{1,2,3}}
                          {{1,3},{1,2,3}}
                          {{2,3},{1,2,3}}
                          {{1},{1,2},{1,2,3}}
                          {{1},{1,3},{1,2,3}}
                          {{1,2},{1,3},{2,3}}
                          {{2},{1,2},{1,2,3}}
                          {{2},{2,3},{1,2,3}}
                          {{3},{1,3},{1,2,3}}
                          {{3},{2,3},{1,2,3}}
                          {{1,2},{1,3},{1,2,3}}
                          {{1,2},{2,3},{1,2,3}}
                          {{1,3},{2,3},{1,2,3}}
                          {{1},{1,2},{1,3},{1,2,3}}
                          {{2},{1,2},{2,3},{1,2,3}}
                          {{3},{1,3},{2,3},{1,2,3}}
                          {{1,2},{1,3},{2,3},{1,2,3}}

Intersecting covering set-systems are A305843.
The unlabeled multiset partition version is A319765.
The case where the dual is strict is A319774.
The BII-numbers of these set-systems are A326912.
The non-covering version is A327038.
Cointersectng covering set-systems are A327040.
Cf. A003465, A319767, A326853, A326854, A326910.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],Intersection[#1,#2]=={}&],Union@@#==Range[n]&&stableQ[dual[#],Intersection[#1,#2]=={}&]&]],{n,0,4}]

Inverse binomial transform of A327038.

a(6)-a(7) from Christian Sievers, Aug 18 2024

A327053 Number of T_0 (costrict) set-systems covering n vertices where every two vertices appear together in some edge (cointersecting).

Original entry on oeis.org

1, 1, 3, 62, 24710, 2076948136, 9221293198653529144, 170141182628636920684331812494864430896

Offset: 0

Gus Wiseman, Aug 18 2019

A set-system is a finite set of finite nonempty sets. Its elements are sometimes called edges. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. This sequence counts covering set-systems whose dual is strict and pairwise intersecting.

			The a(1) = 1 through a(2) = 3 set-systems:
  {}  {{1}}  {{1},{1,2}}
             {{2},{1,2}}
             {{1},{2},{1,2}}
The a(3) = 62 set-systems:
  1 2 123    1 2 3 123    1 2 12 13 23   1 2 3 12 13 23   1 2 3 12 13 23 123
  1 3 123    1 12 13 23   1 2 3 12 123   1 2 3 12 13 123
  2 3 123    1 2 12 123   1 2 3 13 123   1 2 3 12 23 123
  1 12 123   1 2 13 123   1 2 3 23 123   1 2 3 13 23 123
  1 13 123   1 2 23 123   1 3 12 13 23   1 2 12 13 23 123
  12 13 23   1 3 12 123   2 3 12 13 23   1 3 12 13 23 123
  2 12 123   1 3 13 123   1 2 12 13 123  2 3 12 13 23 123
  2 23 123   1 3 23 123   1 2 12 23 123
  3 13 123   2 12 13 23   1 2 13 23 123
  3 23 123   2 3 12 123   1 3 12 13 123
  12 13 123  2 3 13 123   1 3 12 23 123
  12 23 123  2 3 23 123   1 3 13 23 123
  13 23 123  3 12 13 23   2 3 12 13 123
             1 12 13 123  2 3 12 23 123
             1 12 23 123  2 3 13 23 123
             1 13 23 123  1 12 13 23 123
             2 12 13 123  2 12 13 23 123
             2 12 23 123  3 12 13 23 123
             2 13 23 123
             3 12 13 123
             3 12 23 123
             3 13 23 123
             12 13 23 123

The pairwise intersecting case is A319774.
The BII-numbers of these set-systems are the intersection of A326947 and A326853.
The non-T_0 version is A327040.
The non-covering version is A327052.
Cf. A003465, A305843, A319767, A326854, A327020, A327037, A327039.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&UnsameQ@@dual[#]&&stableQ[dual[#],Intersection[#1,#2]=={}&]&]],{n,0,3}]

Inverse binomial transform of A327052.

a(5)-a(7) from Christian Sievers, Feb 04 2024

A327100 BII-numbers of antichains of sets with cut-connectivity 1.

Original entry on oeis.org

1, 2, 8, 20, 36, 48, 128, 260, 272, 276, 292, 304, 308, 320, 516, 532, 544, 548, 560, 564, 576, 768, 784, 788, 800, 804, 1040, 1056, 2064, 2068, 2080, 2084, 2096, 2100, 2112, 2304, 2308, 2324, 2336, 2352, 2560, 2564, 2576, 2596, 2608, 2816, 2820, 2832, 2848

Offset: 1

Gus Wiseman, Aug 22 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system (finite set of finite nonempty sets) has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.

We define the cut-connectivity of a set-system to be the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a disconnected or empty set-system, with the exception that a set-system with one vertex has cut-connectivity 1. Except for cointersecting set-systems (A326853, A327039, A327040), this is the same as vertex-connectivity (A327334, A327051).

			The sequence of all antichains of sets with vertex-connectivity 1 together with their BII-numbers begins:
    1: {{1}}
    2: {{2}}
    8: {{3}}
   20: {{1,2},{1,3}}
   36: {{1,2},{2,3}}
   48: {{1,3},{2,3}}
  128: {{4}}
  260: {{1,2},{1,4}}
  272: {{1,3},{1,4}}
  276: {{1,2},{1,3},{1,4}}
  292: {{1,2},{2,3},{1,4}}
  304: {{1,3},{2,3},{1,4}}
  308: {{1,2},{1,3},{2,3},{1,4}}
  320: {{1,2,3},{1,4}}
  516: {{1,2},{2,4}}
  532: {{1,2},{1,3},{2,4}}
  544: {{2,3},{2,4}}
  548: {{1,2},{2,3},{2,4}}
  560: {{1,3},{2,3},{2,4}}
  564: {{1,2},{1,3},{2,3},{2,4}}

Positions of 1's in A326786.
The graphical case is A327114.
BII numbers of antichains with vertex-connectivity >= 1 are A326750.
BII-numbers for cut-connectivity 2 are A327082.
BII-numbers for cut-connectivity 1 are A327098.
Cf. A000120, A000372, A006126, A048143, A048793, A070939, A322390, A326031, A326749, A326751, A327071, A327111.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Select[Range[0,100],stableQ[bpe/@bpe[#],SubsetQ]&&cutConnSys[Union@@bpe/@bpe[#],bpe/@bpe[#]]==1&]

If (+) is union and (-) is complement, we have A327100 = A058891 + (A326750 - A326751).

A326854 BII-numbers of T_0 (costrict), pairwise intersecting set-systems where every two vertices appear together in some edge (cointersecting).

Original entry on oeis.org

0, 1, 2, 5, 6, 8, 17, 24, 34, 40, 52, 69, 70, 81, 84, 85, 88, 98, 100, 102, 104, 112, 116, 120, 128, 257, 384, 514, 640, 772, 1029, 1030, 1281, 1284, 1285, 1408, 1538, 1540, 1542, 1664, 1792, 1796, 1920, 2056, 2176, 2320, 2592, 2880, 3120, 3152, 3168, 3184

Offset: 1

Gus Wiseman, Aug 18 2019

nonn

A set-system is a finite set of finite nonempty sets. Its elements are sometimes called edges. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. This sequence gives all BII-numbers (defined below) of pairwise intersecting set-systems whose dual is strict and pairwise intersecting.

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18.

			The sequence of all set-systems that are pairwise intersecting, cointersecting, and costrict, together with their BII-numbers, begins:
    0: {}
    1: {{1}}
    2: {{2}}
    5: {{1},{1,2}}
    6: {{2},{1,2}}
    8: {{3}}
   17: {{1},{1,3}}
   24: {{3},{1,3}}
   34: {{2},{2,3}}
   40: {{3},{2,3}}
   52: {{1,2},{1,3},{2,3}}
   69: {{1},{1,2},{1,2,3}}
   70: {{2},{1,2},{1,2,3}}
   81: {{1},{1,3},{1,2,3}}
   84: {{1,2},{1,3},{1,2,3}}
   85: {{1},{1,2},{1,3},{1,2,3}}
   88: {{3},{1,3},{1,2,3}}
   98: {{2},{2,3},{1,2,3}}
  100: {{1,2},{2,3},{1,2,3}}
  102: {{2},{1,2},{2,3},{1,2,3}}

Equals the intersection of A326947, A326910, and A326853.
These set-systems are counted by A319774 (covering).
The non-T_0 version is A327061.
Cf. A029931, A048793, A051185, A305843, A319765, A326031, A327037, A327038, A327041, A327052, A327053.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Select[Range[0,10000],UnsameQ@@dual[bpe/@bpe[#]]&&stableQ[bpe/@bpe[#],Intersection[#1,#2]=={}&]&&stableQ[dual[bpe/@bpe[#]],Intersection[#1,#2]=={}&]&]

A327060 Number of non-isomorphic weight-n weak antichains of multisets where every two vertices appear together in some edge (cointersecting).

Original entry on oeis.org

1, 1, 3, 4, 9, 11, 30, 42, 103, 194, 443

Offset: 0

Gus Wiseman, Aug 18 2019

A multiset partition is a finite multiset of finite nonempty multisets. It is a weak antichain if no part is a proper submultiset of any other.

			Non-isomorphic representatives of the a(0) = 1 through a(5) = 11 multiset partitions:
  {}  {{1}}  {{11}}    {{111}}      {{1111}}        {{11111}}
             {{12}}    {{122}}      {{1122}}        {{11222}}
             {{1}{1}}  {{123}}      {{1222}}        {{12222}}
                       {{1}{1}{1}}  {{1233}}        {{12233}}
                                    {{1234}}        {{12333}}
                                    {{11}{11}}      {{12344}}
                                    {{12}{12}}      {{12345}}
                                    {{12}{22}}      {{11}{122}}
                                    {{1}{1}{1}{1}}  {{12}{222}}
                                                    {{33}{123}}
                                                    {{1}{1}{1}{1}{1}}

Antichains are A000372.
The BII-numbers of these set-systems are the intersection of A326853 and A326704.
Cointersecting set-systems are A327039.
The set-system version is A327057, with covering case A327058.
Cf. A006126, A007716, A051185, A305844, A326965, A327020, A327059, A327062.

A327128 Number of set-systems with n vertices whose edge-set has cut-connectivity 1.

Original entry on oeis.org

0, 1, 2, 27, 2084

Offset: 0

Gus Wiseman, Sep 02 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. We define the cut-connectivity (A326786, A327237, A327126) of a set-system to be the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a disconnected or empty set-system, with the exception that a set-system with one vertex has cut-connectivity 1. Except for cointersecting set-systems (A326853, A327039, A327040), this is the same as vertex-connectivity (A327334, A327051).

The covering version is A327197.
The BII-numbers of these set-systems are A327098.
Cf. A003465, A052442, A052443, A259862, A323818, A326786, A327101, A327112, A327113, A327114, A327126, A327229.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],cutConnSys[Union@@#,#]==1&]],{n,0,3}]

Binomial transform of A327197.

A327061 BII-numbers of pairwise intersecting set-systems where every two covered vertices appear together in some edge (cointersecting).

Original entry on oeis.org

0, 1, 2, 4, 5, 6, 8, 16, 17, 24, 32, 34, 40, 52, 64, 65, 66, 68, 69, 70, 72, 80, 81, 84, 85, 88, 96, 98, 100, 102, 104, 112, 116, 120, 128, 256, 257, 384, 512, 514, 640, 772, 1024, 1025, 1026, 1028, 1029, 1030, 1152, 1280, 1281, 1284, 1285, 1408, 1536, 1538

Offset: 1

Gus Wiseman, Aug 18 2019

nonn

A set-system is a finite set of finite nonempty sets. Its elements are sometimes called edges. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. This sequence gives all BII-numbers (defined below) of pairwise intersecting set-systems whose dual is also pairwise intersecting.

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18.

			The sequence of all pairwise intersecting, cointersecting set-systems together with their BII-numbers begins:
   0: {}
   1: {{1}}
   2: {{2}}
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   8: {{3}}
  16: {{1,3}}
  17: {{1},{1,3}}
  24: {{3},{1,3}}
  32: {{2,3}}
  34: {{2},{2,3}}
  40: {{3},{2,3}}
  52: {{1,2},{1,3},{2,3}}
  64: {{1,2,3}}
  65: {{1},{1,2,3}}
  66: {{2},{1,2,3}}
  68: {{1,2},{1,2,3}}
  69: {{1},{1,2},{1,2,3}}
  70: {{2},{1,2},{1,2,3}}

The unlabeled multiset partition version is A319765.
Equals the intersection of A326853 and A326910.
The T_0 version is A326854.
These set-systems are counted by A327037 (covering) and A327038 (not covering).
Cf. A029931, A048793, A051185, A305843, A319774, A326031, A327039, A327040, A327041, A327057.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Select[Range[0,100],stableQ[bpe/@bpe[#],Intersection[#1,#2]=={}&]&&stableQ[dual[bpe/@bpe[#]],Intersection[#1,#2]=={}&]&]

A327234 Smallest BII-number of a set-system with cut-connectivity n.

Original entry on oeis.org

0, 1, 4, 52, 2868

Offset: 0

Gus Wiseman, Sep 03 2019

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system (finite set of finite nonempty sets) has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.
We define the cut-connectivity (A326786) of a set-system to be the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a disconnected or empty set-system, with the exception that a set-system with one vertex has cut-connectivity 1. Except for cointersecting set-systems (A326853), this is the same as vertex-connectivity (A327051).
Conjecture: a(n > 1) = A327373(n) = the BII-number of K_n.

			The sequence of terms together with their corresponding set-systems:
     0: {}
     1: {{1}}
     4: {{1,2}}
    52: {{1,2},{1,3},{2,3}}
  2868: {{1,2},{1,3},{2,3},{1,4},{2,4},{3,4}}

The same for spanning edge-connectivity is A327147.
The cut-connectivity of the set-system with BII-number n is A326786(n).
Cf. A000120, A002450, A029931, A048793, A070939, A259862, A326031, A327082, A327098, A327125, A327126, A327127, A327373.

cp's OEIS Frontend

A327037 Number of pairwise intersecting set-systems covering n vertices where every two vertices appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A327053 Number of T_0 (costrict) set-systems covering n vertices where every two vertices appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A327100 BII-numbers of antichains of sets with cut-connectivity 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326854 BII-numbers of T_0 (costrict), pairwise intersecting set-systems where every two vertices appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327060 Number of non-isomorphic weight-n weak antichains of multisets where every two vertices appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

A327128 Number of set-systems with n vertices whose edge-set has cut-connectivity 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A327061 BII-numbers of pairwise intersecting set-systems where every two covered vertices appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327234 Smallest BII-number of a set-system with cut-connectivity n.

Views

Author

Keywords

Comments

Examples

Crossrefs