login
Number of set-systems covering n vertices with spanning edge-connectivity 2.
11

%I #5 Sep 01 2019 08:40:09

%S 0,0,0,32,9552

%N Number of set-systems covering n vertices with spanning edge-connectivity 2.

%C A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. The spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (without removing incident vertices) to obtain a disconnected or empty set-system.

%e The a(3) = 32 set-systems:

%e {12}{13}{23} {1}{12}{13}{23} {1}{2}{12}{13}{23} {1}{2}{3}{12}{13}{23}

%e {12}{13}{123} {2}{12}{13}{23} {1}{3}{12}{13}{23} {1}{2}{3}{12}{13}{123}

%e {12}{23}{123} {3}{12}{13}{23} {2}{3}{12}{13}{23} {1}{2}{3}{12}{23}{123}

%e {13}{23}{123} {1}{12}{13}{123} {1}{2}{12}{13}{123} {1}{2}{3}{13}{23}{123}

%e {1}{12}{23}{123} {1}{2}{12}{23}{123}

%e {1}{13}{23}{123} {1}{2}{13}{23}{123}

%e {2}{12}{13}{123} {1}{3}{12}{13}{123}

%e {2}{12}{23}{123} {1}{3}{12}{23}{123}

%e {2}{13}{23}{123} {1}{3}{13}{23}{123}

%e {3}{12}{13}{123} {2}{3}{12}{13}{123}

%e {3}{12}{23}{123} {2}{3}{12}{23}{123}

%e {3}{13}{23}{123} {2}{3}{13}{23}{123}

%t 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]]]]]]]]];

%t spanEdgeConn[vts_,eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds],Union@@#!=vts||Length[csm[#]]!=1&];

%t Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],spanEdgeConn[Range[n],#]==2&]],{n,0,3}]

%Y The BII-numbers of these set-systems are A327108.

%Y Set-systems with spanning edge-connectivity 1 are A327145.

%Y The restriction to simple graphs is A327146.

%Y Cf. A003465, A323818, A327069, A327109, A327111, A327144.

%K nonn,more

%O 0,4

%A _Gus Wiseman_, Aug 27 2019