Independent sets in powers of odd cycles and the global Min-Cut problem

In the first part of this thesis we consider independent sets in Cd2n+1 . To date, upper bounds on alpha( Cd2m+1 ) have, except for very minor improvements, only been arrived at from the generic upper bound of alpha(G x H) ≤ alpha( G) x alpha*(H) or alpha(G n) ≤ theta(Gn), where alpha* is the fractional vertex packing number and theta is the Lovasz theta function. We introduce a structural technique that determines alpha( C38n+5 ) for 8n+5 prime or 2n+1 prime. We then use a stability result on independent sets in C24n+1 to determine alpha( C38n+1 ) for arbitrary n up to an additive error of 2. Finally, we classify all maximum independent sets in Cdk2d+1 .; In the second part of the thesis we present a linear programming model of the Global Min-Cut problem that requires O(n 2) variables and O(n3) constraints, thereby improving on the smallest previously known linear programming model, which required O(n3) vertices and O(n3) constraints. This model is asymmetric---some vertices and edges are treated differently than others. Yannakakis showed that any symmetric linear programming formulation of the perfect matching requires exponentially many constraints (the question of whether any polynomially-sized linear programming formulation exists is still open). While not conclusive here, the technique here is an example of how improvements may be obtained by not treating all vertices equally.