Combinatorics of Castelnuovo-Mumford Regularity of Binomial Edge Ideals

Abstract

Since the introduction of binomial edge ideals by Herzog et al. and independently Ohtani, there has been significant interest in relating algebraic invariants of the binomial edge ideal with combinatorial invariants of the underlying graph. Here, we take up a question considered by Herzog and Rinaldo regarding Castelnuovo-Mumford regularity of block graphs. To this end, we introduce a new invariant $\nu(G)$ associated to any simple graph $G$, defined as the maximal total length of a certain collection of induced paths within $G$ subject to conditions on the induced subgraph. We prove that for any graph $G$, $\nu(G) \leq \mathrm{reg}(J_{G})-1$, and that the length of a longest induced path of $G$ is less than or equal to $\nu(G)$; this refines an inequality of Matsuda and Murai. We then investigate the question: when is $\nu(G) = \mathrm{reg}(J_{G})-1$? We prove that equality holds for closed graphs, and for bipartite graphs $G$ such that $J_{G}$ is Cohen-Macaulay. For block graphs, we prove that $\nu(G)$ admits a combinatorial characterization independent of any auxiliary choices, and we prove that $\nu(G) = \mathrm{reg}(J_{G})-1$. This gives $\mathrm{reg}(J_{G})$ a combinatorial interpretation for block graphs, and thus answers the question of Herzog and Rinaldo.