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

====== Maximum Frustration of Bipartite Signed Graphs ======

===== Abstract for the Combinatorics Seminar 2009 July 24 =====

This lecture is the Ph.D. thesis defense of Mr. Bowlin. His examining committee is Laura Anderson, Steven Dougherty (University of Scranton), Fernando Guzman, and Thomas Zaslavsky (chair).

Everyone is welcome to attend.

==== Abstract ====

A //signed graph// is a graph where each edge is labeled as either positive or negative. A circle is //positive// if the product of edge labels is positive, and //negative// if the product is negative. The //frustration index// is the least number of edges that need to be removed so that every remaining circle is positive. The //maximum frustration// of a graph is the maximum frustration index over all possible sign labellings.

I prove two results about the maximum frustration of a complete bipartite graph //K<sub>l,r</sub>// with //l// left vertices and //r// right vertices. First, it is bounded above by\\
    //r// (//l///2) { 1 − C( //l//-1, [(//l//-1)/2] ) }\\
where [x] is the greatest integer in x. Second, for each //K<sub>l,r</sub>// there is essentially at most one sign labelling that attains this bound.

The main techniques used are linear programming and matrix theory. I derived the bound using linear programming, and my matrix results prove that the signed graphs which attain the bound are unique. With these two results, I was able to compute exact formulas for the maximum frustration of //K<sub>l,r</sub>// when //l// < 7.

In addition to the main theorems, I have two results about the frustration index of signed complete bipartite graph when the bipartite adjacency matrix is a Hadamard matrix.


----