Today I began thinking more precisely about the structure of the 3XOR instance and what the conflict graph is going to look like. What I believe to have found today is that its not the upper bound on the maximum eigenvalue that is going to be interesting for these SoS-hard instance-hamiltonians, but rather the lower bound, which is the size of the largest independent set. I am still not sure though, my logic was the following, bipartite expansion of the original graph should make it less likely for clauses to share a lot of vertices, including the cases when the number vertices they share is odd. But writing this out now it does not sound right. Ok its a 3XOR instance, the clauses won't share all 3 variables by construction, they can either share 2, 1, or 0. My gut tells me it should be significantly less likely that any two clauses share 2 variables, which may come from expansion: like if a bunch of clauses all share 2 variables, you can probably get some estimate of the boundary and show that its smaller than the expansion gaurantee. So it seems like most of the probability mass should be on either sharing 1 variable or none. If its none, the terms commute, so the question is how many clauses on average are going to share 1 vertex? **Edit**: The lower bound does not work! The commutation index is defined as the maximum over all polynomials that obey the commutation algebra, which is what the independent set number lower bounds, it certainly does not say anything about the max eigenvalue of a specific polynomial in that algebra..