• PDF / 1,227,353 Bytes
• 34 Pages / 439.37 x 666.142 pts Page_size
• 86 Downloads / 368 Views

DOWNLOAD

REPORT

---

On toric ideals arising from signed graphs JiSun Huh1 · Sangwook Kim2 · Boram Park1 Received: 21 August 2019 / Accepted: 18 June 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020

Abstract A signed graph is a pair (G, τ ) of a graph G and its sign τ , where a sign τ is a function from {(e, v) | e ∈ E(G), v ∈ V (G), v ∈ e} to {1, −1}. Note that graphs or digraphs are special cases of signed graphs. In this paper, we study the toric ideal I(G,τ ) associated with a signed graph (G, τ ), and the results of the paper give a unified idea to explain some known results on the toric ideals of a graph or a digraph. We characterize all primitive binomials of I(G,τ ) and then focus on the complete intersection property. More precisely, we find a complete list of graphs G such that I(G,τ ) is a complete intersection for every sign τ . Keywords Signed graph · Toric ideal · Primitive element · Complete intersection Mathematics Subject Classification 14M25 · 05C22 · 05C25

1 Introduction Throughout the paper, a graph means a finite simple graph. A finite graph allowed to have a multiple edge or a loop is called a multigraph. For a graph G, we set V (G) = {v1 , . . . , vn }, E(G) = {e1 , . . . , em } and e = (e1 , . . . , em ) unless otherwise specified. For a positive integer n, we denote {1, . . . , n} by [n]. For an integer vector b, b+ (resp. b− ) means the vector whose ith entry is max{bi , 0} (resp. − min{bi , 0}). xm 1 . For an integer vector x = (x1 , . . . , xm ), ex means a monomial e1x1 e2x2 · · · em

1 Throughout the paper, to denote a vector, we use a, b, c, etc. The standard bold type letters (a, b, c, etc.)

are for walks in a graph.

B

Boram Park [email protected]

1

Department of Mathematics, Ajou University, Suwon 16499, Republic of Korea

2

Department of Mathematics, Chonnam National University, Gwangju 61186, Republic of Korea

123

Journal of Algebraic Combinatorics

Let K [e1 , . . . , em ] be a polynomial ring in m variables over a field K . For an n × m integer matrix A without zero columns, the ideal  +  − I A = eb − eb ∈ K [e1 , . . . , em ] | b ∈ Zm and Ab = 0 is called the toric ideal associated with A. It is well known that a toric ideal is a prime binomial ideal. For more details about toric ideals and related topics, see [11,25]. A (homogeneous) toric ideal not only defines a projective toric variety (see [6, 24]), but also provides wide applications in other areas, such as algebraic statistics, dynamical system, hypergeometric differential equations, toric geometry, and graph theory, see [5,14,25]. Toric ideals arising from various kinds of combinatorial objects have been widely studied by many researchers, see [12,13,19,20] for some recent results. Particularly, the toric ideal of a graph or a digraph, which is the toric ideal associated with its vertex-edge incidence matrix, has been an interesting topic (see [2–4,7,8,17,18,21,22]). A major line of research on toric ideal arising from a combinatorial object focuses on a ‘special’ set of binomials of the ideal (givin