|
%I #27 Mar 28 2019 08:45:05
%S 0,3,4,7,9,11,13,16,17,19,21,24,25,28,29,32,33,36,37,40,42,45,46,48,
%T 50,53,54,57,58,61,63,66,66,69,70,73,75,78,79,82,83,85,87,90,91,94,95,
%U 98,99,102,103,106,108,111,112,114,116,119,120,123,124,127,129
%N Maximum frustration of complete bipartite graph K(n,6).
%C The maximum frustration of a graph is the maximum cardinality of a set of edges that contains at most half the edges of any cut-set. Another term that is used is "line index of imbalance". It is also equal to the covering radius of the coset code of the graph.
%H Robert Israel, <a href="/A245239/b245239.txt">Table of n, a(n) for n = 1..10000</a>
%H G. S. Bowlin, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i4p10">Maximum Frustration in Bipartite Signed Graphs</a>, Electr. J. Comb. 19(4) (2012) #P10.
%H R. L. Graham and N. J. A. Sloane, <a href="http://www.math.ucsd.edu/~ronspubs/85_01_covering_radius.pdf">On the Covering Radius of Codes</a>, IEEE Trans. Inform. Theory, IT-31(1985), 263-290
%H P. Solé and T. Zaslavsky, <a href="http://epubs.siam.org/doi/abs/10.1137/S0895480189174374">A Coding Approach to Signed Graphs</a>, SIAM J. Discr. Math 7 (1994), 544-553
%F a(n) = floor(66/32*n) - 1 if n=6 or n == 5 mod 8 or n == 2,4,7,9 or 11 mod 16 or n == 10,15,16 or 24 mod 32; a(n) = floor(66/32*n) - 2 if n == 1, 3, 17 or 19 mod 32, and floor(66/32*n) otherwise.
%F a(n+32) = a(n) + 66 except for n = 5.
%F a(n) = A245230(max(n,6), min(n,6)).
%F Empirical g.f.: -x^2*(x^35 -x^34 -x^33 +x^32 +x^31 -x^30 -x^29 -2*x^28 -x^27 -x^26 -2*x^24 -x^23 -x^22 -x^21 -x^20 -2*x^18 -2*x^17 -x^16 +x^15 -2*x^14 -2*x^13 -x^12 +x^11 -2*x^10 -2*x^9 -x^8 -x^6 -x^5 -2*x^4 -x^3 -x -3) / ((x -1)^2*(x +1)*(x^4 +1)*(x^8 +1)*(x^16 +1)). - _Colin Barker_, Sep 22 2014
%e For n=2 a set of edges that achieves the maximum cardinality a(2) = 3 is {(1,3),(1,4),(1,5)}.
%p A245239:= n -> floor(66/32*n) - piecewise(n=6 or (n mod 8 = 5) or member(n mod 16, {2,4,7,9,11}) or member(n mod 32, {10,15,16,24}),1, member(n mod 32, {1,3,17,19}),2,0): seq(A245239(n),n=1..30);
%t a[n_] := Floor[66n/32] - Which[n == 6 || Mod[n, 8] == 5 || MemberQ[{2, 4, 7, 9, 11}, Mod[n, 16]] || MemberQ[{10, 15, 16, 24}, Mod[n, 32]], 1, MemberQ[{1, 3, 17, 19}, Mod[n, 32]], 2, True, 0];
%t Array[a, 100] (* _Jean-François Alcover_, Mar 28 2019, from Maple *)
%o (PARI) concat(0, Vec(-x^2*(x^35 -x^34 -x^33 +x^32 +x^31 -x^30 -x^29 -2*x^28 -x^27 -x^26 -2*x^24 -x^23 -x^22 -x^21 -x^20 -2*x^18 -2*x^17 -x^16 +x^15 -2*x^14 -2*x^13 -x^12 +x^11 -2*x^10 -2*x^9 -x^8 -x^6 -x^5 -2*x^4 -x^3 -x -3) / ((x -1)^2*(x +1)*(x^4 +1)*(x^8 +1)*(x^16 +1)) + O(x^10001))) \\ _Colin Barker_, Sep 22 2014
%Y Cf. A245230, A245231, A245227, A245314.
%K nonn
%O 1,2
%A _Robert Israel_, Jul 14 2014
|
