**Problem of the Week**

**BUGCAT**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

**BingAWM**

**Math Club**

You are here: Homepage » Seminars - Academic year 2023-24 » Combinatorics Seminar » Garry Bowlin (Binghamton)

seminars:comb:abstract.200902bow

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*_{n} is equal to floor[(*n*-1)^{2}/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*_{l,r} is bounded above by

*r* · (*l*/2) · [ 1 − 2^{−(l−1)} binom( *l*−1, floor[(*l*−1)/2] ) ]

and that this bound is achieved by a signing of K_{l,2l−1}.

seminars/comb/abstract.200902bow.txt · Last modified: 2020/01/29 14:03 (external edit)

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported