[go: up one dir, main page]

login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A327112
Number of set-systems covering n vertices with cut-connectivity >= 2, or 2-cut-connected set-systems.
9
0, 0, 4, 72, 29856
OFFSET
0,3
COMMENTS
A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. The cut-connectivity of a set-system is the minimum number of vertices that must be removed (along with any empty or duplicate edges) to obtain a disconnected or empty set-system. Except for cointersecting set-systems (A327040), this is the same as vertex-connectivity (A327334, A327051).
EXAMPLE
Non-isomorphic representatives of the a(3) = 72 set-systems:
{{123}}
{{3}{123}}
{{23}{123}}
{{2}{3}{123}}
{{1}{23}{123}}
{{3}{23}{123}}
{{12}{13}{23}}
{{13}{23}{123}}
{{1}{2}{3}{123}}
{{1}{3}{23}{123}}
{{2}{3}{23}{123}}
{{3}{12}{13}{23}}
{{2}{13}{23}{123}}
{{3}{13}{23}{123}}
{{12}{13}{23}{123}}
{{1}{2}{3}{23}{123}}
{{2}{3}{12}{13}{23}}
{{1}{2}{13}{23}{123}}
{{2}{3}{13}{23}{123}}
{{3}{12}{13}{23}{123}}
{{1}{2}{3}{12}{13}{23}}
{{1}{2}{3}{13}{23}{123}}
{{2}{3}{12}{13}{23}{123}}
{{1}{2}{3}{12}{13}{23}{123}}
MATHEMATICA
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]]]]]]]]];
vConn[sys_]:=If[Length[csm[sys]]!=1, 0, Min@@Length/@Select[Subsets[Union@@sys], Function[del, Length[csm[DeleteCases[DeleteCases[sys, Alternatives@@del, {2}], {}]]]!=1]]];
Table[Length[Select[Subsets[Subsets[Range[n], {1, n}]], Union@@#==Range[n]&&vConn[#]>=2&]], {n, 0, 3}]
CROSSREFS
Covering 2-cut-connected graphs are A013922, if we assume A013922(2) = 1.
Covering 1-cut-connected antichains (clutters) are A048143, if we assume A048143(0) = A048143(1) =0.
Covering 2-cut-connected antichains (blobs) are A275307, if we assume A275307(1) = 0.
Covering set-systems with cut-connectivity 2 are A327113.
2-vertex-connected integer partitions are A322387.
BII-numbers of set-systems with cut-connectivity >= 2 are A327101.
The cut-connectivity of the set-system with BII-number n is A326786(n).
Sequence in context: A087315 A081460 A327040 * A284673 A055556 A168299
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Aug 24 2019
STATUS
approved