Linear codes over signed graphs (Q2291662)

A signed graph is a pair \((G,\sigma)\) where \(G\) is a graph (not necessarily simple) and \(\sigma\) is a map of the edge set, \(E(G)\), into \(\{+,-\}\). Letting \(V(G)=\{t_1,\dots,t_s\}\) be the vertex set of \(G\) and \(K\) a field, the incidence matrix of \((G,\sigma)\) is the matrix with columns, indexed by an ordering of the edge set of \(G\), equal to \[\mathbf{e}_i-\sigma(\ell)\mathbf{e}_j,\] where \(\mathbf{e}_i\), for \(i=1,\dots,s\), are the elements of the canonical basis of \(K^s\), for every edge \(\ell\) incident to \(t_i\) and \(t_j\) (choosing an ordering of \(\{t_i,t_j\}\)), and where \(i=j\) if and only if \(\ell\) is a loop. The usual incidence matrix of graph and of a dygraph can be seen as particular cases of this. This article is devoted to the study of linear codes which have generator matrix the incidence matrix of \((G,\sigma)\), as well as the study of some aspects of some combinatorial structures that may be associated to \((G,\sigma)\). The focus on linear codes is in the computation of the sequence of generalized Hamming weights in terms of \((G,\sigma)\). Two ideas come into play. First, Theorem 2 in [\textit{V. K. Wei}, IEEE Trans. Inf. Theory 37, No. 5, 1412--1418 (1991; Zbl 0735.94008)], which enables the computation of the generalized Hamming weights of a linear code using (the dual of) the matroid of the generator matrix of the code. Secondly, Theorems 8B.1 and 8B.2 in [\textit{T. Zaslavsky}, Discrete Appl. Math. 4, 47--74 (1982; Zbl 0476.05080)] stating that for a field of characteristic \(2\) the incidence matrix of a signed graph is a matrix representation for the graphic matroid of the underlying graph and for fields of characteristic different from \(2\), it is a matrix representation for the signed-graphic matroid. (The signed-graphic matroid is the matroid on \(E(G)\) with circuits the sets of edges forming balanced cycles or bow-ties, where a balanced cycle is a cycle with an even number of negative edges and a bow-tie is either the edge disjoint union of two cycles, each with an odd number of negatives edges, having a single common vertex or two such cycles, vertex disjoint, connected by path meeting them exactly at its end-points.) Exploring this connection, the main results of Section 3 of this article (Theorem 3.16 and Theorem 3.19) equate the generalized Hamming weights of the incidence matrix code of \((G,\sigma)\), and of its dual, with (numerical) invariants of \((G,\sigma)\). Section 4 contains the computation of the Castelnuovo-Mumford regularity of the Stanley-Reisner rings of the independence complex of the matroid of the incidence matrix of \((G,\sigma)\) and of its dual in terms of graphs invariants (Theorem 4.7). In Section 5, the authors give an algebraic formula (based on the multiplicity invariant) for the frustration index, i.e., the minimum number of edges the removal of which turns \((G,\sigma)\) into a balanced graph. Finally, Section 6 contains several examples illustrating the results obtained. The article has also an appendix containing procedures, in \texttt{Macaulay2} code, for the computation of the featured ideals and invariants.