{'fraction_non_alphanumeric': 0.06370182359919442, 'fraction_numerical': 0.018898115706127403, 'mean_word_length': 3.265976226903613, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 35, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs

The theta bodies of a polynomial ideal are a series of semidefinite programming relaxations of the convex hull of the real variety of the ideal. In this paper we construct the theta bodies of the vanishing ideal of cycles in a binary matroid. Applied to cuts in graphs, this yields a new hierarchy of semidefinite programming relaxations of the cut polytope of the graph. If the binary matroid avoids certain minors we can characterize when the first theta body in the hierarchy equals the cycle polytope of the matroid. Specialized to cuts in graphs, this result solves a problem posed by Lov\'asz.


Introduction
A central question in combinatorial optimization is to understand the polyhedral structure of the convex hull, conv(S), of a finite set S ⊆ R n . A typical instance is when S is the set of incidence vectors of a finite set of objects over which one is interested to optimize; think for instance of the problem of finding a shortest tour, a maximum independent set, or a maximum cut in a graph. As for hard combinatorial optimization problems one cannot hope in general to be able to find the complete linear description of the polytope conv(S), the objective is then to find good and efficient approximations of this polytope. Such approximations could be polyhedra, obtained by considering classes of valid linear inequalities. In recent years more general convex semidefinite programming (SDP) relaxations have been considered, which sometimes yield much tighter approximations than those from LP methods. This was the case for instance for the approximation of stable sets and coloring in graphs via the theta number introduced by Lovász [18], and for the approximation of the max-cut problem by Goemans and Williamson [8]. See e.g. [17] for an overview. These results spurred intense research activity on constructing stronger SDP relaxations for combinatorial optimization problems (cf. [12,13,17,20,22,23]). In this paper we revisit the hierarchy of SDP relaxations proposed by Gouveia et al. [9] which was inspired by a question of Lovász [19]. To present it we need some definitions.
Let I ⊆ R[x] be an ideal and V R (I ) = {x ∈ R n | f (x) = 0 ∀ f ∈ I } be its real variety. Throughout R[x] denotes the ring of multivariate polynomials in n variables x = (x 1 , . . . , x n ) over R and R[x] d its subspace of polynomials of degree at most d ∈ N. As the convex hull of V R (I ) is completely described by the (linear) polynomials f ∈ R[x] 1 that are non-negative on V R (I ), relaxations of conv(V R (I )) can be obtained by considering sufficient conditions for the non-negativity of linear polynomials on V R (I ).
A polynomial f ∈ R[x] is said to be a sum of squares (sos, for short) if f = t i=1 g 2 i for some polynomials g i ∈ R [x]. Moreover, f is said to be sos modulo the ideal I if f = t i=1 g 2 i + h for some polynomials g i ∈ R[x] and h ∈ I . In addition, if each g i has degree at most k, then we say that f is k-sos modulo I . Obviously any polynomial which is k-sos modulo I is non-negative over V R (I ). Following [9], for each k ∈ N, define the set TH k (I ) := {x ∈ R n | f (x) ≥ 0 for all f ∈ R[x] 1 k-sos modulo I }, called the k-th theta body of the ideal I . Note that TH k (I ) is a (convex) relaxation of conv(V R (I )), with conv(V R (I )) ⊆ TH k+1 (I ) ⊆ TH k (I ).
The ideal I is said to be TH k -exact if the equality conv(V R (I )) = TH k (I ) holds. The theta bodies TH k (I ) were introduced in [9], inspired by a question of Lovász [19,Problem 8.3] asking to characterize TH k -exact ideals, in particular when k = 1. This question of Lovász was motivated by the following result about stable sets in graphs: The stable set ideal of a graph G = (V, E) is TH 1 -exact if and only if the graph G is perfect. Recall that a subset of V is stable in G if it contains no edge. The stable set ideal of G is the vanishing ideal of the 0/1 characteristic vectors of the stable sets in G and is generated by the binomials x 2 i − x i (i ∈ V ) and x i x j ({i, j} ∈ E) (cf. [19] for details).
For a graph G, let I G be the vanishing ideal of the incidence vectors of cuts in G, and the cut polytope, CUT(G), be the convex hull of the incidence vectors of cuts in G. Following Problem 8.3, Problem 8.4 in [19] asks for a characterization of "cutperfect" graphs which are precisely those graphs G for which I G is TH 1 -exact. We answer this question (Corollary 4.12) by studying theta bodies in the more general setting of cycles in binary matroids. As an intermediate step we derive the theta bodies of I G which give rise to a new hierarchy of semidefinite programming relaxations of CUT(G).

Some notation
Let E be a finite set. For a subset F ⊆ E, let 1 F ∈ {0, 1} E denote its 0/1-incidence vector and χ F ∈ {±1} E its ±1-incidence vector, defined by 1 F e = 1, χ F e = −1 if e ∈ F and 1 F e = 0, χ F e = 1 otherwise. Throughout RE := R[x e | e ∈ E] denotes the polynomial ring with variables indexed by E. If F ⊆ E, we set x F := e∈F x e . For a symmetric matrix X ∈ R n×n , X 0 means that X is positive semidefinite, or equivalently, u T X u ≥ 0 for all u ∈ R n .
Contents of the paper Section 2 contains various preliminaries and some results of [9] needed in this paper. In Sect. 3 we introduce binary matroids, which provide the natural setting to present our results for cuts in graphs. A binary matroid is a pair M = (E, C) where E is a finite set and C is a collection of subsets of E (the cycles of M) closed under taking symmetric differences; for instance, cuts (resp., cycles) in a graph form binary matroids. In Sect. 3.1 we present a generating set for the cycle ideal I M (i.e. the vanishing ideal of the incidence vectors of the cycles C ∈ C) and a linear basis B of its quotient space RE/I M (cf. Theorem 3.4). Using this, we can explicitly describe the series of theta bodies TH k (I M) that approximate the cycle polytope CYC(M) (i.e. the convex hull of the incidence vectors of the cycles in C). In Sect. 3.2, we specialize these results to cuts in a graph G and show that B can then be indexed by T -joins of G. This enables a combinatorial description of the theta bodies TH k (I G) that converge to the cut polytope CUT(G) of G. Section 3.3 compares the semidefinite relaxations TH k (I G) to some known semidefinite relaxations of the cut polytope. In Sect. 3.4 the results from Sect. 3.1 are specialized to cycles in a graph. Section 3.5 contains a discussion about the complexity of constructing theta bodies. Section 4 studies the binary matroids M whose cycle ideal I M is TH 1 -exact (i.e., TH 1 (I M) = CYC(M)). Theorem 4.6 characterizes the TH 1 -exact cycle ideals I M when M does not have the three special minors F * 7 , R 10 and M * K 5 . As an application, we obtain characterizations of TH 1 -exact graphic and cographic matroids, and the latter answers Problem 8.4 in [19]. The paper contains several examples of binary matroids for which we exhibit the least k for which I M is TH k -exact. In Sect. 5 we do this computation for an infinite family of graphs; if C n is the circuit with n edges, then the smallest k for which TH k (I C n ) = CUT(C n ) is k = n/4 .

Ideals and combinatorial moment matrices
Let R[x] be the polynomial ring over R in the variables x = (x 1 , . . . , x n ). A non-empty subset I ⊆ R[x] is an ideal if I is closed under addition, and multiplication by ele- is said to be zero-dimensional if its (complex) variety: . By the Real Nullstellensatz (cf. [3]), I is real radical if and only if I = I(V R (I )). Therefore, I is zero-dimensional and real radical if and only if I = I(S) for a finite set S ⊆ R n . If I is real radical, and π W denotes the projection from R [n] to R W , then the elimination ideal I W is the vanishing ideal of π W (V R (I )), and there is a simple relationship between the k-th theta body of I and that of its elimination ideal I W : The quotient space R[x]/I is a R-vector space whose elements, called the cosets of I , are denoted as f The degree of f + I is defined as the smallest possible degree of g ∈ R[x] such that f − g ∈ I . The vector space R[x]/I has finite dimension if and only if I is zero-dimensional; moreover, |V C (I )| ≤ dim R[x]/I , with equality if and only if I is radical.
Gouveia et al. [9] give a geometric characterization of zero-dimensional real radical ideals that are TH 1 -exact. 1 for which the linear inequality f (x) ≥ 0 induces a facet of the polytope conv(S).
Theorem 2.2 [9] Let S ⊆ R n be a finite set. The ideal I(S) is TH 1 -exact (i.e., conv(S) = TH 1 (I(S))) if and only if S is a 2-level set.
More generally, Gouveia et al. [9,Sect. 4] show the implication: the reverse implication however does not hold for k ≥ 2 (see e.g. Remark 5.8 for a counterexample). We now mention an alternative more explicit formulation for the theta body TH k (I ) of an ideal I in terms of positive semidefinite combinatorial moment matrices. We first recall this class of matrices (introduced in [16  In other words, the matrix M B (y) is obtained as follows. The coordinates y l 's correspond to the elements b l + I of B; expand the product b i b j in terms of the basis B as To control which entries of y are involved in the truncated matrix M B k (y), it is useful to suitably choose the basis B. Namely, we choose B satisfying the following property: The combinatorial moment matrix M B 2 (y) for y = (y 0 , y 1 , . . . , 1 y 0 y 1 y 2 y 3 y 4 y 5 x 1 y 1 y 3 y 4 y 6 1 y 7 x 2 y 2 y 4 y 5 1 y 7 y 8 x 2 1 y 3 y 6 1 y 9 y 1 y 2 x 1 x 2 y 4 1 y 7 y 1 y 2 y 10 x 2 2 y 5 y 7 y 8 y 2 y 10 y 11 . Theorem 2.5 [9] Assume B satisfies (4) and B 1 = {1 + I, x 1 + I, . . . , x n + I }, and let the coordinates of y ∈ R B 2k indexed by B 1 be y 0 , y 1 , . . . , y n . Then TH k (I ) is equal to the closure of the set {(y 1 , . . . , y n ) | y ∈ R B 2k with M B k (y) 0 and y 0 = 1}.
When I = I(S) where S ⊆ {0, 1} n , the closure is not needed and TH k (I ) equals the set (5).
Theorem 2.5 implies that optimizing a linear objective function over TH k (I ) can be reformulated as a semidefinite program with the constraints M B k (y) 0 and y 0 = 1 which, for fixed k, can thus be solved in polynomial time (to any precision).

Graphs, cuts and cycles
, the edge set of the complete graph K n is denoted by E n , so that E is a subset of E n , and the edges of is even for all v ∈ V ; every non-empty cycle is an edge-disjoint union of circuits. For S ⊆ V , the cut D corresponding to the partition (S, V \ S) of V is the set of edges {i, j} ∈ E with |{i, j} ∩ S| = 1. A basic property is that each cut intersects each cycle in an even number of edges; this is in fact a property of binary matroids which is why we will present some of our results later in the more general setting of binary matroids (cf. Sect. 3).
Each cut D can be encoded by its ±1-incidence vector χ D ∈ {±1} E , called the cut vector of D. The cut ideal of G, denoted as I G, is the vanishing ideal of the set of cut vectors of G. The cut polytope of G is where π E is the projection from R E n onto R E . (Cf. e.g. [5] for an overview on the cut polytope.) The cuts of K n can also be encoded by the cut matrices X := xx T for x ∈ {±1} n indexing the partitions of [n] corresponding to the cuts. Thus the set is a relaxation of the cut polytope CUT(G), over which one can optimize any linear objective function in polynomial time (to any precision), using semidefinite optimization. Given edge weights w ∈ R E , the max-cut problem asks for a cut D in G of maximum total weight e∈D w e ; thus it can be formulated as where the variable can alternatively be assumed to lie in CUT(K n ). This is a wellknown NP-hard problem [7]. Thus one is interested in finding tight efficient relaxations of the cut polytope, potentially leading to good approximations for the max-cut problem. It turns out that the simple semidefinite programming relaxation (7) has led to the celebrated 0.878-approximation algorithm of Goemans and Williamson [8] which, as of today, still gives the best known performance guarantee for max-cut.

Theta bodies for cuts and matroids
In this section we study in detail the hierarchy of SDP relaxations for the cut polytope arising from the theta bodies of the cut ideal. As is well-known, cuts in graphs form a special class of binary matroids. It is thus natural to consider the theta bodies in the more general setting of binary matroids, where the results become more transparent. Then we will apply the results to cuts in graphs (the case of cographic matroids) and also to cycles in graphs (the case of graphic matroids).

The cycle ideal of a binary matroid and its theta bodies
Let M = (E, C) be a binary matroid; that is, E is a finite set and C is a collection of subsets of E that is closed under taking symmetric differences. Members of C are Here is a property of chords that we will use later.
Lemma 3.1 Let C be a circuit of M, let e ∈ E\C be a chord of C and C 1 , C 2 be circuits with C = C 1 C 2 and C 1 ∩ C 2 = {e}. Then each C i has strictly fewer chords than C.
Proof It suffices to show that each chord e of C 1 is also a chord of C. For this let C 1 , C 1 be two circuits with C 1 ∩ C 1 = {e } and C 1 = C 1 C 1 . Say, e ∈ C 1 , and thus e ∈ C 1 . Suppose first that e ∈ C 2 . Then we have The binary matroids on E correspond to the GF(2)-vector subspaces of GF(2) E , where GF(2) is the two-element field {0, 1} with addition modulo 2. Namely, identifying a set F ⊆ E with its 0/1-incidence vector 1 F ∈ GF(2) E , the set of cycles C is a vector subspace of GF(2) E and the set of cocycles C * is its orthogonal complement. Thus the cycles of a binary matroid also arise as the solutions in GF(2) E of a linear system Mx = 0, where M is a matrix with columns indexed by E, called a representation matrix of the matroid. In what follows we will use C (and C * ) both as a collection of subsets of E and as a G F(2)-vector space.
As before let RE := R[x e | e ∈ E] and, for C ∈ C, let χ C ∈ {±1} E denote its ±1-incidence vector, called its cycle vector. Then, is the cycle polytope of M and is the vanishing ideal of the cycle vectors of M, called the cycle ideal of M. Thus I M is a real radical zero-dimensional ideal in RE.
We first study the quotient space RE/I M. For this consider the set Obviously, H ⊆ I M; Theorem 3.4 below shows that H in fact generates the ideal I M. First we observe that H also generates all binomials Proof First we note that it suffices to show that Next, we show the lemma for the case when D is a cocircuit, using induction on the number p of its chords. If p = 0 then 1 − x D ∈ H by definition. So let p ≥ 1, let e be a chord of D and let D 1 , , using the induction assumption, since each D i has at most p − 1 chords by Lemma 3.1. We have: Finally we show the lemma for D ∈ C * , using induction on the number p of cocircuits in a partition of D. For this, let D = D 1 ∪ D 2 , where D 1 is a cocircuit and D 2 is a cocycle partitioned into p − 1 cocircuits. Then, by the previous case, Define the relation '∼' on P(E), the collection of all subsets of E, by this is an equivalence relation, since C * is closed under taking symmetric differences. The next lemma characterizes the equivalence classes.
vanishes at χ C and thus |C ∩ F| and |C ∩ F | have the same parity, which implies that |C ∩ (F F )| is even and thus F F ∈ C * . Let be a set of distinct representatives of the equivalence classes of P(E)/ ∼ and set

Theorem 3.4 The set B is a basis of the vector space RE/I M and the set H generates the ideal I M.
Proof First, we show that B spans the space RE/(H). As x 2 e − 1 ∈ H (∀e ∈ E), it suffices to show that B spans all cosets of square-free monomials. For this, let F ⊆ E and, say, F ∼ F 1 ; then, x F − x F 1 ∈ I M by Lemma 3.3, which shows that x F + I M ∈ span(B). Therefore, we obtain: To conclude the proof it now suffices to show that |C| = N . For this, fix a basis {C 1 , . . . , C m } of the GF(2)-vector space C, so that |C| = 2 m . Let M be the m × |E| matrix whose rows are the 0/1-incidence vectors of C 1 , . . . , C m . Then Mx takes 2 m distinct values for all x ∈ GF(2) E . As, for F, F ⊆ E, F ∼ F if and only if M1 F = M1 F , we deduce that the equivalence relation (10) has N = 2 m equivalence classes.
We now consider the combinatorial moment matrices for the cycle ideal I M. For any integer k define the set corresponding to the equivalence classes of ∼ having a representative of cardinality at most k. When M has no coloops and no coparallel elements, its k-th theta body TH k (I M) consists of the vectors y ∈ R E for which there exists a positive semidefinite |F k |×|F k | matrix X satisfying X ∅,e = y e for all e ∈ E and Remark 3.5 The constraints (14)(ii) contain in particular the constraints Note that the above constraints are the basic 'moment constraints', which are satisfied by all ±1 vectors. E). Then X 0 since X = uu T where u = ((−1) |F∩F i | ) F i ∈F k , and X satisfies (14) (i) and (15). Therefore the constraints (15) do not cut off any point of the cube [−1, 1] E . Non-trivial constraints that cut off points of [−1, 1] E that do not lie in CYC(M) come from those constraints (14)(ii) where F 1 F 2 F 3 F 4 is a non-empty cocycle.

Application to cuts in graphs
Binary matroids arise naturally from graphs in the following way. Let G = ([n], E) be a graph, let C G denote its collection of cycles, and D G its collection of cuts. Since So I G is an ideal in RE, while I K n is an ideal in RE n . One can easily verify that I G is the elimination ideal, I K n ∩ RE, of I K n with respect to E. By Theorem 3.4, we know that the (edge) binomials x 2 e − 1 (e ∈ E) together with the binomials 1 − x C (C chordless circuit of G) generate the cut ideal I G. When G = K n is a complete graph, the only chordless circuits are the triangles so that, beside the edge binomials, it suffices to consider the binomials 1 − When G is connected, there are 2 n−1 distinct cuts in G (corresponding to the partitions of [n] into two classes) and, when G has p connected components, there are 2 n− p cuts in G and thus dim RE/I G = 2 n− p .
The following notion of T -joins arises naturally when considering the equivalence relation (10). Given a set T ⊆ [n], a set F ⊆ E is called a T -join if T = {v ∈ [n] | deg F (v) is odd}. For instance, the ∅-joins are the cycles of G and, for T = {s, t}, the minimum T -joins correspond to the shortest s − t paths in G. If F is a T -join and F is T -join, then F F is a (T T )-join. In particular, F ∼ F , i.e. F F ∈ C G , precisely when F, F are both T -joins for the same T ⊆ [n].
Thus the equivalence classes of ∼ correspond to the members of the set T G := {T ⊆ [n] | ∃T -join in G} (which consists of the sets T 1 ∪ . . . ∪ T p , where each T i is an even subset of V i and V 1 , . . . , V p are the connected components of G). The set F (in (11)) consists of one T -join F T for each T ∈ T G , and F k = {F T | T ∈ T k }, after defining T k as the set of all T ∈ T G for which there exists a T -join of size at most k. Then the corresponding basis of For instance, F 1 consists of all edges e ∈ E together with the empty set. Hence the first order theta body TH 1 (I G) consists of the vectors y ∈ R E for which there exists a positive semidefinite matrix X indexed by E ∪ {∅} satisfying y e = X ∅,e (e ∈ E) and (i) X ∅,∅ = X e,e = 1 for all e ∈ E, Remark 3.6 When G = K n is the complete graph, for any even T ⊆ [n], the minimum cardinality of a T -join is |T |/2; just choose for F T a set of |T |/2 disjoint edges (i.e. a perfect matching) on T . Hence the set T k consists of all even T ⊆ [n] with |T | ≤ 2k. As an illustration, if we index the combinatorial moment matrices by T k , then the condition (14) (ii) reads: This observation will enable us to relate the theta body hierarchy to the semidefinite relaxations of the cut polytope considered in [15], cf. Sect. 3.3.  In Sect. 3.3 below we will characterize the graphs whose cut ideals are TH 1 -exact and we will determine the precise order k at which the cut ideal of a circuit is TH k -exact in Sect. 5.

Comparison with other SDP relaxations of the cut polytope
We mention here the link between the theta bodies of the cut ideal I G and some other semidefinite relaxations of the cut polytope CUT(G). First note that the relaxation TH 1 (I G) coincides with the edge-relaxation considered by Rendl and Wiegele (see [25]) and numerical experiments there indicates that it is often tighter than the basic semidefinite relaxation (7) of CUT(G).
Next we compare the theta bodies of I G with the relaxations Q t (G) of CUT(G) considered in [15]. 1 For t ∈ N, set O t (n) := {T ⊆ [n] | |T | ≤ t and |T | ≡ t mod 2}. Then Q t (G) consists of the vectors y ∈ R E for which there exists a positive semidefinite matrix X indexed by O t (n) satisfying (17), X T,T = 1 (T ∈ O t (n)), and y {i, j} = X ∅,{i, j} for t even (resp., y {i, j} = X {i},{ j} for t odd) for all edges {i, j} ∈ E. Therefore, for t = 1, Q 1 (G) coincides with the Goemans-Williamson SDP relaxation (7). Moreover, for even t = 2k, Q 2k (K n ) coincides with the theta body TH k (I K n ).
(To see it use Remark 3.6.) The following chain of inclusions shows the link to the theta bodies: (where the last inclusion follows using (2)). Therefore, the k-th theta body TH k (I G) is in general a weaker relaxation than Q 2k (G). For instance, for the 5-circuit, CUT(C 5 ) = Q 2 (C 5 ) (see [15]) but CUT(C 5 ) is strictly contained in TH 1 (I C 5 ) = [−1, 1] 5 (see Example 3.7). On the other hand, the SDP relaxation TH k (I G) can be much simpler and less costly to compute than Q 2k (G), since its definition exploits the structure of G and thus often uses smaller matrices. Indeed, Q 2k (G) is defined as the projection of Q 2k (K n ), whose definition involves matrices indexed by all even sets T ⊆ [n] of size at most 2k, thus not depending on the structure of G. On the other hand, the matrices needed to define TH k (I G) are indexed by the even sets T ⊆ [n] of size at most 2k for which G has a T -join of size at most k. This can be checked efficiently since the minimum weight T -join problem has a polynomial time algorithm (cf. [6]). For instance, for k = 1, TH 1 (I G) uses matrices of size 1 + |E|, while Q 2 (G) needs matrices of size 1 + n 2 . We refer to Sect. 3.5 for more details on the complexity of constructing the above theta bodies.

Example 3.9
It was shown in [14] that CUT(K n ) is strictly contained in Q k (K n ) for k < n 2 − 1. Therefore, CUT(K n ) ⊂ TH k (I K n ) = Q 2k (K n ) for all 2k < n 2 − 1. This implies that I K n is not TH k -exact for k ≤ n−1 4 . However, it is known that CUT(K n ) = Q n 2 (K n ) when n ≤ 7. Therefore, I K 5 , I K 6 and I K 7 are all TH 2exact.
For some graphs there is a special inclusion relationship between the theta bodies and the Q t -hierarchy. We consider first graphs with bounded diameter. Lemma 3.10 Let G be a graph with diameter at most k, i.e., such that any two vertices can be joined by a path traversing at most k edges. Then TH k (I G) ⊆ Q 2 (G).
Proof It suffices to observe that the set T k indexing the matrices in the definition of TH k (I G) (which consists of the even sets T ⊆ V for which there is a T -join of size at most k) contains all pairs of vertices. Thus T k contains the set O 2 (n) indexing the matrices in the definition of Q 2 (G).
Next we observe that TH k (I G) refines the Goemans-Williamson relaxation (7) for graphs with radius k.  (17)). This shows y ∈ Q 1 (G), concluding the proof.

Lemma 3.11 Let G be a graph with radius at most k, i.e., there exists a vertex that can be joined to any other vertex by a path traversing at most k edges. Then
In particular, as already noted in [25], TH 1 (I G) ⊆ Q 1 (G) if G contains a vertex adjacent to all other vertices. For an arbitrary graph G, let G * be the graph obtained by adding edges to G so that one of its vertices is adjacent to all other vertices. Thus, TH 1 (I G * ) ⊆ Q 1 (G * ) by Lemma 3.11. Taking projections onto the edge set of G, the relaxation π E (TH 1 (I G * )) is contained in π E (Q 1 (G * )) = Q 1 (G) (and in TH 1 (I G)).

Application to circuits in graphs
Let us consider briefly the case when M = M G is the graphic matroid of a graph G = (V, E), i.e. C = C G is the collection of cycles of G and C * = D G is its collection of cuts.
One can find a set F of representatives for the equivalence classes of (10) as follows. Namely, assume for simplicity that G is connected and let E 0 ⊆ E be the edge set of a spanning tree in G. Then the collection F := P(E\E 0 ) is a set of distinct representatives for the classes of (10). Indeed, note first that no two distinct subsets F, F of E\E 0 are in relation by ∼, since each non-empty cut meets the tree E 0 . Next, any subset X ⊆ E 0 determines a unique cut D X for which D X ∩ E 0 = X , so that X ∼ X D X . Hence, for any set Z ⊆ E, write Z = X ∪ Y with X ⊆ E 0 and Y ⊆ E\E 0 ; then Z ∼ X D X Y is thus in the same equivalence class as a subset of E\E 0 .
Note however that the above set F may not consist of the minimum cardinality representatives. In fact, as we observe in the next section, finding a minimum cardinality representative in each equivalence class amounts to solving a maximum weight cut problem, thus a hard problem. Nevertheless this collection F can be used to index truncated moment matrices (simply index the k-th order matrix by all F ∈ F with |F| ≤ k). However, studying this SDP hierarchy is less relevant for optimization purposes since the linear inequality description of CYC(M G ) is completely known (see Theorem 4.4 below), and one can find a maximum weight cycle in a graph in polynomial time (cf. [6]).

Computational complexity of theta bodies
We group here some observations about the computational complexity of building the matrices M B k (y) needed to define the theta body TH k (I M) of a binary matroid M.
The computation of the matrix M B k (y) is done in two steps: -First compute the sets F k and F 2k .
-Then compute the entries of M B k (y), i.e., for all F, F ∈ F k , find F ∈ F 2k such that F F ∼ F , i.e., F F F ∈ C * .
As we see below both steps involve making repeated calls to a membership oracle for C * . Such a membership oracle gives a yes/no answer to any query of the form: Given X ⊆ E, does X belong to C * ?
If the binary matroid M is given by a representation matrix M, then it is easy to answer such a query. Indeed, first bring M into the form M = (I r A), where A ∈ {0, 1} r ×s (using Gaussian elimination). Then M * := A T I s is a representing matrix for M * and thus X ∈ C * if and only if M * 1 X = 0 modulo 2.
In the case when M is the cographic matroid of a graph G = (V, E), checking membership in C * is easy: X ∈ C * (i.e., X is a cycle of G) if and only if each node v ∈ V is adjacent to an even number of edges of X .
We first indicate how to construct the set F k . Say M = (E, C) is a binary matroid on E, m := |E|, and P k (E) denotes the collection of all subsets of E with cardinality at most k. As in (11), F denotes a set of distinct representatives for the equivalence classes of the relation ∼ in (10), and F k is (as in (13)) a set of distinct representatives for those classes that contain at least one set of cardinality at most k. For any F ⊆ E, check that the subsets of E that are equivalent to F are precisely those of the form F D, D ∈ C * , and that for two distinct elements D 1 and D 2 in C * , F D 1 = F D 2 . Therefore, |F| = 2 m /|C * | and Such a set F k can be constructed using the following simple procedure: if X i+1 F s ∈ C * ∀s = 1, . . . , r , then F r +1 := X i+1 is selected; otherwise we do not select it; go on with next set X i+2 . Let F 1 , . . . , F p be the sets which have been selected by this procedure. Then, F r ∼ F r for 1 ≤ r < r ≤ p, and any X ∈ P k (E) is equal or equivalent to one of F 1 , . . . , F p . Therefore, the set {F 1 , . . . , F p } constitutes a set of distinct representatives for the classes of ∼ containing some set of size at most k and thus it can be chosen for F k . Moreover it has the property that any member of F k has the smallest cardinality in its equivalence class.
The above procedure makes a number of calls to a membership oracle in C * which is of order O(m k ), thus polynomial in m = |E|, when k is fixed.
Next we see how to construct the entries of M B k (y). For this we need to build the multiplication table: for any F, F ∈ F k , we must find the element F ∈ F for which x F x F = x F modulo I M or, equivalently, F F ∼ F . As |F F | ≤ 2k, F ∈ F 2k . Therefore, in order to build M B k (y) it suffices to build the set F 2k which, for fixed k, can be done with a polynomial number of calls to a membership oracle for C * .

Remark 3.12
On the other hand, let us point out that, given F ⊆ E, the problem of finding a representative F of minimum cardinality in the equivalence class of F is hard in general. (Of course, if we fix the cardinality of F the problem becomes easy as we just observed.) Indeed this is the problem: min |D F| such that D ∈ C * (19) or equivalently after defining w ∈ R E by w e = −1 for e ∈ F and w e = 1 for e ∈ E\F (and noting that w T χ D = |E| − 2|F D|).
When M is a cographic matroid, the above problem (19) asks to find a minimum cardinality T -join (where T is the set of odd degree nodes in F) which can be solved in polynomial time (see [6]).
When M is a graphic matroid, the above problem (20) is an instance of the maximum cut problem, which is an NP-hard problem for general graphs. However (20) is polynomial time solvable if M has no M(K 5 )-minor (see [1]).
The problem (20) is also polynomial time solvable when M or M * does not have F 7 or M(K 5 ) * as a minor; see [11] for details and for other classes of matroids for which (20) is polynomial time solvable. Example 4.1 Let M r denote the r × (2 r − 1) matrix whose columns are all nonzero 0/1 vectors of length r , and let P r denote the binary matroid represented by M r , called the binary projective space of dimension r − 1. One can verify that P r has 2 r cocycles; the non-empty cocycles have size 2 r −1 and thus are cocircuits. Hence, CYC(P * r ) is a simplex and I P * r is TH 1 -exact. When n = 3, P 3 =: F 7 is called the Fano matroid. It will follow from Theorem 4.6 that I F 7 is also TH 1exact.
where it is convenient to index the columns by the edge set E 5 of K 5 . Then the cycles of R 10 correspond to the even cycles of K 5 , and the cocycles of R 10 to the cuts of K 5 and their complements. Note that R 10 is isomorphic to its dual. Consider the inequality: where F consists of three edges adjacent to a common vertex (e.g. F = {12, 13, 14}).
(Thus (21) is of the form (22), but with a shifted right hand side.) One can verify that (21) defines a facet of CYC(R 10 ) and that the linear function in (21) takes three distinct values on the cycles of R 10 (namely, 0, 4, and -4). Therefore, in view of Theorem 2.2, we can conclude that R 10 is not TH 1 -exact. Thus we may assume without loss of generality that M has no coloops and no coparallel elements. We will use the following known results.   in Example 4.1 that the cycle ideal of P * r is TH 1 -exact, while I M is not always TH 1 -exact. See Sect. 5 for examples of cographic matroids whose cycle ideal is TH 2 -exact while they have a contraction minor whose cycle ideal is not TH k -exact for large k (this is the case for wheels, cf. Corollary 5.10).
We now characterize the TH 1 -exact cographic matroids. We begin with a lemma relating graph and matroid minors involving K 5 .

Lemma 4.10
The cographic matroid M * G of a graph G has a M * K 5 minor if and only if K 5 is a contraction minor of G.
x e − f ∈C\{e} is valid for TH k (I G).
The proof uses the following preliminary results. For convenience, for a graph G = (V, E), let S k denote the set of polynomials f ∈ RE that are k-sos modulo the cut ideal I G.
f C := x e − f ∈F\{e} x f + |C| − 2 is k-sos modulo I G. For this we consider a partition of F into four sets F 1 , . . . , F 4 with |F i | ≤ m ≤ k for i = 1, . . . , 4; say e ∈ F 1 . Applying Lemma 5.2, we obtain that Next, applying the condition (24) (i) to F 1 we obtain and applying the condition (24) (ii) to F i yields Summing up the above relations yields the desired result, namely f C is k-sos modulo I G and thus f C ≥ 0 is valid for TH k (I G).

Corollary 5.5
For the circuit C n of length n, the equality TH k (I C n ) = CUT(C n ) holds for n ≤ 4k.
Proof Consider the circuit C n = ([n], E) with n ≤ 4k. By Theorem 4.4, the complete linear description of CUT(C n ) is provided by the inequalities (i) e∈F x e − e∈E\F x e ≥ 2 − n where F is any odd subset of E, and (ii) −1 ≤ x e ≤ 1 for all e ∈ E. Thus in order to show TH k (I C n ) = CUT(C n ), it suffices to show that the inequalities (i),(ii) are all valid for TH k (I C n ). This is obvious for (ii). Using the well-known switching symmetries of the cut polytope (cf. [2,5]), it suffices to show the desired property for the inequalities (i) with |F| = 1. But this result has just been shown in Theorem 5.1.
Proof In view of Remark 3.5, it suffices to observe that the constraints (14) defining the theta body TH k (I C n ) reduce to the constraints (14) (i) and (15). Let F k be the set indexing the combinatorial moment matrices in the definition of TH k (I C n ), where we can assume that each F i ∈ F k has cardinality at most k. Now consider a constraint of type (14) (ii). Since F 1 , . . . , F 4 ∈ F k have size at most k and i F i is a cycle of C n , this cycle must be the empty set since | i F i | ≤ 4k < n. Therefore we have a constraint of type (15).

Corollary 5.7
The smallest order k at which I C n is TH k -exact is k = n/4 . Proof Directly from Theorem 5.1 and Lemma 5.6.
Remark 5.8 One can verify that the linear form x e − f ∈C n \{e} x f takes (n + 1)/2 distinct values at the cut vectors of the circuit C n . By (3), this permits to conclude that I C n is TH k -exact for k = (n + 1)/2 − 1. This value is however larger than the order n/4 shown in Corollary 5.7 (for n ≥ 6). Thus the reverse implication of (3) does not hold.

Corollary 5.9
If the graph G has no K 5 minor and no chordless circuit of length at least 9, then its cut ideal I G is TH 2 -exact.
Proof Direct application of Theorems 4.4 and 5.1.
Note that the reverse implication in Corollary 5.9 does not hold. We will see below (in Corollary 5.10) that the cut ideal of a wheel is TH 2 -exact, but a wheel can contain a chordless circuit of arbitrary length.
While we could characterize the graphs whose cut ideal is TH 1 -exact, it is an open problem to characterize the graphs whose cut ideal is TH 2 -exact. We conclude this section with several observations about these graphs.

Corollary 5.10
If the graph G has no K 5 minor and has diameter at most 2 then its cut ideal I G is TH 2 -exact.
Proof As G has diameter at most 2, Lemma 3.10 gives the inclusion TH 2 (I G) ⊆ Q 2 (G). It was shown in [15] that if G has no K 5 minor then Q 2 (G) = CUT(G).
A wheel of length n is a graph consisting of a circuit of length n with an additional vertex adjacent to all vertices on the circuit. As wheels have no K 5 minor and their diameter is 2, their cut ideal is TH 2 -exact. Hence, within graphs with no K 5 minors, the cut ideal is TH 2 -exact for the following two classes: graphs with diameter at most 2 and graphs with no chordless circuit of size at least 9. Note that there is no containment between these two classes; e.g. wheels of length n ≥ 9 have diameter 2 but contain a circuit of length n, and C 8 has diameter larger than 2.
The following further graphs have a TH 2 -exact cut ideal: K 5 , K 6 , K 7 (and probably K 8 too, as conjectured in [15]). Finally, if the cut ideal of a graph G is TH 2 -exact, then the same holds for the cut ideal of any contraction minor H of G; in particular, C 9 is not a contraction minor of G.
Open Access This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.