signed graph, frame matroid, nowhere-zero flow, representability, Tutte polynomial, delta-matroid
2020 MSC: 05B35, 05C21, 05C22, 05C31, 81P70
Introduction
Symplectic matroids are the Coxeter matroids of type C n C_n C n [1 ] . We define symplectic matroids on the ground set J = [ n ] ⊔ [ n ] ∗ J=[n]\sqcup[n]^* J = [ n ] ⊔ [ n ] ∗ with the involution i ↔ i ∗ i\leftrightarrow i^* i ↔ i ∗ , and their bases are admissible k k k -subsets of J J J , that is, k k k -subsets containing at most one element of each pair { i , i ∗ } \{i,i^*\} { i , i ∗ } . A k k k -dimensional subspace W ≤ F q 2 n W\leq\mathbb{F}_q^{2n} W ≤ F q 2 n that is totally isotropic for the standard alternating form, given as the row space of a matrix H = [ X ∣ Z ] H=[X\mid Z] H = [ X ∣ Z ] with X Z T = Z X T XZ^{\mathsf{T}}=ZX^{\mathsf{T}} X Z T = Z X T , determines a represented symplectic matroid: its bases are the admissible k k k -sets B B B with det H [ B ] ≠ 0 \det H[B]\ne0 det H [ B ] = 0 . Lagrangian matroids are the rank n n n symplectic matroids, which are equivalent to Bouchet’s delta-matroids. Let F q \mathbb{F}_q F q be a finite field. Under the standard symplectic representation, the images of stabilizer groups in F q 2 n \mathbb{F}_q^{2n} F q 2 n are precisely the totally isotropic subspaces; together with a compatible choice of phases, such a subspace determines the corresponding F q \mathbb{F}_q F q -linear quantum stabilizer code, and this is where the questions answered here come from [2 ] .
Chow [3 ] introduced a graphical family of symplectic matroids. For a multigraph G = ( V , E ) G=(V,E) G = ( V , E ) with E = { e 1 , … , e n } E=\{e_1,\ldots,e_n\} E = { e 1 , … , e n } , the pair { i , i ∗ } \{i,i^*\} { i , i ∗ } is identified with the edge e i e_i e i , and i ∗ i^* i ∗ is thought of as a starred copy of e i e_i e i . An admissible set S S S is independent in S ( G ) \mathcal{S}(G) S ( G ) if every component of the spanning subgraph formed by the edges met by S S S is either a tree or unicyclic with an odd number of starred edges on its cycle. For every transversal T T T , the restriction S ( G ) ∣ T \mathcal{S}(G)|_T S ( G ) ∣ T is the frame matroid of the signed graph in which the starred edges are negative; Chow’s theorem says that these local frame matroids glue together to a symplectic matroid. In the coding application, a representation of S ( G ) \mathcal{S}(G) S ( G ) over F q \mathbb{F}_q F q is a stabilizer matrix of an [ [ ∣ E ∣ , ∣ E ∣ − r ] ] q [[|E|,|E|-r]]_q [[ ∣ E ∣ , ∣ E ∣ − r ] ] q quantum code, where r = r ( S ( G ) ) r=r(\mathcal{S}(G)) r = r ( S ( G )) . Sarvepalli [2 Sec. V] asked to “find representations for the graphical symplectic matroids” or, alternatively, to “find a criterion to test which of these matroids are representable”. Chow mentioned that, on the basis of a personal communication with N. White, he mentioned that, a graph with three vertices and four edges, two of which form a double edge, gives a non-representable example [3 ] .
Main results
The main difficulty is that a representation of S ( G ) S(G) S ( G ) is a single isotropic subspace that must realize, all at once, the frame matroids of the 2 ∣ E ∣ 2^{|E|} 2 ∣ E ∣ signed graphs obtained by starring edges of G G G . Isotropy is a quadratic condition; in characteristic 2 2 2 , frame matroids of signed graphs are in general not representable canonically. Our starting point is that most of this difficulty disappears once a representation is written in the right coordinates. After that, the problem splits into a flow, a linear system, and determinant conditions.
A normal form. Restricted to the unstarred elements, a representation of S ( G ) S(G) S ( G ) represents the cycle matroid M ( G ) M(G) M ( G ) . Since regular matroids are uniquely representable [4 ] , row operations and pair scalings bring every representation to the matrix form (5), whose first block is the reduced incidence matrix D D D of G G G (Theorem 3.8 ). Isotropy gives two linear conditions: z z z is an F \mathbb{F} F -flow and D Z 1 T DZ_{1}^{\mathsf{T}} D Z 1 T is symmetric. The bases further force z e ≠ 0 z_{e} \ne0 z e = 0 on every cyclic edge; on bridges, the flow condition gives z e = 0 z_{e}=0 z e = 0 . What remains of the matroid is a set of vanishing and nonvanishing minors (Remark 3.10). The dependent sets with at most two starred elements turn into linear equations, the two-star relations of Lemma 3.9 .
Flows. The last row of the normal form is a nowhere-zero ( F , + ) (\mathbb{F},+) ( F , + ) -flow on the graph G ∘ G^{\circ} G ∘ obtained by deleting loops and bridges (Theorem 4.1 ). For a finite field F q \mathbb{F}_{q} F q , the existence of such a flow is equivalent to the existence of a nowhere-zero integer q q q -flow. So flow theory immediately excludes small fields: S ( K 4 ) S(K_{4}) S ( K 4 ) is not F 2 \mathbb{F}_{2} F 2 -representable, and the matroid of the Petersen graph is representable neither over F 2 \mathbb{F}_{2} F 2 nor over F 4 \mathbb{F}_{4} F 4 (Corollary 4.2 ). Theorem 5.1 also excludes S ( K 4 ) S(K_{4}) S ( K 4 ) , S ( K 3 , 3 ) S(K_{3,3}) S ( K 3 , 3 ) and S ( P 10 ) S(P_{10}) S ( P 10 ) in characteristic ≠ 2 \ne2 = 2 see Remark 4.3.
Characteristic ≠ 2 \ne2 = 2 . We derive a complete answer. The symplectic matroid S ( G ) S(G) S ( G ) is representable over a field of characteristic ≠ 2 \ne2 = 2 if and only if every edge on a cycle, other than a loop, has a parallel mate (Theorem 5.1 ); the answer does not depend on the field. For sufficiency we build the representation from signed incidence vectors (Lemma 2.16 ), with coefficients on each parallel class that sum to zero. For necessity we contract a forest (Corollary 3.5 (3)) so that an edge without a parallel mate becomes the common edge of a fan of triangles. The two-star
relations and isotropy then produce a factor 2 that must vanish, and three starred edges of a triangle, which form an independent set, end up with proportional columns. In particular, a simple graph with a cycle can only be represented in characteristic 2 (Corollary 5.2).
Characteristic 2 without two disjoint cycles. Here the flow obstruction is the only one: if G G G is loopless and has no two vertex-disjoint cycles, then S ( G ) \mathcal{S}(G) S ( G ) is F \mathbb{F} F -representable if and only if G ∘ G^{\circ} G ∘ has a nowhere-zero ( F , + ) (\mathbb{F},+) ( F , + ) -flow (Theorem 6.2 ). The representation is the one-row lift (9) of such a flow (Proposition 6.1 ). The construction works because G [ S ] G[S] G [ S ] cannot have two distinct cyclic components. If its cycle space has dimension at least two, the columns are dependent, and Chow’s independence rule also fails. If that dimension is one, independence is determined by the parity of the starred edges on the unique cycle, so its independence reduces to a single parity check on that cycle. By Jaeger’s theorem [5 ] the condition always holds when ∣ F ∣ ≥ 8 |\mathbb{F}| \ge8 ∣ F ∣ ≥ 8 ; over F 4 \mathbb{F}_4 F 4 it asks for a nowhere-zero 4-flow, and over F 2 \mathbb{F}_2 F 2 for G ∘ G^{\circ} G ∘ to be Eulerian.
Characteristic 2: obstructions. Short cycles carry almost no freedom: on a cycle of length 2 or 3 the vectors w e w_e w e of (6) have the rigid form (10) (Lemma 6.4 ). If two such cycles are linked by other cycles in the sense of Definition 6.5 , the two rigid forms are incompatible, and S ( G ) \mathcal{S}(G) S ( G ) is not representable over any field of characteristic 2 (Theorem 6.6 ). Together with Theorem 5.1 , this shows that the prism, the octahedron and K n K_n K n for n ≥ 6 n \ge6 n ≥ 6 give matroids representable over no field (Corollary 6.7 ). Contracting a forest carries the obstruction over to long cycles, so every graph that contains a subdivision of the prism is excluded in characteristic 2 (Proposition 6.9 ). The examples in Example 6.8 show that neither this obstruction nor the flow condition characterizes characteristic 2 in general.
3-connected graphs. For 3-connected graphs the two sides meet. If such a graph has two vertex-disjoint cycles, Menger’s theorem links them by three disjoint paths and Proposition 6.9 applies; otherwise the graph is one of the graphs of Dirac and Lovász (Remark 6.3), for which we write down nowhere-zero flows explicitly (Lemma 6.10 ). The result is a complete classification (Theorem 6.11 ): for a 3-connected simple graph G G G , S ( G ) \mathcal{S}(G) S ( G ) is F \mathbb{F} F -representable if and only if char F = 2 \operatorname{char}\mathbb{F}=2 char F = 2 , G G G has no two vertex-disjoint cycles, and either ∣ F ∣ > 2 |\mathbb{F}|>2 ∣ F ∣ > 2 or G ≅ K 5 G\cong K_5 G ≅ K 5 . In
particular, the matroid of the Petersen graph is representable over no field (Corollary 6.12 ).
Small graphs and Chow’s remark. For a connected unicyclic graph with cycle C C C , the matrix ( D D 0 1 C ) \begin{pmatrix} D & D \\ 0 & 1_C \end{pmatrix} ( D 0 D 1 C ) represents S ( G ) S(G) S ( G ) over every field of characteristic 2 2 2 , and characteristic 2 2 2 is necessary when G G G is simple (Corollary 7.1 ). The doubled triangle, which is the graph behind Chow’s example of a non-representable graphical symplectic matroid, is representable exactly over the fields of characteristic 2 2 2 with more than two elements (Corollary 7.3 ). So Chow’s remark is correct over F 2 \mathbb{F}_2 F 2 and in characteristic ≠ 2 \ne2 = 2 , but not over F 4 \mathbb{F}_4 F 4 (Remark 7.4).
Rank enumerators. The admissible corank–nullity polynomial T S T_S T S of (11) is defined for every symplectic matroid. For represented matroids the rank of an admissible set is the rank of its columns (Lemma 3.1 ), so T S T_S T S , and with it Sarvepalli’s restricted Tutte-Martin polynomial, does not depend on the representation (Proposition 8.2 ). It satisfies a three-term contraction identity (Theorem 8.4 ). For Lagrangian matroids this is the recursion of the U U U -polynomial, with T S ( u , v ) = U S ( u , u v ) T_S(u,v)=U_S(u,uv) T S ( u , v ) = U S ( u , uv ) [6 , 7 ] (Corollary 8.6 ). For graphical symplectic matroids, switching at a vertex identifies the two contractions of an edge, and we get T S ( G ) = u δ e T S ( G \ e ) + 2 T S ( G / e ) T_S(G)=u^{\delta_e}T_S(G\backslash e)+2T_S(G/e) T S ( G ) = u δ e T S ( G \ e ) + 2 T S ( G / e ) for every edge e e e that is not a loop (Corollary 8.7 ). A loop is different: contracting its starred element marks its vertex. Allowing marked vertices (Definition 8.8 , Proposition 8.9 ) gives a minor-closed class on which the recursion is complete (Theorem 8.10 and Corollary 8.11 ). For general symplectic matroids, however, restriction to the remaining pairs need not produce a symplectic matroid (Remark 8.5 ), so the three-term identity does not automatically give a closed recursion within that class. Finally, a polynomial built from an enveloping matroid agrees with T S T_S T S exactly when the envelope is sheltering (Proposition 8.13 ), which every representation provides (Corollary 8.14 ). Duchamp’s delta-matroid has twelve envelopes, none of them sheltering, and they give two different polynomials (Example 8.15 ).
Paper organization
The rest of the paper is organized as follows. In Section 2, we fix the notations and recall the necessary definitions that will be used throughout the paper. In § 3 we prove the intrinsic-rank lemma, the contraction lemmas and the normal form. In § 4 we discuss the flow obstruction. The classification in characteristic ≠ 2 \ne2 = 2 has been discussed in § 5 , and in § 6 we discuss the results in characteristic 2 2 2 , including the classification for 3-connected graphs. In § 7 we discuss the unicyclic graphs, the doubled triangle and Chow’s remark, and in § 8 we discuss the rank enumerators. We propose a few open problems in § 9 . Statements whose proofs use a computer search are confined to Examples 6.8 and 8.15. The searches and lists the matrices found, and the programs, are provided as supplementary material in Appendix A.
Preliminaries
We begin by fixing the notation and recalling the necessary definitions.
Notation
Throughout the paper, F \mathbb{F} F is a field, F × = F ∖ { 0 } \mathbb{F}^{\times}=\mathbb{F}\setminus\{0\} F × = F ∖ { 0 } , and F q \mathbb{F}_{q} F q is the field with q q q elements. For a vector y y y , supp ( y ) \operatorname{supp}(y) supp ( y ) is the set of coordinates at which y y y is nonzero; for a column vector y y y and a scalar c c c , ( y ; c ) (y;c) ( y ; c ) is the column vector obtained from y y y by appending the entry c c c . We follow matroid terminologies from Oxley [8 ] , and for symplectic matroids we follow Borovik, Gelfand and White [1 ] .
Symplectic matroids
Definition 2.1 (Admissible sets). Let n ≥ 0 n\ge0 n ≥ 0 , [ n ] = { 1 , … , n } [n]=\{1,\ldots,n\} [ n ] = { 1 , … , n } , [ n ] ∗ = { 1 ∗ , … , n ∗ } [n]^{*}=\{1^{*},\ldots,n^{*}\} [ n ] ∗ = { 1 ∗ , … , n ∗ } and J = [ n ] ⊔ [ n ] ∗ J=[n]\sqcup[n]^{*} J = [ n ] ⊔ [ n ] ∗ , with the fixed-point-free involution a ↦ a ∗ a\mapsto a^{*} a ↦ a ∗ given by i ↦ i ∗ i\mapsto i^{*} i ↦ i ∗ and i ∗ ↦ i i^{*}\mapsto i i ∗ ↦ i . For A ⊆ J A\subseteq J A ⊆ J put A ∗ = { a ∗ : a ∈ A } A^{*}=\{a^{*}:a\in A\} A ∗ = { a ∗ : a ∈ A } ; for a ∈ J a\in J a ∈ J put J a = { a , a ∗ } J_{a}=\{a,a^{*}\} J a = { a , a ∗ } , and for Y ⊆ [ n ] Y\subseteq[n] Y ⊆ [ n ] put J Y = Y ⊔ Y ∗ J_{Y}=Y\sqcup Y^{*} J Y = Y ⊔ Y ∗ . A set A ⊆ J A\subseteq J A ⊆ J is admissible if A ∩ A ∗ = ∅ A\cap A^{*}=\varnothing A ∩ A ∗ = ∅ , and a transversal if moreover ∣ A ∣ = n |A|=n ∣ A ∣ = n . We write A ( J ) \mathcal{A}(J) A ( J ) for the family of admissible sets and A k ( J ) \mathcal{A}_{k}(J) A k ( J ) for its members of size k k k ; for a ∗ * ∗ -closed subset J ′ ⊆ J J'\subseteq J J ′ ⊆ J , A ( J ′ ) \mathcal{A}(J') A ( J ′ ) and A k ( J ′ ) \mathcal{A}_{k}(J') A k ( J ′ ) are defined in the same way.
Definition 2.2 (Symplectic matroids [1 Ch. 3] ). A linear order ≺ \prec ≺ on J J J is admissible if a ≺ b a\prec b a ≺ b implies b ∗ ≺ a ∗ b^{*}\prec a^{*} b ∗ ≺ a ∗ . It induces the Gale order on k k k -subsets of J J J : if A = { a 1 ≻ ⋯ ≻ a k } A=\{a_{1}\succ\cdots\succ a_{k}\} A = { a 1 ≻ ⋯ ≻ a k } and B = { b 1 ≻ ⋯ ≻ b k } B=\{b_{1}\succ\cdots\succ b_{k}\} B = { b 1 ≻ ⋯ ≻ b k } , then A ≤ B A\le B A ≤ B if a j ⪯ b j a_{j}\preceq b_{j} a j ⪯ b j for j = 1 , … , k j=1,\ldots,k j = 1 , … , k . A symplectic matroid of rank k k k on J J J is a pair S = ( J , B ) S=(J,\mathcal{B}) S = ( J , B ) with ∅ ≠ B ⊆ A k ( J ) \varnothing\ne\mathcal{B}\subseteq\mathcal{A}_{k}(J) ∅ = B ⊆ A k ( J ) such that, for every admissible order ≺ \prec ≺ , some B ≺ ∈ B B_{\prec}\in\mathcal{B} B ≺ ∈ B satisfies B ≤ B ≺ B\le B_{\prec} B ≤ B ≺ for all B ∈ B B\in\mathcal{B} B ∈ B . The members of B = B ( S ) \mathcal{B}=\mathcal{B}(S) B = B ( S ) are the bases, the subsets of bases are the independent sets , forming the family I ( S ) \mathcal{I}(S) I ( S ) , and r ( S ) = k r(S)=k r ( S ) = k is the rank. An element a ∈ J a\in J a ∈ J is a loop of S S S if it lies in no basis. S S S is Lagrangian if k = n k=n k = n . The uniform symplectic matroid U k , n ∗ U^{*}_{k,n} U k , n ∗ has B = A k ( J ) \mathcal{B}=\mathcal{A}_{k}(J) B = A k ( J ) .
The bases of a symplectic matroid are the maximal independent sets, so S S S is determined by I ( S ) \mathcal{I}(S) I ( S ) . Chow characterized the families I ( S ) \mathcal{I}(S) I ( S ) .
Theorem 2.3 (Chow [3 ] ). A nonempty subset-closed family I \mathcal{I} I of admissible subsets of J J J is the family of independent sets of a symplectic matroid if and only if the following holds. If I , I ′ ∈ I I,I'\in\mathcal{I} I , I ′ ∈ I , ∣ I ∣ < ∣ I ′ ∣ |I|<|I'| ∣ I ∣ < ∣ I ′ ∣ and I ∪ { y } ∉ I I\cup\{y\}\notin\mathcal{I} I ∪ { y } ∈ / I for every y ∈ I ′ ∖ I y\in I'\setminus I y ∈ I ′ ∖ I , then I ∪ I ′ I\cup I' I ∪ I ′ is not admissible, and there is x ∉ I x\notin I x ∈ / I such that I ∪ { x } ∈ I I\cup\{x\}\in\mathcal{I} I ∪ { x } ∈ I and ( I ∖ I ′ ∗ ) ∪ { x ∗ } ∈ I (I\setminus I'^{*})\cup\{x^{*}\}\in\mathcal{I} ( I ∖ I ′ ∗ ) ∪ { x ∗ } ∈ I .
Lemma 2.4 (Restriction to a transversal). Let S S S be a symplectic matroid on J J J and T T T a transversal. Then I ( S ) ∣ T = { I ∈ I ( S ) : I ⊆ T } \mathcal{I}(S)|_{T}=\{I\in\mathcal{I}(S):I\subseteq T\} I ( S ) ∣ T = { I ∈ I ( S ) : I ⊆ T } is the family of independent sets of an ordinary matroid S ∣ T S|_{T} S ∣ T on T T T .
Proof. The family is subset-closed and contains ∅ \varnothing ∅ . Let I , I ′ ∈ I ( S ) ∣ T I,I'\in\mathcal{I}(S)|_{T} I , I ′ ∈ I ( S ) ∣ T with ∣ I ∣ < ∣ I ′ ∣ |I|<|I'| ∣ I ∣ < ∣ I ′ ∣ . If no y ∈ I ′ ∖ I y\in I'\setminus I y ∈ I ′ ∖ I satisfied I ∪ { y } ∈ I ( S ) I\cup\{y\}\in\mathcal{I}(S) I ∪ { y } ∈ I ( S ) , then I ∪ I ′ I\cup I' I ∪ I ′ would be inadmissible by Theorem 2.3 , which is impossible because I ∪ I ′ ⊆ T I\cup I'\subseteq T I ∪ I ′ ⊆ T . Hence the augmentation axiom holds. □ \square □
Definition 2.5 (Rank function). The rank function of a symplectic matroid S S S is r S : A ( J ) → Z ≥ 0 r_{S}:\mathcal{A}(J)\to\mathbb{Z}_{\geq0} r S : A ( J ) → Z ≥ 0 ,
r S ( A ) : = max { ∣ I ∣ : I ⊆ A , I ∈ I ( S ) } = max B ∈ B ( S ) ∣ A ∩ B ∣ . (1) r_{S}(A):=\max\{|I|:I\subseteq A,\ I\in\mathcal{I}(S)\}=\max_{B\in\mathcal{B}(S)}|A\cap B|. \tag*{(1)} r S ( A ) := max { ∣ I ∣ : I ⊆ A , I ∈ I ( S )} = B ∈ B ( S ) max ∣ A ∩ B ∣. (1)
The two expressions in (1) agree because A ∩ B A\cap B A ∩ B is independent and every independent I ⊆ A I\subseteq A I ⊆ A lies in A ∩ B A\cap B A ∩ B for some basis B B B .
Lemma 2.6. Let S S S be a symplectic matroid of rank k k k and let A , A ′ ∈ A ( J ) A,A'\in\mathcal{A}(J) A , A ′ ∈ A ( J ) .
For every transversal T ⊇ A T\supseteq A T ⊇ A , r S ( A ) r_{S}(A) r S ( A ) is the rank of A A A in the matroid S ∣ T S|_{T} S ∣ T .
0 ≤ r S ( A ) ≤ min ( k , ∣ A ∣ ) 0\leq r_{S}(A)\leq\min(k,|A|) 0 ≤ r S ( A ) ≤ min ( k , ∣ A ∣ ) , and r S ( A ) ≤ r S ( A ∪ { a } ) ≤ r S ( A ) + 1 r_{S}(A)\leq r_{S}(A\cup\{a\})\leq r_{S}(A)+1 r S ( A ) ≤ r S ( A ∪ { a }) ≤ r S ( A ) + 1 whenever A ∪ { a } A\cup\{a\} A ∪ { a } is admissible.
If A ∪ A ′ A\cup A' A ∪ A ′ is admissible, then r S ( A ∪ A ′ ) + r S ( A ∩ A ′ ) ≤ r S ( A ) + r S ( A ′ ) r_{S}(A\cup A')+r_{S}(A\cap A')\leq r_{S}(A)+r_{S}(A') r S ( A ∪ A ′ ) + r S ( A ∩ A ′ ) ≤ r S ( A ) + r S ( A ′ ) .
I ( S ) = { A ∈ A ( J ) : r S ( A ) = ∣ A ∣ } \mathcal{I}(S)=\{A\in\mathcal{A}(J):r_{S}(A)=|A|\} I ( S ) = { A ∈ A ( J ) : r S ( A ) = ∣ A ∣ } and B ( S ) = { A ∈ A k ( J ) : r S ( A ) = k } \mathcal{B}(S)=\{A\in\mathcal{A}_{k}(J):r_{S}(A)=k\} B ( S ) = { A ∈ A k ( J ) : r S ( A ) = k } .
Proof. (1) The independent subsets of A A A are exactly the independent sets of S ∣ T S|_{T} S ∣ T contained in A A A . Items (2) and (3) follow from (1) and the rank axioms of the matroid S ∣ T S|_{T} S ∣ T , with T T T a transversal containing A ∪ { a } A \cup\{a\} A ∪ { a } , respectively A ∪ A ′ A \cup A' A ∪ A ′ . Item (4) is immediate from (1).
Lemma 2.8 (Contraction and truncation). Let S S S be a symplectic matroid of rank k ≥ 1 k \ge1 k ≥ 1 on J J J .
Let a ∈ J a \in J a ∈ J be a non-loop of S S S . Then S / a : = J ∖ J a , { B ∖ { a } : a ∈ B ∈ B ( S ) } S/a := J \setminus J_a,\ \{B \setminus\{a\}: a \in B \in\mathcal{B}(S)\} S / a := J ∖ J a , { B ∖ { a } : a ∈ B ∈ B ( S )} is a symplectic matroid of rank k − 1 k - 1 k − 1 with I ( S / a ) = { I ⊆ J ∖ J a : I ∪ { a } ∈ I ( S ) } \mathcal{I}(S/a) = \{I \subseteq J \setminus J_a: I \cup\{a\} \in\mathcal{I}(S)\} I ( S / a ) = { I ⊆ J ∖ J a : I ∪ { a } ∈ I ( S )} .
For 0 ≤ j ≤ k 0 \le j \le k 0 ≤ j ≤ k , the truncation S ( j ) S^{(j)} S ( j ) , whose bases are the independent sets of S S S of size j j j , is a symplectic matroid of rank j j j , and r S ( j ) = min ( r S , j ) r_{S^{(j)}} = \min(r_{S}, j) r S ( j ) = min ( r S , j ) .
Proof. (1) Put I a = { I ⊆ J ∖ J a : I ∪ { a } ∈ I ( S ) } \mathcal{I}_{a} = \{I \subseteq J \setminus J_a: I \cup\{a\} \in\mathcal{I}(S)\} I a = { I ⊆ J ∖ J a : I ∪ { a } ∈ I ( S )} . It is subset-closed, consists of admissible sets, and contains ∅ \varnothing ∅ because a a a is not a loop. We verify the condition of Theorem 2.3 . Let I , I ′ ∈ I a I, I' \in\mathcal{I}_{a} I , I ′ ∈ I a with ∣ I ∣ < ∣ I ′ ∣ |I| < |I'| ∣ I ∣ < ∣ I ′ ∣ and I ∪ { y } ∉ I a I \cup\{y\} \notin\mathcal{I}_{a} I ∪ { y } ∈ / I a for all y ∈ I ′ ∖ I y \in I' \setminus I y ∈ I ′ ∖ I . Put I ^ = I ∪ { a } \widehat{I} = I \cup\{a\} I = I ∪ { a } and I ^ ′ = I ′ ∪ { a } \widehat{I}' = I' \cup\{a\} I ′ = I ′ ∪ { a } . These are independent in S S S , ∣ I ^ ∣ < ∣ I ^ ′ ∣ |\widehat{I}| < |\widehat{I}'| ∣ I ∣ < ∣ I ′ ∣ , I ^ ′ ∖ I ^ = I ′ ∖ I \widehat{I}' \setminus\widehat{I} = I' \setminus I I ′ ∖ I = I ′ ∖ I , and I ^ ∪ { y } ∉ I ( S ) \widehat{I} \cup\{y\} \notin\mathcal{I}(S) I ∪ { y } ∈ / I ( S ) for y ∈ I ^ ′ ∖ I ^ y \in\widehat{I}' \setminus\widehat{I} y ∈ I ′ ∖ I . By Theorem 2.3 , I ^ ∪ I ^ ′ \widehat{I} \cup\widehat{I}' I ∪ I ′ is not admissible; since a ∗ ∉ I ∪ I ′ a^* \notin I \cup I' a ∗ ∈ / I ∪ I ′ , already I ∪ I ′ I \cup I' I ∪ I ′ is not admissible. Moreover there is x ∉ I ^ x \notin\widehat{I} x ∈ / I with I ^ ∪ { x } ∈ I ( S ) \widehat{I} \cup\{x\} \in\mathcal{I}(S) I ∪ { x } ∈ I ( S ) and ( I ^ ∖ I ^ ′ ∗ ) ∪ { x ∗ } ∈ I ( S ) (\widehat{I} \setminus\widehat{I}'^*) \cup\{x^*\} \in\mathcal{I}(S) ( I ∖ I ′ ∗ ) ∪ { x ∗ } ∈ I ( S ) . Here x ≠ a x \ne a x = a , and x ≠ a ∗ x \ne a^* x = a ∗ because I ^ ∪ { a ∗ } \widehat{I} \cup\{a^*\} I ∪ { a ∗ } is not admissible; so x ∈ J ∖ J a x \in J \setminus J_a x ∈ J ∖ J a . Since a ∉ I ^ ′ ∗ a \notin\widehat{I}'^* a ∈ / I ′ ∗ , we have I ^ ∖ I ^ ′ ∗ = ( I ∖ I ′ ∗ ) ∪ { a } \widehat{I} \setminus\widehat{I}'^* = (I \setminus I'^*) \cup\{a\} I ∖ I ′ ∗ = ( I ∖ I ′ ∗ ) ∪ { a } . Hence I ∪ { x } ∈ I a I \cup\{x\} \in\mathcal{I}_{a} I ∪ { x } ∈ I a and ( I ∖ I ′ ∗ ) ∪ { x ∗ } ∈ I a (I \setminus I'^*) \cup\{x^*\} \in\mathcal{I}_{a} ( I ∖ I ′ ∗ ) ∪ { x ∗ } ∈ I a . By Theorem 2.3 , I a \mathcal{I}_{a} I a is the family of independent sets of a symplectic matroid. Its maximal members are the sets B ∖ { a } B \setminus\{a\} B ∖ { a } with a ∈ B ∈ B ( S ) a \in B \in\mathcal{B}(S) a ∈ B ∈ B ( S ) : every I ∈ I a I \in\mathcal{I}_{a} I ∈ I a satisfies I ∪ { a } ⊆ B I \cup\{a\} \subseteq B I ∪ { a } ⊆ B for some basis B B B , which contains a a a , and all these sets have the maximum possible size k − 1 k - 1 k − 1 . (2) Put I j = { I ∈ I ( S ) : ∣ I ∣ ≤ j } \mathcal{I}_j = \{I \in\mathcal{I}(S) : |I| \le j\} I j = { I ∈ I ( S ) : ∣ I ∣ ≤ j } . Let I , I ′ ∈ I j I, I' \in\mathcal{I}_j I , I ′ ∈ I j with ∣ I ∣ < ∣ I ′ ∣ |I| < |I'| ∣ I ∣ < ∣ I ′ ∣ and I ∪ { y } ∉ I j I \cup\{y\} \notin\mathcal{I}_j I ∪ { y } ∈ / I j for y ∈ I ′ ∖ I y \in I' \setminus I y ∈ I ′ ∖ I . Since ∣ I ∪ { y } ∣ ≤ ∣ I ′ ∣ ≤ j |I \cup\{y\}| \le|I'| \le j ∣ I ∪ { y } ∣ ≤ ∣ I ′ ∣ ≤ j , we get I ∪ { y } ∉ I ( S ) I \cup\{y\} \notin\mathcal{I}(S) I ∪ { y } ∈ / I ( S ) . Theorem 2.3 for I ( S ) \mathcal{I}(S) I ( S ) shows that I ∪ I ′ I \cup I' I ∪ I ′ is not admissible and yields x x x with I ∪ { x } I \cup\{x\} I ∪ { x } and ( I ∖ I ′ ∗ ) ∪ { x ∗ } (I \setminus I'{}^*) \cup\{x^*\} ( I ∖ I ′ ∗ ) ∪ { x ∗ } in I ( S ) \mathcal{I}(S) I ( S ) . Both sets have size at most ∣ I ∣ + 1 ≤ j |I|+1 \le j ∣ I ∣ + 1 ≤ j , so they lie in I j \mathcal{I}_j I j . Every member of I j \mathcal{I}_j I j extends to an independent set of size j j j , because it lies in a basis of S S S . The formula for the rank function follows from (1).
Isotropic representations
Definition 2.9 (Representations). Let F \mathbb{F} F be a field. Equip F J = F 2 n \mathbb{F}^J = \mathbb{F}^{2n} F J = F 2 n with the alternating form ω ( x , y ) = ∑ i = 1 n ( x i y i ∗ − x i ∗ y i ) \omega(x,y) = \sum_{i=1}^{n}(x_i y_{i^*} - x_{i^*} y_i) ω ( x , y ) = ∑ i = 1 n ( x i y i ∗ − x i ∗ y i ) . Let H = [ X ∣ Z ] ∈ F k × 2 n H = [X \mid Z] \in\mathbb{F}^{k \times2n} H = [ X ∣ Z ] ∈ F k × 2 n have rank k k k , with the columns of X X X indexed by [ n ] [n] [ n ] and those of Z Z Z by [ n ] ∗ [n]^* [ n ] ∗ . For A ⊆ J A \subseteq J A ⊆ J , H [ A ] H[A] H [ A ] denotes the submatrix formed by the columns indexed by A A A . We call H H H isotropic if X Z T = Z X T XZ^T = ZX^T X Z T = Z X T , that is, if its row space W W W satisfies ω ( W , W ) = 0 \omega(W,W) = 0 ω ( W , W ) = 0 . An isotropic H H H represents the symplectic matroid S S S if B ( S ) = { B ∈ A k ( J ) : det H [ B ] ≠ 0 } \mathcal{B}(S) = \{B \in\mathcal{A}_k(J) : \det H[B] \ne0\} B ( S ) = { B ∈ A k ( J ) : det H [ B ] = 0 } , and S S S is F \mathbb{F} F -representable if some isotropic matrix over F \mathbb{F} F represents it.
For every isotropic H H H of rank k k k , the family { B ∈ A k ( J ) : det H [ B ] ≠ 0 } \{B \in\mathcal{A}_k(J) : \det H[B] \ne0\} { B ∈ A k ( J ) : det H [ B ] = 0 } is the set of bases of a symplectic matroid [1 Ch. 3] ; it is nonempty by the proof of Lemma 3.1 below. For x , y ∈ F m x,y \in\mathbb{F}^m x , y ∈ F m we write x ∧ y : = x y T − y x T x \wedge y := xy^T - yx^T x ∧ y := x y T − y x T . If x i , z i x_i,z_i x i , z i denote the columns of H H H indexed by i i i and i ∗ i^* i ∗ , then X Z T − Z X T = ∑ i = 1 n x i ∧ z i XZ^T - ZX^T = \sum_{i=1}^{n} x_i \wedge z_i X Z T − Z X T = ∑ i = 1 n x i ∧ z i , so H H H is isotropic if and only if
∑ i = 1 n x i ∧ z i = 0. (2) \sum_{i=1}^{n} x_i \wedge z_i = 0. \tag*{(2)} i = 1 ∑ n x i ∧ z i = 0. (2)
Left multiplication by GL k ( F ) \operatorname{GL}_k(\mathbb{F}) GL k ( F ) and the pair scalings ( x i , z i ) ↦ ( c − 1 x i , c z i ) (x_i,z_i) \mapsto(c^{-1}x_i,cz_i) ( x i , z i ) ↦ ( c − 1 x i , c z i ) with c ∈ F × c \in\mathbb{F}^{\times} c ∈ F × preserve isotropy and the represented matroid. A permutation of the pairs preserves isotropy and relabels the represented matroid accordingly. The signed swap ( x i , z i ) ↦ ( − z i , x i ) (x_i,z_i) \mapsto(-z_i,x_i) ( x i , z i ) ↦ ( − z i , x i ) preserves isotropy and exchanges the roles of i i i and i ∗ i^* i ∗ ; in characteristic 2 it is the plain swap ( x i , z i ) ↦ ( z i , x i ) (x_i,z_i) \mapsto(z_i,x_i) ( x i , z i ) ↦ ( z i , x i ) .
Chow's graphical symplectic matroid
Throughout, a graph is a finite multigraph G = ( V , E ) G=(V,E) G = ( V , E ) ; loops and parallel edges are allowed unless stated otherwise. Write E = { e 1 , … , e n } E=\{e_1,\ldots,e_n\} E = { e 1 , … , e n } and identify the pair { i , i ∗ } \{i,i^*\} { i , i ∗ } with the edge e i e_i e i . We write e e e for the unstarred element i i i and e ∗ e^* e ∗ for the starred element i ∗ i^* i ∗ , so that J = E ⊔ E ∗ J=E \sqcup E^* J = E ⊔ E ∗ . A loop is a cycle of length one, and two parallel edges form a cycle of length two.
Definition 2.10 (Graphical symplectic matroid). For S ∈ A ( J ) S \in\mathcal{A}(J) S ∈ A ( J ) let E [ S ] E[S] E [ S ] be the set of edges whose pair meets S S S , and let G [ S ] = ( V , E [ S ] ) G[S] = (V,E[S]) G [ S ] = ( V , E [ S ]) be the spanning subgraph they form. An edge e ∈ E [ S ] e \in E[S] e ∈ E [ S ] is starred in S S S if e ∗ ∈ S e^* \in S e ∗ ∈ S . A connected component K K K of G [ S ] G[S] G [ S ] is good if K K K is a tree, or if ∣ E ( K ) ∣ = ∣ V ( K ) ∣ |E(K)| = |V(K)| ∣ E ( K ) ∣ = ∣ V ( K ) ∣ , that is, K K K is unicyclic, and the unique cycle C K C_K C K contains an odd number of edges starred in S S S . The set S S S is independent if every component of G [ S ] G[S] G [ S ] is good. We write I ( G ) \mathcal{I}(G) I ( G ) for the family of independent sets and S ( G ) \mathcal{S}(G) S ( G ) for the symplectic matroid with I ( S ( G ) ) = I ( G ) \mathcal{I}(\mathcal{S}(G)) = \mathcal{I}(G) I ( S ( G )) = I ( G ) .
Theorem 2.11 (Chow [3 Thm. 2] ). If G G G is loopless, then I ( G ) \mathcal{I}(G) I ( G ) is the family of independent sets of a symplectic matroid.
Corollary 3.5 below extends Theorem 2.11 to graphs with loops, so S ( G ) \mathcal{S}(G) S ( G ) is defined for every graph. Let τ ( G ) \tau(G) τ ( G ) be the number of components of G G G that contain no cycle. Here we consider loops as cycles.
Lemma 2.12. r ( S ( G ) ) = ∣ V ∣ − τ ( G ) r(\mathcal{S}(G)) = |V| - \tau(G) r ( S ( G )) = ∣ V ∣ − τ ( G ) .
Proof. Let S S S be independent. Each component K K K of G [ S ] G[S] G [ S ] satisfies ∣ E ( K ) ∣ ≤ ∣ V ( K ) ∣ |E(K)| \le|V(K)| ∣ E ( K ) ∣ ≤ ∣ V ( K ) ∣ , with ∣ E ( K ) ∣ = ∣ V ( K ) ∣ − 1 |E(K)| = |V(K)| - 1 ∣ E ( K ) ∣ = ∣ V ( K ) ∣ − 1 if K K K is a tree. Each acyclic component of G G G contains at least one component of G [ S ] G[S] G [ S ] , which is a tree. Summing over the components of G [ S ] G[S] G [ S ] gives ∣ S ∣ = ∣ E [ S ] ∣ ≤ ∣ V ∣ − τ ( G ) |S| = |E[S]| \le|V| - \tau(G) ∣ S ∣ = ∣ E [ S ] ∣ ≤ ∣ V ∣ − τ ( G ) . Conversely, in each component L L L of G G G that contains a cycle C C C , choose an edge f ∈ C f \in C f ∈ C and a spanning tree Y L Y_L Y L of L L L containing C ∖ { f } C \setminus\{f\} C ∖ { f } , and put S L = Y L ∪ { f ∗ } S_L = Y_L \cup\{f^*\} S L = Y L ∪ { f ∗ } ; then L [ S L ] L[S_L] L [ S L ] is unicyclic with exactly one starred edge on its cycle. In each acyclic component take a spanning tree. The union of these sets is independent of size ∣ V ∣ − τ ( G ) |V| - \tau(G) ∣ V ∣ − τ ( G ) .
For a transversal T T T , the restriction S ( G ) ∣ T \mathcal{S}(G)|_T S ( G ) ∣ T is the frame matroid of the signed graph on G G G whose negative edges are the e e e with e ∗ ∈ T e^* \in T e ∗ ∈ T [10 , 11 ] , and a representation of S ( G ) \mathcal{S}(G) S ( G ) has to realize all these frame matroids by a single isotropic subspace. In the coding application [2 Sec. III] , an F q \mathbb{F}_q F q -representation of S ( G ) \mathcal{S}(G) S ( G ) is a stabilizer matrix of an [ [ ∣ E ∣ , ∣ E ∣ − r ( S ( G ) ) ] ] q [[|E|, |E| - r(\mathcal{S}(G))]]_q [[ ∣ E ∣ , ∣ E ∣ − r ( S ( G ))] ] q code.
Lemma 2.13. For a vertex s s s of G G G , let σ s : J → J \sigma_s : J \to J σ s : J → J exchange e e e and e ∗ e^* e ∗ for every non-loop edge e e e incident with s s s , and fix all other elements. Then S ∈ I ( G ) S \in\mathcal{I}(G) S ∈ I ( G ) if and only if σ s ( S ) ∈ I ( G ) \sigma_s(S) \in\mathcal{I}(G) σ s ( S ) ∈ I ( G ) . Consequently σ s \sigma_s σ s maps B ( S ( G ) ) \mathcal{B}(\mathcal{S}(G)) B ( S ( G )) onto itself and r S ( G ) ( σ s ( A ) ) = r S ( G ) ( A ) r_{\mathcal{S}(G)}(\sigma_s(A)) = r_{\mathcal{S}(G)}(A) r S ( G ) ( σ s ( A )) = r S ( G ) ( A ) for all A ∈ A ( J ) A \in\mathcal{A}(J) A ∈ A ( J ) .
Proof. S S S and σ s ( S ) \sigma_s(S) σ s ( S ) meet the same pairs, so G [ S ] = G [ σ s ( S ) ] G[S] = G[\sigma_s(S)] G [ S ] = G [ σ s ( S )] . A cycle of length at least two contains either zero or exactly two non-loop edges incident with s s s , and a loop is fixed by σ s \sigma_s σ s . Hence the parity of the number of starred edges on every cycle is the same for S S S and σ s ( S ) \sigma_s(S) σ s ( S ) .
Graphs, incidence matrices and flows
For a graph G G G , c ( G ) c(G) c ( G ) is its number of components. A bridge is a non-loop edge whose deletion increases the number of components; an edge is a bridge if and only if it lies on no cycle. For an edge e e e , G ∖ e G \setminus e G ∖ e is obtained by deleting e e e . If e e e is not a loop, G / e G/e G / e is obtained by identifying the ends of e e e and deleting e e e ; edges parallel to e e e become loops. For the edge set P P P of a forest, G / P G/P G / P is obtained by contracting the edges of P P P one by one. For X ⊆ E X \subseteq E X ⊆ E we write 1 X ∈ F E \mathbf{1}_X \in\mathbb{F}^E 1 X ∈ F E for its indicator vector, and for s ∈ V s \in V s ∈ V we write 1 s ∈ F V \mathbf{1}_s \in\mathbb{F}^V 1 s ∈ F V for the corresponding unit vector. M ( G ) M(G) M ( G ) denotes the cycle matroid of G G G .
Definition 2.14 (Incidence matrices). Fix an orientation of G G G , so that every non-loop edge e e e has a tail s s s and a head t t t . The oriented incidence matrix D ^ ∈ F V × E \widehat{D} \in\mathbb{F}^{V \times E} D ∈ F V × E has column 1 s − 1 t \mathbf{1}_s-\mathbf{1}_t 1 s − 1 t for such an edge and a zero column for every loop. Fix one vertex, the root , in each component of G G G . The reduced incidence matrix D ∈ F ( ∣ V ∣ − c ( G ) ) × E D \in\mathbb{F}^{(|V|-c(G)) \times E} D ∈ F ( ∣ V ∣ − c ( G )) × E is obtained from D ^ \widehat{D} D by deleting the rows of the roots. Thus D D D has exactly one column for each edge e e e ; we denote it by ∂ e \partial e ∂ e . Explicitly, ∂ e \partial e ∂ e is 1 s − 1 t \mathbf{1}_s-\mathbf{1}_t 1 s − 1 t with the entries at the roots deleted, and ∂ e = 0 \partial e=0 ∂ e = 0 if e e e is a loop.
Reversing the orientation of e e e replaces ∂ e \partial e ∂ e by − ∂ e -\partial e − ∂ e , and parallel edges with the same orientation have equal columns. The matrix D D D has rank ∣ V ∣ − c ( G ) |V|-c(G) ∣ V ∣ − c ( G ) and represents M ( G ) M(G) M ( G ) over every field [8 Sec. 5.1] . In the normal form of § 3 , ∂ e \partial e ∂ e is the upper part of the column of the unstarred element e e e ; the starred element e ∗ e^* e ∗ contributes a column of the second block, not of D D D . For U ⊆ V U \subseteq V U ⊆ V let
F 0 U = { y ∈ F V : supp ( y ) ⊆ U , ∑ s ∈ V y s = 0 } . \mathbb{F}_0^U=\left\{y\in\mathbb{F}^V:\operatorname{supp}(y)\subseteq U,\ \sum_{s\in V}y_s=0\right\}. F 0 U = { y ∈ F V : supp ( y ) ⊆ U , s ∈ V ∑ y s = 0 } . If G G G is connected with root s 0 s_0 s 0 , we identify F V ∖ { s 0 } \mathbb{F}^{V\setminus\{s_0\}} F V ∖ { s 0 } with F 0 V \mathbb{F}_0^V F 0 V via y ↦ ( y , − ∑ s y s ) y\mapsto(y,-\sum_s y_s) y ↦ ( y , − ∑ s y s ) . Then ∂ e = 1 s − 1 t \partial e=\mathbf{1}_s-\mathbf{1}_t ∂ e = 1 s − 1 t , and for every connected subgraph K K K of G G G
span { ∂ e : e ∈ E ( K ) } = F 0 V ( K ) . (3) \operatorname{span}\{\partial e:e\in E(K)\}=\mathbb{F}_0^{V(K)}. \tag*{(3)} span { ∂ e : e ∈ E ( K )} = F 0 V ( K ) . (3)
Definition 2.15 (Flows). Let Λ \Lambda Λ be an abelian group. A Λ \Lambda Λ -flow on G G G is a map z : E → Λ z:E\to\Lambda z : E → Λ such that at every vertex the sum of the values on the edges
leaving it equals the sum of the values on the edges entering it; loops impose no condition. It is nowhere-zero if z ( e ) ≠ 0 z(e) \ne0 z ( e ) = 0 for all e e e . A nowhere-zero k k k -flow is a nowhere-zero Z \mathbb{Z} Z -flow with values in { ± 1 , … , ± ( k − 1 ) } \{\pm1,\ldots,\pm(k-1)\} { ± 1 , … , ± ( k − 1 )} . For Λ = ( F , + ) \Lambda= (\mathbb{F},+) Λ = ( F , + ) , z z z is a flow if and only if D ^ z = 0 \widehat{D}z=0 D z = 0 , if and only if D z = 0 Dz=0 D z = 0 , because the row of a root is minus the sum of the other rows of its component.
We use the following standard facts. (F1) Every flow vanishes on bridges. (F2) For a finite abelian group Λ \Lambda Λ , G G G has a nowhere-zero Λ \Lambda Λ -flow if and only if it has a nowhere-zero ∣ Λ ∣ |\Lambda| ∣Λ∣ -flow [12 ] . (F3) Every bridgeless graph has a nowhere-zero Z 2 \mathbb{Z}_2 Z 2 -flow [5 ] . (F4) A loopless graph has a nowhere-zero Z 2 \mathbb{Z}_2 Z 2 -flow if and only if all its degrees are even. (F5) A cubic graph has a nowhere-zero 4 4 4 -flow if and only if it is 3-edge-colourable, and a nowhere-zero 3 3 3 -flow if and only if it is bipartite [13 ] .
We write G ∘ G^\circ G ∘ for the graph obtained from G G G by deleting all loops and all bridges. An edge of G ∘ G^\circ G ∘ lies on a cycle of G G G that contains no bridge and no loop, so G ∘ G^\circ G ∘ is bridgeless and loopless. We write ν ∘ ( G ) \nu_\circ(G) ν ∘ ( G ) for the maximum number of pairwise vertex-disjoint cycles of G G G .
Lemma 2.16 (Signed incidence vectors). Let char F ≠ 2 \operatorname{char}\mathbb{F}\ne2 char F = 2 , and let K K K be a graph with a sign σ ( e ) ∈ { 1 , − 1 } \sigma(e)\in\{1,-1\} σ ( e ) ∈ { 1 , − 1 } on every edge. For an edge e e e with ends s , t s,t s , t , where s = t s=t s = t if e e e is a loop, put c e = 1 s − σ ( e ) 1 t ∈ F V ( K ) c_e=\mathbf{1}_s-\sigma(e)\mathbf{1}_t\in\mathbb{F}^{V(K)} c e = 1 s − σ ( e ) 1 t ∈ F V ( K ) . The vectors c e c_e c e , e ∈ E ( K ) e\in E(K) e ∈ E ( K ) , are linearly independent if and only if every component of K K K is a tree or is unicyclic with an odd number of negative edges on its cycle.
Proof. Up to sign, c e c_e c e does not depend on the order of s , t s,t s , t . Vectors of different components have disjoint supports, so we may assume that K K K is connected. If ∣ E ( K ) ∣ > ∣ V ( K ) ∣ |E(K)|>|V(K)| ∣ E ( K ) ∣ > ∣ V ( K ) ∣ , the vectors are dependent. In a relation ∑ e λ e c e = 0 \sum_e\lambda_e c_e=0 ∑ e λ e c e = 0 , a vertex of degree one forces the coefficient of its edge to vanish, so we may delete leaves repeatedly. This settles the case of trees. If K K K is unicyclic, we are reduced to its cycle s 1 e 1 s 2 e 2 ⋯ s m e m s 1 s_1e_1s_2e_2\cdots s_me_ms_1 s 1 e 1 s 2 e 2 ⋯ s m e m s 1 with m ≥ 1 m\ge1 m ≥ 1 , where e j e_j e j joins s j s_j s j and s j + 1 s_{j+1} s j + 1 (indices modulo m m m ; for m = 1 m=1 m = 1 the cycle is a loop). Write c j = 1 s j − σ j 1 s j + 1 c_j=\mathbf{1}_{s_j}-\sigma_j\mathbf{1}_{s_{j+1}} c j = 1 s j − σ j 1 s j + 1 with σ j = σ ( e j ) \sigma_j=\sigma(e_j) σ j = σ ( e j ) . Comparing coefficients at s j + 1 s_{j+1} s j + 1 in ∑ j λ j c j = 0 \sum_j\lambda_jc_j=0 ∑ j λ j c j = 0 gives λ j + 1 = σ j λ j \lambda_{j+1}=\sigma_j\lambda_j λ j + 1 = σ j λ j , hence λ 1 = ( ∏ j σ j ) λ 1 \lambda_1=(\prod_j\sigma_j)\lambda_1 λ 1 = ( ∏ j σ j ) λ 1 . If ∏ j σ j = 1 \prod_j\sigma_j=1 ∏ j σ j = 1 , then λ j = σ 1 ⋯ σ j − 1 \lambda_j=\sigma_1\cdots\sigma_{j-1} λ j = σ 1 ⋯ σ j − 1 is a nontrivial relation. If ∏ j σ j = − 1 \prod_j\sigma_j=-1 ∏ j σ j = − 1 , then 2 λ 1 = 0 2\lambda_1=0 2 λ 1 = 0 , so all λ j \lambda_j λ j vanish because char F ≠ 2 \operatorname{char}\mathbb{F}\ne2 char F = 2 .
The intrinsic rank, contraction, normal form
The rank of admissible sets in a representation
Lemma 3.1 (Intrinsic rank). Let H ∈ F k × 2 n H \in\mathbb{F}^{k \times2n} H ∈ F k × 2 n be isotropic of rank k k k , and let S \mathcal{S} S be the symplectic matroid it represents. Then for every A ∈ A ( J ) A \in\mathcal{A}(J) A ∈ A ( J )
rank H [ A ] = r S ( A ) . \operatorname{rank} H[A] = r_{\mathcal{S}}(A). rank H [ A ] = r S ( A ) . In particular, an admissible set is independent in S \mathcal{S} S if and only if its columns are linearly independent.
Proof. Let W W W be the row space of H H H , and for U ⊆ J U \subseteq J U ⊆ J let L U ≤ F J L_U \leq\mathbb{F}^{J} L U ≤ F J be the span of the unit vectors indexed by U U U . For a transversal T T T , the projection of W W W onto the coordinates in T T T has kernel W ∩ L J ∖ T = W ∩ L T ∗ W \cap L_{J\setminus T} = W \cap L_{T^*} W ∩ L J ∖ T = W ∩ L T ∗ , so
rank H [ T ] = k − dim ( W ∩ L T ∗ ) . (4) \operatorname{rank} H[T] = k - \dim(W \cap L_{T^*}). \tag*{(4)} rank H [ T ] = k − dim ( W ∩ L T ∗ ) . (4)
Step 1. Let I I I be admissible with linearly independent columns. Then W ∩ L I ∗ = 0 W \cap L_{I^*} = 0 W ∩ L I ∗ = 0 . Indeed, let Ω = ( 0 I n − I n 0 ) \Omega= \begin{pmatrix} 0 & I_n \\ -I_n & 0 \end{pmatrix} Ω = ( 0 − I n I n 0 ) , so that ω ( x , y ) = x Ω y T \omega(x,y) = x\Omega y^{T} ω ( x , y ) = x Ω y T . For w ∈ W w \in W w ∈ W , isotropy gives H Ω w T = 0 H\Omega w^{T} = 0 H Ω w T = 0 , so Ω w T \Omega w^{T} Ω w T is a linear relation among the columns of H H H ; its support is supp ( w ) ∗ \operatorname{supp}(w)^* supp ( w ) ∗ . A nonzero w ∈ W ∩ L I ∗ w \in W \cap L_{I^*} w ∈ W ∩ L I ∗ would therefore give a nontrivial relation among the columns of I I I .
Step 2. Let U U U be admissible with W ∩ L U = 0 W \cap L_U = 0 W ∩ L U = 0 , and let { i , i ∗ } \{i,i^*\} { i , i ∗ } be a pair not met by U U U . Then W ∩ L U ∪ { i } = 0 W \cap L_{U\cup\{i\}} = 0 W ∩ L U ∪ { i } = 0 or W ∩ L U ∪ { i ∗ } = 0 W \cap L_{U\cup\{i^*\}} = 0 W ∩ L U ∪ { i ∗ } = 0 . Otherwise choose nonzero w 1 ∈ W ∩ L U ∪ { i } w_1 \in W \cap L_{U\cup\{i\}} w 1 ∈ W ∩ L U ∪ { i } and w 2 ∈ W ∩ L U ∪ { i ∗ } w_2 \in W \cap L_{U\cup\{i^*\}} w 2 ∈ W ∩ L U ∪ { i ∗ } . Since W ∩ L U = 0 W \cap L_U = 0 W ∩ L U = 0 , we have ( w 1 ) i ≠ ( w 2 ) i ∗ ≠ 0 (w_1)_i \ne(w_2)_{i^*} \ne0 ( w 1 ) i = ( w 2 ) i ∗ = 0 , while ( w 1 ) i ∗ = ( w 2 ) i = 0 (w_1)_{i^*} = (w_2)_i = 0 ( w 1 ) i ∗ = ( w 2 ) i = 0 . For j ≠ i j \ne i j = i , U U U contains at most one of j , j ∗ j,j^* j , j ∗ , so ( w 1 ) j ( w 2 ) j ∗ = ( w 1 ) j ∗ ( w 2 ) j = 0 (w_1)_j(w_2)_{j^*} = (w_1)_{j^*}(w_2)_j = 0 ( w 1 ) j ( w 2 ) j ∗ = ( w 1 ) j ∗ ( w 2 ) j = 0 . Hence ω ( w 1 , w 2 ) = ( w 1 ) i ( w 2 ) i ∗ ≠ 0 \omega(w_1,w_2) = (w_1)_i(w_2)_{i^*} \ne0 ω ( w 1 , w 2 ) = ( w 1 ) i ( w 2 ) i ∗ = 0 , contradicting isotropy.
Step 3. Let I ⊆ A I \subseteq A I ⊆ A index a basis of the column space of H [ A ] H[A] H [ A ] , so ∣ I ∣ = rank H [ A ] |I| = \operatorname{rank} H[A] ∣ I ∣ = rank H [ A ] . By Step 1, W ∩ L I ∗ = 0 W \cap L_{I^*} = 0 W ∩ L I ∗ = 0 . Applying Step 2 to one pair at a time, extend I ∗ I^* I ∗ to a transversal T ∗ T^* T ∗ with W ∩ L T ∗ = 0 W \cap L_{T^*} = 0 W ∩ L T ∗ = 0 . Then T ⊇ I T \supseteq I T ⊇ I , and rank H [ T ] = k \operatorname{rank} H[T] = k rank H [ T ] = k by (4). Extending I I I inside T T T to a basis of the column space of H [ T ] H[T] H [ T ] gives B ∈ A k ( J ) B \in\mathcal{A}_k(J) B ∈ A k ( J ) with det H [ B ] ≠ 0 \det H[B] \ne0 det H [ B ] = 0 and I ⊆ B I \subseteq B I ⊆ B . With A = ∅ A = \varnothing A = ∅ this shows that S \mathcal{S} S has a basis. Thus r S ( A ) ≥ ∣ A ∩ B ∣ ≥ ∣ I ∣ = rank H [ A ] r_{\mathcal{S}}(A) \geq|A \cap B| \geq|I| = \operatorname{rank} H[A] r S ( A ) ≥ ∣ A ∩ B ∣ ≥ ∣ I ∣ = rank H [ A ] . Conversely, the columns of A ∩ B A \cap B A ∩ B are linearly independent for every basis B B B , so rank H [ A ] ≥ r S ( A ) \operatorname{rank} H[A] \geq r_{\mathcal{S}}(A) rank H [ A ] ≥ r S ( A ) .
Remark 3.2. For Lagrangian matroids, Bouchet [14 Thm. 4.1] computed the rank function of a represented delta-matroid in terms of matrix ranks; see also [7 Sec. 1] . Lemma 3.1 treats isotropic subspaces of every dimension. It also shows that the ordinary vector matroid of the columns of H H H assigns to every admissible set the same rank as S \mathcal{S} S (Proposition 8.2 ).
Contraction
Lemma 3.3 (Contraction of representations). Let H ∈ F k × 2 n H \in\mathbb{F}^{k\times2n} H ∈ F k × 2 n be isotropic and represent S S S , and let a ∈ J a \in J a ∈ J have a nonzero column. After left multiplication by an element of GL k ( F ) \operatorname{GL}_k(\mathbb{F}) GL k ( F ) , assume that the column of a a a is the first unit vector. Let H / a H/a H / a be obtained by deleting the first row and the columns indexed by a a a and a ∗ a^* a ∗ . Then H / a H/a H / a is isotropic of rank k − 1 k-1 k − 1 and represents S / a S/a S / a .
Proof. By Lemma 3.1, a a a is not a loop, so S / a S/a S / a is defined (Lemma 2.8). Rows 2 , … , k 2,\ldots,k 2 , … , k of H H H vanish in column a a a . Hence, for 2 ≤ i , j ≤ k 2 \leq i,j \leq k 2 ≤ i , j ≤ k , the contribution of the pair J a J_a J a to ω ( h i , h j ) \omega(h_i,h_j) ω ( h i , h j ) is h i ( a ) h j ( a ∗ ) − h i ( a ∗ ) h j ( a ) = 0 h_i(a)h_j(a^*)-h_i(a^*)h_j(a)=0 h i ( a ) h j ( a ∗ ) − h i ( a ∗ ) h j ( a ) = 0 , and the shortened rows remain pairwise orthogonal. If a linear combination w w w of rows 2 , … , k 2,\ldots,k 2 , … , k vanished outside J a J_a J a , then w ∈ W ∩ L { a ∗ } w \in W \cap L_{\{a^*\}} w ∈ W ∩ L { a ∗ } , which is 0 by Step 1 of the proof of Lemma 3.1 applied to I = { a } I=\{a\} I = { a } ; hence H / a H/a H / a has rank k − 1 k-1 k − 1 . Expanding along column a a a gives det H [ B ′ ∪ { a } ] = ± det ( H / a ) [ B ′ ] \det H[B' \cup\{a\}] = \pm\det(H/a)[B'] det H [ B ′ ∪ { a }] = ± det ( H / a ) [ B ′ ] for every admissible ( k − 1 ) (k-1) ( k − 1 ) -set B ′ ⊆ J ∖ J a B' \subseteq J \setminus J_a B ′ ⊆ J ∖ J a .
Lemma 3.4 (Contraction of graphical symplectic matroids). Let P ⊆ E P \subseteq E P ⊆ E be the edge set of a forest of G G G , viewed as a set of unstarred elements. For every admissible S S S disjoint from J P J_P J P ,
S ∪ P ∈ I ( G ) ⟺ S ∈ I ( G / P ) . S \cup P \in\mathcal{I}(G) \Longleftrightarrow S \in\mathcal{I}(G/P). S ∪ P ∈ I ( G ) ⟺ S ∈ I ( G / P ) . Proof. Contracting P P P maps the components of G [ S ∪ P ] G[S \cup P] G [ S ∪ P ] bijectively onto the components of ( G / P ) [ S ] (G/P)[S] ( G / P ) [ S ] . A component K K K containing p p p edges of P P P is mapped to a component K ′ K' K ′ with ∣ V ( K ′ ) ∣ = ∣ V ( K ) ∣ − p |V(K')| = |V(K)| - p ∣ V ( K ′ ) ∣ = ∣ V ( K ) ∣ − p and ∣ E ( K ′ ) ∣ = ∣ E ( K ) ∣ − p |E(K')| = |E(K)| - p ∣ E ( K ′ ) ∣ = ∣ E ( K ) ∣ − p , because P ∩ E ( K ) P \cap E(K) P ∩ E ( K ) is a forest. Hence trees go to trees and unicyclic components to unicyclic components. The cycle of K ′ K' K ′ consists of the edges of the cycle of K K K not in P P P , and it has the same starred edges, because the edges of P P P are unstarred.
Corollary 3.5.
For every graph G G G , I ( G ) \mathcal{I}(G) I ( G ) is the family of independent sets of a symplectic matroid S ( G ) \mathcal{S}(G) S ( G ) .
If P P P is the edge set of a forest of G G G , then S ( G / P ) = S ( G ) / P \mathcal{S}(G/P) = \mathcal{S}(G)/P S ( G / P ) = S ( G ) / P , the iterated contraction by the unstarred elements of P P P , and r ( S ( G / P ) ) = r ( S ( G ) ) − ∣ P ∣ r(\mathcal{S}(G/P)) = r(\mathcal{S}(G)) - |P| r ( S ( G / P )) = r ( S ( G )) − ∣ P ∣ .
If H H H represents S ( G ) \mathcal{S}(G) S ( G ) , then the iterated contraction H / P H/P H / P (Lemma 3.3) represents S ( G / P ) \mathcal{S}(G/P) S ( G / P ) .
Proof. For loopless G G G , (2) follows from Lemma 3.4, Theorem 2.11 and Lemma 2.8(1), since P P P is independent and the independent sets of S ( G ) / P S(G)/P S ( G ) / P are the sets S S S with S ∪ P ∈ I ( G ) S \cup P \in\mathcal{I}(G) S ∪ P ∈ I ( G ) . For (1), let G G G have loops ℓ 1 , … , ℓ m \ell_1,\ldots,\ell_m ℓ 1 , … , ℓ m , at vertices s 1 , … , s m s_1,\ldots,s_m s 1 , … , s m . Let G ′ G' G ′ be the loopless graph obtained by replacing each ℓ j \ell_j ℓ j by two parallel edges ℓ j , f j \ell_j,f_j ℓ j , f j joining s j s_j s j to a new vertex t j t_j t j . Then P = { f 1 , … , f m } P=\{f_1,\ldots,f_m\} P = { f 1 , … , f m } is a forest and G ′ / P = G G'/P=G G ′ / P = G , so (1) follows from the loopless case of (2). Now (2) holds in general by the same argument, and (3) follows from (2) and Lemma 3.3, applied once for each edge of P P P ; each such edge has a nonzero column because P P P is independent.
Lemma 3.6 (Components). If G = G 1 ⊔ G 2 G=G_1\sqcup G_2 G = G 1 ⊔ G 2 , then S ( G ) = S ( G 1 ) ⊕ S ( G 2 ) S(G)=S(G_1)\oplus S(G_2) S ( G ) = S ( G 1 ) ⊕ S ( G 2 ) , and S ( G ) S(G) S ( G ) is F \mathbb{F} F -representable if and only if both S ( G 1 ) S(G_1) S ( G 1 ) and S ( G 2 ) S(G_2) S ( G 2 ) are.
Proof. The components of G [ S ] G[S] G [ S ] are those of G 1 [ S ∩ J E ( G 1 ) ] G_1[S\cap J_{E(G_1)}] G 1 [ S ∩ J E ( G 1 ) ] and of G 2 [ S ∩ J E ( G 2 ) ] G_2[S\cap J_{E(G_2)}] G 2 [ S ∩ J E ( G 2 ) ] , which gives the direct sum decomposition; block-diagonal matrices give one direction of the second claim. Conversely, let H H H represent S ( G ) S(G) S ( G ) and let B 2 B_2 B 2 be a basis of S ( G 2 ) S(G_2) S ( G 2 ) . Then S ( G ) / B 2 S(G)/B_2 S ( G ) / B 2 is S ( G 1 ) S(G_1) S ( G 1 ) together with the elements of the remaining pairs of G 2 G_2 G 2 , all of which are loops. By Lemmas 3.3 and 3.1, the iterated contraction H / B 2 H/B_2 H / B 2 represents S ( G ) / B 2 S(G)/B_2 S ( G ) / B 2 , and its loop columns are zero. Deleting these pairs preserves isotropy and leaves a representation of S ( G 1 ) S(G_1) S ( G 1 ) .
The normal form
Definition 3.7 (Normal form). Let G G G be a connected graph containing a cycle, with n = ∣ E ∣ n=|E| n = ∣ E ∣ , a fixed orientation and a fixed root, and let D ∈ F ( ∣ V ∣ − 1 ) × n D\in\mathbb{F}^{(|V|-1)\times n} D ∈ F ( ∣ V ∣ − 1 ) × n be its reduced incidence matrix. A representation of S ( G ) S(G) S ( G ) over F \mathbb{F} F is in normal form if it has the shape
H = [ D Z 1 0 z ] ∈ F ∣ V ∣ × 2 n , Z 1 ∈ F ( ∣ V ∣ − 1 ) × n , z ∈ F 1 × n . (5) H=\begin{bmatrix}D&Z_1\\0&z\end{bmatrix}\in\mathbb{F}^{|V|\times2n},\qquad Z_1\in\mathbb{F}^{(|V|-1)\times n},\quad z\in\mathbb{F}^{1\times n}. \tag*{(5)} H = [ D 0 Z 1 z ] ∈ F ∣ V ∣ × 2 n , Z 1 ∈ F ( ∣ V ∣ − 1 ) × n , z ∈ F 1 × n . (5) We write Z 1 , e Z_{1,e} Z 1 , e for the column of Z 1 Z_1 Z 1 indexed by e e e and z e z_e z e for the entry of z z z , so that the columns of e e e and e ∗ e^* e ∗ are ( ∂ e ; 0 ) (\partial_e;0) ( ∂ e ; 0 ) and ( Z 1 , e ; z e ) (Z_{1,e};z_e) ( Z 1 , e ; z e ) .
Theorem 3.8 (Normal form). Let G G G be a connected graph containing a cycle. If S ( G ) S(G) S ( G ) is F \mathbb{F} F -representable, then it has a representation in normal form ; more precisely, every representation of S ( G ) S(G) S ( G ) over F \mathbb{F} F is brought into normal form by left multiplication by an element of GL ∣ V ∣ ( F ) \operatorname{GL}_{|V|}(\mathbb{F}) GL ∣ V ∣ ( F ) followed by pair scalings. Every representation (5) in normal form satisfies
(N1) D z T = 0 Dz^{T}=0 D z T = 0 , that is, z z z is an F \mathbb{F} F -flow on G G G ;
(N2) z e ≠ 0 z_e \ne0 z e = 0 for every edge e e e lying on a cycle (loops included), and z e = 0 z_e=0 z e = 0 for every bridge e e e ;
(N3) D Z 1 T DZ_1^{T} D Z 1 T is symmetric, that is, ∑ e ∈ E ∂ e ∧ Z 1 , e = 0 \sum_{e\in E}\partial_e\wedge Z_{1,e}=0 ∑ e ∈ E ∂ e ∧ Z 1 , e = 0 .
Conversely, every matrix of the shape (5) with z ≠ 0 z\ne0 z = 0 that satisfies (N1) and (N3) is isotropic of rank ∣ V ∣ |V| ∣ V ∣ .
Proof. Let H ′ = [ X ′ ∣ Z ′ ] H'=[X'\mid Z'] H ′ = [ X ′ ∣ Z ′ ] represent S ( G ) S(G) S ( G ) ; its rank is ∣ V ∣ |V| ∣ V ∣ by Lemma 2.12. A set A ⊆ E A\subseteq E A ⊆ E of unstarred elements has no starred edges, so A A A is independent in S ( G ) S(G) S ( G ) if and only if G [ A ] G[A] G [ A ] is a forest; in particular loops are dependent. By Lemma 3.1, X ′ X' X ′ represents the cycle matroid M ( G ) M(G) M ( G ) , which has rank ∣ V ∣ − 1 |V|-1 ∣ V ∣ − 1 , and loops have zero columns. Since M ( G ) M(G) M ( G ) is regular, any two of its representations over F \mathbb{F} F are projectively equivalent [4 ] , [8 Sec. 6.3, 6.6] . Applying this to X ′ X' X ′ , viewed as a matrix of rank ∣ V ∣ − 1 |V|-1 ∣ V ∣ − 1 whose column space is identified with F ∣ V ∣ − 1 \mathbb{F}^{|V|-1} F ∣ V ∣ − 1 , and to D D D , we obtain an injective linear map φ : F ∣ V ∣ − 1 → F ∣ V ∣ \varphi:\mathbb{F}^{|V|-1}\to\mathbb{F}^{|V|} φ : F ∣ V ∣ − 1 → F ∣ V ∣ and scalars c e ∈ F × c_e\in\mathbb{F}^{\times} c e ∈ F × with X e ′ = c e φ ( ∂ e ) X'_e=c_e\varphi(\partial_e) X e ′ = c e φ ( ∂ e ) for every non-loop edge e e e . Choose R ∈ GL ∣ V ∣ ( F ) R\in\operatorname{GL}_{|V|}(\mathbb{F}) R ∈ GL ∣ V ∣ ( F ) with R φ ( y ) = ( y ; 0 ) R\varphi(y)=(y;0) R φ ( y ) = ( y ; 0 ) for all y y y , and apply the pair scalings ( x e , z e ) ↦ ( c e − 1 x e , c e z e ) (x_e,z_e)\mapsto(c_e^{-1}x_e,c_ez_e) ( x e , z e ) ↦ ( c e − 1 x e , c e z e ) . These operations preserve isotropy and the represented matroid and produce the matrix form (5) .
For any matrix of this shape,
X Z T − Z X T = ( D Z 1 T − Z 1 D T D z T − z D T 0 ) , XZ^{T}-ZX^{T}=
\begin{pmatrix}
DZ_1^{T}-Z_1D^{T} & Dz^{T}\\
-zD^{T} & 0
\end{pmatrix}, X Z T − Z X T = ( D Z 1 T − Z 1 D T − z D T D z T 0 ) ,
so isotropy is equivalent to (N1) together with (N3). If z ≠ 0 z\ne0 z = 0 , the last row is not a linear combination of the others, because D D D has full row rank; this proves the converse.
For (N2), let e e e lie on a cycle C C C . Choose a spanning tree Y Y Y of G G G containing C ∖ { e } C\setminus\{e\} C ∖ { e } (any spanning tree if e e e is a loop). Then G [ Y ∪ { e ∗ } ] G[Y\cup\{e^*\}] G [ Y ∪ { e ∗ }] is connected and unicyclic, and its cycle C C C contains exactly one starred edge, so Y ∪ { e ∗ } Y\cup\{e^*\} Y ∪ { e ∗ } is a basis. Expanding along the last row, det H [ Y ∪ { e ∗ } ] = ± z e det D [ Y ] \det H[Y\cup\{e^*\}]=\pm z_e\det D[Y] det H [ Y ∪ { e ∗ }] = ± z e det D [ Y ] , and D [ Y ] D[Y] D [ Y ] is invertible; hence z e ≠ 0 z_e\ne0 z e = 0 . Finally, z e = 0 z_e=0 z e = 0 for bridges by (N1) and (F1). □
For an edge e e e with z e ≠ 0 z_e\ne0 z e = 0 we put
w e : = z e − 1 Z 1 , e ∈ F ∣ V ∣ − 1 , so that the column of e ∗ is z e ( w e ; 1 ) . (6) w_e:=z_e^{-1}Z_{1,e}\in\mathbb{F}^{|V|-1},
\qquad\text{so that the column of }e^*\text{ is }z_e(w_e;1). \tag*{(6)} w e := z e − 1 Z 1 , e ∈ F ∣ V ∣ − 1 , so that the column of e ∗ is z e ( w e ; 1 ) . (6)
Using the next lemma we extract linear information from the matroid.
Lemma 3.9 (Two-star relations). Let H H H be a representation in normal form, let C C C be a cycle of G G G consisting of non-loop edges, and let e ≠ f e \ne f e = f be edges of C C C . Then
w e − w f ∈ span { ∂ g : g ∈ C ∖ { e , f } } ⊆ F 0 V ( C ) w_e-w_f \in\operatorname{span}\{\partial_g : g \in C \setminus\{e,f\}\} \subseteq\mathbb{F}^{V(C)}_0 w e − w f ∈ span { ∂ g : g ∈ C ∖ { e , f }} ⊆ F 0 V ( C ) In particular w e = w f w_e=w_f w e = w f if e e e and f f f are parallel. If C = { e , f , g } C=\{e,f,g\} C = { e , f , g } is a triangle, there is t ∈ F t \in\mathbb{F} t ∈ F with
w e − w f = t ε g ∂ g , w f − w g = t ε e ∂ e , w g − w e = t ε f ∂ f , (7) w_e-w_f=t\varepsilon_g\partial_g,\qquad w_f-w_g=t\varepsilon_e\partial_e,\qquad w_g-w_e=t\varepsilon_f\partial_f, \tag*{(7)} w e − w f = t ε g ∂ g , w f − w g = t ε e ∂ e , w g − w e = t ε f ∂ f , (7) where ε e ∂ e + ε f ∂ f + ε g ∂ g = 0 \varepsilon_e\partial_e+\varepsilon_f\partial_f+\varepsilon_g\partial_g=0 ε e ∂ e + ε f ∂ f + ε g ∂ g = 0 , ε ∈ { ± 1 } \varepsilon\in\{\pm1\} ε ∈ { ± 1 } , is the cycle relation of $C.
Proof. The set S = ( C ∖ { e , f } ) ∪ { e ∗ , f ∗ } S=(C\setminus\{e,f\})\cup\{e^*,f^*\} S = ( C ∖ { e , f }) ∪ { e ∗ , f ∗ } is admissible, and the only nontrivial component of G [ S ] G[S] G [ S ] is the cycle C C C , with two starred edges. So S S S is dependent. Its unstarred part C ∖ { e , f } C\setminus\{e,f\} C ∖ { e , f } is a forest, so the columns ( ∂ g ; 0 ) (\partial_g;0) ( ∂ g ; 0 ) , g ∈ C ∖ { e , f } g \in C\setminus\{e,f\} g ∈ C ∖ { e , f } , are linearly independent. A linear relation therefore has the form α z e ( w e ; 1 ) + β z f ( w f ; 1 ) ∈ span { ( ∂ g ; 0 ) } \alpha z_e(w_e;1)+\beta z_f(w_f;1)\in\operatorname{span}\{(\partial_g;0)\} α z e ( w e ; 1 ) + β z f ( w f ; 1 ) ∈ span {( ∂ g ; 0 )} with ( α , β ) ≠ ( 0 , 0 ) (\alpha,\beta)\ne(0,0) ( α , β ) = ( 0 , 0 ) . The last coordinate gives α z e = − β z f \alpha z_e=-\beta z_f α z e = − β z f , and this is nonzero; dividing by it gives the first claim. If C = { e , f , g } C=\{e,f,g\} C = { e , f , g } is a triangle, the three relations read w e − w f = α ∂ g w_e-w_f=\alpha\partial_g w e − w f = α ∂ g , w f − w g = β ∂ e w_f-w_g=\beta\partial_e w f − w g = β ∂ e and w g − w e = γ ∂ f w_g-w_e=\gamma\partial_f w g − w e = γ ∂ f . Their sum gives β ∂ e + γ ∂ f + α ∂ g = 0 \beta\partial_e+\gamma\partial_f+\alpha\partial_g=0 β ∂ e + γ ∂ f + α ∂ g = 0 . Since any two of ∂ e , ∂ f , ∂ g \partial_e,\partial_f,\partial_g ∂ e , ∂ f , ∂ g are linearly independent, ( β , γ , α ) (\beta,\gamma,\alpha) ( β , γ , α ) is a multiple of ( ε e , ε f , ε g ) (\varepsilon_e,\varepsilon_f,\varepsilon_g) ( ε e , ε f , ε g ) .
Remark 3.10. Theorem 3.8 replaces the ∣ V ∣ ( 2 n − ∣ V ∣ ) |V|(2n-|V|) ∣ V ∣ ( 2 n − ∣ V ∣ ) coordinates of an affine chart of the Grassmannian by the ( ∣ V ∣ − 1 ) n (|V|-1)n ( ∣ V ∣ − 1 ) n entries of Z 1 Z_1 Z 1 and a flow z z z . For a finite field F \mathbb{F} F there are at most ∣ F ∣ n − ∣ V ∣ + 1 |\mathbb{F}|^{n-|V|+1} ∣ F ∣ n − ∣ V ∣ + 1 flows. For a fixed flow, (N3) and the relations obtained as in the proof of Lemma 3.9 from all dependent admissible sets with at most two starred elements and a forest as unstarred part are linear in Z 1 Z_1 Z 1 ; only the remaining determinant conditions are nonlinear. This is the procedure used for the computations reported in Appendix A.
The flow obstruction
Theorem 4.1. Let G G G be a graph and F \mathbb{F} F a field. If S ( G ) S(G) S ( G ) is F \mathbb{F} F -representable, then G ∘ G^\circ G ∘ admits a nowhere-zero ( F , + ) (\mathbb{F},+) ( F , + ) -flow. If F \mathbb{F} F is finite, this is equivalent to a nowhere-zero ∣ F ∣ |\mathbb{F}| ∣ F ∣ -flow on G ∘ G^\circ G ∘ .
Proof. By Lemma 3.6 each component L L L of G G G gives a representable S ( L ) S(L) S ( L ) , and G ∘ G^\circ G ∘ is the disjoint union of the graphs L ∘ L^\circ L ∘ . If L L L is acyclic, L ∘ L^\circ L ∘ has no edges. Otherwise take a representation of S ( L ) S(L) S ( L ) in normal form (Theorem 3.8). By (N1) the vector z z z is a flow on L L L , and by (N2) it is nonzero exactly on the edges lying on cycles. The edges of L ∘ L^\circ L ∘ are the non-loop edges lying on cycles. Deleting loops does not affect Kirchhoff’s law, and deleting bridges does not affect it either, because z z z vanishes there. So the restriction of z z z is a nowhere-zero flow on L ∘ L^\circ L ∘ . The last statement is (F2).
Corollary 4.2. Let G G G be loopless.
If S ( G ) S(G) S ( G ) is F 2 \mathbb{F}_2 F 2 -representable, every vertex has even degree in G ∘ G^\circ G ∘ .
If S ( G ) S(G) S ( G ) is F 4 \mathbb{F}_4 F 4 -representable, G ∘ G^\circ G ∘ has a nowhere-zero 4-flow; if moreover G ∘ G^\circ G ∘ is cubic, it is 3-edge-colourable.
S ( K 4 ) S(K_4) S ( K 4 ) and S ( K 3 , 3 ) S(K_{3,3}) S ( K 3 , 3 ) are not F 2 \mathbb{F}_2 F 2 -representable, and the matroid S ( P 10 ) S(P_{10}) S ( P 10 ) of the Petersen graph is representable neither over F 2 \mathbb{F}_2 F 2 nor over F 4 \mathbb{F}_4 F 4 .
Proof. (1) and (2) follow from Theorem 4.1 together with (F2), (F4) and (F5). For (3): K 4 K_4 K 4 , K 3 , 3 K_{3,3} K 3 , 3 and P 10 P_{10} P 10 are cubic and bridgeless, so they have no nowhere-zero Z 2 \mathbb{Z}_2 Z 2 -flow, and P 10 P_{10} P 10 is not 3-edge-colourable.
Remark 4.3. Theorem 4.1 is relevant only in characteristic 2. Indeed, let char F ≠ 2 \operatorname{char}\mathbb{F} \ne2 char F = 2 and suppose that every edge on a cycle of G G G , other than a loop, has a parallel mate, which by Theorem 5.1 below is necessary for representability. Then G ∘ G^\circ G ∘ is a union of parallel classes Π \Pi Π with ∣ Π ∣ ≥ 2 |\Pi| \ge2 ∣Π∣ ≥ 2 , and choosing values λ e ∈ F × \lambda_e \in\mathbb{F}^{\times} λ e ∈ F × with ∑ e ∈ Π λ e = 0 \sum_{e\in\Pi}\lambda_e=0 ∑ e ∈ Π λ e = 0 on each class, all edges of a class oriented alike, gives a nowhere-zero ( F , + ) (\mathbb{F},+) ( F , + ) -flow on G ∘ G^\circ G ∘ . Combined with Theorem 5.1 , the graphs K 4 K_4 K 4 , K 3 , 3 K_{3,3} K 3 , 3 and P 10 P_{10} P 10 of Corollary 4.2 give matroids that are not representable in any characteristic ≠ 2 \ne2 = 2 . S ( K 4 ) S(K_4) S ( K 4 ) and S ( K 3 , 3 ) S(K_{3,3}) S ( K 3 , 3 ) are representable over every field of characteristic 2 with more than two elements (Remark 6.3), whereas S ( P 10 ) S(P_{10}) S ( P 10 ) is representable over no field (Corollary 6.12 ).
Characteristic different from two: a complete classification
Theorem 5.1. Let G G G be a graph and F \mathbb{F} F a field with char F ≠ 2 \operatorname{char}\mathbb{F} \ne2 char F = 2 . Then S ( G ) S(G) S ( G ) is F \mathbb{F} F -representable if and only if every edge of G G G that lies on a cycle and is not a loop has a parallel mate. In particular, the answer does not depend on F \mathbb{F} F .
Proof. By Lemma 3.6 we may assume that G G G is connected. If G G G is a tree, every admissible set is independent, so S ( G ) = U n , n ∗ S(G)=U^{*}_{n,n} S ( G ) = U n , n ∗ with n = ∣ E ∣ n=|E| n = ∣ E ∣ , which is represented by [ I n ∣ I n ] [I_n\mid I_n] [ I n ∣ I n ] . Assume that G G G contains a cycle. Index rows by V V V , orient every edge that is not a loop, and give parallel edges the same orientation. For an edge e e e from s s s to t t t , where s = t s=t s = t if e e e is a loop, let d e = 1 s − 1 t d_e=1_s-1_t d e = 1 s − 1 t and q e = 1 s + 1 t q_e=1_s+1_t q e = 1 s + 1 t ; thus d e = 0 d_e=0 d e = 0 and q e = 21 s q_e=2 1_s q e = 2 1 s for a loop. Every edge on a cycle that is not a loop lies in a parallel class Π \Pi Π with ∣ Π ∣ ≥ 2 |\Pi|\ge2 ∣Π∣ ≥ 2 , and all edges of such a class lie on cycles. Choose λ e ∈ F × \lambda_e\in F^\times λ e ∈ F × for e ∈ Π e\in\Pi e ∈ Π with ∑ e ∈ Π λ e = 0 \sum_{e\in\Pi}\lambda_e=0 ∑ e ∈ Π λ e = 0 , for instance ( 1 , − 1 ) (1,-1) ( 1 , − 1 ) repeated, together with one triple ( 1 , 1 , − 2 ) (1,1,-2) ( 1 , 1 , − 2 ) if ∣ Π ∣ |\Pi| ∣Π∣ is odd; this is possible because char F ≠ 2 \operatorname{char} F\ne2 char F = 2 . Put λ e = 1 \lambda_e=1 λ e = 1 for every loop e e e , and
x e = d e ( e ∈ E ) , z e = λ e q e ( e not a bridge ) , z e = d e ( e a bridge ) , x_e=d_e\ (e\in E),\qquad z_e=\lambda_e q_e\ (e\text{ not a bridge}),\qquad z_e=d_e\ (e\text{ a bridge}), x e = d e ( e ∈ E ) , z e = λ e q e ( e not a bridge ) , z e = d e ( e a bridge ) ,
and H = [ X ∣ Z ] ∈ F V × 2 n H=[X\mid Z]\in F^{V\times2n} H = [ X ∣ Z ] ∈ F V × 2 n . Writing d Π , q Π d_\Pi,q_\Pi d Π , q Π for the common vectors of a class, and using d e = 0 d_e=0 d e = 0 for loops,
∑ e x e ∧ z e = ∑ Π ( ∑ e ∈ Π λ e ) d Π ∧ q Π + ∑ e b r i d g e d e ∧ d e = 0. \sum_e x_e\wedge z_e=\sum_\Pi\left(\sum_{e\in\Pi}\lambda_e\right)d_\Pi\wedge q_\Pi+\sum_{e\ \mathrm{bridge}}d_e\wedge d_e=0. e ∑ x e ∧ z e = Π ∑ ( e ∈ Π ∑ λ e ) d Π ∧ q Π + e bridge ∑ d e ∧ d e = 0.
so H H H is isotropic by (2) . Let S S S be admissible. After rescaling columns, H [ S ] H[S] H [ S ] consists of the vectors d e d_e d e for the unstarred edges of G [ S ] G[S] G [ S ] and for its starred edges that are bridges of G G G , and of the vectors q e q_e q e for its starred edges that are not bridges of G G G . These are the vectors c e c_e c e of Lemma 2.16 for the signed graph G [ S ] G[S] G [ S ] whose negative edges are the starred edges that are not bridges of G G G . Since bridges of G G G lie on no cycle, the negative edges on a cycle of G [ S ] G[S] G [ S ] are exactly its starred edges. By Lemma 2.16 , the columns of S S S are independent if and only if S S S satisfies Chow’s rule. Finally, the set described in the proof of Lemma 2.12 has ∣ V ∣ |V| ∣ V ∣ independent columns, so rank H = ∣ V ∣ = r ( S ( G ) ) \operatorname{rank} H=|V|=r(S(G)) rank H = ∣ V ∣ = r ( S ( G )) and H H H represents S ( G ) S(G) S ( G ) .
Conversely, suppose that H H H represents S ( G ) S(G) S ( G ) over F F F with char F ≠ 2 \operatorname{char} F\ne2 char F = 2 , and that an edge e 0 e_0 e 0 with distinct ends a a a and b b b lies on a cycle and has no parallel mate. By Lemma 3.6 we may assume G G G is connected.
Let K 1 , … , K m K_1,\ldots,K_m K 1 , … , K m be the components of G − { a , b } G-\{a,b\} G − { a , b } . Each of them is adjacent to a a a or to b b b . Since e 0 e_0 e 0 lies on a cycle and has no parallel mate, at least one K j K_j K j is adjacent to both. For each j j j let Y j Y_j Y j be a spanning tree of K j K_j K j . Put P j = Y j P_j=Y_j P j = Y j if K j K_j K j is adjacent to both a a a and b b b ; otherwise put P j = Y j ∪ { f j } P_j=Y_j\cup\{f_j\} P j = Y j ∪ { f j } , where f j f_j f j is an edge from K j K_j K j to the endpoint of e 0 e_0 e 0 to which K j K_j K j is adjacent. Then P = ⋃ j P j P=\bigcup_jP_j P = ⋃ j P j is a forest. In G ′ = G / P G'=G/P G ′ = G / P the vertex set is { a , b , k 1 , … , k r } \{a,b,k_1,\ldots,k_r\} { a , b , k 1 , … , k r } with r ≥ 1 r\ge1 r ≥ 1 , where k i k_i k i is the image of the i i i -th component adjacent to both a a a and b b b . The edges of G ′ G' G ′ are: e 0 e_0 e 0 , which is the only non-loop edge between a a a and b b b , because a component merged into a a a is not adjacent to b b b and vice versa; for each i i i a nonempty class H i \mathcal{H}_i H i of parallel a a a –k i k_i k i edges and a nonempty class G i \mathcal{G}_i G i of parallel k i k_i k i –b b b edges; and possibly loops. By Corollary 3.5 (3), S ( G ′ ) \mathcal{S}(G') S ( G ′ ) is F \mathbb{F} F -representable.
Now orient e 0 e_0 e 0 from a a a to b b b , the edges of H i \mathcal{H}_i H i from a a a to k i k_i k i and those of G i \mathcal{G}_i G i from k i k_i k i to b b b , choose b b b as the root, and apply Theorem 3.8 to G ′ G' G ′ . Every non-loop edge lies on a triangle a k i b ak_ib a k i b , so z e ≠ 0 z_e \ne0 z e = 0 and w e w_e w e is defined for all of them. Write ∂ i a = 1 a − 1 k i \partial_i^a=\mathbf{1}_a-\mathbf{1}_{k_i} ∂ i a = 1 a − 1 k i and ∂ i b = 1 k i \partial_i^b=\mathbf{1}_{k_i} ∂ i b = 1 k i for the common columns of D D D on H i \mathcal{H}_i H i and G i \mathcal{G}_i G i , with the coordinate of b b b deleted. Then ∂ e 0 = 1 a = ∂ i a + ∂ i b \partial_{e_0}=\mathbf{1}_a=\partial_i^a+\partial_i^b ∂ e 0 = 1 a = ∂ i a + ∂ i b for every i i i .
By Lemma 3.9 applied to cycles of length two, w w w is constant on each H i \mathcal{H}_i H i and on each G i \mathcal{G}_i G i ; call the values w i a w_i^a w i a and w i b w_i^b w i b . Apply Lemma 3.9 to the triangle { e 0 , h , g } \{e_0,h,g\} { e 0 , h , g } with h ∈ H i h\in\mathcal{H}_i h ∈ H i and g ∈ G i g\in\mathcal{G}_i g ∈ G i . It gives w e 0 − w i a ∈ span ( ∂ i b ) w_{e_0}-w_i^a\in\operatorname{span}(\partial_i^b) w e 0 − w i a ∈ span ( ∂ i b ) , w i b − w e 0 ∈ span ( ∂ i a ) w_i^b-w_{e_0}\in\operatorname{span}(\partial_i^a) w i b − w e 0 ∈ span ( ∂ i a ) and w i a − w i b ∈ span ( ∂ i a + ∂ i b ) w_i^a-w_i^b\in\operatorname{span}(\partial_i^a+\partial_i^b) w i a − w i b ∈ span ( ∂ i a + ∂ i b ) . Writing w i a = w e 0 − t i ∂ i b w_i^a=w_{e_0}-t_i\partial_i^b w i a = w e 0 − t i ∂ i b and w i b = w e 0 + s i ∂ i a w_i^b=w_{e_0}+s_i\partial_i^a w i b = w e 0 + s i ∂ i a , the third relation forces s i = t i s_i=t_i s i = t i , because ∂ i a \partial_i^a ∂ i a and ∂ i b \partial_i^b ∂ i b are linearly independent. Hence
w i a = w e 0 − t i ∂ i b , w i b = w e 0 + t i ∂ i a ( t i ∈ F ) . (8) w_i^a=w_{e_0}-t_i\partial_i^b,\qquad w_i^b=w_{e_0}+t_i\partial_i^a\qquad(t_i\in\mathbb{F}). \tag*{(8)} w i a = w e 0 − t i ∂ i b , w i b = w e 0 + t i ∂ i a ( t i ∈ F ) . (8)
The columns of D D D corresponding to loops are zero. Put Z i = ∑ h ∈ H i z h Z_i=\sum_{h\in\mathcal{H}_i}z_h Z i = ∑ h ∈ H i z h and Z i ′ = ∑ g ∈ G i z g Z'_i=\sum_{g\in\mathcal{G}_i}z_g Z i ′ = ∑ g ∈ G i z g . Kirchhoff’s law at k i k_i k i and at a a a gives Z i = Z i ′ Z_i=Z'_i Z i = Z i ′ and z e 0 + ∑ i Z i = 0 z_{e_0}+\sum_i Z_i=0 z e 0 + ∑ i Z i = 0 . By (N3), (6) and (8),
0 = ∑ e z e ∂ e ∧ w e = z e 0 ∂ e 0 ∧ w e 0 + ∑ i Z i [ ∂ i a ∧ ( w e 0 − t i ∂ i b ) + ∂ i b ∧ ( w e 0 + t i ∂ i a ) ] = ( z e 0 + ∑ i Z i ) ∂ e 0 ∧ w e 0 − 2 ∑ i Z i t i ∂ i a ∧ ∂ i b = − 2 ∑ i Z i t i 1 a ∧ 1 k i . \begin{aligned}
0&=\sum_e z_e\partial_e\wedge w_e\\
&=z_{e_0}\partial_{e_0}\wedge w_{e_0}+\sum_i Z_i\left[\partial_i^a\wedge(w_{e_0}-t_i\partial_i^b)+\partial_i^b\wedge(w_{e_0}+t_i\partial_i^a)\right]\\
&=\left(z_{e_0}+\sum_i Z_i\right)\partial_{e_0}\wedge w_{e_0}-2\sum_i Z_it_i\partial_i^a\wedge\partial_i^b\\
&=-2\sum_i Z_it_i\mathbf{1}_a\wedge\mathbf{1}_{k_i}.
\end{aligned} 0 = e ∑ z e ∂ e ∧ w e = z e 0 ∂ e 0 ∧ w e 0 + i ∑ Z i [ ∂ i a ∧ ( w e 0 − t i ∂ i b ) + ∂ i b ∧ ( w e 0 + t i ∂ i a ) ] = ( z e 0 + i ∑ Z i ) ∂ e 0 ∧ w e 0 − 2 i ∑ Z i t i ∂ i a ∧ ∂ i b = − 2 i ∑ Z i t i 1 a ∧ 1 k i .
The matrices 1 a ∧ 1 k i \mathbf{1}_a\wedge\mathbf{1}_{k_i} 1 a ∧ 1 k i are linearly independent and 2 ≠ 0 2\ne0 2 = 0 , so Z i t i = 0 Z_it_i=0 Z i t i = 0 for every i i i . Since z e 0 = − ∑ i Z i ≠ 0 z_{e_0}=-\sum_i Z_i\ne0 z e 0 = − ∑ i Z i = 0 , some Z i 0 Z_{i_0} Z i 0 is nonzero, and therefore t i 0 = 0 t_{i_0}=0 t i 0 = 0 .
With t i 0 = 0 t_{i_0}=0 t i 0 = 0 , (8) gives w i 0 a = w i 0 b = w e 0 w_{i_0}^a=w_{i_0}^b=w_{e_0} w i 0 a = w i 0 b = w e 0 . Take h ∈ H i 0 h\in\mathcal{H}_{i_0} h ∈ H i 0 and g ∈ G i 0 g\in\mathcal{G}_{i_0} g ∈ G i 0 . The set { e 0 ∗ , h ∗ , g ∗ } \{e_0^*,h^*,g^*\} { e 0 ∗ , h ∗ , g ∗ } is a triangle with three starred edges, hence independent in S ( G ′ ) \mathcal{S}(G') S ( G ′ ) . But its three columns are multiples of the same vector ( w e 0 ; 1 ) (w_{e_0};1) ( w e 0 ; 1 ) , a contradiction.
Corollary 5.2. If G G G is a simple graph containing a cycle, then S ( G ) \mathcal{S}(G) S ( G ) is not representable over any field of characteristic ≠ 2 \ne2 = 2 . If every edge of G G G that lies
on a cycle and is not a loop has a parallel mate, then S ( G ) \mathcal{S}(G) S ( G ) is representable over every field of characteristic ≠ 2 \ne2 = 2 .
Characteristic two
Throughout this section char F = 2 \operatorname{char}\mathbb{F}=2 char F = 2 , so signs play no role: ∂ e = 1 s + 1 t \partial e=\mathbf{1}_s+\mathbf{1}_t ∂ e = 1 s + 1 t for an edge e e e with ends s , t s,t s , t (in the coordinates of F V \mathbb{F}^{V} F V ), and D D D does not depend on the orientation.
The one-row lift and graphs without two disjoint cycles
Proposition 6.1 (One-row lift). Let char F = 2 \operatorname{char}\mathbb{F}=2 char F = 2 and let G G G be a connected loopless graph with ν ∘ ( G ) ≤ 1 \nu_{\circ}(G)\le1 ν ∘ ( G ) ≤ 1 that contains a cycle. Let λ ∈ F E \lambda\in\mathbb{F}^{E} λ ∈ F E be an F \mathbb{F} F -flow on G G G with λ e ≠ 0 \lambda_e\ne0 λ e = 0 for every edge e e e that is not a bridge, and put d e = λ e d_e=\lambda_e d e = λ e if e e e is not a bridge and d e = 1 d_e=1 d e = 1 if e e e is a bridge. Then
H λ = [ D D diag ( d ) 0 λ ] (9) H_{\lambda}=
\begin{bmatrix}
D & D\operatorname{diag}(d)\\
0 & \lambda
\end{bmatrix} \tag*{(9)} H λ = [ D 0 D diag ( d ) λ ] (9) represents S ( G ) \mathcal{S}(G) S ( G ) over F \mathbb{F} F .
Proof. H λ H_{\lambda} H λ has the matrix form (5) with Z 1 = D diag ( d ) Z_1=D\operatorname{diag}(d) Z 1 = D diag ( d ) and z = λ ≠ 0 z=\lambda\ne0 z = λ = 0 . (N1) holds because λ \lambda λ is a flow, and (N3) holds because D Z 1 T = D diag ( d ) D T DZ_1^{T}=D\operatorname{diag}(d)D^{T} D Z 1 T = D diag ( d ) D T is symmetric. By Theorem 3.8, H λ H_{\lambda} H λ is isotropic of rank ∣ V ∣ = r ( S ( G ) ) |V|=r(\mathcal{S}(G)) ∣ V ∣ = r ( S ( G )) . Let S S S be admissible. The column of e ∗ e^{*} e ∗ is ( d e ∂ e ; λ e ) (d_e\partial e;\lambda_e) ( d e ∂ e ; λ e ) ; dividing it by d e d_e d e turns H λ [ S ] H_{\lambda}[S] H λ [ S ] into ( D [ E [ S ] ] δ S T ) \left(\begin{smallmatrix}D[E[S]]\\ \delta_S^{T}\end{smallmatrix}\right) ( D [ E [ S ]] δ S T ) , where δ S ∈ F E [ S ] \delta_S\in\mathbb{F}^{E[S]} δ S ∈ F E [ S ] is the indicator vector of the edges that are starred in S S S and are not bridges of G G G . Hence the columns of S S S are dependent if and only if some nonzero c ∈ F E [ S ] c\in\mathbb{F}^{E[S]} c ∈ F E [ S ] satisfies D [ E [ S ] ] c = 0 D[E[S]]c=0 D [ E [ S ]] c = 0 and δ S T c = 0 \delta_S^{T}c=0 δ S T c = 0 . The solutions of D [ E [ S ] ] c = 0 D[E[S]]c=0 D [ E [ S ]] c = 0 are the F \mathbb{F} F -flows on G [ S ] G[S] G [ S ] , a space of dimension β = ∣ E [ S ] ∣ − ∣ V ∣ + c ( G [ S ] ) \beta=|E[S]|-|V|+c(G[S]) β = ∣ E [ S ] ∣ − ∣ V ∣ + c ( G [ S ]) . If β = 0 \beta=0 β = 0 , the columns are independent. If β = 1 \beta=1 β = 1 , then G [ S ] G[S] G [ S ] has a single cyclic component, which is unicyclic with cycle C C C , and the flows are the multiples of 1 C \mathbf{1}_C 1 C . The edges of C C C lie on a cycle of G G G and are not bridges, so δ S T 1 C \delta_S^{T}\mathbf{1}_C δ S T 1 C is the number of starred edges of C C C , taken modulo 2 2 2 . Thus the columns are independent if and only if C C C has an odd number of starred edges. If β ≥ 2 \beta\ge2 β ≥ 2 , the columns are dependent. On the other hand, G [ S ] G[S] G [ S ] cannot have two cyclic components, because ν ∘ ( G ) ≤ 1 \nu_{\circ}(G)\le1 ν ∘ ( G ) ≤ 1 . So in each case the columns of S S S are independent exactly when S S S satisfies Chow’s rule. □
Theorem 6.2. Let char F = 2 \operatorname{char}\mathbb{F}=2 char F = 2 and let G G G be a loopless graph with ν ∘ ( G ) ≤ 1 \nu_{\circ}(G)\le1 ν ∘ ( G ) ≤ 1 . Then S ( G ) \mathcal{S}(G) S ( G ) is F \mathbb{F} F -representable if and only if G ∘ G^{\circ} G ∘ has a nowhere-zero ( F , + ) (\mathbb{F},+) ( F , + ) -flow. Consequently:
S ( G ) S(G) S ( G ) is representable over every field of characteristic 2 with at least 8 elements;
S ( G ) S(G) S ( G ) is F 4 \mathbb{F}_4 F 4 -representable if and only if G ∘ G^\circ G ∘ has a nowhere-zero 4-flow;
S ( G ) S(G) S ( G ) is F 2 \mathbb{F}_2 F 2 -representable if and only if every vertex has even degree in G ∘ G^\circ G ∘ .
Proof. Necessity is Theorem 4.1 . For sufficiency, by Lemma 3.6 it suffices to treat each component L L L of G G G ; note that ν ∘ ( L ) ≤ 1 \nu^\circ(L) \le1 ν ∘ ( L ) ≤ 1 and that L ∘ L^\circ L ∘ is a union of components of G ∘ G^\circ G ∘ . If L L L is a tree, S ( L ) S(L) S ( L ) is represented by [ I ∣ I ] [I \mid I] [ I ∣ I ] . Otherwise a nowhere-zero F \mathbb{F} F -flow on L ∘ L^\circ L ∘ , extended by 0 to the bridges of L L L , is a flow λ \lambda λ on L L L as in Proposition 6.1 , which gives a representation. For (1), L ∘ L^\circ L ∘ is bridgeless, so it has a nowhere-zero Z 2 3 \mathbb{Z}_2^3 Z 2 3 -flow by (F3); if ∣ F ∣ ≥ 8 \lvert\mathbb{F}\rvert\ge8 ∣ F ∣ ≥ 8 , then ( F , + ) (\mathbb{F},+) ( F , + ) is an F 2 \mathbb{F}_2 F 2 -vector space of dimension at least 3 and contains a copy of Z 2 3 \mathbb{Z}_2^3 Z 2 3 . Items (2) and (3) follow from (F2) and (F4).
Remark 6.3. Graphs without two vertex-disjoint cycles were characterized by Lovász [15 ] . In the 3-connected case, Dirac [16] and Lovász showed that they are K 5 K_5 K 5 , K 5 K_5 K 5 minus an edge, the wheels, and the graphs obtained from K 3 , p K_{3,p} K 3 , p , p ≥ 3 p \ge3 p ≥ 3 , by adding any set of edges inside the part of size three. Theorem 6.2 therefore applies to cycles, theta graphs, flowers of cycles sharing one vertex, wheels, K 4 K_4 K 4 , K 3 , 3 K_{3,3} K 3 , 3 and K 5 K_5 K 5 . For example, K 5 K_5 K 5 is Eulerian, so S ( K 5 ) S(K_5) S ( K 5 ) is representable over every field of characteristic 2; K 4 K_4 K 4 and K 3 , 3 K_{3,3} K 3 , 3 are cubic and 3-edge-colourable, so combining Theorem 5.1 and Corollary 4.2 S ( K 4 ) S(K_4) S ( K 4 ) and S ( K 3 , 3 ) S(K_{3,3}) S ( K 3 , 3 ) are representable exactly over the fields of characteristic 2 with more than two elements.
An obstruction: rigidly linked short cycles
Lemma 6.4. Let char F = 2 \operatorname{char}\mathbb{F} = 2 char F = 2 , let G G G be connected, and let H H H be a representation of S ( G ) S(G) S ( G ) in normal form. For every cycle C C C of length 2 or 3 there are y C ∈ F ∣ V ∣ − 1 y_C \in\mathbb{F}^{\lvert V\rvert-1} y C ∈ F ∣ V ∣ − 1 and t C ∈ F t_C \in\mathbb{F} t C ∈ F such that
w e = y C + t C ∂ e for all e ∈ C , (10) w_e = y_C + t_C\,\partial_e \qquad\text{for all } e \in C, \tag*{(10)} w e = y C + t C ∂ e for all e ∈ C , (10) and t C = 0 t_C = 0 t C = 0 if ∣ C ∣ = 2 \lvert C\rvert= 2 ∣ C ∣ = 2 .
Proof. If C = { e , f } C = \{e,f\} C = { e , f } , then w e = w f w_e = w_f w e = w f by Lemma 3.9 ; take y C = w e y_C = w_e y C = w e and t C = 0 t_C = 0 t C = 0 . If C = { e , f , g } C = \{e,f,g\} C = { e , f , g } , then (7) reads w e + w f = t ∂ g w_e + w_f = t\partial_g w e + w f = t ∂ g , w f + w g = t ∂ e w_f + w_g = t\partial_e w f + w g = t ∂ e , w g + w e = t ∂ f w_g + w_e = t\partial_f w g + w e = t ∂ f , and ∂ e + ∂ f + ∂ g = 0 \partial_e + \partial_f + \partial_g = 0 ∂ e + ∂ f + ∂ g = 0 . Put y C = w e + t ∂ e y_C = w_e + t\partial_e y C = w e + t ∂ e and t C = t t_C = t t C = t . Then w f + t ∂ f = w e + t ( ∂ g + ∂ f ) = w e + t ∂ e = y C w_f + t\partial_f = w_e + t(\partial_g + \partial_f) = w_e + t\partial_e = y_C w f + t ∂ f = w e + t ( ∂ g + ∂ f ) = w e + t ∂ e = y C , and similarly for g g g . For cycles of length at least 4, Lemma 3.9 gives only w e − w f ∈ span { ∂ g : g ∈ C ∖ { e , f } } w_e-w_f\in\operatorname{span}\{\partial_g:g\in C\setminus\{e,f\}\} w e − w f ∈ span { ∂ g : g ∈ C ∖ { e , f }} , a space of dimension ∣ C ∣ − 2 ≥ 2 |C|-2\ge2 ∣ C ∣ − 2 ≥ 2 , and no relation of the form (10) follows.
Definition 6.5 (Rigidly linked cycles). Let C 1 , C 2 C_1,C_2 C 1 , C 2 be vertex-disjoint cycles of G G G . The linking family Q ( C 1 , C 2 ) \mathcal{Q}(C_1,C_2) Q ( C 1 , C 2 ) is the set of cycles Q Q Q of G G G with E ( Q ) ∩ E ( C 1 ) ≠ ∅ E(Q)\cap E(C_1)\ne\varnothing E ( Q ) ∩ E ( C 1 ) = ∅ and E ( Q ) ∩ E ( C 2 ) ≠ ∅ E(Q)\cap E(C_2)\ne\varnothing E ( Q ) ∩ E ( C 2 ) = ∅ . If Q ( C 1 , C 2 ) ≠ ∅ \mathcal{Q}(C_1,C_2)\ne\varnothing Q ( C 1 , C 2 ) = ∅ , the core is
core ( C 1 , C 2 ) = ⋂ Q ∈ Q ( C 1 , C 2 ) V ( Q ) . \operatorname{core}(C_1,C_2)=\bigcap_{Q\in\mathcal{Q}(C_1,C_2)}V(Q). core ( C 1 , C 2 ) = Q ∈ Q ( C 1 , C 2 ) ⋂ V ( Q ) . The pair C 1 , C 2 C_1,C_2 C 1 , C 2 is rigidly linked if both cycles have length 2 or 3, Q ( C 1 , C 2 ) ≠ ∅ \mathcal{Q}(C_1,C_2)\ne\varnothing Q ( C 1 , C 2 ) = ∅ , and core ( C 1 , C 2 ) ⊆ V ( C 1 ) \operatorname{core}(C_1,C_2)\subseteq V(C_1) core ( C 1 , C 2 ) ⊆ V ( C 1 ) or core ( C 1 , C 2 ) ⊆ V ( C 2 ) \operatorname{core}(C_1,C_2)\subseteq V(C_2) core ( C 1 , C 2 ) ⊆ V ( C 2 ) ; for instance, if core ( C 1 , C 2 ) = ∅ \operatorname{core}(C_1,C_2)=\varnothing core ( C 1 , C 2 ) = ∅ .
Theorem 6.6. If G G G contains a rigidly linked pair of cycles, then S ( G ) \mathcal{S}(G) S ( G ) is not representable over any field of characteristic 2.
Proof. Let C 1 , C 2 C_1,C_2 C 1 , C 2 be rigidly linked, say core ( C 1 , C 2 ) ⊆ V ( C 1 ) \operatorname{core}(C_1,C_2)\subseteq V(C_1) core ( C 1 , C 2 ) ⊆ V ( C 1 ) . They lie in one component of G G G , so by Lemma 3.6 we may assume G G G connected. Suppose that S ( G ) \mathcal{S}(G) S ( G ) is F \mathbb{F} F -representable with char F = 2 \operatorname{char}\mathbb{F}=2 char F = 2 , and take a representation in normal form. Every edge used below lies on a cycle, so z e ≠ 0 z_e\ne0 z e = 0 and w e w_e w e is defined. We use the coordinates of F 0 V \mathbb{F}_0^V F 0 V , so that (3) holds. Write y j = y C j y_j=y_{C_j} y j = y C j and t j = t C j t_j=t_{C_j} t j = t C j as in Lemma 6.4, and put y = y 1 + y 2 y=y_1+y_2 y = y 1 + y 2 .
Let Q ∈ Q ( C 1 , C 2 ) Q\in\mathcal{Q}(C_1,C_2) Q ∈ Q ( C 1 , C 2 ) , and pick h 1 ∈ E ( Q ) ∩ E ( C 1 ) h_1\in E(Q)\cap E(C_1) h 1 ∈ E ( Q ) ∩ E ( C 1 ) and h 2 ∈ E ( Q ) ∩ E ( C 2 ) h_2\in E(Q)\cap E(C_2) h 2 ∈ E ( Q ) ∩ E ( C 2 ) . The cycle Q Q Q has length at least 2, so it consists of non-loop edges, and Lemma 3.9 gives w h 1 + w h 2 ∈ F 0 V ( Q ) w_{h_1}+w_{h_2}\in\mathbb{F}_0^{V(Q)} w h 1 + w h 2 ∈ F 0 V ( Q ) . Since ∂ h 1 , ∂ h 2 ∈ F 0 V ( Q ) \partial_{h_1},\partial_{h_2}\in\mathbb{F}_0^{V(Q)} ∂ h 1 , ∂ h 2 ∈ F 0 V ( Q ) , (10) gives y = w h 1 + w h 2 + t 1 ∂ h 1 + t 2 ∂ h 2 ∈ F 0 V ( Q ) y=w_{h_1}+w_{h_2}+t_1\partial_{h_1}+t_2\partial_{h_2}\in\mathbb{F}_0^{V(Q)} y = w h 1 + w h 2 + t 1 ∂ h 1 + t 2 ∂ h 2 ∈ F 0 V ( Q ) . Hence
y ∈ ⋂ Q ∈ Q ( C 1 , C 2 ) F 0 V ( Q ) = F 0 core ( C 1 , C 2 ) ⊆ F 0 V ( C 1 ) . y\in\bigcap_{Q\in\mathcal{Q}(C_1,C_2)}\mathbb{F}_0^{V(Q)}
=\mathbb{F}_0^{\operatorname{core}(C_1,C_2)}
\subseteq\mathbb{F}_0^{V(C_1)}. y ∈ Q ∈ Q ( C 1 , C 2 ) ⋂ F 0 V ( Q ) = F 0 core ( C 1 , C 2 ) ⊆ F 0 V ( C 1 ) .
Fix h j ∈ E ( C j ) h_j\in E(C_j) h j ∈ E ( C j ) and consider
S = { h 1 ∗ , h 2 ∗ } ∪ ( C 1 ∖ { h 1 } ) ∪ ( C 2 ∖ { h 2 } ) . S=\{h_1^*,h_2^*\}\cup(C_1\setminus\{h_1\})\cup(C_2\setminus\{h_2\}). S = { h 1 ∗ , h 2 ∗ } ∪ ( C 1 ∖ { h 1 }) ∪ ( C 2 ∖ { h 2 }) .
The nontrivial components of G [ S ] G[S] G [ S ] are C 1 C_1 C 1 and C 2 C_2 C 2 , each a cycle with exactly one starred edge, so S S S is independent. On the other hand,
z h 1 − 1 col ( h 1 ∗ ) + z h 2 − 1 col ( h 2 ∗ ) = ( w h 1 + w h 2 ; 0 ) = ( y + t 1 ∂ h 1 + t 2 ∂ h 2 ; 0 ) . z_{h_1}^{-1}\operatorname{col}(h_1^*)+z_{h_2}^{-1}\operatorname{col}(h_2^*)
=(w_{h_1}+w_{h_2};0)=(y+t_1\partial_{h_1}+t_2\partial_{h_2};0). z h 1 − 1 col ( h 1 ∗ ) + z h 2 − 1 col ( h 2 ∗ ) = ( w h 1 + w h 2 ; 0 ) = ( y + t 1 ∂ h 1 + t 2 ∂ h 2 ; 0 ) .
By (3) , y y y and ∂ h 1 \partial_{h_1} ∂ h 1 lie in F 0 V ( C 1 ) = span { ∂ g : g ∈ C 1 ∖ { h 1 } } \mathbb{F}_0^{V(C_1)}=\operatorname{span}\{\partial_g:g\in C_1\setminus\{h_1\}\} F 0 V ( C 1 ) = span { ∂ g : g ∈ C 1 ∖ { h 1 }} , and ∂ h 2 ∈ span { ∂ g : g ∈ C 2 ∖ { h 2 } } \partial_{h_2}\in\operatorname{span}\{\partial_g:g\in C_2\setminus\{h_2\}\} ∂ h 2 ∈ span { ∂ g : g ∈ C 2 ∖ { h 2 }} . This is a nontrivial linear relation among the columns of S S S , a contradiction. □
Corollary 6.7. Suppose that G G G contains vertex-disjoint triangles x 0 x 1 x 2 x_0x_1x_2 x 0 x 1 x 2 and y 0 y 1 y 2 y_0y_1y_2 y 0 y 1 y 2 and pairwise vertex-disjoint paths P 0 , P 1 , P 2 P_0,P_1,P_2 P 0 , P 1 , P 2 , where P i P_i P i joins x i x_i x i to y i y_i y i and has no inner vertex on the triangles. Then S ( G ) \mathcal{S}(G) S ( G ) is not representable
over any field of characteristic 2. If, in addition, some edge of G G G that lies on a cycle and is not a loop has no parallel mate (for instance, if G G G is simple), then S ( G ) S(G) S ( G ) is representable over no field. This applies to the triangular prism K 3 □ K 2 K_{3}\square K_{2} K 3 □ K 2 , the octahedron K 2 , 2 , 2 K_{2,2,2} K 2 , 2 , 2 and K n K_{n} K n for n ≥ 6 n \ge6 n ≥ 6 .
Proof. For { i , j , l } = { 0 , 1 , 2 } \{i,j,l\}=\{0,1,2\} { i , j , l } = { 0 , 1 , 2 } let Q i j Q_{ij} Q ij be the cycle formed by the edge x i x j x_{i}x_{j} x i x j , the path P j P_{j} P j , the edge y j y i y_{j}y_{i} y j y i and the path P i P_{i} P i . Then Q 01 , Q 12 , Q 20 ∈ Q Q_{01}, Q_{12}, Q_{20} \in\mathcal{Q} Q 01 , Q 12 , Q 20 ∈ Q . The vertices x i , y i x_{i}, y_{i} x i , y i and the inner vertices of P i P_{i} P i lie only on the two cycles Q i j Q_{ij} Q ij and Q l i Q_{li} Q l i among these three, so no vertex lies on all of them. Hence the core is empty, the triangles are rigidly linked, and Theorem 6.6 applies. The second statement follows from Theorem 5.1 . The octahedron contains two disjoint triangles joined by a perfect matching, and K n K_{n} K n contains the octahedron for n ≥ 6 n \ge6 n ≥ 6 . □
Example 6.8. The following examples show that neither Theorem 6.2 nor Theorem 6.6 characterizes representability in characteristic 2 when ν ∘ ( G ) ≥ 2 \nu_{\circ}(G) \ge2 ν ∘ ( G ) ≥ 2 . Vertices are 0 , 1 , 2 , … 0,1,2,\ldots 0 , 1 , 2 , … , and s t st s t denotes an edge with ends s , t s,t s , t . Items (2), (3) and (5) rely on computer searches, described in Appendix A, where the matrices found are listed.
The dumbbell X 1 X_{1} X 1 consists of the triangles T 1 = { 01 , 12 , 20 } T_{1}=\{01,12,20\} T 1 = { 01 , 12 , 20 } and T 2 = { 34 , 45 , 53 } T_{2}=\{34,45,53\} T 2 = { 34 , 45 , 53 } joined by the bridge g = 03 g=03 g = 03 . Here ν ∘ ( X 1 ) = 2 \nu_{\circ}(X_{1})=2 ν ∘ ( X 1 ) = 2 , and X 1 ∘ X_{1}^{\circ} X 1 ∘ is Eulerian. S ( X 1 ) S(X_{1}) S ( X 1 ) is F 2 \mathbb{F}_{2} F 2 -representable: take the root 0 0 0 , z = 1 T 1 ∪ T 2 z=1_{T_{1}\cup T_{2}} z = 1 T 1 ∪ T 2 , Z 1 , e = ∂ e Z_{1,e}=\partial_{e} Z 1 , e = ∂ e for e ∈ T 1 ∪ { g } e\in T_{1}\cup\{g\} e ∈ T 1 ∪ { g } and Z 1 , e = ∂ e + ∂ g Z_{1,e}=\partial_{e}+\partial_{g} Z 1 , e = ∂ e + ∂ g for e ∈ T 2 e\in T_{2} e ∈ T 2 . With the columns ordered 01 , 12 , 20 , 34 , 45 , 53 , 03 01,12,20,34,45,53,03 01 , 12 , 20 , 34 , 45 , 53 , 03 and the rows indexed by 1 , … , 5 1,\ldots,5 1 , … , 5 and the extra row,
H = [ 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 ] . H=\begin{bmatrix}
1&1&0&0&0&0&0&1&1&0&0&0&0&0\\
0&1&1&0&0&0&0&0&1&1&0&0&0&0\\
0&0&0&1&0&1&1&0&0&0&0&1&0&1\\
0&0&0&1&1&0&0&0&0&0&1&1&0&0\\
0&0&0&0&1&1&0&0&0&0&0&1&1&0\\
0&0&0&0&0&0&0&1&1&1&1&1&1&0
\end{bmatrix}. H = 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 0 0 0 .
(N1) holds because every vertex meets 0 or 2 edges of T 1 ∪ T 2 T_{1}\cup T_{2} T 1 ∪ T 2 , and (N3) holds because ∑ e ∈ T 2 ∂ e ∧ ( ∂ e + ∂ g ) = ( ∑ e ∈ T 2 ∂ e ) ∧ ∂ g = 0 \sum_{e\in T_{2}}\partial_{e}\wedge(\partial_{e}+\partial_{g})=(\sum_{e\in T_{2}}\partial_{e})\wedge\partial_{g}=0 ∑ e ∈ T 2 ∂ e ∧ ( ∂ e + ∂ g ) = ( ∑ e ∈ T 2 ∂ e ) ∧ ∂ g = 0 . To see that H H H represents S ( X 1 ) S(X_{1}) S ( X 1 ) , let S S S be admissible and let c ∈ F 2 E [ S ] c\in\mathbb{F}_{2}^{E[S]} c ∈ F 2 E [ S ] be the coefficient vector of a linear relation among the columns of S S S ; put c g = 0 c_{g}=0 c g = 0 if g ∉ E [ S ] g\notin E[S] g ∈ / E [ S ] . The columns of g g g and g ∗ g^{*} g ∗ both equal ( ∂ g ; 0 ) (\partial_{g};0) ( ∂ g ; 0 ) , and the column of e ∗ e^{*} e ∗ is ( ∂ e ; 1 ) (\partial_e;1) ( ∂ e ; 1 ) for e ∈ T 1 e \in T_1 e ∈ T 1 and ( ∂ e + ∂ g ; 1 ) (\partial_e+\partial_g;1) ( ∂ e + ∂ g ; 1 ) for e ∈ T 2 e \in T_2 e ∈ T 2 . Let γ \gamma γ be the sum of the c e c_e c e over the edges e ∈ T 2 e \in T_2 e ∈ T 2 that are starred in S S S , and let k j k_j k j be the number of edges of T j T_j T j starred in S S S . The first five rows say that c + γ 1 g c+\gamma1_g c + γ 1 g is a flow on X 1 [ S ] ∪ { g } X_1[S]\cup\{g\} X 1 [ S ] ∪ { g } . As g g g is a bridge, this flow vanishes at g g g , so c g = γ c_g=\gamma c g = γ , and on T 1 ∪ T 2 T_1\cup T_2 T 1 ∪ T 2 it equals μ 1 1 T 1 + μ 2 1 T 2 \mu_1 1_{T_1}+\mu_2 1_{T_2} μ 1 1 T 1 + μ 2 1 T 2 , where μ j = 0 \mu_j=0 μ j = 0 unless T j ⊆ E [ S ] T_j\subseteq E[S] T j ⊆ E [ S ] . Hence γ = μ 2 k 2 \gamma=\mu_2 k_2 γ = μ 2 k 2 , which must vanish if g ∉ E [ S ] g\notin E[S] g ∈ / E [ S ] , and the last row reads μ 1 k 1 + μ 2 k 2 = 0 \mu_1 k_1+\mu_2 k_2=0 μ 1 k 1 + μ 2 k 2 = 0 . Since c c c is determined by ( μ 1 , μ 2 ) (\mu_1,\mu_2) ( μ 1 , μ 2 ) , a nontrivial relation exists if and only if some T j ⊆ E [ S ] T_j\subseteq E[S] T j ⊆ E [ S ] has an even number of starred edges, or g ∈ E [ S ] g\in E[S] g ∈ E [ S ] and T 1 ∪ T 2 ⊆ E [ S ] T_1\cup T_2\subseteq E[S] T 1 ∪ T 2 ⊆ E [ S ] . These are exactly the admissible sets that violate Chow’s rule. By contrast, for every one-row lift (9), two vertex-disjoint triangles, each with one starred edge, form a dependent set (the case β = 2 \beta=2 β = 2 in the proof of Proposition 6.1 ); shifting Z 1 Z_1 Z 1 by ∂ g \partial_g ∂ g on one side of the bridge removes this dependence.
Two triangles joined by two disjoint paths: X 2 X_2 X 2 has edges 01, 12, 20, 34, 45, 53, 03, 25. Here core ( T 1 , T 2 ) = { 0 , 2 , 3 , 5 } \operatorname{core}(T_1,T_2)=\{0,2,3,5\} core ( T 1 , T 2 ) = { 0 , 2 , 3 , 5 } meets both triangles, so Theorem 6.6 does not apply, and S ( X 2 ) \mathcal{S}(X_2) S ( X 2 ) is representable over F 4 \mathbb{F}_4 F 4 and over F 8 \mathbb{F}_8 F 8 . It is not F 2 \mathbb{F}_2 F 2 -representable, since vertex 0 has degree 3 in X 2 = X 3 ∘ X_2=X_3^{\circ} X 2 = X 3 ∘ .
A 4-cycle with two opposite edges doubled: X 3 X_3 X 3 has edges 01, 01, 23, 23, 02, 13. The two cycles of length two are vertex-disjoint and their core is { 0 , 1 , 2 , 3 } \{0,1,2,3\} { 0 , 1 , 2 , 3 } . S ( X 3 ) \mathcal{S}(X_3) S ( X 3 ) is F 4 \mathbb{F}_4 F 4 -representable.
A triangle and a cycle of length two, rigidly linked: X 4 X_4 X 4 has edges 01, 12, 20, two parallel edges 34, and 03, 14, 23, 04. The core of the triangle and the 2-cycle is { 3 , 4 } \{3,4\} { 3 , 4 } , so they are rigidly linked, and S ( X 4 ) \mathcal{S}(X_4) S ( X 4 ) is not representable over any field of characteristic 2; since the triangle edges have no parallel mates, it is representable over no field. Nevertheless X 4 X_4 X 4 is bridgeless and has a nowhere-zero 4-flow, so Theorem 4.1 does not exclude F 4 \mathbb{F}_4 F 4 .
A chain of three triangles: X 5 X_5 X 5 has edges 01, 12, 20, 23, 34, 42, 45, 56, 64. It is bridgeless and Eulerian, every block has ν ∘ ≤ 1 \nu_{\circ}\leq1 ν ∘ ≤ 1 , and no cycle meets both T 1 = { 01 , 12 , 20 } T_1=\{01,12,20\} T 1 = { 01 , 12 , 20 } and T 3 = { 45 , 56 , 64 } T_3=\{45,56,64\} T 3 = { 45 , 56 , 64 } . S ( X 5 ) \mathcal{S}(X_5) S ( X 5 ) is F 4 \mathbb{F}_4 F 4 -representable but not F 2 \mathbb{F}_2 F 2 -representable. Thus over F 2 \mathbb{F}_2 F 2 the flow condition is not sufficient even when every block has ν ∘ ≤ 1 \nu_{\circ}\leq1 ν ∘ ≤ 1 . Since the subgraph formed by the first two triangles has ν ∘ = 1 \nu_{\circ}=1 ν ∘ = 1 and is Eulerian,
its matroid is F 2 \mathbb{F}_2 F 2 -representable by Theorem 6.2 , as is that of a triangle; so F 2 \mathbb{F}_2 F 2 -representability is not preserved under 1-sums.
Prism subdivisions and 3-connected graphs
Contracting a forest shortens cycles, and Corollary 3.5 (3) carries representations of S ( G ) S(G) S ( G ) over to S ( G / F ) S(G/F) S ( G / F ) . This turns Corollary 6.7 into an obstruction involving long cycles.
Proposition 6.9. Let C 1 C_1 C 1 and C 2 C_2 C 2 be vertex-disjoint cycles of G G G of length at least 3, and let P 0 P_0 P 0 , P 1 P_1 P 1 , P 2 P_2 P 2 be pairwise vertex-disjoint paths such that P i P_i P i joins a vertex x i x_i x i of C 1 C_1 C 1 to a vertex y i y_i y i of C 2 C_2 C 2 and has no inner vertex on C 1 ∪ C 2 C_1\cup C_2 C 1 ∪ C 2 . Then S ( G ) S(G) S ( G ) is not representable over any field of characteristic 2. In particular, this holds whenever G G G contains a subdivision of the prism K 3 □ K 2 K_3\square K_2 K 3 □ K 2 .
Proof. The vertices x 0 , x 1 , x 2 x_0,x_1,x_2 x 0 , x 1 , x 2 divide C 1 C_1 C 1 into three paths. Keep one edge on each of them, and let F 1 F_1 F 1 be the set of the other edges of C 1 C_1 C 1 . Define F 2 ⊆ E ( C 2 ) F_2\subseteq E(C_2) F 2 ⊆ E ( C 2 ) in the same way with respect to y 0 , y 1 , y 2 y_0,y_1,y_2 y 0 , y 1 , y 2 , and let F 3 F_3 F 3 consist of the edges of P 0 ∪ P 1 ∪ P 2 P_0\cup P_1\cup P_2 P 0 ∪ P 1 ∪ P 2 other than the edge of P i P_i P i at y i y_i y i , for i = 0 , 1 , 2 i=0,1,2 i = 0 , 1 , 2 . Since the paths are disjoint and their inner vertices avoid C 1 ∪ C 2 C_1\cup C_2 C 1 ∪ C 2 , the set F = F 1 ∪ F 2 ∪ F 3 F=F_1\cup F_2\cup F_3 F = F 1 ∪ F 2 ∪ F 3 is the edge set of a forest, and F F F joins every vertex of C 1 ∪ C 2 ∪ P 0 ∪ P 1 ∪ P 2 C_1\cup C_2\cup P_0\cup P_1\cup P_2 C 1 ∪ C 2 ∪ P 0 ∪ P 1 ∪ P 2 to exactly one of the six vertices x i , y i x_i,y_i x i , y i . In G / F G/F G / F the images of C 1 C_1 C 1 and C 2 C_2 C 2 are therefore vertex-disjoint triangles, and the edges of the paths P i P_i P i at y i y_i y i form a perfect matching between them; the other edges of G G G remain, possibly as loops or parallel edges. By Corollary 6.7 , S ( G / F ) S(G/F) S ( G / F ) is not representable over a field of characteristic 2, and by Corollary 3.5 (3) neither is S ( G ) S(G) S ( G ) . A subdivision of the prism consists of two cycles and three paths of this kind. □ \square □
For 3-connected graphs, Proposition 6.9 and Theorem 6.2 together settle the question. The flows needed in Theorem 6.2 can be written down explicitly.
Lemma 6.10. Let char F = 2 \operatorname{char}\mathbb{F}=2 char F = 2 and ∣ F ∣ > 2 |\mathbb{F}|>2 ∣ F ∣ > 2 . Every 3-connected simple graph without two vertex-disjoint cycles has a nowhere-zero ( F , + ) (\mathbb{F},+) ( F , + ) -flow.
Proof. Choose distinct a , b ∈ F × a,b\in\mathbb{F}^{\times} a , b ∈ F × and put c = a + b c=a+b c = a + b . Then a , b , c a,b,c a , b , c are nonzero and pairwise distinct, and a + b + c = 0 a+b+c=0 a + b + c = 0 . In characteristic 2 an ( F , + ) (\mathbb{F},+) ( F , + ) -flow is an assignment of values to the edges whose sum at every vertex is 0. By Remark 6.3, the graph is K 5 K_5 K 5 , a wheel, or a graph K 3 , p + L K_{3,p}+L K 3 , p + L obtained from K 3 , p K_{3,p} K 3 , p , p ≥ 2 p\geq2 p ≥ 2 , by adding a set L L L of edges inside the part { s 1 , s 2 , s 3 } \{s_1,s_2,s_3\} { s 1 , s 2 , s 3 } ; the case p = 2 p = 2 p = 2 , ∣ L ∣ = 3 |L| = 3 ∣ L ∣ = 3 is K 5 K_5 K 5 minus an edge. On K 5 K_5 K 5 the constant value a a a is a flow, because all degrees are 4.
Let the wheel have hub h h h and rim v 1 v 2 ⋯ v m v 1 v_1v_2\cdots v_mv_1 v 1 v 2 ⋯ v m v 1 , m ≥ 3 m \ge3 m ≥ 3 . Let x 1 , … , x m x_1,\ldots,x_m x 1 , … , x m alternate between a a a and b b b , and replace x m x_m x m by c c c if m m m is odd; then x i ≠ x i + 1 x_i \ne x_{i+1} x i = x i + 1 for all i i i , with indices modulo m m m . Give the rim edge v i v i + 1 v_iv_{i+1} v i v i + 1 the value x i x_i x i and the spoke h v i hv_i h v i the value x i − 1 + x i ≠ 0 x_{i-1}+x_i \ne0 x i − 1 + x i = 0 . The sum at v i v_i v i is x i − 1 + x i + ( x i − 1 + x i ) = 0 x_{i-1}+x_i+(x_{i-1}+x_i)=0 x i − 1 + x i + ( x i − 1 + x i ) = 0 , and the sum at h h h is ∑ i ( x i − 1 + x i ) = 0 \sum_i(x_{i-1}+x_i)=0 ∑ i ( x i − 1 + x i ) = 0 .
On K 3 , p + L K_{3,p}+L K 3 , p + L , with second part { t 1 , … , t p } \{t_1,\ldots,t_p\} { t 1 , … , t p } , give every edge of L L L the value a a a , and put γ i = a \gamma_i=a γ i = a if s i s_i s i has odd degree in L L L and γ i = 0 \gamma_i=0 γ i = 0 otherwise. It remains to find a 3 × p 3 \times p 3 × p matrix with entries in { a , b , c } \{a,b,c\} { a , b , c } , whose ( i , j ) (i,j) ( i , j ) entry is the value of s i t j s_it_j s i t j , such that every column sums to 0 and the i i i th row sums to γ i \gamma_i γ i . Since L L L has an even number of vertices of odd degree, we may renumber so that ( γ 1 , γ 2 , γ 3 ) (\gamma_1,\gamma_2,\gamma_3) ( γ 1 , γ 2 , γ 3 ) is ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) or ( a , a , 0 ) (a,a,0) ( a , a , 0 ) . Start with
( a a b b c c ) , ( a b c b c a c a b ) , ( b c c b a a ) , ( b a b c c a a b c ) \begin{pmatrix}a&a\\b&b\\c&c\end{pmatrix},
\quad
\begin{pmatrix}a&b&c\\b&c&a\\c&a&b\end{pmatrix},
\quad
\begin{pmatrix}b&c\\c&b\\a&a\end{pmatrix},
\quad
\begin{pmatrix}b&a&b\\c&c&a\\a&b&c\end{pmatrix} a b c a b c , a b c b c a c a b , b c a c b a , b c a a c b b a c
if the target is ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) and p p p is even or odd, or ( a , a , 0 ) (a,a,0) ( a , a , 0 ) and p p p is even or odd, respectively, and append pairs of equal columns ( a , b , c ) T (a,b,c)^T ( a , b , c ) T until there are p p p columns. Every column sums to 0, and the row sums are γ 1 , γ 2 , γ 3 \gamma_1,\gamma_2,\gamma_3 γ 1 , γ 2 , γ 3 .
Theorem 6.11. Let G G G be a 3-connected simple graph and F F F a field. Then S ( G ) S(G) S ( G ) is F F F -representable if and only if char F = 2 \operatorname{char} F=2 char F = 2 , G G G has no two vertex-disjoint cycles, and either ∣ F ∣ > 2 |F|>2 ∣ F ∣ > 2 or G ≅ K 5 G\cong K_5 G ≅ K 5 .
Proof. A 3-connected simple graph contains a cycle, and none of its edges has a parallel mate, so Theorem 5.1 excludes every characteristic ≠ 2 \ne2 = 2 . Let char F = 2 \operatorname{char} F=2 char F = 2 , and suppose first that G G G has vertex-disjoint cycles C 1 C_1 C 1 and C 2 C_2 C 2 ; both have length at least 3. If a set Z Z Z of at most two vertices met every path from V ( C 1 ) V(C_1) V ( C 1 ) to V ( C 2 ) V(C_2) V ( C 2 ) , then G − Z G-Z G − Z would contain a vertex of each cycle, because ∣ V ( C j ) ∣ ≥ 3 |V(C_j)| \ge3 ∣ V ( C j ) ∣ ≥ 3 , but no path between them, contradicting 3-connectivity. By Menger’s theorem [17 Thm. 3.3.1] there are three disjoint V ( C 1 ) V(C_1) V ( C 1 ) –V ( C 2 ) V(C_2) V ( C 2 ) paths, that is, paths meeting C 1 C_1 C 1 only in their first and C 2 C_2 C 2 only in their last vertex, and Proposition 6.9 shows that S ( G ) S(G) S ( G ) is not F F F -representable.
Suppose now that G G G has no two vertex-disjoint cycles. Since G G G has no loops and no bridges, G ∘ = G G^\circ=G G ∘ = G , and by Theorem 6.2 , S ( G ) S(G) S ( G ) is F F F -representable if and only if G G G has a nowhere-zero ( F , + ) (F,+) ( F , + ) -flow. If ∣ F ∣ > 2 |F|>2 ∣ F ∣ > 2 , such a flow exists by Lemma 6.10. Over F 2 \mathbb{F}_2 F 2 it exists if and only if all degrees are even, by (F4). By Remark 6.3, G G G is either K 5 K_5 K 5 , which is 4-regular, or K 5 K_5 K 5 minus an edge, a wheel, or a graph obtained from K 3 , p K_{3,p} K 3 , p , and each of the latter has a vertex of degree 3.
Corollary 6.12. The matroid S ( P 10 ) S(P_{10}) S ( P 10 ) of the Petersen graph is representable over no field.
Proof. The Petersen graph is simple and 3-connected, and it has two disjoint 5-cycles, so Theorem 6.11 applies. Explicitly, write its vertices as u i u_i u i , v i v_i v i , i ∈ Z 5 i \in\mathbb{Z}_5 i ∈ Z 5 , with edges u i u i + 1 u_i u_{i+1} u i u i + 1 , v i v i + 2 v_i v_{i+2} v i v i + 2 and u i v i u_i v_i u i v i . Contracting the matching { u 0 u 1 , u 2 u 3 , v 0 v 2 , v 1 v 4 } \{u_0u_1, u_2u_3, v_0v_2, v_1v_4\} { u 0 u 1 , u 2 u 3 , v 0 v 2 , v 1 v 4 } turns the two 5-cycles into triangles, and the edges u 0 v 0 u_0v_0 u 0 v 0 , u 3 v 3 u_3v_3 u 3 v 3 , u 4 v 4 u_4v_4 u 4 v 4 become a perfect matching between them; so Corollaries 6.7 and 3.5(3) exclude characteristic 2.
Unicyclic graphs, the doubled triangle and Chow’s remark
Corollary 7.1 (Unicyclic graphs). Let G G G be a connected loopless graph with exactly one cycle C C C , of length m ≥ 2 m \ge2 m ≥ 2 , let D D D be its reduced incidence matrix, and put
H G = [ D D 0 1 C ] ∈ F ∣ V ∣ × 2 ∣ E ∣ . H_G =
\begin{bmatrix}
D & D \\
0 & 1_C
\end{bmatrix}
\in\mathbb{F}^{|V|\times2|E|}. H G = [ D 0 D 1 C ] ∈ F ∣ V ∣ × 2∣ E ∣ . If char F = 2 \operatorname{char}\mathbb{F}=2 char F = 2 , then H G H_G H G represents S ( G ) S(G) S ( G ) .
If m ≥ 3 m \ge3 m ≥ 3 , equivalently if G G G is simple, then S ( G ) S(G) S ( G ) is F \mathbb{F} F -representable if and only if char F = 2 \operatorname{char}\mathbb{F}=2 char F = 2 .
If m = 2 m=2 m = 2 , then S ( G ) S(G) S ( G ) is representable over every field.
Proof. (1) Here ν ∘ ( G ) = 1 \nu_{\circ}(G)=1 ν ∘ ( G ) = 1 , and the edges of C C C are exactly the edges of G G G that are not bridges. In characteristic 2, 1 C 1_C 1 C is a flow on G G G , because every vertex of C C C meets exactly two edges of C C C . In Proposition 6.1 with λ = 1 C \lambda=1_C λ = 1 C we have d e = 1 d_e=1 d e = 1 for all e e e , so H λ = H G H_\lambda=H_G H λ = H G . (2) and (3) Two parallel edges form a cycle, so G G G is simple if and only if m ≥ 3 m \ge3 m ≥ 3 . If m ≥ 3 m \ge3 m ≥ 3 , the edges of C C C have no parallel mates, and Theorem 5.1 excludes every characteristic ≠ 2 \ne2 = 2 . If m = 2 m=2 m = 2 , the two edges of C C C are parallel mates of each other and are the only edges on cycles, so Theorem 5.1 gives representability in every characteristic ≠ 2 \ne2 = 2 . Combine with (1).
Since ∣ E ∣ = ∣ V ∣ |E|=|V| ∣ E ∣ = ∣ V ∣ for a connected unicyclic graph, S ( G ) \mathcal{S}(G) S ( G ) is Lagrangian; over a finite field of characteristic 2, H G H_G H G is therefore the stabilizer matrix of a quantum stabilizer state. Adding a single edge to a unicyclic graph can destroy F 2 \mathbb{F}_2 F 2 -representability: the doubled triangle below has ν ∘ = 1 \nu_\circ=1 ν ∘ = 1 , but its bridgeless part is not Eulerian.
Example 7.2. Let n = ∣ E ∣ n=|E| n = ∣ E ∣ , and label the cycle edges by 1 , … , m 1,\ldots,m 1 , … , m and the remaining edges by m + 1 , … , n m+1,\ldots,n m + 1 , … , n . For the unicyclic case in characteristic 2, the matrix M 0 = [ A ∣ I n ] M_0=[A\mid I_n] M 0 = [ A ∣ I n ] , with
A = [ J m − I m 0 m × ( n − m ) 0 ( n − m ) × m I n − m ] , A=\begin{bmatrix}
\mathcal{J}_m-I_m & 0_{m\times(n-m)}\\
0_{(n-m)\times m} & I_{n-m}
\end{bmatrix}, A = [ J m − I m 0 ( n − m ) × m 0 m × ( n − m ) I n − m ] , where J m \mathcal{J}_m J m is the all-ones matrix and I m I_m I m is the identity matrix, represents S ( G ) \mathcal{S}(G) S ( G ) when the cycle length m m m is odd. When m m m is even, interchanging the columns 1 and 1 ∗ 1^* 1 ∗ gives a representation.
Proof. The matrix A A A is symmetric, so M 0 = [ A ∣ I n ] M_0=[A\mid I_n] M 0 = [ A ∣ I n ] is isotropic and has rank n n n . Let T T T be a transversal; put Y = { i ∈ [ n ] : i ∗ ∈ T } Y=\{i\in[n]:i^*\in T\} Y = { i ∈ [ n ] : i ∗ ∈ T } , U = [ n ] ∖ Y U=[n]\setminus Y U = [ n ] ∖ Y , and s = ∣ U ∩ [ m ] ∣ s=|U\cap[m]| s = ∣ U ∩ [ m ] ∣ . Eliminating the unit columns indexed by Y Y Y gives
det M 0 [ T ] = ± det A [ U , U ] = ± det ( J s − I s ) , \det M_0[T]=\pm\det A[U,U]=\pm\det(\mathcal{J}_s-I_s), det M 0 [ T ] = ± det A [ U , U ] = ± det ( J s − I s ) ,
where the determinant of the empty matrix is 1. For s ≥ 1 s\ge1 s ≥ 1 ,
det ( J s − I s ) = ( − 1 ) s − 1 ( s − 1 ) . \det(\mathcal{J}_s-I_s)=(-1)^{s-1}(s-1). det ( J s − I s ) = ( − 1 ) s − 1 ( s − 1 ) .
Since Char F = 2 \operatorname{Char}\mathbb{F}=2 Char F = 2 , this determinant is nonzero exactly when s s s is even. If t = ∣ Y ∩ [ m ] ∣ t=|Y\cap[m]| t = ∣ Y ∩ [ m ] ∣ is the number of starred cycle edges, then s = m − t s=m-t s = m − t . Hence, when m m m is odd, det M 0 [ T ] ≠ 0 \det M_0[T]\ne0 det M 0 [ T ] = 0 exactly when t t t is odd, as required by Chow’s rule.
When m m m is even, swapping columns 1 and 1 ∗ 1^* 1 ∗ replaces Y Y Y by Y △ { 1 } Y\mathbin{\triangle}\{1\} Y △ { 1 } , where △ \triangle △ is the symmetric difference, and therefore reverses this parity condition. The swap preserves isotropy in characteristic two. Thus the resulting matrix has precisely the required admissible bases. □
Corollary 7.3. Let K 3 + K_3^+ K 3 + have vertices 1 , 2 , 3 1,2,3 1 , 2 , 3 , two parallel edges e 1 , e 2 e_1,e_2 e 1 , e 2 joining 1 and 2, and edges e 3 = 23 e_3=23 e 3 = 23 , e 4 = 31 e_4=31 e 4 = 31 . Then S ( K 3 + ) \mathcal{S}(K_3^+) S ( K 3 + ) is F \mathbb{F} F -representable if and
only if char F = 2 \operatorname{char}\mathbb{F}=2 char F = 2 and ∣ F ∣ > 2 |\mathbb{F}|>2 ∣ F ∣ > 2 . In that case, for distinct α , μ ∈ F × \alpha,\mu\in\mathbb{F}^{\times} α , μ ∈ F × and κ = α + μ \kappa=\alpha+\mu κ = α + μ , the matrix
H α , μ = [ 1 1 0 1 α μ 0 κ 1 1 1 0 α μ κ 0 0 0 0 0 α μ κ κ ] , H_{\alpha,\mu}=
\begin{bmatrix}
1 & 1 & 0 & 1 & \alpha& \mu& 0 & \kappa\\
1 & 1 & 1 & 0 & \alpha& \mu& \kappa& 0 \\
0 & 0 & 0 & 0 & \alpha& \mu& \kappa& \kappa
\end{bmatrix}, H α , μ = 1 1 0 1 1 0 0 1 0 1 0 0 α α α μ μ μ 0 κ κ κ 0 κ ,
with columns e 1 , … , e 4 , e 1 ∗ , … , e 4 ∗ e_1,\ldots,e_4,e_1^*,\ldots,e_4^* e 1 , … , e 4 , e 1 ∗ , … , e 4 ∗ and the root 3 3 3 , represents S ( K 3 + ) S(K_3^+) S ( K 3 + ) . Over F 4 = F 2 ( ϑ ) \mathbb{F}_4=\mathbb{F}_2(\vartheta) F 4 = F 2 ( ϑ ) , ϑ 2 = ϑ + 1 \vartheta^2=\vartheta+1 ϑ 2 = ϑ + 1 , one may take ( α , μ ) = ( 1 , ϑ ) (\alpha,\mu)=(1,\vartheta) ( α , μ ) = ( 1 , ϑ ) and κ = ϑ 2 \kappa=\vartheta^2 κ = ϑ 2 .
Proof. The edge e 3 e_3 e 3 lies on a cycle and has no parallel mate, so Theorem 5.1 excludes characteristic ≠ 2 \ne2 = 2 . The vertices 1 1 1 and 2 2 2 have degree 3 3 3 in ( K 3 + ) ∘ = K 3 + (K_3^+)^{\circ}=K_3^+ ( K 3 + ) ∘ = K 3 + , so Theorem 4.1 and (F4) exclude F 2 \mathbb{F}_2 F 2 . If char F = 2 \operatorname{char}\mathbb{F}=2 char F = 2 and ∣ F ∣ > 2 |\mathbb{F}|>2 ∣ F ∣ > 2 , then λ = ( α , μ , κ , κ ) \lambda=(\alpha,\mu,\kappa,\kappa) λ = ( α , μ , κ , κ ) is a nowhere-zero flow: the sums at the vertices 1 1 1 , 2 2 2 and 3 3 3 are α + μ + κ = 0 \alpha+\mu+\kappa=0 α + μ + κ = 0 , α + μ + κ = 0 \alpha+\mu+\kappa=0 α + μ + κ = 0 and κ + κ = 0 \kappa+\kappa=0 κ + κ = 0 , and κ ≠ 0 \kappa\ne0 κ = 0 because α ≠ μ \alpha\ne\mu α = μ . Since ν ∘ ( K 3 + ) = 1 \nu_{\circ}(K_3^+)=1 ν ∘ ( K 3 + ) = 1 and K 3 + K_3^+ K 3 + is bridgeless, Proposition 6.1 applies with d = λ d=\lambda d = λ , and H λ = H α , μ H_\lambda=H_{\alpha,\mu} H λ = H α , μ , because ∂ e 1 = ∂ e 2 = 1 1 + 1 2 \partial e_1=\partial e_2=1_1+1_2 ∂ e 1 = ∂ e 2 = 1 1 + 1 2 , ∂ e 3 = 1 2 \partial e_3=1_2 ∂ e 3 = 1 2 and ∂ e 4 = 1 1 \partial e_4=1_1 ∂ e 4 = 1 1 .
Remark 7.4 (Chow’s remark). Chow [3 ] , crediting a personal communication of N. White, states that a graph with three vertices and four edges, two of which form a double edge, has a non-representable graphical symplectic matroid. A connected loopless graph with three vertices and four edges containing exactly one pair of parallel edges is the doubled triangle K 3 + K_3^+ K 3 + : the two remaining edges must join the third vertex to both ends of the double edge. By Corollary 7.3 , S ( K 3 + ) S(K_3^+) S ( K 3 + ) is not representable over F 2 \mathbb{F}_2 F 2 or over any field of characteristic ≠ 2 \ne2 = 2 , but it is representable over F 4 \mathbb{F}_4 F 4 , explicitly by H 1 , ϑ H_{1,\vartheta} H 1 , ϑ . Since the definition of representability in [1 ] allows every field, the remark holds precisely with the qualification “over F 2 \mathbb{F}_2 F 2 or over a field of characteristic ≠ 2 \ne2 = 2 ”.
Rank enumerators: intrinsic versus enveloped
The intrinsic corank–nullity polynomial
Definition 8.1. Let S S S be a symplectic matroid of rank k k k on J J J . Its admissible corank–nullity polynomial and its restricted Tutte–Martin polynomial are
T S ( u , v ) = ∑ A ∈ A ( J ) u k − r S ( A ) v ∣ A ∣ − r S ( A ) , m S ( x ) = ∑ A ∈ A k ( J ) ( x − 1 ) k − r S ( A ) . (11) T_S(u,v)=\sum_{A\in\mathcal{A}(J)}u^{k-r_S(A)}v^{|A|-r_S(A)},\qquad m_S(x)=\sum_{A\in\mathcal{A}_k(J)}(x-1)^{k-r_S(A)}. \tag*{(11)} T S ( u , v ) = A ∈ A ( J ) ∑ u k − r S ( A ) v ∣ A ∣ − r S ( A ) , m S ( x ) = A ∈ A k ( J ) ∑ ( x − 1 ) k − r S ( A ) . (11)
For a ∈ J a \in J a ∈ J we also put
T S , a ∘ ( u , v ) = ∑ A ∈ A ( J ∖ J a ) u k − r S ( A ) v ∣ A ∣ − r S ( A ) . T_{S,a}^{\circ}(u,v)=\sum_{A\in\mathcal{A}(J\setminus J_a)}u^{k-r_S(A)}v^{|A|-r_S(A)}. T S , a ∘ ( u , v ) = A ∈ A ( J ∖ J a ) ∑ u k − r S ( A ) v ∣ A ∣ − r S ( A ) .
By Lemma 2.6(2) all exponents are nonnegative. Both polynomials depend only on S S S . Since ∣ A ∣ = k |A|=k ∣ A ∣ = k exactly when the two exponents in (11) coincide, m S ( x ) = ∑ j c j j ( x − 1 ) j m_S(x)=\sum_j c_{jj}(x-1)^j m S ( x ) = ∑ j c j j ( x − 1 ) j , where c i j c_{ij} c ij is the coefficient of u i v j u^iv^j u i v j in T S T_S T S . Moreover T S ( 1 , 1 ) = 3 n T_S(1,1)=3^n T S ( 1 , 1 ) = 3 n , T S ( 1 , 0 ) = ∣ I ( S ) ∣ T_S(1,0)=|\mathcal{I}(S)| T S ( 1 , 0 ) = ∣ I ( S ) ∣ , T S ( 0 , 0 ) = ∣ B ( S ) ∣ T_S(0,0)=|\mathcal{B}(S)| T S ( 0 , 0 ) = ∣ B ( S ) ∣ , and T S ( 0 , 1 ) T_S(0,1) T S ( 0 , 1 ) is the number of admissible sets containing a basis. For Lagrangian matroids m S m_S m S is Bouchet’s restricted Tutte–Martin polynomial [18 ] , and in general it is the polynomial (13) of [2 ] , which Sarvepalli defined for represented S S S using the ranks of column sets of a representation; the next proposition shows that the two agree.
Proposition 8.2. Let H H H represent S S S , and let M H M_H M H be the ordinary matroid on J J J represented by the columns of H H H . Then r M H ( A ) = r S ( A ) r_{M_H}(A)=r_S(A) r M H ( A ) = r S ( A ) for every A ∈ A ( J ) A\in\mathcal{A}(J) A ∈ A ( J ) . Consequently ∑ A ∈ A k ( J ) ( x − 1 ) k − rank H [ A ] = m S ( x ) \sum_{A\in\mathcal{A}_k(J)}(x-1)^{k-\operatorname{rank}H[A]}=m_S(x) ∑ A ∈ A k ( J ) ( x − 1 ) k − rank H [ A ] = m S ( x ) and ∑ A ∈ A ( J ) u k − rank H [ A ] v ∣ A ∣ − rank H [ A ] = T S ( u , v ) \sum_{A\in\mathcal{A}(J)}u^{k-\operatorname{rank}H[A]}v^{|A|-\operatorname{rank}H[A]}=T_S(u,v) ∑ A ∈ A ( J ) u k − rank H [ A ] v ∣ A ∣ − rank H [ A ] = T S ( u , v ) ; both are independent of the representation.
Proof. This is Lemma 3.1.
Proposition 8.3. Let S S S be a symplectic matroid and a ∈ J a\in J a ∈ J . For every X ∈ A ( J ∖ J a ) X\in\mathcal{A}(J\setminus J_a) X ∈ A ( J ∖ J a ) ,
r S ( X ∪ { a } ) = { 1 + r S / a ( X ) if a is not a loop of S , r S ( X ) if a is a loop of S . r_S(X\cup\{a\})=\begin{cases}1+r_{S/a}(X) & \text{if }a\text{ is not a loop of }S,\\ r_S(X) & \text{if }a\text{ is a loop of }S.\end{cases} r S ( X ∪ { a }) = { 1 + r S / a ( X ) r S ( X ) if a is not a loop of S , if a is a loop of S .
Proof. If a a a lies in no basis, then ∣ ( X ∪ { a } ) ∩ B ∣ = ∣ X ∩ B ∣ |(X\cup\{a\})\cap B|=|X\cap B| ∣ ( X ∪ { a }) ∩ B ∣ = ∣ X ∩ B ∣ for every basis B B B . Otherwise let T T T be a transversal containing X ∪ { a } X\cup\{a\} X ∪ { a } . By Lemmas 2.4 and 2.6(1), r S ( X ∪ { a } ) r_S(X\cup\{a\}) r S ( X ∪ { a }) is the rank of X ∪ { a } X\cup\{a\} X ∪ { a } in the matroid S ∣ T S|_T S ∣ T , in which { a } \{a\} { a } is independent. In an ordinary matroid, r ( X ∪ { a } ) = 1 + r / a ( X ) r(X\cup\{a\})=1+r_{/a}(X) r ( X ∪ { a }) = 1 + r / a ( X ) for a non-loop a a a , where r / a r_{/a} r / a is the rank function of the contraction. The independent sets of ( S ∣ T ) / a (S|_T)/a ( S ∣ T ) / a are the sets I ⊆ T ∖ { a } I\subseteq T\setminus\{a\} I ⊆ T ∖ { a } with I ∪ { a } ∈ I ( S ) I\cup\{a\}\in\mathcal{I}(S) I ∪ { a } ∈ I ( S ) , that is, by Lemma 2.8(1), the independent sets of S / a S/a S / a contained in T ∖ { a } T\setminus\{a\} T ∖ { a } . Hence r ( S ∣ T ) / a ( X ) = r S / a ( X ) r_{(S|_T)/a}(X)=r_{S/a}(X) r ( S ∣ T ) / a ( X ) = r S / a ( X ) .
Theorem 8.4. Let S S S be a symplectic matroid of rank k k k on J J J , and let a ∈ J a\in J a ∈ J .
If neither a a a nor a ∗ a^{*} a ∗ is a loop, then T S = T S , a ∘ + T S / a + T S / a ∗ T_{S}=T^{\circ}_{S,a}+T_{S/a}+T_{S/a^{*}} T S = T S , a ∘ + T S / a + T S / a ∗ .
If a a a is a loop and a ∗ a^{*} a ∗ is not, then T S = ( 1 + v ) T S , a ∘ + T S / a ∗ T_{S}=(1+v)T^{\circ}_{S,a}+T_{S/a^{*}} T S = ( 1 + v ) T S , a ∘ + T S / a ∗ .
If a a a and a ∗ a^{*} a ∗ are both loops, then T S = ( 1 + 2 v ) T S , a ∘ T_{S}=(1+2v)T^{\circ}_{S,a} T S = ( 1 + 2 v ) T S , a ∘ .
Proof. Every admissible set either avoids J a J_{a} J a , or has the form X ∪ { a } X\cup\{a\} X ∪ { a } or X ∪ { a ∗ } X\cup\{a^{*}\} X ∪ { a ∗ } with X ∈ A ( J ∖ J a ) X\in\mathcal{A}(J\setminus J_{a}) X ∈ A ( J ∖ J a ) , and these three cases are disjoint. The first case contributes T S , a ∘ T^{\circ}_{S,a} T S , a ∘ . If a a a is not a loop, then k ≥ 1 k\geq1 k ≥ 1 , and Proposition 8.3 gives k − r S ( X ∪ { a } ) = ( k − 1 ) − r S / a ( X ) k-r_{S}(X\cup\{a\})=(k-1)-r_{S/a}(X) k − r S ( X ∪ { a }) = ( k − 1 ) − r S / a ( X ) and ∣ X ∪ { a } ∣ − r S ( X ∪ { a } ) = ∣ X ∣ − r S / a ( X ) |X\cup\{a\}|-r_{S}(X\cup\{a\})=|X|-r_{S/a}(X) ∣ X ∪ { a } ∣ − r S ( X ∪ { a }) = ∣ X ∣ − r S / a ( X ) . Since S / a S/a S / a is a symplectic matroid of rank k − 1 k-1 k − 1 on J ∖ J a J\setminus J_{a} J ∖ J a (Lemma 2.8), the second case contributes T S / a T_{S/a} T S / a . If a a a is a loop, the exponent of u u u is unchanged and that of v v v increases by one, so the second case contributes v T S , a ∘ vT^{\circ}_{S,a} v T S , a ∘ . The same applies to a ∗ a^{*} a ∗ .
Corollary 8.6. Let S S S be a Lagrangian matroid on J = [ n ] ∪ [ n ] ∗ J=[n]\cup[n]^{*} J = [ n ] ∪ [ n ] ∗ and i ∈ [ n ] i\in[n] i ∈ [ n ] . Let S ( i ) S(i) S ( i ) be the projection, the Lagrangian matroid on J ∖ J i J\setminus J_{i} J ∖ J i with bases B ∖ J i B\setminus J_{i} B ∖ J i , B ∈ B ( S ) B\in\mathcal{B}(S) B ∈ B ( S ) [6 Def. 5.1] .
If neither i i i nor i ∗ i^{*} i ∗ is a loop, then T S = T S / i + T S / i ∗ + u T S ( i ) T_{S}=T_{S/i}+T_{S/i^{*}}+uT_{S(i)} T S = T S / i + T S / i ∗ + u T S ( i ) .
If i i i is a loop, then T S = ( 1 + u + u v ) T S / i ∗ T_S=(1+u+uv)T_{S/i^*} T S = ( 1 + u + uv ) T S / i ∗ ; symmetrically if i ∗ i^* i ∗ is a loop.
T S ( u , v ) = U S ( u , u v ) T_S(u,v)=U_S(u,uv) T S ( u , v ) = U S ( u , uv ) and m S ( x ) = U S ( 0 , x − 1 ) m_S(x)=U_S(0,x-1) m S ( x ) = U S ( 0 , x − 1 ) , where U S U_S U S is the U U U -polynomial of the delta-matroid of S S S [6 Def. 1.4] , [7 Def. 1.3] . In particular m S ( x ) = Int S ( x − 1 ) m_S(x)=\operatorname{Int}_S(x-1) m S ( x ) = Int S ( x − 1 ) for the interlace polynomial Int S ( v ) = U S ( 0 , v ) \operatorname{Int}_S(v)=U_S(0,v) Int S ( v ) = U S ( 0 , v ) of [6 ] .
If S S S is represented over F 2 \mathbb{F}_2 F 2 by [ I n ∣ A Γ ] [I_n\mid A_\Gamma] [ I n ∣ A Γ ] , where A Γ A_\Gamma A Γ is the adjacency matrix of a simple graph Γ \Gamma Γ on [ n ] [n] [ n ] , then m S ( x ) = q ( Γ ; x ) m_S(x)=q(\Gamma;x) m S ( x ) = q ( Γ ; x ) is the interlace polynomial of Arratia, Bollobás and Sorkin [19 ] .
Proof. Every basis of S S S is a transversal, so it meets J i J_i J i in exactly one element. (1) For A ∈ A ( J ∖ J i ) A\in\mathcal{A}(J\setminus J_i) A ∈ A ( J ∖ J i ) , ∣ A ∩ B ∣ = ∣ A ∩ ( B ∖ J i ) ∣ |A\cap B|=|A\cap(B\setminus J_i)| ∣ A ∩ B ∣ = ∣ A ∩ ( B ∖ J i ) ∣ , so r S ( A ) = r S ( i ) ( A ) r_S(A)=r_{S(i)}(A) r S ( A ) = r S ( i ) ( A ) , and S ( i ) S(i) S ( i ) has rank n − 1 n-1 n − 1 . Hence T S , i ∘ = u T S ( i ) T^\circ_{S,i}=uT_{S(i)} T S , i ∘ = u T S ( i ) , and Theorem 8.4 (1) applies. (2) If i i i is a loop, every basis contains i ∗ i^* i ∗ , so r S ( A ) = r S / i ∗ ( A ) r_S(A)=r_{S/i^*}(A) r S ( A ) = r S / i ∗ ( A ) for A ∈ A ( J ∖ J i ) A\in\mathcal{A}(J\setminus J_i) A ∈ A ( J ∖ J i ) , T S , i = u T S / i ∗ T_{S,i}=uT_{S/i^*} T S , i = u T S / i ∗ , and Theorem 8.4 (2) gives T S = ( 1 + v ) u T S / i ∗ + T S / i ∗ T_S=(1+v)uT_{S/i^*}+T_{S/i^*} T S = ( 1 + v ) u T S / i ∗ + T S / i ∗ . (3) By [7 Def. 1.3] , which agrees with [6 Def. 1.4] by [7 Prop. 3.1] ,
U S ( u , v ) = ∑ A ∈ A ( J ) u n − ∣ A ∣ v ( ∣ A ∣ − g ( A ) ) / 2 , U_S(u,v)=\sum_{A\in\mathcal{A}(J)}u^{n-|A|}v^{(|A|-g(A))/2}, U S ( u , v ) = A ∈ A ( J ) ∑ u n − ∣ A ∣ v ( ∣ A ∣ − g ( A )) /2 ,
where g ( A ) = 2 r S ( A ) − ∣ A ∣ g(A)=2r_S(A)-|A| g ( A ) = 2 r S ( A ) − ∣ A ∣ by Remark 2.7. Thus
U S ( u , v ) = ∑ A u n − ∣ A ∣ v ∣ A ∣ − r S ( A ) , U_S(u,v)=\sum_A u^{n-|A|}v^{|A|-r_S(A)}, U S ( u , v ) = A ∑ u n − ∣ A ∣ v ∣ A ∣ − r S ( A ) ,
and substituting u v uv uv for v v v gives T S T_S T S . Setting u = 0 u=0 u = 0 keeps the terms with ∣ A ∣ = n |A|=n ∣ A ∣ = n , which gives m S ( x ) = U S ( 0 , x − 1 ) m_S(x)=U_S(0,x-1) m S ( x ) = U S ( 0 , x − 1 ) . (Items (1) and (2), after this substitution, are the defining recursion [6 Def. 1.4] .) (4) For a transversal T T T let Y = { j : j ∗ ∈ T } Y=\{j:j^*\in T\} Y = { j : j ∗ ∈ T } . The columns of T T T are the unit vectors 1 j \mathbf{1}_j 1 j , j ∉ Y j\notin Y j ∈ / Y , and the columns of A Γ A_\Gamma A Γ indexed by Y Y Y ; eliminating with the unit vectors gives rank H [ T ] = n − ∣ Y ∣ + rank A Γ [ Y ] \operatorname{rank}H[T]=n-|Y|+\operatorname{rank}A_\Gamma[Y] rank H [ T ] = n − ∣ Y ∣ + rank A Γ [ Y ] , where A Γ [ Y ] A_\Gamma[Y] A Γ [ Y ] is the principal submatrix on Y Y Y . Hence
m S ( x ) = ∑ Y ⊆ [ n ] ( x − 1 ) ∣ Y ∣ − rank A Γ [ Y ] , m_S(x)=\sum_{Y\subseteq[n]}(x-1)^{|Y|-\operatorname{rank}A_\Gamma[Y]}, m S ( x ) = Y ⊆ [ n ] ∑ ( x − 1 ) ∣ Y ∣ − rank A Γ [ Y ] ,
which is q ( Γ ; x ) q(\Gamma;x) q ( Γ ; x ) by the theorem of Aigner and van der Holst [20 ] .
Corollary 8.7 (Deletion–contraction for graphical symplectic matroids). Let G G G be a graph, e e e an edge, and δ e = r ( S ( G ) ) − r ( S ( G ∖ e ) ) \delta_e=r(S(G))-r(S(G\setminus e)) δ e = r ( S ( G )) − r ( S ( G ∖ e )) ; thus δ e ∈ { 0 , 1 } \delta_e\in\{0,1\} δ e ∈ { 0 , 1 } , and δ e = 1 \delta_e=1 δ e = 1 exactly when G ∖ e G\setminus e G ∖ e has more acyclic components than G G G .
If e e e is not a loop, then T S ( G ) = u δ e T S ( G ∖ e ) + 2 T S ( G / e ) T_{S(G)}=u^{\delta_e}T_{S(G\setminus e)}+2T_{S(G/e)} T S ( G ) = u δ e T S ( G ∖ e ) + 2 T S ( G / e ) .
If e e e is a loop, then T S ( G ) = ( 1 + v ) u δ e T S ( G ∖ e ) + T S ( G ) / e ∗ T_{S(G)}=(1+v)u^{\delta_e}T_{S(G\setminus e)}+T_{S(G)/e^*} T S ( G ) = ( 1 + v ) u δ e T S ( G ∖ e ) + T S ( G ) / e ∗ .
Proof. Let S = S ( G ) S=S(G) S = S ( G ) and k = r ( S ) k=r(S) k = r ( S ) . The value of δ e \delta_e δ e follows from Lemma 2.12 , because deleting one edge creates at most one new acyclic component. Admissible subsets of J ∖ J e J\setminus J_e J ∖ J e are admissible sets for G ∖ e G\setminus e G ∖ e , and G [ A ] = ( G ∖ e ) [ A ] G[A]=(G\setminus e)[A] G [ A ] = ( G ∖ e ) [ A ] for them; hence r S ( A ) = r S ( G ∖ e ) ( A ) r_S(A)=r_{S(G\setminus e)}(A) r S ( A ) = r S ( G ∖ e ) ( A ) , and T S , e ∘ = u δ e T S ( G ∖ e ) T^\circ_{S,e}=u^{\delta_e}T_{S(G\setminus e)} T S , e ∘ = u δ e T S ( G ∖ e ) . (1) Neither e e e nor e ∗ e^* e ∗ is a loop of S S S , since a single non-loop edge is a tree. By Corollary 3.5 (2), S / e = S ( G / e ) S/e = S(G/e) S / e = S ( G / e ) . Let s s s be an end of e e e . By Lemma 2.13 , σ s \sigma_s σ s maps B ( S ) \mathcal{B}(S) B ( S ) onto itself, and σ s ( e ) = e ∗ \sigma_s(e)=e^{*} σ s ( e ) = e ∗ ; hence B ( S / e ∗ ) = σ s ( B ( S / e ) ) \mathcal{B}(S/e^{*})=\sigma_s(\mathcal{B}(S/e)) B ( S / e ∗ ) = σ s ( B ( S / e )) . Since σ s \sigma_s σ s permutes A ( J ∖ J e ) \mathcal{A}(J\setminus J_e) A ( J ∖ J e ) preserving sizes, T S / e ∗ = T S / e T_{S/e^{*}}=T_{S/e} T S / e ∗ = T S / e . Now apply Theorem 8.4 (1). (2) A loop without star is a cycle with no starred edge, so e e e is a loop of S S S , while { e ∗ } \{e^{*}\} { e ∗ } is independent. Apply Theorem 8.4 (2).
In (2), S ( G ) / e ∗ S(G)/e^{*} S ( G ) / e ∗ is in general not a graphical symplectic matroid: its independent sets are the sets X X X such that X ∪ { e ∗ } ∈ I ( G ) X\cup\{e^{*}\}\in\mathcal{I}(G) X ∪ { e ∗ } ∈ I ( G ) , that is, the component of G [ X ] G[X] G [ X ] containing the vertex of the loop must be a tree. Matroids of this kind are the subject of the next subsection.
Marked vertices
Definition 8.8 (Marked vertices). Let R ⊆ V R\subseteq V R ⊆ V be a set of marked vertices of G G G . An admissible set S S S is independent in S ( G , R ) S(G,R) S ( G , R ) if every component of G [ S ] G[S] G [ S ] without a vertex of R R R is good (Definition 2.10 ), and every component of G [ S ] G[S] G [ S ] that meets R R R is a tree containing exactly one vertex of R R R . Let τ R ( G ) \tau_R(G) τ R ( G ) be the number of components of G G G that contain neither a cycle nor a vertex of R R R .
For R = ∅ R=\varnothing R = ∅ these are the independent sets of S ( G ) S(G) S ( G ) , and τ ∅ ( G ) = τ ( G ) \tau_{\varnothing}(G)=\tau(G) τ ∅ ( G ) = τ ( G ) .
Proposition 8.9. Let G R G^R G R be obtained from G G G by adding a loop ℓ s \ell_s ℓ s at every s ∈ R s\in R s ∈ R , and let L R = { ℓ s ∗ : s ∈ R } L_R=\{\ell_s^{*}:s\in R\} L R = { ℓ s ∗ : s ∈ R } . Then L R L_R L R is independent in S ( G R ) S(G^R) S ( G R ) , and the independent sets of S ( G R ) / L R S(G^R)/L_R S ( G R ) / L R are the independent sets of Definition 8.8 . Consequently these are the independent sets of a symplectic matroid S ( G , R ) S(G,R) S ( G , R ) , and
r ( S ( G , R ) ) = ∣ V ∣ − ∣ R ∣ − τ R ( G ) . r(S(G,R))=|V|-|R|-\tau_R(G). r ( S ( G , R )) = ∣ V ∣ − ∣ R ∣ − τ R ( G ) . Proof. The nontrivial components of G R [ L R ] G^R[L_R] G R [ L R ] are single loops with one starred edge, so L R L_R L R is independent. By Lemma 2.8 (1), applied ∣ R ∣ |R| ∣ R ∣ times, an admissible set S S S on the edges of G G G is independent in S ( G R ) / L R S(G^R)/L_R S ( G R ) / L R if and only if S ∪ L R S\cup L_R S ∪ L R is independent in S ( G R ) S(G^R) S ( G R ) . Let K K K be a component of G [ S ] G[S] G [ S ] with t t t marked vertices. In G R [ S ∪ L R ] G^R[S\cup L_R] G R [ S ∪ L R ] it acquires t t t starred loops. If t = 0 t=0 t = 0 , nothing changes. If t ≥ 1 t\ge1 t ≥ 1 , the new component has ∣ E ( K ) ∣ + t ≥ ∣ V ( K ) ∣ − 1 + t |E(K)|+t\ge|V(K)|-1+t ∣ E ( K ) ∣ + t ≥ ∣ V ( K ) ∣ − 1 + t edges, so it is good if and only if it is unicyclic, that is, if and only if K K K is a tree and t = 1 t=1 t = 1 ; its cycle is then a starred loop. This proves the first two claims. By Lemmas 2.8 (1) and 2.12 , r ( S ( G , R ) ) = r ( S ( G R ) ) − ∣ R ∣ = ∣ V ∣ − τ ( G R ) − ∣ R ∣ r(S(G,R))=r(S(G^R))-|R|=|V|-\tau(G^R)-|R| r ( S ( G , R )) = r ( S ( G R )) − ∣ R ∣ = ∣ V ∣ − τ ( G R ) − ∣ R ∣ , and the components of G R G^R G R without cycles are the components of G G G without cycles and without marked vertices.
On a transversal T T T , Proposition 8.9 exhibits S ( G , R ) ∣ T \mathcal{S}(G,R)|_T S ( G , R ) ∣ T as the contraction of the frame matroid S ( G R ) ∣ T ∪ L R \mathcal{S}(G^R)|_{T\cup L_R} S ( G R ) ∣ T ∪ L R by negative loops, which behave like the half-edges of [11 ] . For an edge e e e of G G G put
δ e R = r ( S ( G , R ) ) − r ( S ( G ∖ e , R ) ) = τ R ( G ∖ e ) − τ R ( G ) . \delta_e^R = r(\mathcal{S}(G,R)) - r(\mathcal{S}(G \setminus e,R)) = \tau_R(G \setminus e) - \tau_R(G). δ e R = r ( S ( G , R )) − r ( S ( G ∖ e , R )) = τ R ( G ∖ e ) − τ R ( G ) .
Deleting e e e replaces the component K K K of G G G containing e e e by one or two components. If K K K has no cycle and no marked vertex, neither have these, and if two of them have none, then neither has K K K . Hence δ e R ∈ { 0 , 1 } \delta_e^R \in\{0,1\} δ e R ∈ { 0 , 1 } .
Theorem 8.10. Let R ⊆ V R \subseteq V R ⊆ V , write T G , R = T S ( G , R ) T_{G,R}=T_{\mathcal{S}(G,R)} T G , R = T S ( G , R ) , and let e e e be an edge with ends s s s and t t t , where s = t s=t s = t if e e e is a loop.
If s , t ∈ R s,t \in R s , t ∈ R , then T G , R = ( 1 + 2 v ) T G ∖ e , R T_{G,R}=(1+2v)T_{G\setminus e,R} T G , R = ( 1 + 2 v ) T G ∖ e , R .
If s ≠ t s\ne t s = t and { s , t } ⊈ R \{s,t\}\not\subseteq R { s , t } ⊆ R , then T G , R = u δ e R T G ∖ e , R + 2 T G / e , R e T_{G,R}=u^{\delta_e^R}T_{G\setminus e,R}+2T_{G/e,R_e} T G , R = u δ e R T G ∖ e , R + 2 T G / e , R e , where R e R_e R e is the image of R R R in G / e G/e G / e .
If s = t ∉ R s=t\notin R s = t ∈ / R , then T G , R = ( 1 + v ) u δ e R T G ∖ e , R + T G ∖ e , R ∪ { s } T_{G,R}=(1+v)u^{\delta_e^R}T_{G\setminus e,R}+T_{G\setminus e,R\cup\{s\}} T G , R = ( 1 + v ) u δ e R T G ∖ e , R + T G ∖ e , R ∪ { s } .
If G G G has no edges, then T G , R = 1 T_{G,R}=1 T G , R = 1 . Thus (1)–(3) compute T S ( G ) = T G , ∅ T_{S(G)}=T_{G,\varnothing} T S ( G ) = T G , ∅ recursively, removing one edge at a time.
Proof. An admissible set that avoids J e J_e J e has the same independent subsets, hence the same rank, in S ( G , R ) \mathcal{S}(G,R) S ( G , R ) and in S ( G ∖ e , R ) \mathcal{S}(G\setminus e,R) S ( G ∖ e , R ) . Therefore T S ( G , R ) , e = u δ e R T G ∖ e , R T_{\mathcal{S}(G,R),e}=u^{\delta_e^R}T_{G\setminus e,R} T S ( G , R ) , e = u δ e R T G ∖ e , R .
(1) Here e e e joins two marked vertices or is a loop at a marked vertex, so neither { e } \{e\} { e } nor { e ∗ } \{e^*\} { e ∗ } is independent, and both are loops of S ( G , R ) \mathcal{S}(G,R) S ( G , R ) . The components of G G G and of G ∖ e G\setminus e G ∖ e that contain an end of e e e contain a marked vertex, so δ e R = 0 \delta_e^R=0 δ e R = 0 , and Theorem 8.4 (3) gives (1).
(2) A single edge with at most one marked end is a tree, so neither e e e nor e ∗ e^* e ∗ is a loop. Let X X X be admissible with X ∩ J e = ∅ X\cap J_e=\varnothing X ∩ J e = ∅ . Contracting e e e maps the components of G [ X ∪ { e } ] G[X\cup\{e\}] G [ X ∪ { e }] bijectively onto those of ( G / e ) [ X ] (G/e)[X] ( G / e ) [ X ] . As in the proof of Lemma 3.4 , trees correspond to trees and unicyclic components to unicyclic components with the same starred edges on their cycles, and since s s s and t t t are not both marked, corresponding components contain the same number of marked vertices. Hence X ∪ { e } X\cup\{e\} X ∪ { e } is independent in S ( G , R ) \mathcal{S}(G,R) S ( G , R ) if and only if X X X is independent in S ( G / e , R e ) \mathcal{S}(G/e,R_e) S ( G / e , R e ) , that is, S ( G , R ) / e = S ( G / e , R e ) \mathcal{S}(G,R)/e=\mathcal{S}(G/e,R_e) S ( G , R ) / e = S ( G / e , R e ) by Lemma 2.8 (1). The switching σ s \sigma_s σ s of Lemma 2.13 preserves independence in S ( G , R ) \mathcal{S}(G,R) S ( G , R ) , because it does not change G [ S ] G[S] G [ S ] and preserves the parity of the number of starred edges on every cycle. As in the proof of Corollary 8.7 , σ s \sigma_s σ s maps S ( G , R ) / e \mathcal{S}(G,R)/e S ( G , R ) / e onto S ( G , R ) / e ∗ \mathcal{S}(G,R)/e^* S ( G , R ) / e ∗ , so both contractions have the polynomial T G / e , R e T_{G/e,R_e} T G / e , R e , and Theorem 8.4 (1) gives (2).
(3) The unstarred loop e e e is a cycle without starred edges in a component without marked vertices, so e e e is a loop of S ( G , R ) \mathcal{S}(G,R) S ( G , R ) , whereas { e ∗ } \{e^*\} { e ∗ } is independent. For X X X as above, X ∪ { e ∗ } X\cup\{e^*\} X ∪ { e ∗ } is independent if and only if the component of s s s in G [ X ] G[X] G [ X ] is a tree without marked vertices and the other components satisfy Definition 8.8 , that is, if and only if X X X is independent in S ( G ∖ e , R ∪ { s } ) \mathcal{S}(G\setminus e,R\cup\{s\}) S ( G ∖ e , R ∪ { s }) . Hence S ( G , R ) / e ∗ = S ( G ∖ e , R ∪ { s } ) \mathcal{S}(G,R)/e^*=\mathcal{S}(G\setminus e,R\cup\{s\}) S ( G , R ) / e ∗ = S ( G ∖ e , R ∪ { s }) , and Theorem 8.4 (2) gives (3).
If G G G has no edges, the empty set is the only admissible set and the rank is 0.
Call two symplectic matroids isomorphic if a bijection between their ground sets that commutes with the involution maps the bases of one onto the bases of the other.
Corollary 8.11. Let M \mathcal{M} M be the class of symplectic matroids isomorphic to some S ( G , R ) \mathcal{S}(G,R) S ( G , R ) ; it contains all graphical symplectic matroids. Let S ∈ M \mathcal{S}\in\mathcal{M} S ∈ M be a symplectic matroid on J J J , and let a ∈ J a\in J a ∈ J .
The independent sets of S \mathcal{S} S contained in J ∖ J a J\setminus J_a J ∖ J a are those of a member S ∖ J a \mathcal{S}\setminus J_a S ∖ J a of M \mathcal{M} M , and T S , a ∘ = u r ( S ) − r ( S ∖ J a ) T S ∖ J a T^{\circ}_{\mathcal{S},a}=u^{r(\mathcal{S})-r(\mathcal{S}\setminus J_a)}T_{\mathcal{S}\setminus J_a} T S , a ∘ = u r ( S ) − r ( S ∖ J a ) T S ∖ J a .
If a a a is not a loop of S \mathcal{S} S , then S / a ∈ M \mathcal{S}/a\in\mathcal{M} S / a ∈ M .
Hence Theorem 8.4 computes T S T_{\mathcal{S}} T S for every S ∈ M \mathcal{S}\in\mathcal{M} S ∈ M by a recursion that stays inside M \mathcal{M} M .
Proof. We may assume that S = S ( G , R ) \mathcal{S}=\mathcal{S}(G,R) S = S ( G , R ) and a ∈ { e , e ∗ } a\in\{e,e^*\} a ∈ { e , e ∗ } for an edge e e e . Then S ∖ J e = S ( G ∖ e , R ) \mathcal{S}\setminus J_e=\mathcal{S}(G\setminus e,R) S ∖ J e = S ( G ∖ e , R ) , and the formula for T S , a ∘ T^{\circ}_{\mathcal{S},a} T S , a ∘ was shown at the beginning of the proof of Theorem 8.10 . In case (1) of that theorem both elements of J e J_e J e are loops. In case (2), S / e = S ( G / e , R e ) \mathcal{S}/e=\mathcal{S}(G/e,R_e) S / e = S ( G / e , R e ) , and σ s \sigma_s σ s is an isomorphism from S / e \mathcal{S}/e S / e onto S / e ∗ \mathcal{S}/e^* S / e ∗ . In case (3), e e e is a loop and S / e ∗ = S ( G ∖ e , R ∪ { s } ) \mathcal{S}/e^*=\mathcal{S}(G\setminus e,R\cup\{s\}) S / e ∗ = S ( G ∖ e , R ∪ { s }) .
By Remark 8.5 , a class with property (1) cannot contain all symplectic matroids.
Envelopes
Definition 8.12 (Envelopes). Let S \mathcal{S} S be a symplectic matroid of rank k k k on J J J . A pair-compatible envelope of S \mathcal{S} S is an ordinary matroid M M M of rank k k k on J J J with B ( M ) ∩ A k ( J ) = B ( S ) \mathcal{B}(M) \cap\mathcal{A}_k(J) = \mathcal{B}(\mathcal{S}) B ( M ) ∩ A k ( J ) = B ( S ) . These are the enveloping matroids of [1 Exercise 3.12.6] (cf. [6 Rem. 6.7] ). An envelope M M M is sheltering if its admissible independent sets are exactly the independent sets of S \mathcal{S} S [9 Sec. 4] . The envelope polynomial is
T S , M ( u , v ) = ∑ A ∈ A ( J ) u k − r M ( A ) v ∣ A ∣ − r M ( A ) . T_{\mathcal{S},M}(u,v)=\sum_{A\in\mathcal{A}(J)}u^{k-r_M(A)}v^{|A|-r_M(A)}. T S , M ( u , v ) = A ∈ A ( J ) ∑ u k − r M ( A ) v ∣ A ∣ − r M ( A ) .
Proposition 8.13. Let M M M be a pair-compatible envelope of S \mathcal{S} S . Then r M ( A ) ≥ r S ( A ) r_M(A)\ge r_{\mathcal{S}}(A) r M ( A ) ≥ r S ( A ) for every A ∈ A ( J ) A\in\mathcal{A}(J) A ∈ A ( J ) , with equality for all A A A if and only if M M M is sheltering. Moreover T S , M = T S T_{\mathcal{S},M}=T_{\mathcal{S}} T S , M = T S if and only if M M M is sheltering.
Proof. Bases of S \mathcal{S} S are bases of M M M , so A ∩ B A\cap B A ∩ B is M M M -independent for every B ∈ B ( S ) B\in\mathcal{B}(\mathcal{S}) B ∈ B ( S ) , which gives the inequality. If equality holds everywhere and A A A is admissible and M M M -independent, then r S ( A ) = r M ( A ) = ∣ A ∣ r_{\mathcal{S}}(A)=r_M(A)=|A| r S ( A ) = r M ( A ) = ∣ A ∣ , so A ∈ I ( S ) A\in\mathcal{I}(\mathcal{S}) A ∈ I ( S ) ; conversely, if M M M is sheltering, the M M M -independent subsets of an admissible A A A are the S \mathcal{S} S -independent ones, so r M ( A ) = r S ( A ) r_M(A)=r_{\mathcal{S}}(A) r M ( A ) = r S ( A ) . If r M ( A 0 ) > r S ( A 0 ) r_M(A_0)>r_{\mathcal{S}}(A_0) r M ( A 0 ) > r S ( A 0 ) for some A 0 A_0 A 0 , then, differentiating with respect to u u u ,
∂ u T S , M ( 1 , 1 ) = ∑ A ( k − r M ( A ) ) < ∑ A ( k − r S ( A ) ) = ∂ u T S ( 1 , 1 ) . \partial_u T_{\mathcal{S},M}(1,1)=\sum_A(k-r_M(A))<\sum_A(k-r_{\mathcal{S}}(A))=\partial_u T_{\mathcal{S}}(1,1). ∂ u T S , M ( 1 , 1 ) = A ∑ ( k − r M ( A )) < A ∑ ( k − r S ( A )) = ∂ u T S ( 1 , 1 ) .
Corollary 8.14. If H H H represents S \mathcal{S} S , then M H M_H M H is a sheltering envelope of S \mathcal{S} S and T S , M H = T S T_{\mathcal{S},M_H}=T_{\mathcal{S}} T S , M H = T S . In particular, a symplectic matroid without a sheltering envelope is not representable over any field.
Proof. M H M_H M H has rank k k k , and its admissible bases are the admissible k k k -sets with nonzero determinant, that is, the bases of S \mathcal{S} S . It is sheltering by Lemma 3.1.
Example 8.15 (Duchamp’s delta-matroid). Let S \mathcal{S} S be the Lagrangian matroid on [ 4 ] ∪ [ 4 ] ∗ [4]\cup[4]^* [ 4 ] ∪ [ 4 ] ∗ with bases
B = { 1 ∗ 2 ∗ 3 ∗ 4 ∗ , 1 ∗ 2 ∗ 3 ∗ 4 , 1 ∗ 234 ∗ , 12 ∗ 34 ∗ , 123 ∗ 4 ∗ , 1 ∗ 234 , 12 ∗ 34 , 123 ∗ 4 , 1234 } , \mathcal{B}=\{1^*2^*3^*4^*,1^*2^*3^*4,1^*234^*,12^*34^*,123^*4^*,1^*234,12^*34,123^*4,1234\}, B = { 1 ∗ 2 ∗ 3 ∗ 4 ∗ , 1 ∗ 2 ∗ 3 ∗ 4 , 1 ∗ 23 4 ∗ , 1 2 ∗ 3 4 ∗ , 12 3 ∗ 4 ∗ , 1 ∗ 234 , 1 2 ∗ 34 , 12 3 ∗ 4 , 1234 } , where 1 ∗ 2 ∗ 3 ∗ 4 ∗ 1^*2^*3^*4^* 1 ∗ 2 ∗ 3 ∗ 4 ∗ stands for { 1 ∗ , 2 ∗ , 3 ∗ , 4 ∗ } \{1^*,2^*,3^*,4^*\} { 1 ∗ , 2 ∗ , 3 ∗ , 4 ∗ } . Bouchet [9 Sec. 4] gives this example, which he attributes to Duchamp, in his discussion of sheltering matroids; see also [6 Ex. 6.12] . A SAT enumeration (Appendix A) shows:
S S S has exactly twelve pair-compatible envelopes; six of them have 49 bases and six have 53 bases;
none of them is sheltering. For example, the rank-4 matroid M 0 M_0 M 0 on J J J whose non-bases are the 21 four-element sets
1 ∗ 2 ∗ 3 ∗ , 1 ∗ 2 ∗ 34 , 1 ∗ 2 ∗ 34 ∗ , 1 ∗ 22 ∗ 3 , 1 ∗ 22 ∗ 3 ∗ , 1 ∗ 23 ∗ 4 , 1 ∗ 23 ∗ 4 ∗ , 1\ast2\ast3\ast,\ 1\ast2\ast34,\ 1\ast2\ast34\ast,\ 1\ast22\ast3,\ 1\ast22\ast3\ast,\ 1\ast23\ast4,\ 1\ast23\ast4\ast, 1 ∗ 2 ∗ 3 ∗ , 1 ∗ 2 ∗ 34 , 1 ∗ 2 ∗ 34 ∗ , 1 ∗ 22 ∗ 3 , 1 ∗ 22 ∗ 3 ∗ , 1 ∗ 23 ∗ 4 , 1 ∗ 23 ∗ 4 ∗ ,
1 ∗ 233 ∗ , 1 ∗ 244 ∗ , 1 ∗ 3 ∗ 44 ∗ , 11 ∗ 2 ∗ 3 , 11 ∗ 23 ∗ , 12 ∗ 3 ∗ 4 , 12 ∗ 3 ∗ 4 ∗ , 1\ast233\ast,\ 1\ast244\ast,\ 1\ast3\ast44\ast,\ 11\ast2\ast3,\ 11\ast23\ast,\ 12\ast3\ast4,\ 12\ast3\ast4\ast, 1 ∗ 233 ∗ , 1 ∗ 244 ∗ , 1 ∗ 3 ∗ 44 ∗ , 11 ∗ 2 ∗ 3 , 11 ∗ 23 ∗ , 12 ∗ 3 ∗ 4 , 12 ∗ 3 ∗ 4 ∗ ,
12 ∗ 44 ∗ , 1234 ∗ , 13 ∗ 44 ∗ , 2 ∗ 3 ∗ 44 ∗ , 22 ∗ 33 ∗ , 23 ∗ 44 ∗ , 33 ∗ 44 ∗ 12\ast44\ast,\ 1234\ast,\ 13\ast44\ast,\ 2\ast3\ast44\ast,\ 22\ast33\ast,\ 23\ast44\ast,\ 33\ast44\ast 12 ∗ 44 ∗ , 1234 ∗ , 13 ∗ 44 ∗ , 2 ∗ 3 ∗ 44 ∗ , 22 ∗ 33 ∗ , 23 ∗ 44 ∗ , 33 ∗ 44 ∗
is an envelope with 49 bases in which { 1 , 2 ∗ , 3 ∗ } \{1,2\ast,3\ast\} { 1 , 2 ∗ , 3 ∗ } is independent, although no basis of S S S contains it; so r M 0 ( { 1 , 2 ∗ , 3 ∗ } ) = 3 > 2 = r S ( { 1 , 2 ∗ , 3 ∗ } ) r_{M_0}(\{1,2\ast,3\ast\})=3>2=r_S(\{1,2\ast,3\ast\}) r M 0 ({ 1 , 2 ∗ , 3 ∗ }) = 3 > 2 = r S ({ 1 , 2 ∗ , 3 ∗ }) ;
the twelve envelopes have exactly two different polynomials. Let M 1 M_1 M 1 be the matroid whose bases are those of M 0 M_0 M 0 together with the four inadmissible sets 11 ∗ 23 ∗ 11\ast23\ast 11 ∗ 23 ∗ , 1 ∗ 233 ∗ 1\ast233\ast 1 ∗ 233 ∗ , 22 ∗ 33 ∗ 22\ast33\ast 22 ∗ 33 ∗ and 1 ∗ 22 ∗ 3 ∗ 1\ast22\ast3\ast 1 ∗ 22 ∗ 3 ∗ ; it is one of the envelopes with 53 bases. Then
T S = u 4 + 8 u 3 + 3 u 2 v + 24 u 2 + 7 u v + 29 u + 9 , T S , M 0 = u 4 + 8 u 3 + 2 u 2 v + 24 u 2 + 7 u v + 30 u + 9 , T S , M 1 = u 4 + 8 u 3 + u 2 v + 24 u 2 + 7 u v + 31 u + 9. \begin{aligned}
T_S &= u^4+8u^3+3u^2v+24u^2+7uv+29u+9,\\
T_{S,M_0} &= u^4+8u^3+2u^2v+24u^2+7uv+30u+9,\\
T_{S,M_1} &= u^4+8u^3+u^2v+24u^2+7uv+31u+9.
\end{aligned} T S T S , M 0 T S , M 1 = u 4 + 8 u 3 + 3 u 2 v + 24 u 2 + 7 uv + 29 u + 9 , = u 4 + 8 u 3 + 2 u 2 v + 24 u 2 + 7 uv + 30 u + 9 , = u 4 + 8 u 3 + u 2 v + 24 u 2 + 7 uv + 31 u + 9.
and nine of the envelopes, among them all six with 49 bases, have the polynomial T S , M 0 T_{S,M_0} T S , M 0 , while the other three have T S , M 1 T_{S,M_1} T S , M 1 .
By (2) and Proposition 8.13, no envelope polynomial of S S S equals T S T_S T S , and by Corollary 8.14, S S S is not representable over any field. By (3), the envelope polynomial T S , M T_{S,M} T S , M depends on the choice of M M M , whereas T S T_S T S is an invariant of S S S . The statement in [6 Ex. 6.12] that no matroid on [ 4 ] ⊔ [ 4 ] ∗ [4]\mathbin{\sqcup}[4]^\ast [ 4 ] ⊔ [ 4 ] ∗ has B \mathcal{B} B as its family of admissible bases is correct for sheltering matroids, the notion relevant there (cf. [6 Rem. 6.7] ), but not for the enveloping matroids of [1 Exercise 3.12.6] .
Remark 8.16. For U k , n ∗ U^\ast_{k,n} U k , n ∗ one has r ( A ) = min ( k , ∣ A ∣ ) r(A)=\min(k,\lvert A\rvert) r ( A ) = min ( k , ∣ A ∣) and there are 2 s ( n s ) 2^s\binom{n}{s} 2 s ( s n ) admissible s s s -sets, so
T U k , n ∗ ( u , v ) = ∑ s = 0 k 2 s ( n s ) u k − s + ∑ s = k + 1 n 2 s ( n s ) v s − k . T_{U^\ast_{k,n}}(u,v)=\sum_{s=0}^{k}2^s\binom{n}{s}u^{k-s}+\sum_{s=k+1}^{n}2^s\binom{n}{s}v^{s-k}. T U k , n ∗ ( u , v ) = s = 0 ∑ k 2 s ( s n ) u k − s + s = k + 1 ∑ n 2 s ( s n ) v s − k .
Every envelope of U k , n ∗ U^{*}_{k,n} U k , n ∗ is sheltering, because every admissible set of size at most k k k is independent in U k , n ∗ U^{*}_{k,n} U k , n ∗ ; hence every envelope polynomial of U k , n ∗ U^{*}_{k,n} U k , n ∗ equals T U k , n ∗ T_{U^{*}_{k,n}} T U k , n ∗ . Let P n , k P_{n,k} P n , k be the truncation to rank k k k of the direct sum of the rank-one uniform matroids on the pairs J 1 , … , J n J_1,\ldots,J_n J 1 , … , J n ; its independent sets are the admissible sets of size at most k k k . It is an envelope of U k , n ∗ U^{*}_{k,n} U k , n ∗ , and it is the least envelope in the weak order: for every envelope M M M , every independent set of P n , k P_{n,k} P n , k lies in an admissible k k k -set, which is a basis of M M M , so r P n , k ≤ r M r_{P_{n,k}}\leq r_M r P n , k ≤ r M . For k ≥ 2 k\geq2 k ≥ 2 its rank-one flats are the inadmissible pairs J i J_i J i (and for k = 1 k=1 k = 1 its only rank-one flat is J J J ), so P n , k P_{n,k} P n , k is not an admissible matroid in the sense of Raz, whose atoms are admissible [21 Lemma 2.3] . Relaxing an inadmissible circuit-hyperplane of an envelope [8 Prop. 1.5.14] produces another envelope with the same ranks on admissible sets.
Open problems
The normal form (Theorem 3.8 ) reduces the representation problem for S ( G ) \mathcal{S}(G) S ( G ) to the choice of a flow, linear conditions on Z 1 \mathcal{Z}_1 Z 1 , and the prescribed vanishing and nonvanishing of maximal minors (Remark 3.10). The problem is solved in characteristic ≠ 2 \ne2 = 2 , in characteristic 2 2 2 for loopless graphs without two vertex-disjoint cycles, and over every field for 3 3 3 -connected simple graphs (Theorem 6.11 ). Characteristic 2 2 2 in general remains open.
Question 9.1. Characterize the graphs G G G for which S ( G ) \mathcal{S}(G) S ( G ) is representable over a field of characteristic 2 2 2 with at least 8 8 8 elements, where flows impose no restriction. If S ( G ) \mathcal{S}(G) S ( G ) is not representable over such a field, does G G G have a forest F F F such that G / F G/F G / F contains a rigidly linked pair of cycles, as in Proposition 6.9 ?
Question 9.2. Over fields of characteristic 2 2 2 with at least 4 4 4 elements, is representability of S ( G ) \mathcal{S}(G) S ( G ) preserved under 1 1 1 -sums and under joining two graphs by a bridge? The graphs X 1 X_1 X 1 and X 5 X_5 X 5 of Example 6.8 are instances of a positive answer, whereas X 5 X_5 X 5 shows that 1 1 1 -sums do not preserve representability over F 2 \mathbb{F}_2 F 2 .
Question 9.3. By Theorem 6.2 , F 4 \mathbb{F}_4 F 4 -representability of S ( G ) \mathcal{S}(G) S ( G ) is equivalent to the existence of a nowhere-zero 4 4 4 -flow on G ∘ G^\circ G ∘ when ν ∘ ( G ) ≤ 1 \nu^\circ(G)\leq1 ν ∘ ( G ) ≤ 1 . Is deciding F 4 \mathbb{F}_4 F 4 -representability of S ( G ) \mathcal{S}(G) S ( G ) NP-hard in general, as deciding 3 3 3 -edge-colourability of cubic graphs is [22 ] ?
Computations
Only Examples 6.8(2), (3), (5) and 8.15 depend on computer calculations; all other statements are proved in the text.
Representability searches. For a connected graph G G G with a fixed orientation and root and a finite field F q \mathbb{F}_q F q , the program enumerates all F q \mathbb{F}_q F q -flows z z z that are nonzero exactly on the non-bridges, up to a scalar factor (the last row of a normal form may be rescaled). For each such z z z it solves the linear system in the entries of Z 1 Z_1 Z 1 formed by (N3) and by the relations obtained, as in the proof of Lemma 3.9 , from every dependent admissible set with at most two starred elements whose unstarred part is a forest. By Theorem 3.8 , every representation in normal form arises in this way. If the solution space has at most 2 18 2^{18} 2 18 elements, all solutions are enumerated; otherwise random solutions are sampled, which can only establish representability. Each candidate H H H is compared with Chow’s rule on all admissible ∣ V ∣ |V| ∣ V ∣ -sets. The results are as follows.
X 4 X_4 X 4 over F 4 \mathbb{F}_4 F 4 : there are 24 flows up to scalars, each with a solution space of dimension 5, and none of the 24 ⋅ 4 5 24\cdot4^5 24 ⋅ 4 5 candidates is a representation, in accordance with Theorem 6.6 .
We write F 4 = F 2 ( ϑ ) \mathbb{F}_4=\mathbb{F}_2(\vartheta) F 4 = F 2 ( ϑ ) with ϑ 2 = ϑ + 1 \vartheta^2=\vartheta+1 ϑ 2 = ϑ + 1 and ϑ ˉ = ϑ 2 \bar{\vartheta}=\vartheta^2 ϑ ˉ = ϑ 2 , and F 8 = F 2 ( η ) \mathbb{F}_8=\mathbb{F}_2(\eta) F 8 = F 2 ( η ) with η 3 = η + 1 \eta^3=\eta+1 η 3 = η + 1 ; in the matrix over F 8 \mathbb{F}_8 F 8 , an entry c = c 0 + 2 c 1 + 4 c 2 c=c_0+2c_1+4c_2 c = c 0 + 2 c 1 + 4 c 2 (c j ∈ { 0 , 1 } c_j\in\{0,1\} c j ∈ { 0 , 1 } ) stands for c 0 + c 1 η + c 2 η 2 c_0+c_1\eta+c_2\eta^2 c 0 + c 1 η + c 2 η 2 . In each matrix the columns are indexed by the edges in the order listed in Example 6.8, first unstarred and then starred, the root is the vertex 0, and the first ∣ V ∣ − 1 |V|-1 ∣ V ∣ − 1 rows are indexed by the vertices 1 , … , ∣ V ∣ − 1 1,\ldots,|V|-1 1 , … , ∣ V ∣ − 1 .
X 2 , F 4 : [ 1 1 0 0 0 0 0 0 0 0 1 ϑ ˉ ϑ ˉ 1 ϑ ϑ 0 1 1 0 0 0 0 1 ϑ ˉ 0 0 ϑ ϑ ϑ ˉ 1 0 0 0 0 1 0 1 1 0 ϑ ˉ ϑ ˉ 1 ϑ ϑ ˉ ϑ ˉ 1 ϑ 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 1 ϑ ϑ ϑ ˉ 1 1 ϑ 0 0 0 0 0 0 0 0 1 1 ϑ 1 1 ϑ ϑ ˉ ϑ ˉ ] X_2,\ \mathbb{F}_4:\quad
\left[
\begin{array}{cccccccc|cccccccc}
1&1&0&0&0&0&0&0&0&0&1&\bar{\vartheta}&\bar{\vartheta}&1&\vartheta&\vartheta\\
0&1&1&0&0&0&0&1&\bar{\vartheta}&0&0&\vartheta&\vartheta&\bar{\vartheta}&1&0\\
0&0&0&1&0&1&1&0&\bar{\vartheta}&\bar{\vartheta}&1&\vartheta&\bar{\vartheta}&\bar{\vartheta}&1&\vartheta\\
0&0&0&1&1&0&0&0&0&0&0&1&1&0&0&0\\
0&0&0&0&1&1&0&1&1&1&\vartheta&\vartheta&\bar{\vartheta}&1&1&\vartheta\\
0&0&0&0&0&0&0&0&1&1&\vartheta&1&1&\vartheta&\bar{\vartheta}&\bar{\vartheta}
\end{array}
\right] X 2 , F 4 : 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 ϑ ˉ ϑ ˉ 0 1 1 0 0 ϑ ˉ 0 1 1 1 0 1 0 ϑ ϑ ϑ ˉ ϑ ϑ 1 ϑ 1 ϑ ˉ ϑ ϑ ˉ 1 ϑ ˉ 1 1 ϑ ˉ ϑ ˉ 0 1 ϑ ϑ 1 1 0 1 ϑ ˉ ϑ 0 ϑ 0 ϑ ϑ ˉ
X 2 , F 8 : [ 1 1 0 0 0 0 0 0 4 4 1 5 5 1 4 4 0 1 1 0 0 0 0 1 6 7 5 1 1 2 3 2 0 0 0 1 0 1 1 0 5 5 1 2 3 4 6 4 0 0 0 1 1 0 0 0 6 6 7 7 7 7 1 1 0 0 0 0 1 1 0 1 7 7 5 0 1 2 1 3 0 0 0 0 0 0 0 0 1 1 2 1 1 2 3 3 ] X_{2},\,F_{8}:\quad
\begin{bmatrix}
1&1&0&0&0&0&0&0&4&4&1&5&5&1&4&4\\
0&1&1&0&0&0&0&1&6&7&5&1&1&2&3&2\\
0&0&0&1&0&1&1&0&5&5&1&2&3&4&6&4\\
0&0&0&1&1&0&0&0&6&6&7&7&7&7&1&1\\
0&0&0&0&1&1&0&1&7&7&5&0&1&2&1&3\\
0&0&0&0&0&0&0&0&1&1&2&1&1&2&3&3
\end{bmatrix} X 2 , F 8 : 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 4 6 5 6 7 1 4 7 5 6 7 1 1 5 1 7 5 2 5 1 2 7 0 1 5 1 3 7 1 1 1 2 4 7 2 2 4 3 6 1 1 3 4 2 4 1 3 3
X 3 , F 4 : [ 1 1 0 0 0 1 0 0 1 ϑ 1 0 0 0 1 1 1 0 0 0 ϑ ϑ ˉ 1 ϑ 0 0 1 1 0 1 0 0 1 ϑ 0 ϑ ˉ 0 0 0 0 0 0 1 ϑ 1 ϑ ϑ ˉ ϑ ˉ ] X_{3},\,F_{4}:\quad
\begin{bmatrix}
1&1&0&0&0&1&0&0&1&\vartheta&1&0\\
0&0&1&1&1&0&0&0&\vartheta&\bar{\vartheta}&1&\vartheta\\
0&0&1&1&0&1&0&0&1&\vartheta&0&\bar{\vartheta}\\
0&0&0&0&0&0&1&\vartheta&1&\vartheta&\bar{\vartheta}&\bar{\vartheta}
\end{bmatrix} X 3 , F 4 : 1 0 0 0 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 ϑ 1 ϑ 1 1 ϑ ϑ ˉ ϑ ϑ 1 1 0 ϑ ˉ 0 ϑ ϑ ˉ ϑ ˉ
X 5 , F 4 : [ 1 1 0 0 0 0 0 0 0 0 0 ϑ ϑ ϑ ϑ ϑ ϑ ϑ 0 1 1 1 0 1 0 0 0 1 ϑ ˉ ϑ ˉ ϑ ϑ ϑ ˉ ϑ ˉ 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 ϑ ϑ ϑ ϑ ˉ 1 ϑ ˉ 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 ϑ ϑ 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 ϑ ϑ 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 ] X_{5},\,F_{4}:\quad
\begin{bmatrix}
1&1&0&0&0&0&0&0&0&0&0&\vartheta&\vartheta&\vartheta&\vartheta&\vartheta&\vartheta&\vartheta\\
0&1&1&1&0&1&0&0&0&1&\bar{\vartheta}&\bar{\vartheta}&\vartheta&\vartheta&\bar{\vartheta}&\bar{\vartheta}&0&0\\
0&0&0&1&1&0&0&0&0&0&0&0&1&1&0&0&0&0\\
0&0&0&0&1&1&1&0&1&0&0&0&\vartheta&\vartheta&\vartheta&\bar{\vartheta}&1&\bar{\vartheta}\\
0&0&0&0&0&0&1&1&0&0&0&0&0&0&0&\vartheta&\vartheta&0\\
0&0&0&0&0&0&0&1&1&0&0&0&0&0&0&0&\vartheta&\vartheta\\
0&0&0&0&0&0&0&0&0&1&1&1&1&1&1&1&1&1
\end{bmatrix} X 5 , F 4 : 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 ϑ ˉ 0 0 0 0 1 ϑ ϑ ˉ 0 0 0 0 1 ϑ ϑ 1 ϑ 0 0 1 ϑ ϑ 1 ϑ 0 0 1 ϑ ϑ ˉ 0 ϑ 0 0 1 ϑ ϑ ˉ 0 ϑ ˉ ϑ 0 1 ϑ 0 0 1 ϑ ϑ 1 ϑ 0 0 ϑ ˉ 0 ϑ 1
Envelopes of Duchamp’s matroid. Rank-4 matroids on the 8-element set J J J are encoded by ( 8 4 ) = 70 \binom{8}{4}=70 ( 4 8 ) = 70 Boolean variables, one for each 4-subset, with unit clauses fixing the 16 admissible 4-sets according to B \mathcal{B} B and clauses expressing the basis exchange axiom. All solutions were enumerated with the SAT solver Glucose by adding a blocking clause after each solution, and each solution was checked independently. There are 12 solutions, six with 49 and six with 53 bases, and none is sheltering. Adding the clauses that make every admissible set not contained in a member of B \mathcal{B} B dependent gives an unsatisfiable instance. A sheltering matroid of rank larger than 4 would truncate to a sheltering envelope of rank 4, so S \mathcal{S} S has no sheltering matroid of any rank. The polynomials T S , M T_{\mathcal{S},M} T S , M of the twelve envelopes were computed from their bases; they take the two values listed in Example 8.15 (3).
Further checks. The computer programs are also tested, on random and on structured instances, the general statements of the paper: Lemmas 2.4 , 2.8 , 2.16 (with loops) and 3.1; the constructions of Theorem 5.1 (with loops), Proposition 6.1 and Corollaries 7.1 and 7.3 ; the flow facts used in Corollary 4.2 ; the cores in Example 6.8 and the matrix of its item (1), on all 448 admissible 6-sets; the forest of Proposition 6.9 on random prism subdivisions, the flows of Lemma 6.10 , the list of Remark 6.3 against all 3-connected simple graphs with at most seven vertices, and Corollary 6.12 ; Theorem 8.4 , Corollaries 8.6 and 8.7 , and Proposition 8.9 and Theorem 8.10 on random graphs with marked vertices. An exhaustive search also confirms that the prism is not F 4 \mathbb{F}_4 F 4 -representable, as Corollary 6.7 predicts. These checks are not used in the proofs.