betaFeedback

WorksMathematics

Representability of Graphical Symplectic Matroids

Abstract

Chow associated with every finite multigraph GG a symplectic matroid \GraphS{G} on the signed edge set E⊔E∗E\sqcup E^{*}, whose restrictions to transversals are frame matroids of signed graphs, and Sarvepalli asked which of these matroids are representable. For a connected graph containing a cycle, we show that every isotropic representation of S(G)S(G) admits an incidence-flow normal form. The remaining representation conditions are expressed through its admissible minors. Consequently, if \GraphS{G} is \F-representable, then the bridgeless part of GG has a nowhere-zero (\F,+)-flow. In characteristic other than two, \GraphS{G} is representable if and only if every non-loop edge on a cycle has a parallel mate. In characteristic two, we characterize the loopless graphs without two vertex-disjoint cycles by the existence of a nowhere-zero (\F,+)-flow, and we show that rigidly linked short cycles, and hence subdivisions of the prism, are obstructions. For 33-connected simple graphs this gives a complete answer: \GraphS{G} is \F-representable if and only if \F has characteristic two, GG has no two vertex-disjoint cycles, and either |\F|>2 or G≅K5G\cong K_5. In particular, the matroid of the Petersen graph is representable over no field. Finally, the admissible corank–nullity polynomial of an arbitrary symplectic matroid is intrinsic and satisfies a three-term contraction identity. For graphical symplectic matroids, this becomes a deletion-contraction recursion that closes up once marked vertices are allowed, and polynomials built from enveloping matroids agree with it exactly for sheltering envelopes.

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 CnC_n [1]. We define symplectic matroids on the ground set J=[n]⊔[n]∗J=[n]\sqcup[n]^* with the involution i↔i∗i\leftrightarrow i^*, and their bases are admissible kk-subsets of JJ, that is, kk-subsets containing at most one element of each pair {i,i∗}\{i,i^*\}. A kk-dimensional subspace W≤Fq2nW\leq\mathbb{F}_q^{2n} that is totally isotropic for the standard alternating form, given as the row space of a matrix H=[X∣Z]H=[X\mid Z] with XZT=ZXTXZ^{\mathsf{T}}=ZX^{\mathsf{T}}, determines a represented symplectic matroid: its bases are the admissible kk-sets BB with det⁡H[B]≠0\det H[B]\ne0. Lagrangian matroids are the rank nn symplectic matroids, which are equivalent to Bouchet’s delta-matroids. Let Fq\mathbb{F}_q be a finite field. Under the standard symplectic representation, the images of stabilizer groups in Fq2n\mathbb{F}_q^{2n} are precisely the totally isotropic subspaces; together with a compatible choice of phases, such a subspace determines the corresponding Fq\mathbb{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) with E={e1,…,en}E=\{e_1,\ldots,e_n\}, the pair {i,i∗}\{i,i^*\} is identified with the edge eie_i, and i∗i^* is thought of as a starred copy of eie_i. An admissible set SS is independent in S(G)\mathcal{S}(G) if every component of the spanning subgraph formed by the edges met by SS is either a tree or unicyclic with an odd number of starred edges on its cycle. For every transversal TT, the restriction S(G)∣T\mathcal{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) over Fq\mathbb{F}_q is a stabilizer matrix of an [[∣E∣,∣E∣−r]]q[[|E|,|E|-r]]_q quantum code, where r=r(S(G))r=r(\mathcal{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) is a single isotropic subspace that must realize, all at once, the frame matroids of the 2∣E∣2^{|E|} signed graphs obtained by starring edges of GG. Isotropy is a quadratic condition; in characteristic 22, 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.

  1. A normal form. Restricted to the unstarred elements, a representation of S(G)S(G) represents the cycle matroid 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 DD of GG (Theorem 3.8). Isotropy gives two linear conditions: zz is an F\mathbb{F}-flow and DZ1TDZ_{1}^{\mathsf{T}} is symmetric. The bases further force ze≠0z_{e} \ne0 on every cyclic edge; on bridges, the flow condition gives ze=0z_{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.

  1. Flows. The last row of the normal form is a nowhere-zero (F,+)(\mathbb{F},+)-flow on the graph G∘G^{\circ} obtained by deleting loops and bridges (Theorem 4.1). For a finite field Fq\mathbb{F}_{q}, the existence of such a flow is equivalent to the existence of a nowhere-zero integer qq-flow. So flow theory immediately excludes small fields: S(K4)S(K_{4}) is not F2\mathbb{F}_{2}-representable, and the matroid of the Petersen graph is representable neither over F2\mathbb{F}_{2} nor over F4\mathbb{F}_{4} (Corollary 4.2). Theorem 5.1 also excludes S(K4)S(K_{4}), S(K3,3)S(K_{3,3}) and S(P10)S(P_{10}) in characteristic ≠2\ne2 see Remark 4.3.

  1. Characteristic ≠2\ne2. We derive a complete answer. The symplectic matroid S(G)S(G) is representable over a field of characteristic ≠2\ne2 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).

  1. Characteristic 2 without two disjoint cycles. Here the flow obstruction is the only one: if GG is loopless and has no two vertex-disjoint cycles, then S(G)\mathcal{S}(G) is F\mathbb{F}-representable if and only if G∘G^{\circ} has a nowhere-zero (F,+)(\mathbb{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] 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; over F4\mathbb{F}_4 it asks for a nowhere-zero 4-flow, and over F2\mathbb{F}_2 for G∘G^{\circ} to be Eulerian.

  1. Characteristic 2: obstructions. Short cycles carry almost no freedom: on a cycle of length 2 or 3 the vectors wew_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) 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 KnK_n for n≥6n \ge6 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.

  1. 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 GG, S(G)\mathcal{S}(G) is F\mathbb{F}-representable if and only if char⁡F=2\operatorname{char}\mathbb{F}=2, GG has no two vertex-disjoint cycles, and either ∣F∣>2|\mathbb{F}|>2 or G≅K5G\cong K_5. In

particular, the matroid of the Petersen graph is representable over no field (Corollary 6.12).

  1. Small graphs and Chow’s remark. For a connected unicyclic graph with cycle CC, the matrix (DD01C)\begin{pmatrix} D & D \\ 0 & 1_C \end{pmatrix} represents S(G)S(G) over every field of characteristic 22, and characteristic 22 is necessary when GG 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 22 with more than two elements (Corollary 7.3). So Chow’s remark is correct over F2\mathbb{F}_2 and in characteristic ≠2\ne2, but not over F4\mathbb{F}_4 (Remark 7.4).

  1. Rank enumerators. The admissible corank–nullity polynomial TST_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 TST_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 UU-polynomial, with TS(u,v)=US(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 TS(G)=uδeTS(G\e)+2TS(G/e)T_S(G)=u^{\delta_e}T_S(G\backslash e)+2T_S(G/e) for every edge ee 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 TST_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 has been discussed in § 5, and in § 6 we discuss the results in characteristic 22, 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} is a field, F×=F∖{0}\mathbb{F}^{\times}=\mathbb{F}\setminus\{0\}, and Fq\mathbb{F}_{q} is the field with qq elements. For a vector yy, supp⁡(y)\operatorname{supp}(y) is the set of coordinates at which yy is nonzero; for a column vector yy and a scalar cc, (y;c)(y;c) is the column vector obtained from yy by appending the entry cc. 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≥0n\ge0, [n]={1,…,n}[n]=\{1,\ldots,n\}, [n]∗={1∗,…,n∗}[n]^{*}=\{1^{*},\ldots,n^{*}\} and J=[n]⊔[n]∗J=[n]\sqcup[n]^{*}, with the fixed-point-free involution a↦a∗a\mapsto a^{*} given by i↦i∗i\mapsto i^{*} and i∗↦ii^{*}\mapsto i. For A⊆JA\subseteq J put A∗={a∗:a∈A}A^{*}=\{a^{*}:a\in A\}; for a∈Ja\in J put Ja={a,a∗}J_{a}=\{a,a^{*}\}, and for Y⊆[n]Y\subseteq[n] put JY=Y⊔Y∗J_{Y}=Y\sqcup Y^{*}. A set A⊆JA\subseteq J is admissible if A∩A∗=∅A\cap A^{*}=\varnothing, and a transversal if moreover ∣A∣=n|A|=n. We write A(J)\mathcal{A}(J) for the family of admissible sets and Ak(J)\mathcal{A}_{k}(J) for its members of size kk; for a ∗*-closed subset J′⊆JJ'\subseteq J, A(J′)\mathcal{A}(J') and Ak(J′)\mathcal{A}_{k}(J') are defined in the same way.

Definition 2.2 (Symplectic matroids [1 Ch. 3]). A linear order ≺\prec on JJ is admissible if a≺ba\prec b implies b∗≺a∗b^{*}\prec a^{*}. It induces the Gale order on kk-subsets of JJ: if A={a1≻⋯≻ak}A=\{a_{1}\succ\cdots\succ a_{k}\} and B={b1≻⋯≻bk}B=\{b_{1}\succ\cdots\succ b_{k}\}, then A≤BA\le B if aj⪯bja_{j}\preceq b_{j} for j=1,…,kj=1,\ldots,k. A symplectic matroid of rank kk on JJ is a pair S=(J,B)S=(J,\mathcal{B}) with ∅≠B⊆Ak(J)\varnothing\ne\mathcal{B}\subseteq\mathcal{A}_{k}(J) such that, for every admissible order ≺\prec, some B≺∈BB_{\prec}\in\mathcal{B} satisfies B≤B≺B\le B_{\prec} for all B∈BB\in\mathcal{B}. The members of B=B(S)\mathcal{B}=\mathcal{B}(S) are the bases, the subsets of bases are the independent sets, forming the family I(S)\mathcal{I}(S), and r(S)=kr(S)=k is the rank. An element a∈Ja\in J is a loop of SS if it lies in no basis. SS is Lagrangian if k=nk=n. The uniform symplectic matroid Uk,n∗U^{*}_{k,n} has B=Ak(J)\mathcal{B}=\mathcal{A}_{k}(J).

The bases of a symplectic matroid are the maximal independent sets, so SS is determined by I(S)\mathcal{I}(S). Chow characterized the families I(S)\mathcal{I}(S).

References

  1. [1]A. V. Borovik, I. M. Gelfand, N. White, Coxeter Matroids, Vol. 216 of Progress in Mathematics, Birkhäuser, Boston, 2003.
  2. [2]P. Sarvepalli, Quantum codes and symplectic matroids, arXiv:1104.1171 [quant-ph] (2011).arxiv.org/abs/1104.1171
  3. [3]T. Y. Chow, Symplectic matroids, independent sets, and signed graphs, Discrete Math. 263 (2003) 35–45.DOI
  4. [4]T. H. Brylawski, D. Lucas, Uniquely representable combinatorial geometries, in: Theorie Combinatorie (Proc. 1973 Internat. Colloq.), Accademia Nazionale dei Lincei, Rome, 1976, pp. 83–104.
  5. [5]F. Jaeger, Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B 26 (1979) 205–216.DOI
  6. [6]C. Eur, A. Fink, M. Larson, H. Spink, Signed permutohedra, delta-matroids, and beyond, Proc. Lond. Math. Soc. (3) 128 (2024) e12592, arXiv:2209.06752.arxiv.org/abs/2209.06752
  7. [7]M. Larson, Rank functions and invariants of delta-matroids, Electron. J. Combin. 32 (2) (2025) Paper No. P2.4.arxiv.org/abs/2305.01008
  8. [8]J. Oxley, Matroid Theory, 2nd Edition, Oxford University Press, Oxford, 2011.
  9. [9]A. Bouchet, Multimatroids I. Coverings by independent sets, SIAM J. Discrete Math. 10 (1997) 626–646.DOI
  10. [10]T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982) 47–74.
  11. [11]T. Zaslavsky, Biased graphs. II. The three matroids, J. Combin. Theory Ser. B 51 (1991) 46–72.DOI
  12. [12]W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954) 80–91.DOI
  13. [13]C.-Q. Zhang, Integer Flows and Cycle Covers of Graphs, Marcel Dekker, New York, 1997.
  14. [14]A. Bouchet, Representability of Δ-matroids, in: Combinatorics (Eger, 1987), Vol. 52 of Colloq. Math. Soc. János Bolyai, North-Holland, Amsterdam, 1988, pp. 167–182.
  15. [15]L. Lovász, On graphs not containing independent circuits, Mat. Lapok 16 (1965) 289–299. (in Hungarian).
  16. [17]R. Diestel, Graph Theory, 5th Edition, Vol. 173 of Graduate Texts in Mathematics, Springer, Berlin, 2017.
  17. [18]A. Bouchet, Graph polynomials derived from Tutte–Martin polynomials, Discrete Math. 302 (2005) 32–38.DOI
  18. [19]R. Arratia, B. Bollobás, G. B. Sorkin, The interlace polynomial of a graph, J. Combin. Theory Ser. B 92 (2004) 199–233.DOI
  19. [20]M. Aigner, H. van der Holst, Interlace polynomials, Linear Algebra Appl. 377 (2004) 11–30.DOI
  20. [21]O. Raz, The geometry of ranked symplectic matroids, arXiv:2411.09396 (2024).arxiv.org/abs/2411.09396
  21. [22]I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 718–720.DOI

Paper details

vlnc:W_kcatpbgf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents