====== Garry Bowlin (Binghamton) ======

====== Maximum Frustration in Signed Complete Bipartite Graphs ======

===== Abstract for the Combinatorics Seminar 2009 February 9 =====

The //frustration index// of a signed graph is the smallest number of edges whose sign reversal yields a balanced signed graph (i.e., where all circles have positive sign product). In 1966, Petersdorf showed that the maximum frustration of a signed complete graph //K//<sub>//n//</sub> is equal to floor[(//n//-1)<sup>2</sup>/4], and it is achieved by the all-negative signing. This is the only interesting graph family for which the problem has been solved. Using convex geometry, I show that the maximum frustration for a signed //K//<sub>//l,r//</sub> is bounded above by\\
\\
    //r// · (//l///2) · [ 1 − 2<sup>−(//l//−1)</sup> binom( //l//−1, floor[(//l//−1)/2] ) ]\\
\\
and that this bound is achieved by a signing of K<sub>//l//,2<sup>//l//−1</sup></sub>.


----