Invariants of Binomial Edge Ideals via Linear Programs

Adam LaClair Adam LaClair
Department of Mathematics
Purdue University
West Lafayette
IN 47907
USA [email protected]

Abstract.

We associate to every graph a linear program for packings of vertex disjoint paths. We show that the optimal primal and dual values of the corresponding integer program are the binomial grade and height of the binomial edge ideal of the graph. We deduce from this a new combinatorial characterization of graphs of König type and use it to show that all trees are of König type.

The log canonical threshold and the F-threshold are important invariants associated to the singularities of a variety in characteristic $0$ and characteristic $p$ . We show that the optimal value of the linear program (computed over the rationals) agrees with both the F-threshold and the log canonical threshold of the binomial edge ideal if the graph is a block graph or of König type. We conjecture that this linear program computes the log canonical threshold of the binomial edge ideal of any graph.

Our results resemble theorems on monomial ideals arising from hypergraphs due to Howald and others.

The author was partially supported by NSF grant DMS-2100288 and by Simons Foundation Collaboration Grant for Mathematicians #580839

1. Introduction

The theory of matchings of a graph has a long and rich history within graph theory with important applications in industry and also to other branches of mathematics. There are classical theorems relating the combinatorics of hypergraphs, the linear program realizing a maximal matching in a hypergraph, and algebraic invariants of the edge ideal associated to a hypergraph. For a hypergraph $\mathcal{H}$ let $\operatorname{MM}_{\mathcal{H},\mathbb{Z}}$ (respectively $\operatorname{MM}_{\mathcal{H},\mathbb{Q}}$ ) denote the optimal value of the linear program associated to $\mathcal{H}$ realizing a maximal matching of $\mathcal{H}$ over $\mathbb{Z}$ (respectively $\mathbb{Q}$ ), and $\operatorname{MM}_{\mathcal{H},\mathbb{Z}}^{\ast}$ denote the optimal value of the dual linear program over $\mathbb{Z}$ . For background on hypergraphs and the edge ideal of a hypergraph see [MV12]. For background on (fractional) maximal matchings of a hypergraph or the associated linear program $\operatorname{MM}_{\mathcal{H},-}$ see [LP86].

Theorem A (classical).

Let $\mathcal{H}$ be a hypergraph, $I(\mathcal{H})$ the associated edge ideal, and $\operatorname{MM}$ as above.

(1)

The monomial grade of $I(\mathcal{H})$ is equal to $\operatorname{MM}_{\mathcal{H},\mathbb{Z}}$ , and also to the size of a maximal matching of $\mathcal{H}$ . (folklore)
(2)
The following quanitites are equal:
- •
  
  For any prime $p$ the F-threshold of $I(\mathcal{H})$ ,
- •
  
  The log canonical threshold of $I(\mathcal{H})$ ,
- •
  
  $\operatorname{MM}_{\mathcal{H},\mathbb{Q}}$ ,
- •
  
  The size of a maximal fractional matching of $\mathcal{H}$ .
This was proven by [How01], but see also [Her16], [Pag18].
(3)

The height of $I(\mathcal{H})$ is equal to $\operatorname{MM}^{\ast}_{\mathcal{H},\mathbb{Z}}$ , and also to the size of a minimal vertex cover of $\mathcal{H}$ (see for instance [HH11, Lemma 9.1.4] and [LP86]).

Theorem A can be formulated for an arbitrary monomial ideal if one is willing to sacrifice combinatorial notions (see [How01], [Her16], [Pag18], [HH11, Lemma 9.1.4]).

Another classical theorem in matching theory is König’s theorem.

Theorem B (König).

Let $G$ be a bipartite graph, then the size of a maximal matching is equal to the size of a minimal vertex cover.

Finally, we recall results on the coordinates of the vertices of the fractional matching polytope.

Theorem C.

For a graph $G$ each coordinate of a vertex of the fractional matching polytope is either $0$ , $1$ , or $\frac{1}{2}$ . (Balinski, see [LP86, Theorem 7.5.1]. If $G$ is a bipartite graph, then each coordinate of the vertex of the fractional matching polytope is either $0$ or $1$ . (see [LP86, Theorem 7.1.2].

In this paper we introduce a new linear program associated to a graph. We prove analogues of the above statements relating the linear program, the combinatorics of the graph, and algebraic properties of the binomial edge ideal.

The class of binomial edge ideals was introduced in [HHH⁺10] and independently in [Oht11]. They are defined as

Definition 1.1 ([HHH⁺10]).

Let $G=(V,E)$ be a finite simple graph with vertex set $V=\{1,\ldots,n\}$ and edge set $E$ . Fix a field $\mathbb{K}$ . Consider the polynomial ring $R:=\mathbb{K}[X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{n}]$ , and for each edge $\{i,j\}\in E$ with $i<j$ define $f_{ij}:=X_{i}Y_{j}-X_{j}Y_{i}\in R$ . Define the binomial edge ideal of $G$ , denoted $J_{G}$ , to be the ideal

(1)

J_{G}:=(\{f_{ij}\mid\{i,j\}\in E\}).

Numerous papers have studied algebraic invariants of a binomial edge ideal in terms of combinatorial properties of the underlying graph; see [SM18] for a survey.

In [TW04], the authors introduced the notion of F-pure threshold which is a characteristic $p$ -invariant having properties analogous to log canonical thresholds. In our situation the F-pure threshold is equivalent to the F-threshold introduced in [MTW05]. Throughout this paper $p$ will always denote a positive prime integer. When $S=\mathbb{Z}[X_{1},\ldots,X_{n}]$ and $I$ is an $S$ -ideal, we denote by $I_{\mathbb{C}}$ , respectively $I_{p}$ , the image of $I$ in $S\otimes_{\mathbb{Z}}\mathbb{C}$ , respectively $S\otimes_{\mathbb{Z}}\mathbb{Z}/p\mathbb{Z}$ . We denote by $\operatorname{lct}(I)$ the log canonical threshold of $I_{\mathbb{C}}$ around the origin which is an important invariant appearing in birational geometry (see [Laz04]) and by $\operatorname{ft}(I_{p})$ the F-threshold of $I_{p}$ . Throughout this paper we will often write $\operatorname{ft}(J_{G})$ instead of $\operatorname{ft}(J_{G,p})$ since our computations will be independent of characteristic. It is known that:

Theorem 1.2 ([MTW05, Theorem 3.4]).

In the above setup,

(2)

\operatorname{ft}(I_{p})\leq\operatorname{lct}(I)

for all $p\gg 0$ and

(3)

\operatorname{lct}(I)=\lim_{p\rightarrow\infty}\operatorname{ft}(I_{p}).

In practice it is difficult to give explicit formulas for the log canonical threshold or F-threshold of an ideal, apart from special cases. Relevant for us are the following computations. The F-threshold and log canonical threshold of monomial ideals can be computed via a linear program (see [How01], [Her16], [Pag18]). Shibuta and Takagi [ST09] used this linear program to compute the log canonical threshold of certain classes of binomial ideals as the optimal value of a linear programming problem over $\mathbb{Q}$ . Hernández [Her14] expands on their ideas to show how the optimal value of this linear program over $\mathbb{Q}$ can be used to compute the F-threshold of a binomial hypersurface. In [MSV14], the authors compute the F-threshold of determinantal ideals. This computation was later generalized by Henriques and Varbaro [HV16] where they compute the multiplier and test ideals of GL-equivariant ideals, and as a consequence they obtain a formula for the F-threshold of GL-equivariant ideals. In [BE18], the authors give an algorithm to compute the log canonical threshold of any binomial ideal. Velez [Vel19] computes the F-threshold of the ideal of adjacent maximal minors which in the case of a $2\times n$ matrix corresponds to the binomial edge ideal of a path. González-Martínez computes the F-threshold of the graded maximal ideal in the quotient ring $R/J_{G}$ for any graph $G$ and uses this computation to characterize which binomial edge ideals are Gorenstein [GM21]. The main goal of this paper is to investigate the computation of the log canonical threshold and F-threshold of a binomial edge ideal in terms of combinatorial properties of the underlying graph. To this end we introduce the following linear programming problem which is a modification of the linear programming problem considered by Shibuta and Takagi (see [ST09]) and Hernández (see [Her14]).

For $U\subseteq V(G)$ , define $G[U]$ to be the induced graph on $U$ . Let $\mathcal{A}:=\{U\subseteq V(G)\mid\lvert U\rvert\geq 2\}$ . Consider the following linear program associated to the graph $G$ .

(4)	$\displaystyle\operatorname*{maximize}\,Z_{\operatorname{PP},G}$	$\displaystyle:=\phantom{a}\sum_{e\in E(G)}X_{\operatorname{PP},e}$
	$\displaystyle\operatorname{subject\,to:}$
	$\displaystyle X_{\operatorname{PP},e}$	$\displaystyle\in\mathbbm{k}_{\geq 0}\text{ for all }e\in E(G)$
	$\displaystyle C_{\operatorname{PP},U}$	$\displaystyle\leq\lvert U\rvert-1\text{ for all }U\in\mathcal{A}$
	$\displaystyle C_{\operatorname{PP},v}$	$\displaystyle\leq 2\text{ for all }v\in V(G)$

where for each $U\in\mathcal{A}$ and $v\in V$ , $C_{\operatorname{PP},U}$ and $C_{\operatorname{PP},v}$ are the functions

	$\displaystyle C_{\operatorname{PP},U}$	$\displaystyle:=\phantom{}\sum_{e\in E(G[U])}X_{\operatorname{PP},e}$
	$\displaystyle C_{\operatorname{PP},v}$	$\displaystyle:=\sum_{\begin{subarray}{c}v\text{ is incident }\\ \text{with }e\end{subarray}}X_{\operatorname{PP},e}.$

Throughout this paper let $\mathbbm{k}$ denote a choice of ring $\mathbb{Z}$ , $\mathbb{Q}$ , or $\mathbb{R}$ . Use (4) on different choices of $\mathbbm{k}$ , and denote the optimal value of (4) with respect to a choice of $\mathbbm{k}$ by $\operatorname{PP}_{G,\mathbbm{k}}$ .

This paper studies $\operatorname{PP}_{G,\mathbbm{k}}$ as it relates to the combinatorial properties of $G$ and the algebraic properties of $J_{G}$ . In Section 2 we introduce the relevant background. In Section 3 we show

Theorem D.

With the notation as above,

(1)

$\operatorname{PP}_{G,\mathbb{Z}}$ equals the binomial grade of $J_{G}$ (which is equal to the maximal number of edges in a semi-path of $G$ ) (Proposition 3.1 and Remark 3.2),
(2)

The optimal value of the dual program over $\mathbb{Z}$ , $\operatorname{PP}^{\ast}_{G,\mathbb{Z}}$ , equals $\operatorname{ht}J_{G}$ (Proposition 3.4),
(3)

$\operatorname{ft}(J_{G,p})\leq\operatorname{PP}_{G,\mathbb{Q}}$ for any prime number $p$ (Proposition 3.12).

This establishes an analogue of Theorem A parts (1) and (3).

In Section 4 we prove the main result of this paper.

Theorem E (Theorem 4.14, Corollary 4.18).

Let $G$ be a block graph, then

\displaystyle\operatorname{ft}(J_{G,p})=\operatorname{lct}(J_{G})=\operatorname{PP}_{G,\mathbb{Q}}\in\mathbb{Z}[\tfrac{1}{2}]

for any prime number $p$ .

This result establishes a special case of an analogue of Theorem A part (2).

Motivated by Theorem E, Corollary 5.2, and computational experiments we formulate

Conjecture 1.3.

Let $G$ be a graph, then

(1)

$\operatorname{lct}(J_{G})=\operatorname{PP}_{G,\mathbb{Q}}$
(2)

$\operatorname{PP}_{G,\mathbb{Q}}\in\mathbb{Z}[\frac{1}{2}]$ .

We prove this conjecture when $G$ is a block graph or $G$ is of König type. This conjecture suggests that a partial analogue of Theorem A item (2) may hold.

In Section 5 we give a new characterization of graphs of König type, Lemma 5.3. This enables us to show that every tree is of König type, Theorem 5.9. This establishes an analogue of Theorem B. In Section 6 we investigate for a connected graph $G$ the relationship between the equality $\operatorname{PP}_{G,\mathbb{Q}}=\lvert V\rvert-1$ and $G$ being traceable.

In upcoming work [LaC], the author shows when the graph is a tree that the polytope determined by the constraints of Algorithm 4 (i.e. fractional path packing polytope) has integral vertices, i.e. each coordinate of such a vertex is either $0$ or $1$ . This result gives a partial analogue of Theorem C. The author also investigates the question whether for a general graph each coordinate of a vertex of the fractional path packing is either $0$ , $1$ , or $\frac{1}{2}$ [LaC].

Acknowledgments

The author found computations in Macaulay 2 [GS], Python [Pyt], Sage [S⁺22], and Online Linear Optimization Solver [Zwo] immensely helpful. The author would like to thank Alex Black, Jean-Philippe Labbe, and Vic Reiner for helpful conversations, Santiago Encinas for providing source code for the algorithm described in his paper [BE18], and Uli Walther for many helpful discussions and suggestions.

2. Background

2.1. Linear Programs

For further background on linear programs and for proofs not contained here see [Dan63]. A linear programming problem refers to the computation of the extremal value of a linear function over a convex polytope, i.e. any region defined by linear half-spaces. Any linear programming problem can be put into standard form which in this paper we take to be the following setup.

Let $A$ be an $n\times m$ matrix having entries in $\mathbbm{k}$ . Let $\mathbf{c}\in\mathbbm{k}^{m}$ and $\mathbf{b}\in\mathbbm{k}^{n}$ . Then, the linear programming problem in standard form refers to

(5)

\begin{split}\operatorname*{maximize}\limits_{\mathbf{x}\in\mathbbm{k}^{m}}\quad&\mathbf{c}^{T}\mathbf{x}\\ \operatorname{subject\,to:}\hskip 6.99997pt&\phantom{}\\ &A\mathbf{x}\leq\mathbf{b}\\ &\phantom{A}\mathbf{x}\geq 0\end{split}

A linear programming problem written in this form will be called primal, and it can be shown that every linear programming problem is equivalent to a primal linear programming problem.

Given a primal problem we can associate the following linear programming problem

(6)

\begin{split}\operatorname*{minimize}_{\mathbf{y}\in\mathbbm{k}^{n}}\quad&\mathbf{b}^{T}\mathbf{y}\\ \operatorname{subject\,to:}\hskip 5.0pt&\phantom{}\\ &A^{T}\mathbf{y}\geq\mathbf{c}\\ &\phantom{A^{T}}\mathbf{y}\geq 0\end{split}

which is called the dual linear programming problem of the primal.

Given a linear programming problem, a vector is called feasible if it satisfies the constraints of the problem. If such a vector exists the linear programming problem is called feasible. A linear programming problem is called bounded if the optimal value of the linear programming problem is finite. When a linear programming problem is bounded feasible we call the value attained by the linear program to be the optimal value, and we call a vector which realizes the optimal value and satisfies the constraints of the linear programming problem an optimal solution.

Theorem 2.1 ([Dan63, p.125 Duality Theorem] Strong duality of linear programs).

Given a primal (resp. dual) feasible, bounded linear programming problem, then the dual (resp. primal) programming problem is feasible, bounded and the optimal values of the primal (resp. dual) agrees with the optimal value of the dual (resp. primal) provided that $\mathbb{Q}\subseteq\mathbbm{k}\subseteq\mathbb{R}$ .

Remark 2.2.

When $\mathbbm{k}=\mathbb{Z}$ , then optimal value of a bounded feasible primal can be strictly smaller than the optimal value of the dual.

In the above setup of the Equation (5), let $A_{i}$ denote the $i$ -th column of $A$ and $a_{j}^{T}$ denote the $j$ -th row of $A$ .

Theorem 2.3 ( [Dan63, p.136 Theorem 4] Complementary Slackness).

Let $\mathbf{x}$ and $\mathbf{y}$ be primal (respectively dual) optimal solutions of (5) (respectively (6)) and suppose that $\mathbf{c}^{T}\mathbf{x}=\mathbf{b}^{T}\mathbf{y}$ , then

(1)

for $1\leq i\leq m$ , $(\mathbf{c}_{i}-\mathbf{y}^{T}A_{i})x_{i}=0$ .
(2)

for $1\leq j\leq n$ , $(a_{j}^{T}\mathbf{x}-\mathbf{b}_{j})y_{j}=0$ .

Sketch of Proof.

It is always true that

\displaystyle\mathbf{c}^{T}\mathbf{x}\leq\mathbf{y}^{T}A\mathbf{x}\leq\mathbf{y}^{T}\mathbf{b}.

Equality of the outer two terms implies equality throughout and complementary slackness follows by distributing terms appropriately.

2.2. Binomial Edge Ideals

Throughout this paper we will only consider finite simple graphs, i.e. graphs without multiple edges or loops and on a finite number of vertices. Given a graph $G$ we denote its set of vertices by $V(G)$ , or $V$ when the context is clear, and denote its set of edges by $E(G)$ , or $E$ when the context is clear. Throughout this paper we will assume that $V(G)=\{1,\ldots,n\}$ for some positive integer $n$ . Given a subset $U\subseteq V(G)$ , we denote by $G[U]$ the subgraph of $G$ induced on the vertices $U$ .

By a path in $G$ we mean an alternating sequence of distinct vertices and edges of $G$ , $v_{1},e_{1},v_{2},\ldots,e_{\ell-1},v_{\ell}$ so that $e_{i}=\{v_{i},v_{i+1}\}\in E(G)$ for $1\leq i\leq\ell-1$ . By a cycle in $G$ we mean an alternating sequence of distinct vertices and edges of $G$ , $v_{1},e_{1},v_{2},\ldots,e_{\ell-1},v_{\ell},e_{\ell}$ so that $e_{i}=\{v_{i},v_{i+1}\}\in E(G)$ for $1\leq i\leq\ell-1$ and $e_{\ell}=\{v_{1},v_{\ell}\}\in E(G)$ . By a semi-path we mean a subgraph $P$ of $G$ such that each connected component of $G$ is a path. Let $\hat{G}$ be the induced graph on $V(G)\smallsetminus\mathcal{I}(G)$ where $\mathcal{I}(G)$ denotes the isolated vertices of $G$ .

The following proposition gives a combinatorial description of the minimal primes of a binomial edge ideal and a formula for the height of prime ideals.

Proposition 2.4 ([HHH⁺10, Lemma 3.1, Corollary 3.9]).

Let $G$ be a graph on $n$ vertices. If $T\subseteq[n]:=\{1,\ldots,n\}$ , we will denote the induced subgraph on the vertices $G\smallsetminus T$ by $G_{T}$ . Let $c_{G}(T)$ denote the number of connected components of $G_{T}$ , and let $G_{1},\ldots,G_{c_{G}(T)}$ denote the distinct connected components of $G_{T}$ . Let $\tilde{G}_{i}$ denote the complete graph on the vertices $V(G_{i})$ . Put

\displaystyle P_{T}(G):=\big{(}\bigcup_{i\in T}\{X_{i},Y_{i}\},J_{\tilde{G}_{1}},\ldots,J_{\tilde{G}_{c_{G}(T)}}\big{)}

where $J_{\tilde{G}_{\ast}}$ is as defined in Definition 1.1. Then, $P_{T}(G)$ is a minimal prime ideal of $J_{G}$ and

\displaystyle\operatorname{ht}P_{T}(G)=2\lvert T\rvert+\sum_{i=1}^{c_{G}(T)}\left(\lvert V(G_{i})\rvert-1\right)=n-c_{G}(T)+\lvert T\rvert.

Moreover, every minimal prime ideal of $J_{G}$ is of the form $P_{T}(G)$ where $T=\varnothing$ , or $T\neq\varnothing$ and for each $i\in T$ one has that $c_{G}(T\smallsetminus i)<c_{G}(T)$ .

Definition 2.5.

For a graph $G$ define the invariant

\displaystyle r(G):=\sup\left\{\lvert E(P)\rvert\mathrel{}\middle|\mathrel{}P\subseteq G\text{ is a semi-path}\right\}.

We call a disjoint union of paths realizing $r(G)$ a path packing of $G$ .

Definition 2.6.

A graph $G$ is called traceable if $G$ has a Hamiltonian path.

Remark 2.7.

$G$ is traceable if and only if $r(G)=\lvert V\rvert-1$ .

2.3. F-Thresholds

Definition 2.8 ([MTW05, Lemma 1.1, Remark 1.5]).

Let $S=\mathbb{K}[X_{1},\ldots,X_{n}]$ be a polynomial ring, $\operatorname{char}(\mathbb{K})=p>0$ , $\mathfrak{m}=(X_{1},\ldots,X_{n})$ the homogeneous maximal ideal, and $I$ an $S$ -ideal with $I\subseteq\mathfrak{m}$ . For $e\in\mathbb{N}$ , set

\displaystyle\nu_{e}(I):=\max\{r\mid I^{r}\not\subseteq\mathfrak{m}^{[p^{e}]}\}

where $\mathfrak{m}^{[p^{e}]}:=(X_{1}^{p^{e}},\ldots,X_{n}^{p^{e}})$ . Then,

\displaystyle\operatorname{ft}(I):=\lim_{e\rightarrow\infty}\frac{\nu_{e}(I)}{p^{e}}

exists and is called the F-threshold of $I$ .

We review three lemmas well-known to experts. The first lemma says that the computation of F-threshold is additive over ideals in disjoint variables and enables us to reduce the computation of the F-threshold of a binomial edge ideal to the computation of the F-threshold of the binomial edge ideal of its connected components.

Lemma 2.9.

Let $\operatorname{char}\mathbb{K}=p>0$ , $I\subseteq S:=\mathbb{K}[X_{1},\ldots,X_{n}]$ with $\mathfrak{m}$ its homogeneous maximal ideal, $J\subseteq S^{{}^{\prime}}:=\mathbb{K}[Y_{1},\ldots,Y_{m}]$ with $\mathfrak{n}$ its homogeneous maximal ideal, $T:=S\otimes_{\mathbb{K}}S^{{}^{\prime}}$ with $\mathfrak{o}$ its homogeneous maximal ideal. Then,

\displaystyle\operatorname{ft}_{T}(I\cdot T+J\cdot T)=\operatorname{ft}_{S}(I)+\operatorname{ft}_{S^{{}^{\prime}}}(J).

In particular, if $G$ is a graph and $G_{1},\ldots,G_{c}$ are its connected components, then

\displaystyle\operatorname{ft}(J_{G})=\sum_{i=1}^{c}\operatorname{ft}(J_{G_{i}}).

The next lemma says that the F-threshold is monotonic along ideal inclusion which allows us to obtain lower bounds on a graph via its subgraphs.

Lemma 2.10.

Let $I\subseteq J\subseteq\mathfrak{m}$ be ideals in $\mathbb{K}[X_{1},\ldots,X_{n}]$ . Then,

\displaystyle\operatorname{ft}(I)\leq\operatorname{ft}(J).

In particular, if $H$ is a subgraph of $G$ , then

\displaystyle\operatorname{ft}(J_{H})\leq\operatorname{ft}(J_{G}).

Proof.

It follows from the definition that $\nu_{e}(I)\leq\nu_{e}(J)$ for all $e\in\mathbb{N}$ . ∎

The final lemma says that the F-threshold can only decrease under taking initial ideals.

Lemma 2.11 ([TW04, Proposition 4.5]).

Let $I\subseteq\mathfrak{m}$ be ideal in $\mathbb{K}[X_{1},\ldots,X_{n}]$ and $<$ a term order on the polynomial ring. Then, $\operatorname{ft}(\operatorname{in}_{<}(I))\leq\operatorname{ft}(I)$ .

Miller, Singh, and Varbaro [MSV14] computed the F-threshold of a determinantal ideal of a generic matrix as follows.

Theorem 2.12 ([MSV14, Theorem 1.2]).

Fix positive integers $t\leq m\leq n$ , and let $X$ be an $m\times n$ matrix of indeterminates over a field $\mathbb{F}$ of prime characteristic. Let $S$ be the polynomial ring $\mathbb{F}[X]$ , and $I_{t}$ the ideal generated by the size $t$ minors of $X$ .

The F-threshold of $I_{t}$ is

\displaystyle\min\bigg{\{}\frac{(m-k)(n-k)}{t-k}\mid k=0,\ldots,t-1\bigg{\}}.

Remark 2.13.

In the above theorem, when $t=m=2\leq n$ , then $I_{t}(X)$ corresponds to $J_{K_{n}}$ where $K_{n}$ denotes the complete graph on $n$ vertices, and thus

\displaystyle\operatorname{ft}(J_{K_{n}})=n-1.

In the master’s thesis of Velez [Vel19], he proves

Proposition 2.14 ([Vel19, Theorem 3.1.6]).

Let $M$ be a generic $m\times n$ matrix with $m\leq n$ . Let $\delta_{i}$ denote the determinant of the submatrix given by the columns $\{i,i+1,\ldots,i+m-1\}$ for $1\leq i\leq n-m+1$ . Let $J:=(\delta_{i}\mid 1\leq i\leq n-m+1)$ . Then, $\operatorname{ft}(J)=n-m+1$ .

Sketch of Proof.

By Lemma 2.11 and Theorem 2.12,

\displaystyle n-m+1=\operatorname{ft}(\operatorname{in}_{<}(J_{G}))\leq\operatorname{ft}(J_{G})\leq n-m+1.

Remark 2.15.

When $t=m=2$ in Proposition 2.14 the ideal $J_{G}$ corresponds the binomial edge ideal of a path on $n$ vertices. I.e., if $G=P_{n}$ is a path on $n$ vertices, then $\operatorname{ft}(J_{G})=n-1$ .

Theorem 2.16 ([Luc78] Lucas’s theorem).

Let $p$ be a prime integer and $m$ and $n$ positive integers. Choose a positive integer $e$ so that we can write $m=\sum_{i=0}^{e}m_{i}p^{i}$ and $n=\sum_{i=0}^{e}n_{i}p^{i}$ where $0\leq m_{i},n_{i}<p$ for $0\leq i\leq e$ . Then,

\displaystyle\binom{n}{m}\equiv\prod_{i=1}^{e}\binom{n_{i}}{m_{i}}\mod{p}

with the convention that $\binom{a}{b}=0$ if $a<b$ .

3. Linear Programs and Binomial Edge Ideals

3.1. Binomial Grade, Height, and Linear Programs

Recall that $r(G)$ is the maximal length of a path packing (Definition 2.5), and $\operatorname{PP}_{G,\mathbb{Z}}$ is the optimal value of an integer program (discussion surrounding (4)).

Proposition 3.1.

Given a graph $G$ , $r(G)=\operatorname{PP}_{G,\mathbb{Z}}$ .

Proof.

For $v\in V$ , the constraint $C_{\operatorname{PP},v}\leq 2$ forces that a feasible solution has at most two edges incident to $v$ . For $U\in\mathcal{A}$ , the constraint $C_{\operatorname{PP},U}\leq\lvert U\rvert-1$ forces that a feasible solution does not induce a Hamiltonian cycle on $G[U]$ . Thus, an optimal solution to (4) consists of disjoint paths. Conversely, a path packing is a feasible solution of (4). ∎

Remark 3.2.

The feasible solutions of (4) are precisely the semi-paths of $G$ . Moreover, in [HHM22, Lemma 3.2, Lemma 3.3] the authors show that $r(G)$ is equal to the binomial grade of $J_{G}$ , i.e. the length of a longest regular sequence in $J_{G}$ consisting of binomials which form part of a minimal generating set of $J_{G}$ .

The dual linear program of (4) solved over $\mathbbm{k}$ is given by

(7)

\begin{split}\operatorname*{minimize}\quad&Z_{\operatorname{PP^{\ast}},G}:=\sum_{v\in V(G)}2\cdot W_{\operatorname{PP^{\ast}},v}+\sum_{U\in\mathcal{A}}(\lvert U\rvert-1)\cdot W_{\operatorname{PP^{\ast}},U}\\ \operatorname{subject\,to:}\hskip 5.0pt&\phantom{}\\ &W_{\operatorname{PP^{\ast}},v}\in\mathbbm{k}_{\geq 0}\text{ for all }v\in V(G)\\ &W_{\operatorname{PP^{\ast}},U}\in\mathbbm{k}_{\geq 0}\text{ for all }U\in\mathcal{A}\\ &D_{\operatorname{PP^{\ast}},e}:=W_{\operatorname{PP^{\ast}},i}+W_{\operatorname{PP^{\ast}},j}+\sum_{\begin{subarray}{c}U\in\mathcal{A}\\ e\in G[U]\end{subarray}}W_{\operatorname{PP^{\ast}},U}\geq 1\text{ for all }e=\{i,j\}\in E(G)\end{split}

Denote the optimal value of (7) over $\mathbbm{k}$ by $\operatorname{PP}_{G,\mathbbm{k}}^{\ast}$ .

From a combinatorial perspective, the integral linear program (7) computes a minimal weighted edge covering of the graph by stars and induced subgraphs. From a commutative algebra perspective, (7) computes the height of $J_{G}$ .

Lemma 3.3.

Fix a graph $G$ and set $\mathbbm{k}=\mathbb{Z}$ . There exists an optimal solution of the linear program (7) of the form $(\{b_{v}\}_{v\in V},\{c_{U}\}_{U\in\mathcal{A}})$ satisfying

(1)

$b_{v}\in\{0,1\}$ for all $v\in V$ and $c_{U}\in\{0,1\}$ for all $U\in\mathcal{A}$ ,
(2)

if $U$ and $U^{{}^{\prime}}$ are elements of $\mathcal{A}$ with $c_{U}=c_{U^{{}^{\prime}}}=1$ , then $U\cap U^{{}^{\prime}}=\varnothing$ ,
(3)

if $b_{v}=1$ for some $v\in V(G)$ , then $v\notin U$ for all $c_{U}=1$ ,
(4)

if $c_{U}=1$ for some $U\in\mathcal{A}$ , then $U$ is connected.

For such a solution, let $T:=\{v\in V\mid c_{v}=1\}$ and $U_{1},\ldots,U_{c}$ to be the elements of $\mathcal{A}$ which satisfy $c_{U_{i}}=1$ . Then, the $U_{i}$ are the connected components of $\widehat{G\smallsetminus T}$ .

Proof.

Let $(\{b_{v}\}_{v\in V},\{c_{U}\}_{U\in\mathcal{A}})$ be any optimal solution to (7).

(1)

We may assume that $b_{v},c_{U}\in\{0,1\}$ for all $v\in V$ and $U\in\mathcal{A}$ . Otherwise, for each non-zero $b_{v}$ or non-zero $c_{U}$ reassign it the value $1$ .
(2)

We may suppose that if $U$ and $U^{{}^{\prime}}$ are elements of $\mathcal{A}$ with $c_{U}=c_{U^{{}^{\prime}}}=1$ , then $U\cap U^{{}^{\prime}}=\varnothing$ . Otherwise, redefine $c_{U}=c_{U^{{}^{\prime}}}=0$ and $c_{U\cup U^{{}^{\prime}}}=1$ .
(3)

We may suppose that if $b_{v}=1$ for some $v\in V(G)$ , then $v\notin U$ for all $c_{U}=1$ . Otherwise, if $\lvert U\rvert>2$ put $c_{U}=0$ and $c_{U\smallsetminus\{v\}}=1$ , and if $\lvert U\rvert=2$ put $c_{U}=0$ .
(4)

We may suppose that if $c_{U}=1$ for some $U\in\mathcal{A}$ , then $U$ is connected. Otherwise, write $U=U_{1}\cup U_{2}$ with $U_{1}\cup U_{2}=\varnothing$ . Put $c_{U}=0$ and $c_{U_{i}}=1$ if $U_{i}\in\mathcal{A}$ for $i=1,2$ .

After each application of one of the above steps this defines a new feasible solution of (7) which does not increase the cost function.

After these reductions, define $T:=\{v\in V\mid a_{v}=1\}$ and $U_{1},\ldots,U_{c}$ to be elements of $\mathcal{A}$ which satisfy $c_{U_{i}}=1$ . The above reductions together with the constraints $D_{\operatorname{PP^{\ast}},e}\geq 1$ for every $e\in E(G)$ implies that the $U_{i}$ are the connected components of $\widehat{G\smallsetminus T}$ . ∎

Proposition 3.4.

Let $G$ be a graph, then $\operatorname{PP}_{G,\mathbb{Z}}^{\ast}=\operatorname{ht}J_{G}$ .

Proof.

We first show $\operatorname{PP}_{G,\mathbb{Z}}^{\ast}\leq\operatorname{ht}J_{G}$ . Let $T\subseteq V(G)$ be chosen so that $\operatorname{ht}J_{G}=\operatorname{ht}P_{T}(G)=2\lvert T\rvert+\sum_{i=1}^{c_{T}(G)}\big{(}\lvert V(G_{i})\rvert-1\big{)}$ where the notation is as in Proposition 2.4. For $v\in V$ let

\displaystyle b_{v}:=\begin{cases}1,&v\in T\\ 0,&\text{else}\end{cases}

and for $U\in\mathcal{A}$ let

\displaystyle c_{U}=\begin{cases}1,&U=V(G_{i})\text{ for some }1\leq i\leq c_{T}(G)\\ 0,&\text{else}\end{cases}.

Then the tuple $\big{(}\{b_{v}\}_{v\in V},\{c_{U}\}_{U\in\mathcal{A}}\big{)}$ is a feasible solution to (7), and moreover

\displaystyle\operatorname{PP}_{G,\mathbb{Z}}^{\ast}\leq Z_{\operatorname{PP^{\ast}},G}\big{(}\{b_{v}\}_{v\in V},\{c_{U}\}_{U\in\mathcal{A}}\big{)}=2\lvert T\rvert+\sum_{i=1}^{c_{T}(G)}\big{(}\lvert V(G_{i})\rvert-1\big{)}=\operatorname{ht}J_{G}.

Next, we show that $\operatorname{ht}J_{G}\leq\operatorname{PP}_{G,\mathbb{Z}}^{\ast}$ . Let $\big{(}\{b_{v}\}_{v\in V},\{c_{U}\}_{U\in\mathcal{A}}\big{)}$ be an optimal solution of (7) when $\mathbbm{k}=\mathbb{Z}$ of the form guaranteed by Lemma 3.3. Let $T$ and $U_{1},\ldots,U_{c}$ be as constructed by Lemma 3.3. The cost of this optimal tuple is precisely $2\lvert T\rvert+\sum_{i=1}^{c}(\lvert U_{i}\rvert-1)$ which is equal to $\operatorname{ht}P_{T}(G)$ . This proves that

\displaystyle\operatorname{ht}J_{G}\leq\operatorname{ht}P_{T}(G)=\operatorname{PP}_{G,\mathbb{Z}}^{\ast}

which completes the proof. ∎

3.2. Thresholds and Linear Programs

Next, we study the LP relaxation of the above linear programs, i.e. we allow the variables to take values in $\mathbb{R}_{\geq 0}$ , and how the optimal solution relates to commutative algebra invariants.

For a graph $G$ denote by $\operatorname{LP}_{G,\mathbbm{k}}$ the optimal value of the following linear program over $(\mathbbm{k}_{\geq 0})^{2\lvert E\rvert}$ .

(8)

\begin{split}\operatorname*{maximize}\quad&Z_{\operatorname{LP},G}:=\sum_{e\in E(G)}(X_{\operatorname{LP},e}+Y_{\operatorname{LP},e})\\ \operatorname{subject\,to:}\hskip 6.99997pt&\phantom{}\\ &X_{\operatorname{LP},e}\in\mathbbm{k}_{\geq 0}\text{ for all }e\in E(G)\\ &Y_{\operatorname{LP},e}\in\mathbbm{k}_{\geq 0}\text{ for all }e\in E(G)\\ &C_{\operatorname{LP},U}:=\sum_{e\in E(G[U])}(X_{\operatorname{LP},e}+Y_{\operatorname{LP},e})\leq\lvert U\rvert-1\text{ for all }U\in\mathcal{A}\\ &C_{\operatorname{LP},v,x}:=\sum_{\begin{subarray}{c}e=\{v,w\}\\ v<w\end{subarray}}X_{\operatorname{LP},e}+\sum_{\begin{subarray}{c}e=\{w,v\}\\ w<v\end{subarray}}Y_{\operatorname{LP},e}\leq 1\text{ for all }v\in V(G)\\ &C_{\operatorname{LP},v,y}:=\sum_{\begin{subarray}{c}e=\{v,w\}\\ v<w\end{subarray}}Y_{\operatorname{LP},e}+\sum_{\begin{subarray}{c}e=\{w,v\}\\ w<v\end{subarray}}X_{\operatorname{LP},e}\leq 1\text{ for all }v\in V(G)\\ \end{split}

Remark 3.5.

Let $G$ be a graph and $G_{1},\ldots,G_{c}$ the connected components of $G$ . Then,

\displaystyle\operatorname{LP}_{G,\mathbb{Q}}=\sum_{i=1}^{c}\operatorname{LP}_{G_{i},\mathbb{Q}}.

The following proposition says that the constraint $C_{\operatorname{LP},U}\leq\lvert U\rvert-1$ in (8) can be strengthened by requiring that in addition $U$ is biconnected. Recall that a connected graph $G$ is biconnected if $G\smallsetminus\{v\}$ is connected for every $v\in V(G)$ . In the following linear program we differentiate the intdeterminates and constraints from those appearing in (8) by utilizing the superscript “ $\operatorname{bi}$ ”.

Proposition 3.6.

The set of feasible solutions of (8) is the same as the set of feasible solutions of the following linear program

(9)

\begin{split}\operatorname*{maximize}\quad&Z_{\operatorname{LP},G}^{\operatorname{bi}}:=\sum_{e\in E(G)}(X_{\operatorname{LP},e}^{\operatorname{bi}}+Y_{\operatorname{LP},e}^{\operatorname{bi}})\\ \operatorname{subject\,to:}\hskip 6.99997pt&\phantom{}\\ &X_{\operatorname{LP},e}^{\operatorname{bi}}\in\mathbbm{k}_{\geq 0}\text{ for all }e\in E(G)\\ &Y_{\operatorname{LP},e}^{\operatorname{bi}}\in\mathbbm{k}_{\geq 0}\text{ for all }e\in E(G)\\ &C_{\operatorname{LP},U}^{\operatorname{bi}}:=\sum_{e\in E(G[U])}(X_{\operatorname{LP},e}^{\operatorname{bi}}+Y_{\operatorname{LP},e}^{\operatorname{bi}})\leq\lvert U\rvert-1\text{ for all }U\in\mathcal{A},\phantom{}G[U]\text{ biconnected}\\ &C_{\operatorname{LP},v,x}^{\operatorname{bi}}:=\sum_{\begin{subarray}{c}e=\{v,w\}\\ v<w\end{subarray}}X_{\operatorname{LP},e}^{\operatorname{bi}}+\sum_{\begin{subarray}{c}e=\{w,v\}\\ w<v\end{subarray}}Y_{\operatorname{LP},e}^{\operatorname{bi}}\leq 1\text{ for all }v\in V(G)\\ &C_{\operatorname{LP},v,y}^{\operatorname{bi}}:=\sum_{\begin{subarray}{c}e=\{v,w\}\\ v<w\end{subarray}}Y_{\operatorname{LP},e}^{\operatorname{bi}}+\sum_{\begin{subarray}{c}e=\{w,v\}\\ w<v\end{subarray}}X_{\operatorname{LP},e}^{\operatorname{bi}}\leq 1\text{ for all }v\in V(G)\\ \end{split}

where $v<w$ means that the label on the vertex $v$ is smaller than the label on the vertex $w$ .

Proof.

It suffices to show that feasible solutions of (9) are feasible solutions of (8). It suffices to restrict to the case of $U\in\mathcal{A}$ is connected. Write $U=U_{1}\cup\cdots\cup U_{c}$ as a union of its maximal biconnected components. Let $\mathbf{{a}}$ denote a feasible solution of (8). Observe that

\displaystyle C_{U}(\mathbf{{a}})=\sum_{i=1}^{c}C_{U_{i}}(\mathbf{{a}})=\sum_{i=1}^{c}C_{U_{i}}^{\operatorname{bi}}(\mathbf{{a}})\leq\sum_{i=1}^{c}(\lvert U_{i}\rvert-1).

The above assumptions on $U$ together with induction on $c$ shows that

\displaystyle\sum_{i=1}^{c}(\lvert U_{i}\rvert-1)\leq\lvert U\rvert-1.

∎

Remark 3.7.

Linear program (9) will have $O(2^{n})$ constraints for a complete graph on $n$ vertices.

Example 3.8.

Let $G$ be the graph depicted in Figure 1.

Figure 1. Net

We label the edges of the graph with the letters a through f and the vertices with the numbers $1$ through $6$ as in Figure 1. Then, the constraints in (9) are

$\displaystyle C_{\operatorname{LP},\{1,2\}}^{\operatorname{bi}}$	$\displaystyle=X_{a}^{\operatorname{bi}}+Y_{a}^{\operatorname{bi}}\leq 1$	$\displaystyle C_{\operatorname{LP},4,x}^{\operatorname{bi}}$	$\displaystyle=X_{f}^{\operatorname{bi}}+Y_{c}^{\operatorname{bi}}+Y_{d}^{\operatorname{bi}}\leq 1$	$\displaystyle C_{\operatorname{LP},1,x}^{\operatorname{bi}}$	$\displaystyle=X_{a}^{\operatorname{bi}}\leq 1$
$\displaystyle C_{\operatorname{LP},\{2,3\}}^{\operatorname{bi}}$	$\displaystyle=X_{b}^{\operatorname{bi}}+Y_{b}^{\operatorname{bi}}\leq 1$	$\displaystyle C_{\operatorname{LP},4,y}^{\operatorname{bi}}$	$\displaystyle=Y_{f}^{\operatorname{bi}}+X_{c}^{\operatorname{bi}}+X_{d}^{\operatorname{bi}}\leq 1$	$\displaystyle C_{\operatorname{LP},1,y}^{\operatorname{bi}}$	$\displaystyle=Y_{a}^{\operatorname{bi}}\leq 1$
$\displaystyle C_{\operatorname{LP},\{2,4\}}^{\operatorname{bi}}$	$\displaystyle=X_{c}^{\operatorname{bi}}+Y_{c}^{\operatorname{bi}}\leq 1$	$\displaystyle C_{\operatorname{LP},2,x}^{\operatorname{bi}}$	$\displaystyle=Y_{a}^{\operatorname{bi}}+X_{b}^{\operatorname{bi}}+X_{c}^{\operatorname{bi}}\leq 1$	$\displaystyle C_{\operatorname{LP},5,x}^{\operatorname{bi}}$	$\displaystyle=Y_{e}^{\operatorname{bi}}\leq 1$
$\displaystyle C_{\operatorname{LP},\{3,4\}}^{\operatorname{bi}}$	$\displaystyle=X_{d}^{\operatorname{bi}}+Y_{d}^{\operatorname{bi}}\leq 1$	$\displaystyle C_{\operatorname{LP},2,y}^{\operatorname{bi}}$	$\displaystyle=X_{a}^{\operatorname{bi}}+Y_{b}^{\operatorname{bi}}+Y_{c}^{\operatorname{bi}}\leq 1$	$\displaystyle C_{\operatorname{LP},5,y}^{\operatorname{bi}}$	$\displaystyle=X_{e}^{\operatorname{bi}}\leq 1$
$\displaystyle C_{\operatorname{LP},\{3,5\}}^{\operatorname{bi}}$	$\displaystyle=X_{e}^{\operatorname{bi}}+Y_{e}^{\operatorname{bi}}\leq 1$	$\displaystyle C_{\operatorname{LP},3,x}^{\operatorname{bi}}$	$\displaystyle=X_{d}^{\operatorname{bi}}+X_{e}^{\operatorname{bi}}+Y_{b}^{\operatorname{bi}}\leq 1$	$\displaystyle C_{\operatorname{LP},6,x}^{\operatorname{bi}}$	$\displaystyle=Y_{f}^{\operatorname{bi}}\leq 1$
$\displaystyle C_{\operatorname{LP},\{4,6\}}^{\operatorname{bi}}$	$\displaystyle=X_{f}^{\operatorname{bi}}+Y_{f}^{\operatorname{bi}}\leq 1$	$\displaystyle C_{\operatorname{LP},3,y}^{\operatorname{bi}}$	$\displaystyle=Y_{d}^{\operatorname{bi}}+Y_{e}^{\operatorname{bi}}+X_{b}^{\operatorname{bi}}\leq 1$	$\displaystyle C_{\operatorname{LP},6,y}^{\operatorname{bi}}$	$\displaystyle=X_{f}^{\operatorname{bi}}\leq 1$

and $C_{\{2,3,4\}}^{\operatorname{bi}}=X_{b}^{\operatorname{bi}}+Y_{b}^{\operatorname{bi}}+X_{c}^{\operatorname{bi}}+Y_{c}^{\operatorname{bi}}+X_{d}^{\operatorname{bi}}+Y_{d}^{\operatorname{bi}}\leq 2$ .

In the linear program (10) below, whenever we write $\{i,j\}$ for an edge of a graph we will in addition assume that $i<j$ . The dual of the linear program (8) is given by

(10)

\begin{split}\operatorname*{minimize}\hskip 8.50006pt&Z_{\operatorname{LP^{\ast}},G}:=\sum_{v\in V(G)}(W_{\operatorname{LP^{\ast}},v,x}+W_{\operatorname{LP^{\ast}},v,y})+\sum_{U\in\mathcal{A}}(\lvert U\rvert-1)W_{\operatorname{LP^{\ast}},U}\\ \operatorname{subject\,to:}\hskip 2.5pt&\phantom{}\\ &W_{\operatorname{LP^{\ast}},v,x}\in\mathbbm{k}_{\geq 0}\text{ for all }v\in V(G)\\ &W_{\operatorname{LP^{\ast}},v,y}\in\mathbbm{k}_{\geq 0}\text{ for all }v\in V(G)\\ &W_{\operatorname{LP^{\ast}},U}\in\mathbbm{k}_{\geq 0}\text{ for all }U\subseteq V(G)\text{ with }\lvert U\rvert\geq 2\\ &D_{\operatorname{LP^{\ast}},e,x}:=\sum_{\begin{subarray}{c}e\in E(G[U])\\ U\in\mathcal{A}\end{subarray}}W_{\operatorname{LP^{\ast}},U}+W_{\operatorname{LP^{\ast}},i,x}+W_{\operatorname{LP^{\ast}},j,y}\geq 1\text{ for all }e=\{i,j\}\in E(G)\\ &D_{\operatorname{LP^{\ast}},e,y}:=\sum_{\begin{subarray}{c}e\in E(G[U])\\ U\in\mathcal{A}\end{subarray}}W_{\operatorname{LP^{\ast}},U}+W_{\operatorname{LP^{\ast}},j,x}+W_{\operatorname{LP^{\ast}},i,y}\geq 1\text{ for all }e=\{i,j\}\in E(G)\end{split}

We denote by $\operatorname{LP}_{G,\mathbbm{k}}^{\ast}$ the optimal value of (10).

Proposition 3.9.

Let $G$ be a labeled graph. Then, $\operatorname{PP}_{G,\mathbbm{k}}=\operatorname{LP}_{G,\mathbbm{k}}$ and $\operatorname{PP}_{G,\mathbbm{k}}^{\ast}=\operatorname{LP}_{G,\mathbbm{k}}^{\ast}$ .

Proof.

Let $\Sigma$ (respectively $\Sigma^{{}^{\prime}}$ ) denote the set of feasible solutions of (4) (respectively of the feasible solutions of (8)). If $\mathbbm{k}$ is a field, then there are linear bijections

	$\displaystyle\Sigma$	$\displaystyle\leftrightarrow\Sigma^{{}^{\prime}}$
	$\displaystyle(a_{e})_{e\in E(G)}$	$\displaystyle\mapsto\big{(}\{\frac{a_{e}}{2}\}_{e\in E(G)},\{\frac{a_{e}}{2})\}_{e\in E(G)}\big{)}$
	$\displaystyle(a_{e}+b_{e})_{e\in E(G)}$	$\displaystyle\mapsfrom\big{(}\{a_{e}\}_{e\in E(G)},\{b_{e}\}_{e\in E(G)}\big{)}$

If $\mathbbm{k}=\mathbb{Z}$ , then there are a linear bijections

	$\displaystyle\Sigma$	$\displaystyle\leftrightarrow\Sigma^{{}^{\prime}}$
	$\displaystyle(a_{e})_{e\in E(G)}$	$\displaystyle\mapsto\big{(}\{a_{e}\}_{e\in E(G)},\{0\}_{e\in E(G)}\big{)}$
	$\displaystyle(a_{e}+b_{e})_{e\in E(G)}$	$\displaystyle\mapsfrom\big{(}a_{e}\}_{e\in E(G)},\{b_{e}\}_{e\in E(G)}\big{)}$

The constraint $C_{U}\leq 1$ for $U=e$ shows that the map from $\Sigma^{{}^{\prime}}\rightarrow\Sigma$ is well-defined.

The dual case is proved analogously. ∎

Proposition 3.10.

Let $G$ be a graph, then

\displaystyle r(G)\leq\operatorname{ft}(J_{G})

where $r(G)$ is as found in Definition 2.5.

Proof.

Let $<$ denote the lex monomial order on $R$ with $X_{1}>\cdots>X_{n}>Y_{1}>\cdots>Y_{n}$ . Then,

\displaystyle r(G)\leq\operatorname{ft}(\operatorname{in}_{<}J_{G})\leq\operatorname{ft}(J_{G}).

∎

Lemma 3.11 ([MSV14, Lemma 1.2]).

Fix a $2\times n$ generic matrix $M$ and $S=\mathbb{F}_{p}[M]$ . There exists a non-negative integer $N_{M}$ , so that for every $q=p^{e}$ where $e\in\mathbb{Z}_{\geq 0}$ , we have $\nu_{q}(I_{2}(M))\leq N_{M}+(q-1)(n-1)$ .

Proof.

Follows from the proof of their Lemma 1.2 by taking, in their notation, $m=t=2$ and $k=1$ . ∎

Proposition 3.12.

Let $G$ be a labeled graph, then

\displaystyle\operatorname{ft}(J_{G})\leq\operatorname{LP}_{G,\mathbb{Q}}

Proof.

Fix notation of $M$ as a $2\times\lvert V(G)\rvert$ generic matrix, $S=\mathbb{F}_{p}[M]$ . For $U\subseteq V(G)$ we consider $M_{U}$ and $S_{U}$ the restriction of $M$ and $S$ to the submatrix (respectively subring) of variables corresponding to the vertices of $U$ . We take $N:=\max\big{\{}\lvert V(G)\rvert,\{N_{M_{U}}\mid U\in\mathcal{A}\}\big{\}}$ where $N_{M_{U}}$ is as defined in Lemma 3.11.

We denote by $P_{\infty}$ the polytope contained in $(\mathbb{R}_{\geq 0})^{2\lvert E\rvert}$ determined by the constraints of linear program (8).

For every $t\in\mathbb{N}$ , let $P_{t}$ be the polytope inside $(\mathbb{R}_{\geq 0})^{2\lvert E\rvert}$ determined by the following constraints

	$\displaystyle\tilde{X}_{\operatorname{LP},e}\geq 0\text{ for all }e\in E(G)$
	$\displaystyle\tilde{Y}_{\operatorname{LP},e}\geq 0\text{ for all }e\in E(G)$
(11)		$\displaystyle\tilde{C}_{\operatorname{LP},U}:=\sum_{e\in E(G[U])}(\tilde{X}_{\operatorname{LP},e}+\tilde{Y}_{\operatorname{LP},e})\leq\frac{N+(p^{t}-1)(\lvert U\rvert-1)}{p^{t}}\text{ for all }U\in\mathcal{A}$
(12)		$\displaystyle\tilde{C}_{\operatorname{LP},v,x}:=\sum_{\begin{subarray}{c}e=\{v,w\}\\ v<w\end{subarray}}\tilde{X}_{\operatorname{LP},e}+\sum_{\begin{subarray}{c}e=\{w,v\}\\ w<v\end{subarray}}\tilde{Y}_{\operatorname{LP},e}\leq 1\text{ for all }v\in V(G)$
(13)		$\displaystyle\tilde{C}_{\operatorname{LP},v,y}:=\sum_{\begin{subarray}{c}e=\{v,w\}\\ v<w\end{subarray}}\tilde{Y}_{\operatorname{LP},e}+\sum_{\begin{subarray}{c}e=\{w,v\}\\ w<v\end{subarray}}\tilde{X}_{\operatorname{LP},e}\leq 1\text{ for all }v\in V(G)$

We denote by $\operatorname{LP}_{G,\mathbb{Q},t}$ to be the maximum of the function

\displaystyle\mathbb{R}^{2\lvert E\rvert}\rightarrow\mathbb{R}:(\{\tilde{X}_{\operatorname{LP},e}\}_{e\in E(G)},\{\tilde{Y}_{\operatorname{LP},e}\}_{e\in E(G)})\mapsto\sum_{e\in E(G)}(\tilde{X}_{\operatorname{LP},e}+\tilde{Y}_{\operatorname{LP},e})

when restricted to the region $P_{t}$ .

Fix $t$ a positive integer. Then, there exist non-negative integers $a_{e},b_{e}$ for $e\in E(G)$ satisfying $\sum_{e\in E(G)}(a_{e}+b_{e})=\nu_{t}(J_{G})$ and a monomial

\displaystyle\mu:=\prod\limits_{\begin{subarray}{c}e=(i,j)\in E(G)\\ i<j\end{subarray}}(X_{i}Y_{j})^{a_{e}}(X_{j}Y_{i})^{b_{e}}

belonging to the monomial support of some element of $J_{G}^{\nu_{t}(J_{G})}\smallsetminus m^{[p^{t}]}$ .

Observe that the tuple $\left(\mathbf{{a}},\mathbf{{b}}\right)=\left(\{\frac{a_{e}}{p^{t}}\}_{e\in E(G)},\{\frac{b_{e}}{p^{t}}\}_{e\in E(G)}\right)\in P_{t}$ . Indeed, since $\mu\notin m^{[p^{t}]}$ ,

	$\displaystyle\tilde{C}_{\operatorname{LP},v,x}\big{(}\mathbf{{a}},\mathbf{{b}}\big{)}$	$\displaystyle=\deg_{X_{v}}\mu\leq p^{t}$
	$\displaystyle\tilde{C}_{\operatorname{LP},v,y}\big{(}\mathbf{{a}},\mathbf{{b}}\big{)}$	$\displaystyle=\deg_{Y_{v}}\mu\leq p^{t}.$

Indeed, by Lemma 3.11,

\displaystyle\tilde{C}_{\operatorname{LP},U}\big{(}\mathbf{{a}},\mathbf{{b}}\big{)}\leq N+(p^{t}-1)(\lvert U\rvert-1).

This shows that $\frac{\nu_{t}(J_{G})}{p^{t}}\leq\operatorname{LP}_{G,\mathbb{Q},t}$ . Taking limit as $t\rightarrow\infty$ it follows by Lemma 3.13 that $\operatorname{ft}(J_{G})\leq\operatorname{LP}_{G,\mathbb{Q}}$ . ∎

Lemma 3.13.

With the notation as above,

(1)

For every $0<\epsilon<1$ , there exists $t\in\mathbb{N}$ so that for every $\mathbf{{x}}\in P_{t}$ there exists $\mathbf{{y}}\in P_{\infty}$ with $||\mathbf{{x}}-\mathbf{{y}}||_{1}<\epsilon$ .
(2)

$\lim_{t\rightarrow\infty}\operatorname{LP}_{G,\mathbb{Q},t}=\operatorname{LP}_{G,\mathbb{Q}}$ .

Proof.

(1)

Fix $0<\epsilon<1$ . Take $t\in\mathbb{N}$ so that $2\lvert E\rvert\frac{N}{p^{t}}<\epsilon$ . For $\mathbf{{x}}\in P_{t}$ , define $\mathbf{{y}}$ via $y_{i}:=x_{i}-\min\{x_{i},\frac{N}{p^{t}}\}$ for $1\leq i\leq 2\lvert E\rvert$ . We observe that

\displaystyle||\mathbf{{x}}-\mathbf{{y}}||_{1}\leq 2\lvert E\rvert\frac{N}{p^{t}}<\epsilon.

Since $\mathbf{{y}}$ is pointwise less than $\mathbf{{x}}$ and $\mathbf{{x}}$ satisfies the constraints (12) and (13), $C_{\operatorname{LP},v,x}(\mathbf{{y}})<1$ and $C_{\operatorname{LP},v,y}(\mathbf{{y}})<1$ for all $v\in V$ . Thus, to show that $\mathbf{{y}}\in P_{\infty}$ it suffices to show that $C_{U}(\mathbf{{y}})\leq\lvert U\rvert-1$ for all $U\in\mathcal{A}$ .

Observation 1.

The constraint $\tilde{C}_{\operatorname{LP},U}(\mathbf{{x}})\leq\frac{N+(p^{t}-1)(\lvert U\rvert-1)}{p^{t}}$ implies that

(14)

\displaystyle\tilde{C}_{\operatorname{LP},U}(\mathbf{{x}})-\frac{N}{p^{t}}<\lvert U\rvert-1.

Observation 2.

If $\tilde{C}_{\operatorname{LP},U}(\mathbf{{x}})>\lvert U\rvert-1$ , then $x_{\max,U}\geq\frac{N}{p^{t}}$ where $x_{\max,U}$ is the largest value of $\mathbf{{x}}$ that appears in the support of $\tilde{C}_{\operatorname{LP},U}(\mathbf{{x}})$ . If this is not the case, then we have that

	$\displaystyle\lvert U\rvert-1$	$\displaystyle<\tilde{C}_{\operatorname{LP},U}(\mathbf{{x}})$
		$\displaystyle\leq 2\lvert E(G[U])\rvert\cdot x_{\max,U}$
		$\displaystyle\leq 2\lvert E\rvert\frac{N}{p^{t}}$
		$\displaystyle<\epsilon$
		$\displaystyle<1.$

But, then this implies that $\lvert U\rvert<2$ ; a contradiction.

There is nothing to prove if $\tilde{C}_{\operatorname{LP},U}(\mathbf{{x}})\leq\lvert U\rvert-1$ . If $\tilde{C}_{\operatorname{LP},U}>\lvert U\rvert-1$ , then by Observation 2 there exists $x_{i}$ appearing in the support of $\tilde{C}_{\operatorname{LP},U}(\mathbf{{x}})$ with $x_{i}\geq\frac{N}{p^{t}}$ . Then, by construction $y_{i}=x_{i}-\frac{N}{p^{t}}$ . Hence, by Observation 1

\displaystyle C_{U}(\mathbf{{y}})\leq C_{U}(\mathbf{{x}})-\frac{N}{p^{t}}<\lvert U\rvert-1.

Thus, $\mathbf{{y}}\in P_{\infty}$ .

(2)

Let $0<\epsilon<1$ , $\mathbf{{x}}$ a vertex of $P_{t}$ where $\sum_{e\in E(G)}(X_{e}+Y_{e})$ attains a maximum, $t$ and $\mathbf{{y}}\in P_{\infty}$ to be as in part (1) of this Lemma. Since $||\mathbf{{y}}||_{1}\leq\operatorname{LP}_{G,\mathbb{Q}}$ and $||\mathbf{{x}}-\mathbf{{y}}||_{1}<\epsilon$ , it follows that

\displaystyle\operatorname{LP}_{G,\mathbb{Q},t}=||\mathbf{{x}}||_{1}\leq||\mathbf{{x}}-\mathbf{{y}}||_{1}+||\mathbf{{y}}||_{1}\leq\epsilon+\operatorname{LP}_{G,\mathbb{Q}}.

Consequently,

\displaystyle\operatorname{LP}_{G,\mathbb{Q},t}-\operatorname{LP}_{G,\mathbb{Q}}<\epsilon.

This proves that $\lim_{t\rightarrow\infty}\operatorname{LP}_{G,\mathbb{Q},t}=\operatorname{LP}_{G,\mathbb{Q}}$ .

∎

Corollary 3.14.

Let $G$ be a graph, then

\displaystyle\operatorname{lct}(J_{G})\leq\operatorname{LP}_{G,\mathbb{Q}}.

Proof.

Clear from Proposition 3.12 and Theorem 1.2. ∎

Remark 3.15.

One can always bound the F-threshold of an ideal in a polynomial ring with respect to the maximal ideal by the optimal value of a linear programming problem by removing the constraints of the form $\tilde{C}_{U}\leq\lvert U\rvert-1$ from (8) (cf. [ST09] or [Her14]).

The previous results of this section can be summarized as

(15)

\text{binomial grade }J_{G}=r(G)=\operatorname{LP}_{G,\mathbb{Z}}\leq\operatorname{ft}(J_{G})\leq\operatorname{LP}_{G,\mathbb{Q}}=\operatorname{LP}_{G,\mathbb{Q}}^{\ast}\leq\operatorname{LP}_{G,\mathbb{Z}}^{\ast}=\operatorname{ht}(J_{G}).

Remark 3.16.

The relation $\operatorname{ft}(I)\leq\operatorname{ht}(I)$ holds more generally, cf. [TW04, Proposition 2.6(1)].

4. Proof of Conjecture 1.3 for Block Graphs

Definition 4.1.

A graph $G$ is called biconnected if $G$ is connected and $G\smallsetminus v$ is connected for every vertex $v$ of $G$ . A graph $G$ is called a block graph if every maximal biconnected component of $G$ is a complete graph. We call a maximal biconnected component of $G$ a block. A vertex $v$ of $G$ is called a cut vertex if the number of connected components of $G\smallsetminus v$ is strictly larger than the number of connected components of $G$ .

Let $G$ be a block graph and $B$ a block of $G$ , then we define $\operatorname{cut}(B)$ to be the set of all cut vertices of $G$ contained in $B$ . We say that $B$ is a leaf of $G$ if $\lvert\operatorname{cut}(B)\rvert=1$ , and we say that $G$ has the two block property if every cut vertex of $G$ is adjacent to exactly two blocks of $G$ . An edge of $G$ which is also a leaf of $G$ is called a whisker of $G$ .

Throughout this section we will let $n_{G}:=\lvert V(G)\rvert$ , $\ell_{G}$ will denote the number of leaves of $G$ , $w_{G}$ will denote the number of connected components of $G$ isomorphic to a complete graph. When the graph $G$ is clear from context we will omit the subscript $G$ .

Proposition 4.2.

Let $G$ be a block graph. Then,

\displaystyle\operatorname{LP}_{G,\mathbb{Q}}\leq n_{G}-\frac{1}{2}\ell-w.

Proof.

By Remark 3.5 we may assume that $G$ is connected. If $G$ is a complete graph there is nothing to prove. We reduce to the case that $G$ is a connected block graph which is not a complete graph.

Since $G$ is a connected block graph which is not a complete graph $w=0$ and $\ell\geq 1$ . Partition the blocks of $G$ into $\mathcal{B}_{1}$ , the leaves of $G$ , and $\mathcal{B}_{2}$ , the remaining blocks. Write $\mathcal{B}_{1}=\{B_{1},\ldots,B_{\ell}\}$ . Each $B_{i}\in\mathcal{B}_{1}$ has exactly one cut vertex which we will call $c_{i}$ and at least one other vertex, i.e. $\lvert V(B_{i})\rvert\geq 2$ . Let

\displaystyle T:=\left(\bigcup_{B\in\mathcal{B}_{2}}V(B)\right)\cup\left(\bigcup\{c_{i}\mid 1\leq i\leq\ell\}\right).

For $v\in V$ , define

(16)

b_{v,x}=b_{v,y}=\begin{cases}1/2,&v\in T\\ 0,&v\in V(G)\smallsetminus T.\end{cases}

For $U\in\mathcal{A}$ , define

(17)

c_{U}=\begin{cases}1/2,&U\in\mathcal{B}_{1}\\ 1/2,&U=B_{i}\smallsetminus\{c_{i}\}\text{ for some }1\leq i\leq\ell,\\ 0,&\text{ else}.\end{cases}

Then, the tuple $(\{b_{v,x}\}_{v\in V},\{b_{v,y}\}_{v\in V},\{c_{U}\}_{U\in\mathcal{A}})$ is a feasible solution to the linear program (10), and the cost of this feasible solution is

\displaystyle n_{G}-\frac{1}{2}\ell.

Thus,

\displaystyle\operatorname{LP}_{G,\mathbb{Q}}^{\ast}\leq n_{G}-\frac{1}{2}\ell.

Hence, the result follows by strong duality, Theorem 2.1. ∎

4.1. Triangle Paths and the Two Block Property

Definition 4.3.

We say that a graph $G$ is a triangle path if every connected component of $G$ which is not an isolated vertex satisfies

(1)

the only cycles in $G$ are $K_{3}$ ’s which we label as $C_{1},\ldots,C_{t}$ (we will sometimes refer to the $C_{i}$ ’s as the triangles of $\mathit{G}$ ),

(2)

For all $v\in G$ ,

\displaystyle\deg_{G}(v)=\begin{cases}3,&v\in V(C_{i})\text{ for some }1\leq i\leq t\\ 1\text{ or }2,&\text{otherwise}.\end{cases}

(3)

Every vertex of $G$ belongs to at most one triangle of $G$ .

When $G$ is a triangle path and $G$ is a subgraph of $L$ , then we call $G$ a triangle path packing of $L$ .

Example 4.4.

The graph in Figure 2 is an instance of a triangle path.

Figure 2. Triangle Path

Remark 4.5.

A triangle path is an example of a family of block graphs with the two block property.

Proposition 4.6.

Let $G$ be a triangle path. Label the $K_{3}$ ’s in the triangle path $C_{1},\ldots,C_{t}$ . Label the connected components of $G\smallsetminus\bigcup_{k=1}^{t}E(C_{k})$ by $P_{1},\ldots,P_{s}$ . Then,

(18)

\operatorname{ft}(J_{G})=\sum_{i=1}^{s}\lvert E(P_{i})\rvert+\frac{3}{2}t.

Moreover,

(19)

\operatorname{ft}(J_{G})=n_{G}-\frac{1}{2}\ell_{G}-w_{G}.

Proof.

By induction on $t$ it can be shown that (18) and (19) are equivalent. By Lemma 2.9 and Remark 2.13 we may assume that $G$ is connected and not a complete graph, i.e. that $w=0$ . By Proposition 3.12 and Proposition 4.2, and the above mentioned equivalence we have that $\operatorname{ft}(J_{G})\leq\sum_{i=1}^{s}\lvert E(P_{i})\rvert+\frac{3}{2}t$ . It thus suffices to prove the reverse inequality.

Let $R$ and $\mathfrak{m}$ be as in Definition 1.1. First consider the case that $\operatorname{char}(\mathbb{K})=p>2$ . The first step in the proof is to label the vertices of the graph and to assign to every edge $e$ a tuple $(a_{e},b_{e})$ so that the following conditions are satisfied.

(1)

Some vertex having degree one has been assigned the label $1$ .
(2)

If $a\in V(P_{j})$ and $b,c\in V(P_{i})$ for some $1\leq i,j\leq\ell$ with the distance from $b$ to $a$ smaller than the distance from $c$ to $a$ , then either $a<b<c$ or $c<b<a$ .
(3)

$(a_{e},b_{e})$ equals $(0,1)$ , $(1,0)$ , or $(0.5,0.5)$ if $e$ is not an edge of any triangle of $G$ .
(4)

$(a_{e},b_{e})$ equals $(0,0.5)$ or $(0.5,0)$ if $e$ is the edge of any triangle of $G$ .
(5)

$\sum_{e\in E(G)}\left(a_{e}+b_{e}\right)=\sum_{i=1}^{s}\lvert E(P_{i})\rvert+\frac{3}{2}t$ .

(6)

The monomial

(20)

m:=\prod_{\begin{subarray}{c}e=\{i,j\}\in E(G)\\ i<j\end{subarray}}(X_{i}Y_{j})^{a_{ij}\cdot(p^{e}-1)}\cdot(X_{j}Y_{i})^{b_{ij}\cdot(p^{e}-1)}

does not belong to the ideal $\mathfrak{m}^{[p^{e}]}$ and appears in the polynomial

(21)

f:=\prod_{\begin{subarray}{c}e=\{i,j\}\in E(G)\\ i<j\end{subarray}}f_{ij}^{(a_{ij}+b_{ij})\cdot(p^{e}-1)}.

with a coefficient which is non-zero mod $p$ .

It would follow from items (5) and (21) that

\displaystyle\bigg{(}\sum_{i=1}^{s}\lvert E(P_{i})\rvert+\frac{3}{2}t\bigg{)}(p^{e}-1)\leq\nu_{e}(J_{G}),

and consequently that

\displaystyle\sum_{i=1}^{s}\lvert E(P_{i})\rvert+\frac{3}{2}t\leq\operatorname{ft}(J_{G}).

We prove the existence of this labeling by induction on $t$ . It $t=0$ , then $G$ is a path. Starting at a vertex of degree one assign it the label $1$ , then label the vertices consecutively. Assign to every edge the tuple $(1,0)$ . That the above conditions are satisfied is clear.

Suppose now that $t\geq 1$ . There exists a triangle of $G$ , call it $T$ , so that removing the edges of $T$ from $G$ yields a graph having three connected components—two of which are paths, say $P$ and $Q$ , and the other is a triangle path, call it $G^{{}^{\prime}}$ , having one less triangle than $G$ . Let $b$ be the vertex belonging to $V(T)\cap V(G^{{}^{\prime}})$ . Let $a$ be the vertex adjacent to $b$ in $G^{{}^{\prime}}$ . Apply the induction hypothesis to $G^{{}^{\prime}}$ and we may assume that $b$ has not been given the label $1$ . By item 2, it follows that $a<b$ . Label the remaining vertices of $T$ by $n+1$ and $n+2$ . Label the vertex of $V(P)\cup V(Q)$ adjacent to $n+1$ (respectively $n+2$ ) by $n+3$ (respectively $n+4$ ). Label the remaining vertices of $V(P)\cup V(Q)$ so as to satisfy condition (2). Use Table 1 to assign tuples to the edges of $T$ and to the edges of $P$ and $Q$ incident to the vertices of $T$ based upon the tuple assigned to the edge $\{a,b\}$ . Now, $P$ and $Q$ each have an edge which has been assigned a tuple; extend this label to the remaining edges of $P$ and $Q$ . After performing this construction the coefficient on $m$ in $f$ from item (21) is $\binom{p^{e}-1}{\frac{p^{e}-1}{2}}^{g}$ where $g$ is the number of times that the label $(0.5,0.5)$ appears on an edge. This binomial is non-zero by Lucas’s theorem, Theorem 2.16.

$\{a,b\}$	$\{b,n+1\}$	$\{b,n+2\}$	$\{n+1,n+2\}$	$\{n+1,n+3\}$	$\{n+2,n+4\}$
$(0,1)$	$(0,0.5)$	$(0,0.5)$	$(0.5,0)$	$(0,1)$	$(0.5,0.5)$
$(1,0)$	$(0.5,0)$	$(0.5,0)$	$(0,0.5)$	$(0,1)$	$(0.5,0.5)$
$(0.5,0.5)$	$(0.5,0)$	$(0,0.5)$	$(0,0.5)$	$(1,0)$	$(0,1)$

Table 1.

\operatorname{char}(\mathbb{K})=p>2

Suppose now that $\operatorname{char}(\mathbb{K})=2$ and fix $r\geq 0$ . We modify the above construction by using Table 2 in the construction. In this case we have that

\displaystyle\bigg{(}2\sum_{i=1}^{s}\lvert E(P_{i})\rvert+3t\bigg{)}(p^{r-1}-1)\leq\nu_{r}(J_{G}).

Dividing by $p^{r}$ and taking limit as $r\rightarrow\infty$ proves the desired inequality when $\operatorname{char}(\mathbb{K})=p=2$ .

$\{a,b\}$	$\{b,n+1\}$	$\{b,n+2\}$	$\{n+1,n+2\}$	$\{n+1,n+3\}$	$\{n+2,n+4\}$
$(0,p^{r}-1)$	$(0,p^{r-1}-1)$	$(0,p^{r-1}-1)$	$(p^{r-1}-1,0)$	$(0,p^{r}-1)$	$(p^{r-1},p^{r-1}-1)$
$(p^{r}-1,0)$	$(p^{r-1}-1,0)$	$(p^{r-1}-1,0)$	$(0,p^{r-1}-1)$	$(0,p^{r}-1)$	$(p^{r-1},p^{r-1}-1)$
$(p^{r-1},p^{r-1}-1)$	$(p^{r-1}-1,0)$	$(0,p^{r-1}-1)$	$(0,p^{r-1}-1)$	$(p^{r}-1,0)$	$(0,p^{r}-1)$

Table 2.

\operatorname{char}(\mathbb{K})=p=2

∎

Corollary 4.7.

Let $G$ be a triangle path and $G_{1},\ldots,G_{r}$ be subgraphs of $G$ satisfying

(1)

the $G_{i}$ are triangle paths,
(2)

$E(G)=\bigsqcup\limits_{i=1}^{r}E(G_{i})$ ,
(3)

every triangle of $G$ is a subgraph of some $G_{i}$

Then,

\displaystyle\operatorname{ft}(J_{G})=\sum_{i=1}^{r}\operatorname{ft}(J_{G_{i}}).

Proof.

Follows from Proposition 4.6. ∎

Corollary 4.8.

Let $H$ be a triangle path. Suppose $C\subseteq V(H)$ satisfies that $H\smallsetminus C$ is a triangle path, no two vertices of $C$ are adjacent via an edge of $H$ , and every vertex of $C$ has degree two in $H$ . Then we have

\displaystyle\operatorname{ft}(J_{H\smallsetminus C})=\operatorname{ft}(J_{H})-2\lvert C\rvert.

Proof.

Since $H$ and $H\smallsetminus C$ are triangle paths, we can compute their F-threshold as $3/2$ the number of triangles plus the number of edges not in a triangle. The later two conditions on $C$ imply that the number of triangles of $H$ and $H\smallsetminus C$ are the same and the number of edges in $H$ not belonging to any triangle path is equal to the number of edges of $H\smallsetminus C$ not belonging to any triangle path plus $2\lvert C\rvert$ . ∎

We record the following lemma which we will need later which can be viewed as an analogue of Corollary 4.8.

Lemma 4.9.

Let $G$ be a graph, $C\subseteq V(G)$ , and $\{G_{i}\}_{i=1}^{r}$ the connected components of $G\smallsetminus C$ , then

\displaystyle\operatorname{LP}_{G,\mathbb{Q}}\leq\sum_{i=1}^{r}\operatorname{LP}_{G_{i},\mathbb{Q}}+2\lvert C\rvert.

Proof.

By strong duality, Theorem 2.1, it suffices to prove the statement for the dual linear program. For $i=1,\ldots,r$ , let $(\{b_{i,v,x}\}_{v\in V},\{b_{i,v,y}\}_{v\in V},\{c_{i,U}\}_{U\in\mathcal{A}_{i}})$ be an optimal solution to the linear program (10) realizing $\operatorname{LP}^{\ast}_{G_{i},\mathbb{Q}}$ . These local solutions together with the assignments $b_{v,x}:=1$ , $b_{v,y}:=1$ for $v\in C$ , and $c_{U}:=0$ for $U\in\mathcal{A}\smallsetminus\cup_{i=1}^{r}\mathcal{A}_{i}$ yield a feasible solution to the linear program (10) realizing $\operatorname{LP}^{\ast}_{G,\mathbb{Q}}$ . ∎

The next proposition shows that the F-threshold of a block graph with the two block property can be computed by a maximal triangle path packing.

Proposition 4.10.

Let $G$ be a block graph with the two block property. Let $\ell$ denote the number of leaves of $G$ and $w$ the number of connected components of $G$ which are isomorphic to a complete graph. Then, $G$ contains a subgraph $H$ satisfying

(1)

$H$ is a triangle path packing,
(2)

$V(G)=V(H)$ ,
(3)

for every block $B$ of $G$ , $B$ contains at most one triangle of $H$ ,
(4)

a block $B$ of $G$ contains a triangle of $H$ only if $\lvert\operatorname{cut}{B}\rvert$ is odd,
(5)

if $T$ is a triangle of $H$ contained in a block $B$ of $G$ , then $T$ contains two cut vertices unless $\operatorname{cut}(B)=V(B)$ in which case $T$ contains three,
(6)

a block $B$ of $G$ contains exactly one vertex of $H$ of degree one if and only if $B$ is a leaf of $G$ ,
(7)

a block $B$ of $G$ contains a vertex of $H$ of degree zero if and only if $B$ is a single vertex,
(8)

if $T$ is a triangle of $H$ contained in $B$ , $c\in\operatorname{cut}(B)\cap V(T)$ , and $\tilde{B}\neq B$ is the block of $G$ incident to $c$ , then the edge of $H$ incident to $c$ and not contained in $T$ is contained in $\tilde{B}$ ,
(9)

$\operatorname{ft}(J_{H})=n-\frac{1}{2}\ell-w$ .

The proof idea is to induce on the number of blocks of $G$ . We start by choosing a block of $G$ which is not a leaf and so that every incident block with the exception of at most one is a leaf of $G$ . In Figure 3(a), blocks $\{12,13\}$ and $\{1,2,3,4,5,6\}$ are the only such blocks. We will consider block $B:=\{1,2,3,4,5,6\}$ . Next, we choose two leaves of $B$ to delete (if $B$ has only one leaf then delete that leaf), Figure 3(b). By induction we construct a triangle path packing satisfying the above conditions, Figure 3(c). Lastly, extend the triangle path packing of the subgraph to a triangle path packing of the original graph so that the new triangle path packing has the desired properties, Figure 3(d). When the number of cut vertices of $G$ in $B$ is less than or equal to $3$ several cases must be considered to extend the triangle path packing while preserving the above properties. However, when the number of cut vertices of $G$ in $B$ is larger than $3$ then the triangle path packing can be extended by taking a Hamiltonian path on the deleted vertices.

(a) Block Graph

(b) Deleting Leaves

(d) Triangle path of original graph

Figure 3. Proof Idea of Proposition 4.10

Proof.

It is enough to show this proposition for each connected component of $G$ . If $G$ is isomorphic to a complete graph, then take $H$ to be a Hamiltonian path and the Proposition follows since $\ell=0$ and $w=1$ in this case. Thus, we may assume henceforth that $G$ is a connected graph and not isomorphic to a complete graph.

The proof is by induction on the number of blocks of $G$ which we denote by $t$ . Since $G$ is not a complete graph, $t\geq 2$ . If $t=2$ , then $G$ is two complete graphs joined at a cut vertex. In this case, $\ell=2$ and $G$ has a Hamiltonian path. Take $H$ to be a Hamiltonian path of $G$ , and it is clear that $H$ satisfies the conditions listed above.

Suppose now that $t\geq 3$ and that the Proposition has been shown for all block graphs having the two block property with at most $t-1$ blocks. Let $B$ be a block of $G$ which is not a leaf such that every block incident to $B$ with the exception of at most one is a leaf of $G$ . Let $r$ denote the number of cut vertices of $B$ . Observe that $r\geq 2$ since $B$ is not a leaf.

Case $r=2$ : Let $L$ be a leaf of $B$ . Let $\tilde{c}$ be the cut vertex of $B$ which is adjacent to $L$ . If $\lvert V(B)\rvert>2$ put $\tilde{G}:=G\smallsetminus L$ ; otherwise, put $\tilde{G}:=G\smallsetminus(L\smallsetminus\tilde{c})$ . Let $\tilde{B}$ be the image of $B$ in $\tilde{G}$ . Since $\tilde{G}$ has $t-1$ blocks, by induction there exists a triangle path $\tilde{H}$ of $\tilde{G}$ satisfying the above properties. Since $\tilde{B}$ is a leaf in $\tilde{G}$ , $\tilde{H}\mid_{\tilde{B}}$ has a vertex of degree one, say $v$ , by property (6). Consider now $\tilde{H}$ as a subgraph of $G$ , and construct $H$ a triangle path in $G$ as follows. Observe that if $\lvert V(B)\rvert=2$ , then $v=\tilde{c}$ . Otherwise, adjoin an edge from $v$ to $\tilde{c}$ . In either case $H$ is now a subgraph of $G$ containing $\tilde{c}$ as a degree one vertex. Finally, adjoin to $H$ a Hamiltonian path contained in $L$ which has a terminal vertex at $\tilde{c}$ . Now, $H$ is a triangle path of $G$ which satisfies properties (1) through (9). Moreover, $\operatorname{ft}(J_{H})$ is of the desired form by Proposition 4.6, induction hypothesis, and the fact that we obtained $H$ from $\tilde{H}$ by adding a path.

Case $r=3$ : Let $\operatorname{cut}{B}=\{c_{1},c_{2},c_{3}\}$ . Let $L_{i}$ be leaves adjacent to $B$ at $c_{i}$ for $i\in\{1,2\}$ .

Sub-case $\lvert V(B)\rvert=3$ : Let $\tilde{G}$ be the graph attained after removing $L_{1}$ , $L_{2}$ , and $B\smallsetminus\{c_{3}\}$ . Note that $\tilde{G}$ is adjacent to $B$ at $c_{3}$ and that $\tilde{G}$ may or may not be a leaf. Consider the graph $G^{{}^{\prime}}$ which is $\tilde{G}$ adjoined a whisker at the vertex $c_{3}$ . Denote by $n^{{}^{\prime}}$ and $\ell^{{}^{\prime}}$ the number of vertices and leaves of $G^{{}^{\prime}}$ , respectively. By induction hypothesis there exists a triangle path $H^{{}^{\prime}}$ for $G^{{}^{\prime}}$ satisfying the above properties and

\displaystyle\operatorname{ft}(J_{H^{{}^{\prime}}})=n^{{}^{\prime}}-\frac{1}{2}\ell^{{}^{\prime}}.

First, consider the sub-sub-case that there exists a triangle in $H^{{}^{\prime}}$ containing $c_{3}$ ; label the other vertices of this triangle as $a$ and $b$ . Construct $H$ from $H^{{}^{\prime}}$ by deleting the whisker attached at $c_{3}$ , deleting the edge $\{a,b\}$ , adding the edge $\{c_{1},c_{2}\}$ , and adding Hamiltonian paths in $L_{1}$ and $L_{2}$ which have a terminal vertex at $c_{1}$ and $c_{2}$ , respectively. Observe that $H$ is a triangle path, and by Proposition 4.6 we compute that

\displaystyle\operatorname{ft}(J_{H})=\operatorname{ft}(J_{H^{{}^{\prime}}})+(-1-\frac{1}{2}+1)+(\lvert V(L_{1})\rvert-1)+1+\lvert V(L_{2})\rvert-1)

where the term $(-1-\frac{1}{2}+1)$ is counting in $H^{{}^{\prime}}$ the deletion of a whisker, the deletion of an edge of a triangle, and that two edges of a triangle are now counted as edges belonging to a path. The desired formula on $\operatorname{ft}(J_{H})$ now follows after simplifying and using that $n=n^{{}^{\prime}}+(\lvert V(L_{1})\rvert-1)+\lvert V(L_{2})\rvert$ and that $\ell=\ell^{{}^{\prime}}+1$ .

Second, consider the sub-sub-case that $c_{3}$ has degree two in $H^{{}^{\prime}}$ ; call the neighbor of $c_{3}$ contained in $\tilde{G}$ to be $a$ . Construct $H$ from $H^{{}^{\prime}}$ by deleting the whisker, adding the edges $\{c_{1},c_{2}\}$ , $\{c_{2},c_{3}\}$ , $\{c_{1},c_{3}\}$ and adding Hamiltonian paths in $L_{1}$ and $L_{2}$ which have a terminal vertex at $c_{1}$ and $c_{2}$ , respectively. Observe that $H$ is a triangle path, and by Proposition 4.6 we compute that

\displaystyle\operatorname{ft}(J_{H})=\big{(}\operatorname{ft}(J_{H^{{}^{\prime}}})-1\big{)}+\frac{3}{2}+(\lvert V(L_{1})\rvert-1)+\lvert V(L_{2})\rvert-1)

where the $-1$ is the deletion of the whisker and the plus $\frac{3}{2}$ is the addition of the triangle. The formula for $\operatorname{ft}(J_{H})$ now follows after simplifying and using that $n=n^{{}^{\prime}}+(\lvert V(L_{1})\rvert-1)+\lvert V(L_{2})\rvert$ and that $\ell=\ell^{{}^{\prime}}+1$ .

Sub-case $\lvert V(B)\rvert>3$ : Let $\tilde{G}:=G\smallsetminus(L_{1}\cup L_{2})$ . By induction hypothesis there exists a triangle path $\tilde{H}$ of $\tilde{G}$ satisfying the desired properties. Since $\tilde{B}$ is a leaf in $\tilde{G}$ , property (6) guarantees the existence of a vertex $v$ in $\tilde{H}\cap\tilde{B}$ having degree one. Consider $\tilde{H}$ as a subgraph of $G$ , and construct $H$ a triangle path of $G$ from $\tilde{H}$ by adding the edges $\{v,c_{1}\}$ , $\{v,c_{2}\}$ , $\{c_{1},c_{2}\}$ and adding Hamiltonian paths in $L_{1}$ and $L_{2}$ which have a terminal vertex at $c_{1}$ and $c_{2}$ , respectively. Observe that $H$ is a triangle path, and by Proposition 4.6 we compute that

\displaystyle\operatorname{ft}(J_{H})=\operatorname{ft}(J_{\tilde{H}})+\frac{3}{2}+(\lvert V(L_{1})\rvert-1)+(\lvert V(L_{2})\rvert-1)

where the plus $\frac{3}{2}$ is the addition of the triangle. The desired formula on $\operatorname{ft}(J_{H})$ now follows after simplifying and using that $n=\tilde{n}+\lvert V(L_{1})\rvert+\lvert V(L_{2})\rvert$ and that $\ell=\tilde{\ell}+1$ .

Case $r>3$ : Let $c_{1}$ and $c_{2}$ be two cut vertices of $B$ which have leaves $L_{1}$ and $L_{2}$ , respectively. Let $\tilde{G}:=G\smallsetminus(L_{1}\cup L_{2})$ . By induction hypothesis there exists a triangle path $\tilde{H}$ of $\tilde{G}$ satisfying the desired properties. Consider $\tilde{H}$ as a subgraph of $G$ , and construct $H$ a triangle path of $G$ from $\tilde{H}$ by adding the edges $\{c_{1},c_{2}\}$ and adding Hamiltonian paths in $L_{1}$ and $L_{2}$ which have a terminal vertex at $c_{1}$ and $c_{2}$ , respectively. Observe that $H$ is a triangle path, and by Proposition 4.6 we compute that

\displaystyle\operatorname{ft}(J_{H})=\operatorname{ft}(J_{\tilde{H}})+(\lvert V(L_{1})\rvert-1)+1+\lvert V(L_{2})\rvert-1)

where the plus $1$ is the addition of the edge $\{c_{1},c_{2}\}$ . The desired formula on $\operatorname{ft}(J_{H})$ now follows after simplifying and using that $n=\tilde{n}+\lvert V(L_{1})\rvert+\lvert V(L_{2})\rvert$ and that $\ell=\tilde{\ell}+2$ . ∎

Corollary 4.11.

Let $G$ be a block graph having the two block property. Let $\ell$ denote the number of leaves of $G$ and $w$ the number of connected components of $G$ isomorphic to a complete graph. Then, there exists a triangle path packing $H$ of $G$ such that

\displaystyle\operatorname{ft}(J_{H})=\operatorname{ft}(J_{G})=\operatorname{LP}_{G,\mathbb{Q}}=n-\frac{1}{2}\ell-w.

Proof.

Follows from Lemma 2.10, Proposition 3.12, Proposition 4.10, and Proposition 4.2. ∎

4.2. Two Block Approximation and General Case

Next, we show how to reduce the computation of the F-threshold of a block graph to that of a block graph with the two block property.

Definition 4.12.

Let $G$ be a block graph. We call $H$ a two block approximation of $G$ if $H$ can be obtained via the following process

(1)

Enumerate the cut vertices of $G$ incident to at least three blocks of $G$ ; call this set $C$ .
(2)

For each $c\in C$ , choose two blocks incident to $c$ , say $A_{c}$ and $B_{c}$ .
(3)

Delete all edges incident to $c$ and not contained in $E(A_{c})\cup E(B_{c})$ .

Example 4.13.

Let $G$ be the block graph in Figure 4(a). Then, the graphs in Figure 4(b) and 4(c) are two possible block approximations of $G$ . Observe that the F-threshold of the graphs in Figure 4(b) and 4(c) are $8$ and $7$ , respectively.

(a) Block Graph

(b) Two Block Approximation

Figure 4. Examples of Two Block Approximation

Our next goal is to show

Theorem 4.14.

Let $G$ be a block graph, then the following quantities are equal

(1)

$\max\{\operatorname{ft}J_{H}\mid\;H\text{ is a triangle path packing of }G\}$
(2)

$\max\{\operatorname{ft}J_{K}\;\mid K\text{ is a two block approximation of }G\}$
(3)

$\operatorname{ft}(J_{G})$
(4)

$\operatorname{lct}(J_{G})$
(5)

$\max\{\operatorname{LP}_{K,\mathbb{Q}}\mid K\text{ is a two block approximation of }G\}$
(6)

$\operatorname{LP}_{G,\mathbb{Q}}$ .

Lemma 4.15.

In Theorem 4.14 items (1), (2), and (5) are equal.

Proof.

By Corollary 4.11 it follows that (1) is greater than or equal to (2) which is equal to (5). Any triangle path of $G$ has the two block property by Remark 4.5, and hence can be realized as a subgraph of a two block approximation of $G$ . This proves that (1) is less than or equal to (2). ∎

To prove Theorem 4.14 it suffices to prove that (1) is equal to (6). Indeed, (1), (2), and (5) are equal by Lemma 4.15, and equality of (1) and (3) would follow from Lemma 2.10 and Proposition 3.12. In particular, this shows that the computation of $\operatorname{ft}(J_{G})$ is independent of characteristic, and equality of (3) and (4) would follow from Theorem 1.2 and Corollary 3.14.

For the proof of Theorem 4.14 we take the following setup.

Let $G$ be a connected block graph, $K$ a two block approximation of $G$ realizing (5) in Theorem 4.14, and $H$ a path packing of $K$ given by Lemma 4.10. Take $C$ to be the set of cut vertices of $G$ incident to at least three blocks of $G$ such that in $K$ at least one of these blocks becomes a leaf or an isolated connected component. For $c\in C$ , let $B_{c,1},B_{c,2},B_{c,3},\ldots,B_{c,m_{c}}$ denote the blocks of $G$ incident to $c$ for some $m_{c}\geq 3$ . Without loss of generality, we may suppose that $N_{H}(c)\subseteq V(B_{c,1})\cup V(B_{c,2})$ and that $B_{c,3}$ becomes a leaf or an isolated connected component of $K$ . Since $B_{c,3}$ is a leaf or isolated component of $K$ , Proposition 4.10 implies that there exists a vertex $v_{c}\in V(B_{c,3})\cap V(H)$ having degree one or zero in $H$ .

Lemma 4.16.

With the above setup suppose that $C=\varnothing$ . Then $G$ satisfies the conclusions of Theorem 4.14. Moreover, $\operatorname{LP}_{K,\mathbb{Q}}=\operatorname{LP}_{G,\mathbb{Q}}$ .

Proof.

Because $C=\varnothing$ , $\ell_{K}=\ell_{G}$ and $w_{K}=w_{G}$ . Now, the result follows by Lemma 2.10, Proposition 4.2, and Corollary 4.11. ∎

Lemma 4.17.

With the setup from above let $c\in C$ . Then

(1)

$c$ does not belong to a triangle of $H$ ,
(2)

each vertex of $N_{H}(c)$ is not contained in a triangle of $H$ ,
(3)

$\lvert N_{H}(c)\rvert=2$ , and
(4)

$N_{H}(c)\not\subseteq B_{c,j}$ for $j=1,2$ ,
(5)

no two vertices of $C$ are adjacent via an edge of $H$ .

Proof.

(1)

Suppose by contradiction that $c$ belongs to a triangle of $H$ , i.e. that without loss of generality there exists vertices $a,b\in B_{c,1}$ so that $\{a,b\}$ , $\{a,c\}$ , and $\{b,c\}$ belong to $E(H)$ . Let $\tilde{H}$ be the triangle path defined from $H$ by deleting the edges $\{c,a\}$ and $\{c,b\}$ and adding the edge $\{c,v_{c}\}$ . Notice that no new cycles are created in $\tilde{H}$ after these modifications or else it would contradict $G$ being a block graph. Moreover,

$\displaystyle\operatorname{ft}J_{\tilde{H}}=\operatorname{ft}J_{H}+\frac{1}{2}$

because in obtaining $\tilde{H}$ from $H$ we delete two edges of $H$ having weight $\frac{1}{2}$ , increase the weight of one edge of $H$ from weight $\frac{1}{2}$ to weight $1$ in $\tilde{H}$ , and add one edge to $\tilde{H}$ having weight $1$ . This contradicts our choice of $K$ via Lemma 4.15.
(2)

Suppose by contradiction that there exists $a\in N_{H}(c)\cap V(B_{c,1})$ and vertices $b$ and $d$ of $B_{c,1}$ with $\{a,b\}$ , $\{a,d\}$ , and $\{b,d\}$ edges of $H$ . Construct $\tilde{H}$ a triangle path from $H$ by deleting the edges $\{c,a\}$ and $\{b,d\}$ and adding the edge $\{c,v_{c}\}$ . Then, $\operatorname{ft}J_{\tilde{H}}=\frac{1}{2}+\operatorname{ft}J_{H}$ ; a contradiction.
(3)

By Item (2) $\lvert N_{H}(c)\rvert$ is $1$ or $2$ . Suppose by contradiction that $N_{H}(c)=\{a\}\subseteq B_{i,1}$ . Construct $\tilde{H}$ from $H$ by adding the edge $\{c,v_{c}\}$ . Then, $\operatorname{ft}(J_{\tilde{H}})>\operatorname{ft}(J_{H})$ ; a contradiction.
(4)

Suppose by contradiction that $\{a,b\}=N_{H}(c)\subseteq B_{c,1}$ . By the previous item, $a$ and $b$ do not belong to a triangle of $H$ . If $a$ and $b$ have degree two in $H$ , then define $\tilde{H}$ from $H$ by adding the edge $\{a,b\}$ and the edge $\{c,v_{c}\}$ . In the case that $a$ has degree one and $b$ has degree two in $H$ , define $\tilde{H}$ from $H$ by deleting the edge $\{c,b\}$ and adding the edges $\{a,b\}$ and $\{c,v_{c}\}$ . The case that $b$ has degree one and $a$ has degree two in $B_{c,1}$ is handled analogously. If $a$ and $b$ both have degree one in $H$ , define $\tilde{H}$ from $H$ by deleting the edge $\{a,c\}$ and adding the edges $\{a,b\}$ and $\{c,v_{c}\}$ . Notice that in all cases that $\tilde{H}$ is a triangle path, a subgraph of $G$ , and that $\operatorname{ft}(J_{\tilde{H}})>\operatorname{ft}(J_{H})$ ; a contradiction.
(5)

Suppose by contradiction that $c,c^{{}^{\prime}}\in C$ and that $\{c,c^{{}^{\prime}}\}\in E(H)$ . Construct $\tilde{H}$ a triangle path from $H$ by deleting the edge $\{c,c^{{}^{\prime}}\}$ and adding the edges $\{c,v_{c}\}$ and $\{c^{{}^{\prime}},v_{c^{{}^{\prime}}}\}$ . Then, $\operatorname{ft}(J_{\tilde{H}})>\operatorname{ft}(J_{H})$ ; a contradiction.

∎

Proof of Theorem 4.14.

Let the setup be as above. We induce on the number of blocks of $G$ . If the number of blocks of $G$ is one, then there is nothing to prove. Suppose that the number of blocks of $G$ is strictly larger than one. If $C=\varnothing$ , then we are done by Lemma 4.16. Suppose that $C\neq\varnothing$ . Let $\{G_{i}\}_{i=1}^{r}$ denote the connected components of $G\smallsetminus C$ . For $1\leq i\leq r$ , let $H_{i}$ denote the restriction of $H$ to $G_{i}$ . We show

Claim 1.

For $1\leq i\leq r$ ,

\displaystyle\operatorname{ft}(J_{H_{i}})=\operatorname{LP}_{G_{i},\mathbb{Q}}.

Proof of Claim 1.

By induction on number of blocks and the fact that the number of blocks of $G_{i}$ is less than the number of blocks of $G$ , it suffices to show that

\displaystyle\operatorname{ft}(J_{H_{i}})=\max\{\operatorname{ft}J_{\tilde{H}_{i}}\mid\;\tilde{H}_{i}\text{ is a triangle path of }G_{i}\}

for every $1\leq i\leq r$ . Suppose by contradiction that $\operatorname{ft}(J_{H_{i}})<\operatorname{ft}(J_{\tilde{H}_{i}})$ for some fixed choice of $1\leq i\leq r$ and a triangle path $\tilde{H}_{i}$ of $G_{i}$ . Let $c_{1},\ldots,c_{t}$ be the vertices of $C$ which are adjacent to some vertex of $G_{i}$ via an edge of $H$ ; call this vertex $c_{j}^{{}^{\prime}}$ for $1\leq j\leq t$ . Construct $\tilde{H}$ from $H$ as follows.

(i)

Delete the edges $\{c_{j},c_{j}^{{}^{\prime}}\}$ for $1\leq j\leq t$ .
(ii)

Add the edges $\{c_{j},v_{c_{j}}\}$ for $1\leq j\leq t$ .
(iii)

Replace $H_{i}$ on $G_{i}$ by $\tilde{H}_{i}$ .

Now, $\tilde{H}$ is a triangle path. Indeed parts (i) and (ii) of the construction do not create any cycles in $\tilde{H}$ ; otherwise, $G$ could not be a block graph. After performing parts (i) and (ii), $H_{i}$ forms its own connected component by Lemma 4.17 item (4). Thus after performing operation (iii) $\tilde{H}$ will remain a triangle path. Clearly, $\operatorname{ft}(J_{\tilde{H}})>\operatorname{ft}(J_{H})$ which contradicts our choice of $H$ , Lemma 4.15.

Observe that

$\displaystyle\operatorname{ft}(J_{H})\leq\operatorname{LP}_{G,\mathbb{Q}}$	$\displaystyle\leq\sum_{i=1}^{r}\operatorname{LP}_{G_{i},\mathbb{Q}}+2\lvert C\rvert$	$\displaystyle(\text{Lemma }\ref{lem_LP_deleting_vertices})$
	$\displaystyle=\sum_{i=1}^{r}\operatorname{ft}(J_{H_{i}})+2\lvert C\rvert$	$\displaystyle(\text{Claim }\ref{claim_ft_H_i_equals_LP_G_i})$
	$\displaystyle=\operatorname{ft}(J_{H})$	$\displaystyle(\text{Lemma }\ref{lem_vertices_incident_leaves_blocks}\text{ parts }\eqref{item_vertex_not_in_triangle},\,\eqref{item_nbrs_not_in_triangle},\,\eqref{item_vertex_has_two_nbrs},\,\eqref{item_vertices_disconnected}$
$\displaystyle\text{ and Corollary }\ref{cor_ft_deleting_vertices}).$

This proves equality of (1) and (6) and completes the proof. ∎

Corollary 4.18.

Conjecture 1.3 is true when $G$ is a block graph.

Corollary 4.19.

If $G$ is a tree, then

\displaystyle r(G)=\operatorname{ft}(J_{G}).

Proof.

By Theorem 4.14, $\operatorname{ft}(J_{G})=\max\{\operatorname{ft}J_{K}\;\mid K\text{ is a two block approximation of }G\}$ . Any two block approximation $K$ of $G$ is a semi-path of $G$ since $G$ is a tree, and hence $\operatorname{ft}(J_{G})\leq r(G)$ . The inequality $r(G)\leq\operatorname{ft}(J_{G})$ is Equation (15). ∎

In the next section we show the stronger statement that for a tree $G$

\displaystyle r(G)=\operatorname{ht}(J_{G}).

4.3. Remark on the Case of Chordal Graphs

The next proposition shows that if Conjecture 1.3 is true for chordal graphs, then the proof techniques used for block graphs will not suffice. We show:

Proposition 4.20.

There exists a chordal graph $G$ such that

\displaystyle\max\{\operatorname{ft}(J_{H})\mid H\subseteq G\text{ is triangle path packing}\}<\operatorname{LP}_{G,\mathbb{Q}}.

Proof.

Let $G$ be the graph below. Let $G_{1}$ and $G_{2}$ be the subgraphs of $G$ induced on the vertices $\{1,2,3,4,5,6,13,14\}$ and $\{7,8,9,10,11,12,15,16\}$ , respectively. Let $H$ be a triangle path packing of $G$ maximal wrt $\operatorname{ft}(J_{H})$ . Let $H_{1}$ and $H_{2}$ be the restriction of $H$ to $G_{1}$ and $G_{2}$ respectively. For $i=1,2$ , let $t_{i}$ , $e_{i}$ denote the number of triangles of $H_{i}$ and edges of $H_{i}$ not belonging to any triangle, respectively.

Figure 5. Chordal Graph

Claim 2.

$e_{1}+\frac{3}{2}t_{1}=e_{2}+\frac{3}{2}t_{2}$ .

Proof of Claim 2.

Without loss of generality suppose $e_{1}+\frac{3}{2}t_{1}<e_{2}+\frac{3}{2}t_{2}$ . Construct $\tilde{H}$ from $H$ by deleting $H_{1}$ and replicating $H_{2}$ on $V(G_{1})$ . Then, $\tilde{H}$ is a triangle path packing with $\operatorname{ft}(J_{H})<\operatorname{ft}(J_{\tilde{H}})$ ; a contradiction.

It follows from Proposition 4.6 and Claim 2 that $\operatorname{ft}(J_{H})$ is an integer. However, $\operatorname{LP}_{G,\mathbb{Q}}=14.5$ which can be realized by the following assignment

$\displaystyle(a_{[1,2]},b_{[1,2]})$	$\displaystyle=(0.0,1.0)$	$\displaystyle(a_{[9,10]},b_{[9,10]})$	$\displaystyle=(0.0,0.5)$	$\displaystyle(a_{[4,13]},b_{[4,13]})$	$\displaystyle=(0.0,0.5)$
$\displaystyle(a_{[2,3]},b_{[2,3]})$	$\displaystyle=(0.0,1.0)$	$\displaystyle(a_{[10,11]},b_{[10,11]})$	$\displaystyle=(0.0,0.5)$	$\displaystyle(a_{[7,9]},b_{[7,9]})$	$\displaystyle=(0.0,0.0)$
$\displaystyle(a_{[3,4]},b_{[3,4]})$	$\displaystyle=(0.0,0.5)$	$\displaystyle(a_{[11,12]},b_{[11,12]})$	$\displaystyle=(0.5,0.5)$	$\displaystyle(a_{[7,10]},b_{[7,10]})$	$\displaystyle=(0.0,0.0)$
$\displaystyle(a_{[4,5]},b_{[4,5]})$	$\displaystyle=(0.5,0.5)$	$\displaystyle(a_{[1,3]},b_{[1,3]})$	$\displaystyle=(0.0,0.0)$	$\displaystyle(a_{[7,12]},b_{[7,12]})$	$\displaystyle=(0.5,0.0)$
$\displaystyle(a_{[5,6]},b_{[5,6]})$	$\displaystyle=(0.0,0.5)$	$\displaystyle(a_{[1,6]},b_{[1,6]})$	$\displaystyle=(1.0,0.0)$	$\displaystyle(a_{[9,15]},b_{[9,15]})$	$\displaystyle=(0.5,0.0)$
$\displaystyle(a_{[6,7]},b_{[6,7]})$	$\displaystyle=(0.5,0.0)$	$\displaystyle(a_{[3,6]},b_{[3,6]})$	$\displaystyle=(0.0,0.0)$	$\displaystyle(a_{[10,12]},b_{[10,12]})$	$\displaystyle=(0.0,0.5)$
$\displaystyle(a_{[7,8]},b_{[7,8]})$	$\displaystyle=(0.5,0.5)$	$\displaystyle(a_{[3,13]},b_{[3,13]})$	$\displaystyle=(0.0,0.5)$	$\displaystyle(a_{[10,15]},b_{[10,15]})$	$\displaystyle=(0.5,0.0)$
$\displaystyle(a_{[8,9]},b_{[8,9]})$	$\displaystyle=(0.5,0.5)$	$\displaystyle(a_{[4,6]},b_{[4,6]})$	$\displaystyle=(0.0,0.0)$	$\displaystyle(a_{[13,14]},b_{[13,14]})$	$\displaystyle=(0.0,1.0)$
$\displaystyle(a_{[15,16]},b_{[15,16]})$	$\displaystyle=(1.0,0.0)$

∎

5. Binomial Edge Ideals of König type

It is a well-known fact that bipartite graphs satisfy the König–Egervary property, i.e. the size of a minimal vertex cover equals the size of a maximal matching. For (monomial) edge ideals the König-Egervary property translates into the statement that the monomial grade of the ideal is equal to its height. In [HHM22] the authors introduce the notion of graded ideals of König type as a way to extend the König–Egervary property to other homogeneous ideals of a polynomial ring. Because in this section we are only concerned with binomial edge ideals of König type, we (by abuse of notation) define a graph $G$ to be of König type if it satisfies the following characterization:

Definition 5.1 ([HHM22] Theorem 3.5).

A graph $G$ is said to be of König type if $r(G)=\operatorname{ht}(J_{G})$ .

In this section we prove that every graph of König type satisfies Conjecture 1.3, we give a new combinatorial characterization of the König type property, and we use this characterization to prove that every tree is of König type, and hence give a second proof that trees satisfy Conjecture 1.3. Lastly, we give an example of a bipartite graph which is not of König type.

Proposition 5.2.

If $G$ is of König type, then $\operatorname{ft}(J_{G})=r(G)$ . In particular, Conjecture 1.3 holds for every graph $G$ that is of König type.

Proof.

Follows immediately from Equation (15) and Definition 5.1. ∎

The following lemma gives a combinatorial characterization for a graph to be of König type. We use this characterization to show that trees are of König type.

Lemma 5.3.

Let $G$ be a graph. Then, $G$ is of König type if and only if there exists a semi-path $P$ and a choice of distinct vertices $T\subseteq V(G)$ , possibly empty, with the property that

(1)

$r(G)=\lvert E(P)\rvert$ ,
(2)

for all $v\in T$ , $v$ has degree two in $P$ ,
(3)

for all $v,w\in T$ , $\{v,w\}$ is not an edge of $P$ ,
(4)

the number of connected components and the number of vertices of $\widehat{G\smallsetminus T}$ equals the number of connected components and the number of vertices of $\widehat{P\smallsetminus T}$ , respectively.

Proof.

We prove the backward implication. Suppose that a semi-path $P$ of $G$ and a choice of distinct vertices $T\subseteq V(P)$ have been chosen satisfying properties (1) through (4). It is enough to show that $\operatorname{ht}(J_{G})\leq r(G)$ .

Let $c:=c_{G}(T)$ be the number of connected components of $\widehat{G\smallsetminus T}$ and $G_{1},\ldots,G_{c}$ its connected components. Let $Q:=(\{X_{i},Y_{i}\}_{i\in T},J_{\tilde{G}_{1}},\ldots,J_{\tilde{G}_{c}})$ the ideal as defined in Proposition 2.4. Then,

\displaystyle\operatorname{ht}(Q)

\displaystyle=2\cdot\lvert T\rvert+\sum_{i=1}^{c}(\lvert V(G_{i})\rvert-1)

Let $P_{i}$ denote the subgraph of $G_{i}$ given by $G_{i}\cap P$ for $1\leq i\leq c$ . Property (4) implies that $P_{i}$ is a Hamiltonian path of $G_{i}$ , and in particular that

\displaystyle\lvert E(P_{i})\rvert=\lvert V(G_{i})\rvert-1.

Let $E^{{}^{\prime}}$ denote the set of edges of $P$ which are incident to a vertex of $T$ . By assumptions (2) and (3), $\lvert E^{{}^{\prime}}\rvert=2\cdot\lvert T\rvert$ . The edges of $P$ can be partitioned into those which belong to some $P_{i}$ and those which belong to $E^{{}^{\prime}}$ . We compute that

	$\displaystyle r(G)$	$\displaystyle=\lvert E(P)\rvert\phantom{aaaaaaaaaaaaaaaaaaaa}(\text{by \eqref{item_konig_1}})$
		$\displaystyle=\lvert E^{{}^{\prime}}\rvert+\sum_{i=1}^{c}\lvert E(P_{i})\rvert$
		$\displaystyle=2\cdot\lvert T\rvert+\sum_{i=1}^{c}(\lvert V(G_{i})\rvert-1)$
		$\displaystyle=\operatorname{ht}(Q).$

This proves that $\operatorname{ht}J_{G}\leq\operatorname{ht}Q=r(G)$ .

Next, suppose that $G$ is of König type. Let $P$ be a semi-path realizing $r(G)$ . Consider the vector $\mathbf{{a}}=(a_{e})_{e\in E(G)}$ given by

\displaystyle a_{e}=\begin{cases}1,&e\in E(P)\\ 0,&\text{otherwise}\end{cases}

Then, $\mathbf{{a}}:=(a_{e})$ is an optimal solution of the linear program (4). Let $(\mathbf{{b}},\mathbf{{c}}):=(\{b_{v}\}_{v\in V},\{c_{U}\}_{U\in\mathcal{A}})$ be an optimal solution with values in $\mathbb{Z}$ of the linear program (7) having the form guaranteed by Lemma 3.3, and let $T$ and $U_{1},\ldots,U_{c}$ be as in Lemma 3.3.

Let $A$ be the below $\left(2^{\lvert V\rvert}-1\right)\times\lvert E\rvert$ matrix, $\mathbf{X}$ the vector of indeterminates of length $\lvert E\rvert$ , $\mathbf{{1}}$ vector of $1$ ’s of length $\lvert E\rvert$ , and $\mathbf{{d}}$ the vector of length $2^{\lvert V\rvert-1}$ realizing the linear program (4), i.e. algorithm (4) can be expressed as

(22)

\begin{split}\operatorname*{maximize}\hskip 3.00003pt&Z_{\operatorname{PP},G}:=\mathbf{{1}}^{\operatorname{T}}\,\mathbf{X}\\ \operatorname{subject\,to:}&\phantom{}\\ &\mathbf{X}\in\mathbbm{k}_{\geq 0}\\ &A\cdot\mathbf{{X}}\leq\mathbf{{d}}\end{split}

Let $A_{i}$ denote the $i$ -th column of $A$ , and let $a_{j}^{\operatorname{T}}$ denote the $j$ -th row of $A$ .

Because $G$ is of König type the cost of these optimal solutions are equal, and complementary slackness, Theorem 2.3, holds between these pair of solutions.

We prove part (2). Choose $v\in T$ , equivalently, $b_{v}=1$ . Let $a_{v}^{\operatorname{T}}$ denote the row of $A$ corresponding to vertex $v$ . By complementary slackness Theorem 2.3.(2) we have that

\displaystyle 2=a_{v}^{\operatorname{T}}\mathbf{{a}}=\sum_{e\text{ incident to }v}a_{e}.

This shows that there are two edges of $P$ incident with $v$ .

We prove part (3). Let $v\in T$ , i.e. $b_{v}=1$ , and $e=\{v,w\}$ an edge of $P$ , then we want to show that $w\notin T$ . Let $A_{e}$ denote column of $A$ corresponding to the edge $e$ . Theorem 2.3.(1) implies that

(23)

1=(\mathbf{{b}},\mathbf{{c}})^{\operatorname{T}}A_{e}=b_{v}+b_{w}+\sum_{\begin{subarray}{c}U\in\mathcal{A}\\ e\in G[U]\end{subarray}}c_{U}

Since $b_{v}=1$ , Equation (23) implies that $b_{w}=0$ . Hence $w\notin T$ by Lemma 3.3.

We prove part (4). Fix $1\leq i\leq c$ . Let $a_{U_{i}}^{\operatorname{T}}$ denote the row of $A$ corresponding to $U_{i}$ . By the construction of $\mathbf{{c}}$ , $c_{U_{i}}=1$ . Theorem 2.3.(2) implies that

\displaystyle\lvert U_{i}\rvert-1=a_{U_{i}}^{\operatorname{T}}\cdot\mathbf{{a}}=\lvert E(P)\cap E(U_{i})\rvert.

This shows that $P$ restricted to $U_{i}$ induces a Hamiltonian path for every $1\leq i\leq c$ and (4) follows. ∎

5.1. Trees are of König Type

We use Lemma 5.3 to show that trees are of König type. The proof idea is to pick a maximal semi-path and to recursively delete vertices incident with edges not belonging to the semi-path so at the end we are left with no edges between connected components of the semi-path and no two deleted vertices are adjacent.

We set up notation below. Throughout this subsection let $G$ be a tree. Let $P_{1},\ldots,P_{\ell}$ be disjoint paths in $G$ with $r(G)=\sum_{i=1}^{\ell}\lvert E(P_{i})\rvert$ . Put

	$\displaystyle E_{L}:=\bigg{\{}\vphantom{y^{2}}\{v,w\}\in E(G)\mid$	$\displaystyle v\in P_{i}\text{ and }w\in P_{j}\text{ for some }1\leq i<j\leq\ell$
		$\displaystyle\text{ or }\,v\in P_{i}\text{ for some }1\leq i\leq\ell\text{ and }w\notin P_{j}\text{ for any }1\leq j\leq\ell\bigg{\}}.$

Put $V_{L}:=\{V(e)\mid e\in E_{L}\}$ and

\displaystyle B_{v}

\displaystyle:=\{v\in V_{L}\mid v\text{ is an initial or terminal vertex of some }P_{i}\text{ or }v\notin P_{i}\text{ for any }1\leq i\leq\ell\}.

Definition 5.4.

Let $v\in V(G)$ . A subtree of $G$ based at $v$ , denoted $T_{v}$ , is the subtree of $G$ constructed as follows:

	$\displaystyle T_{v,k}$	$\displaystyle:=\varnothing,k\leq 0$
	$\displaystyle T_{v,1}$	$\displaystyle:=\{v\}$
	$\displaystyle T_{v,2k}$	$\displaystyle:=\{v\in V_{L}\mid\exists w\in T_{2k-1}\text{ with }\{v,w\}\in E_{L}\},k\geq 1$
	$\displaystyle T_{v,2k+1}$	$\displaystyle:=\{v\in V(P_{i})\mid\exists w\in T_{2k}\text{ with }\{v,w\}\in E(P_{i})\text{ for some }1\leq i\leq\ell\},k\geq 1.$

Then, $T_{v}$ is the induced subgraph of $G$ on the set of vertices $\bigcup_{k\in\mathbb{Z}}T_{k}$ .

Lemma 5.5.

Let $T_{v}$ be the subtree of $G$ based at $v$ . For $N\neq N^{{}^{\prime}}$ , $T_{v,N}\cap T_{v,N^{{}^{\prime}}}=\varnothing$ .

Proof.

Clear because $T_{v,N}\subseteq\{w\in V(G)\mid d(v,w)=N\}$ , and the later sets are disjoint for $N\neq N^{{}^{\prime}}$ since $G$ is a tree. ∎

The following definition and lemma can be viewed as analogues of the the statement that there are no augmenting paths with respect to a choice of maximal matching in a bipartite graph.

Definition 5.6.

A $(v,w)$ -alternating path with respect to $P$ (respectively a $v$ -alternating path with respect to $P$ ) is a set of distinct vertices $v_{1},v_{2},\ldots,v_{2k-1},v_{2k}$ where $1\leq k\in\mathbb{Z}$ satisfying

(1)

$\{v_{2i-1},v_{2i}\}\in E_{L}$ for $1\leq i\leq k$ ,
(2)

$\{v_{2i},v_{2i+1}\}\in E(P_{j_{i}})$ for $1\leq i\leq k-1$ and for some $1\leq j_{i}\leq\ell$ ,
(3)

$v_{1}=v$ and $v_{2k}=w$ (respectively, $v_{1}=v$ ).

Lemma 5.7.

Let $G$ be a graph. Then, $G$ does not have an alternating path $v_{1}$ , $v_{2},\ldots,$ $v_{2k-1}$ , $v_{2k}$ with both $v_{1}\in B_{v}$ and $v_{2k}\in B_{v}$ .

Proof.

If such an alternating path were to exist, then we could construct a semi-path having more edges than $P$ by adding to $P$ the edges belonging to (1) of Definition 5.6 and deleting from $P$ the edges belonging to (2) of Definition 5.6. ∎

Algorithm 5.8.

Input: Semi-path $P$ of a tree $G$ Output: $T\subseteq\bigcup_{i=1}^{\ell}V(P_{i})$ satisfying conditions (2) - (3) in Lemma 5.3, and every edge of $E_{L}$ contains a vertex belonging to $T$ .

(1)

Initialize $i=0$ and $T_{0,k}=\varnothing$ for $k\in\mathbb{Z}$ .
(2)
While $B_{v}\not\subseteq\bigcup\limits_{n=0}^{i}\bigcup\limits_{k\geq 1}T_{n,k}$ , repeat the following steps:
1. (a)
  
  Increment $i$ ,
2. (b)
  
  Pick a vertex $v_{i}\in B_{v}\smallsetminus\bigcup\limits_{n=0}^{i-1}\bigcup\limits_{k\geq 1}T_{n,k}$ .
3. (c)
  
  Let $T_{i}$ denote the subtree of $G$ based at $v_{i}$ , and for $k\in\mathbb{Z}$ , let $T_{i,k}$ denote the subsets of $T_{i}$ as constructed in Definition 5.4.
(3)

Put $S:=V_{L}\smallsetminus\bigcup\limits_{n=0}^{i}\bigcup\limits_{k\geq 1}T_{n,k}$ .
(4)
While $S\neq\varnothing$ , repeat the following steps:
1. (a)
  
  Increment $i$ ,
2. (b)
  
  Choose $1\leq j\leq\ell$ minimally so that there exists a vertex $v_{i}\in V(P_{j})\cap S$ ,
3. (c)
  
  Let $T_{i}$ denote the subtree of $G$ based at $v_{i}$ , and for $k\in\mathbb{Z}$ , let $T_{i,k}$ denote the subsets of $T_{i}$ as constructed in Definition 5.4,
4. (d)
  
  Go back to part (3) of Algorithm 5.8.
(5)

Put $N:=i$ .
(6)

For $1\leq i\leq N$ , define $T^{\operatorname{even}}_{i}:=\bigcup_{k\in\mathbb{Z}}T_{i,2k}$ and $T^{\operatorname{odd}}_{i}:=\bigcup_{k\in\mathbb{Z}}T_{i,2k+1}$ .
(7)

Put $T:=\bigcup_{i=1}^{N}T_{i}^{\operatorname{even}}$ .

Theorem 5.9.

Algorithm 5.8 is correct, and property (4) of Lemma 5.3 is satisfied by the choice of $T$ . Consequently, $G$ is of König type.

Proof.

First, we remark that each while-loop of Algorithm 5.8 terminates because $B_{v}$ and $V_{L}$ are finite, and $\{\bigcup_{n=0}^{i}\bigcup_{k\geq 1}T_{n,k}\}_{i=1}^{N}$ form a strictly ascending sequence of sets each containing more elements of $B_{v}\cup V_{L}$ than their predecessors.

Claim 3.

For $i\neq j$ , $T^{\operatorname{even}}_{i}\cap T^{\operatorname{odd}}_{j}=\varnothing$ .

Proof of Claim 3.

Suppose by contradiction that $T^{\operatorname{even}}_{i}\cap T^{\operatorname{odd}}_{j}\neq\varnothing$ . Choose $a$ even and $b$ odd satisfying the following

(i)

there exists $w\in T_{i,a}\cap T_{j,b}$ ,
(ii)

if $q_{1}$ (respectively $q_{2}$ ) is the $(v_{i},w)$ -alternating path (respectively $(v_{j},w)$ -alternating path), then the vertices of $q_{1}$ and $q_{2}$ intersect only at $w$ .

Let $w^{{}^{\prime}}$ be the vertex of $q_{2}$ adjacent to $w$ . Then, there is a $(v_{i},v_{j})$ -augmenting path by concatenating $q_{1}$ and $q_{2}$ along the edge $\{w,w^{{}^{\prime}}\}$ . Without loss of generality, suppose that $i<j$ , then $v_{j}\in V(T_{i})$ by construction of $T_{i}$ , but this contradicts the choice of $v_{j}\in V_{L}\smallsetminus\bigcup_{n=1}^{j-1}\bigcup_{k\geq 1}T_{n,k}$ which proves the claim.

$T\subseteq\bigcup_{i=1}^{\ell}V(P_{i})$ : Suppose by contradiction that there exists $w\in T\smallsetminus\bigcup_{i=1}^{\ell}V(P_{i})$ . Since $w\in B_{v}$ and $w\in T_{i}^{\operatorname{even}}$ for some $1\leq i\leq N$ , it must be the case that $v_{i}\in B_{v}$ by part 2 of Algorithm 5.8. This contradicts Lemma 5.7.

$T$ satisfies (2) of Lemma 5.3: $T$ does not contain any initial nor terminal points of any $P_{i}$ by a similar argument to the previous paragraph.

$T$ satisfies (3) of Lemma 5.3: If not, we would contradict $T_{i}^{\operatorname{even}}\cap T_{j}^{\operatorname{odd}}=\varnothing$ .

$T$ satisfies (4) of Lemma 5.3: The construction of $T$ shows that for each edge $\{v,w\}\in E_{L}$ that

(i)

$w\in T$ if $v\notin\bigcup_{i=1}^{\ell}P_{i}$ , and that
(ii)

$v\in T$ or $w\in T$ if $\{v,w\}\in E_{L}$ .

Thus, as sets $\widehat{G\smallsetminus T}$ and $\widehat{P\smallsetminus T}$ are equal, and hence condition (4) is trivially satisfied. Hence by Lemma 5.3 $G$ is of König type. ∎

5.2. Example of Bipartite Graph Not of König Type

The following example shows that there exist bipartite graphs which are not of König type.

Example 5.10.

For this example let $G$ be the graph in Figure 6.

Figure 6. Non-König type Non-Unmixed Bipartite Graph

One can check that $r(G)=12$ , $\operatorname{LP}_{G,\mathbb{Q}}=12.5$ , and $\operatorname{ht}J_{G}=13$ . One realization of $\operatorname{LP}_{G,\mathbb{Q}}$ is via the following assignment

$\displaystyle(a_{[1,2]},b_{[1,2]})$	$\displaystyle=(0.5,0.5)$	$\displaystyle(a_{[6,7]},b_{[6,7]})$	$\displaystyle=(0.0,0.5)$	$\displaystyle(a_{[11,12]},b_{[11,12]})$	$\displaystyle=(1.0,0.0)$
$\displaystyle(a_{[2,3]},b_{[2,3]})$	$\displaystyle=(0.5,0.5)$	$\displaystyle(a_{[7,8]},b_{[7,8]})$	$\displaystyle=(0.5,0.0)$	$\displaystyle(a_{[13,14]},b_{[13,14]})$	$\displaystyle=(0.5,0.5)$
$\displaystyle(a_{[3,4]},b_{[3,4]})$	$\displaystyle=(0.5,0.5)$	$\displaystyle(a_{[8,9]},b_{[8,9]})$	$\displaystyle=(0.5,0.5)$	$\displaystyle(a_{[1,6]},b_{[1,6]})$	$\displaystyle=(0.0,0.5)$
$\displaystyle(a_{[4,5]},b_{[4,5]})$	$\displaystyle=(0.0,0.5)$	$\displaystyle(a_{[9,10]},b_{[9,10]})$	$\displaystyle=(0.5,0.5)$	$\displaystyle(a_{[7,12]},b_{[7,12]})$	$\displaystyle=(0.0,1.0)$
$\displaystyle(a_{[5,6]},b_{[5,6]})$	$\displaystyle=(0.5,0.5)$	$\displaystyle(a_{[10,11]},b_{[10,11]})$	$\displaystyle=(0.5,0.0)$	$\displaystyle(a_{[4,13]},b_{[4,13]})$	$\displaystyle=(0.5,0.0)$
$\displaystyle(a_{[10,13]},b_{[10,13]})$	$\displaystyle=(0.0,0.5)$

This graph is not unmixed. For example, $\{1,3\}$ is a cut set of $G$ and the corresponding prime ideal has height $14$ . This raises

Question 5.11.

Is every unmixed bipartite graph of König type?

Bipartite graphs having unmixed binomial edge ideal were studied in [BMS18]. Bipartite graphs with Cohen–Macaulay binomial edge ideal were characterized in [BMS18, Theorem 6.1]. As a consequence of their characterization, Cohen–Macaulay bipartite graphs are traceable. Herzog et al. proved that traceable implies König type [HHM22, Proposition 3.6.(a)], and thus in particular Cohen–Macaulay bipartite graphs are of König type.

6. $\operatorname{LP}_{G,\mathbb{Q}}$ and Traceable Graphs

In this section, we consider the relationship between maximality of $\operatorname{LP}_{G,\mathbb{Q}}$ of a graph and the graph being traceable. Recall that a graph is called traceable if it has a Hamiltonian path, Definition 2.6.

Proposition 6.1.

If $G$ is a traceable graph on $n$ vertices, then $\operatorname{ft}(J_{G})=\operatorname{LP}_{G,\mathbb{Q}}=n-1$ .

Proof.

We have the graph containments $P_{n}\subseteq G\subseteq K_{n}$ . The result follows from monotonicity of $\operatorname{LP}_{G,\mathbbm{k}}$ and $\operatorname{ft}(J_{P_{n}})=\operatorname{LP}_{K_{n},\mathbb{Q}}=n-1$ . ∎

Remark 6.2.

The above proof shows that for any graph $G$ on $n$ vertices, $\operatorname{ft}(J_{G})\leq n-1$ .

Example 6.3 shows that there exists a graph $G$ with $\operatorname{LP}_{G,\mathbb{Q}}=\lvert V\rvert-1$ yet $G$ is non-traceable. Computations in Macaulay2 [GS] suggest that $\operatorname{ft}(J_{G})$ may agree with $\lvert V\rvert-1$ independent of characteristic in Example 6.3.

Example 6.3.

Throughout this example let $G$ denote the graph in Figure 7. Observe that $G$ is not traceable.

Figure 7. Non-traceable graph

Observe that deleting edges $\{7,8\}$ and $\{8,9\}$ produces a triangle path as a subgraph and that this triangle path has F-threshold equal to $8.5$ by Proposition 4.6. It follows from Proposition 2.10 that $8.5\leq\operatorname{ft}(J_{G})$ . However, it can be computed that $\operatorname{LP}_{G,\mathbb{Q}}=9$ and one such realization is as follows

$\displaystyle(a_{[1,2]},b_{[1,2]})$	$\displaystyle=(1.0,0.0)$	$\displaystyle(a_{[3,5]},b_{[3,5]})$	$\displaystyle=(1.0,0.0)$	$\displaystyle(a_{[7,8]},b_{[7,8]})$	$\displaystyle=(0.5,0.0)$
$\displaystyle(a_{[2,3]},b_{[2,3]})$	$\displaystyle=(0.5,0.0)$	$\displaystyle(a_{[4,6]},b_{[4,6]})$	$\displaystyle=(0.5,0.5)$	$\displaystyle(a_{[7,9]},b_{[7,9]})$	$\displaystyle=(0.5,0.0)$
$\displaystyle(a_{[2,4]},b_{[2,4]})$	$\displaystyle=(0.5,0.0)$	$\displaystyle(a_{[5,7]},b_{[5,7]})$	$\displaystyle=(1.0,0.0)$	$\displaystyle(a_{[8,9]},b_{[8,9]})$	$\displaystyle=(0.5,0.0)$
$\displaystyle(a_{[3,4]},b_{[3,4]})$	$\displaystyle=(0.0,0.5)$	$\displaystyle(a_{[6,8]},b_{[6,8]})$	$\displaystyle=(0.5,0.5)$	$\displaystyle(a_{[9,10]},b_{[9,10]})$	$\displaystyle=(1.0,0.0)$

This bilabeling corresponds to the monomial

\displaystyle\prod_{i=0}^{8}X_{i}\cdot\prod_{i=1}^{9}Y_{i}

belonging to the polynomial

\displaystyle\big{(}f_{01}f_{13}^{1/2}f_{12}^{1/2}f_{23}^{1/2}f_{24}f_{35}f_{46}f_{57}f_{67}^{1/2}f_{68}^{1/2}f_{78}^{1/2}f_{89}\big{)}^{p^{e}-1}\in J_{G}^{9(p^{e}-1)}

which has coefficient given by the expression

\displaystyle\sum_{a=0}^{N/2}\bigg{(}\binom{N/2}{a}\binom{N}{N/2+a}\binom{N}{a}\bigg{)}^{2}

where $N:=p^{e}-1$ . For small values of $p$ and $e$ it can be checked that this coefficient does not vanish mod $p$ . This suggests that $\operatorname{ft}(J_{G})=9$ for any prime $p$ .

The following proposition shows that under additional hypotheses on $G$ that a converse of Proposition 6.1 holds.

Proposition 6.4.

If $G$ is a connected graph on $n+3$ vertices with at least three vertices having degree one (in particular $G$ is not traceable), then $\operatorname{LP}_{G,\mathbb{Q}}\leq n+3/2<n+2$ .

Proof.

Observe that $G$ is a subgraph of a complete graph $H$ on $n$ vertices with three whiskers. Suppose that the whiskers of $H$ do not share a common vertex, then by Corollary 4.11, $\operatorname{LP}_{H,\mathbb{Q}}=n+\frac{3}{2}$ . If two of the three whiskers or all three of the whiskers of $H$ share a common vertex, then we can list the two block approximations of $H$ and show that $\operatorname{LP}_{H,\mathbb{Q}}\leq n+1$ by Theorem 4.14. Since $\operatorname{LP}_{G,\mathbb{Q}}\leq\operatorname{LP}_{H,\mathbb{Q}}$ the result follows. ∎

It can be shown that the graph in Example 6.3 is not unmixed. This raises

Question 6.5.

If $G$ is an unmixed, connected graph and $\operatorname{LP}_{G,\mathbb{Q}}=\lvert V(G)\rvert-1$ , then is $G$ traceable?

Note that $G$ being unmixed and connected implies that $\operatorname{LP}_{G,\mathbb{Z}}^{\ast}=n-1$ . If Question 6.5 were true, this would strengthen a result of [HHM22, 3.6.(b)] that an unmixed graph of König type is traceable. In terms of the notation of this paper, their statement can be rephrased as: if $G$ is unmixed, connected, and $\operatorname{LP}_{G,\mathbb{Z}}=\operatorname{LP}_{G,\mathbb{Z}}^{\ast}$ , then $G$ is traceable. Question 6.5 can be rephrased as: if $G$ is unmixed, connected, and $\operatorname{LP}_{G,\mathbb{Q}}=\operatorname{LP}_{G,\mathbb{Z}}^{\ast}$ , then is $G$ traceable?

References

[BE18] R. Blanco and S. Encinas, A procedure for computing the log canonical threshold of a binomial ideal, Manuscripta Math. 155 (2018), no. 1-2, 141–181.
[BMS18] D. Bolognini, A. Macchia, and F. Strazzanti, Binomial edge ideals of bipartite graphs, European J. Combin. 70 (2018), 1–25.
[Dan63] G. B. Dantzig, Linear programming and extensions, Princeton University Press, Princeton, N.J., 1963, pp. xvi+625.
[GM21] R. González-Martínez, Gorenstein binomial edge ideals, Math. Nachr. 294 (2021), no. 10, 1889–1898.
[GS] Daniel R. Grayson and Michael E. Stillman, Macaulay2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/.
[Her14] D. J. Hernández, $F$ -pure thresholds of binomial hypersurfaces, Proc. Amer. Math. Soc. 142 (2014), no. 7, 2227–2242.
[Her16] by same author, $F$ -purity versus log canonicity for polynomials, Nagoya Math. J. 224 (2016), no. 1, 10–36.
[HH11] J. Herzog and T. Hibi, Monomial ideals, Springer, 2011.
[HHH⁺10] J. Herzog, T. Hibi, F. Hreinsdóttir, T. Kahle, and J. Rauh, Binomial edge ideals and conditional independence statements, Adv. in Appl. Math. 45 (2010), no. 3, 317–333.
[HHM22] J. Herzog, T. H., and S. Moradi, Graded ideals of König type, Trans. Amer. Math. Soc. 375 (2022), no. 1, 301–323.
[How01] J. A. Howald, Multiplier ideals of monomial ideals, Trans. Amer. Math. Soc. 353 (2001), no. 7, 2665–2671.
[HV16] I. B. D. A. Henriques and M. Varbaro, Test, multiplier and invariant ideals, Adv. Math. 287 (2016), 704–732.
[LaC] A. LaClair, In preparation.
[Laz04] R. Lazarsfeld, Positivity in algebraic geometry. II, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 49, Springer-Verlag, Berlin, 2004, Positivity for vector bundles, and multiplier ideals.
[LP86] L. Lovász and M. D. Plummer, Matching theory, North-Holland Mathematics Studies, vol. 121, North-Holland Publishing Co., Amsterdam; North-Holland Publishing Co., Amsterdam, 1986, Annals of Discrete Mathematics, 29.
[Luc78] E. Lucas, Theorie des Fonctions Numeriques Simplement Periodiques, Amer. J. Math. 1 (1878), no. 4, 289–321.
[MSV14] L. E. Miller, A. K. Singh, and M. Varbaro, The $F$ -pure threshold of a determinantal ideal, Bull. Braz. Math. Soc. (N.S.) 45 (2014), no. 4, 767–775.
[MTW05] M. Mustaţǎ, S. Takagi, and K. Watanabe, F-thresholds and Bernstein-Sato polynomials, European Congress of Mathematics, Eur. Math. Soc., Zürich, 2005, pp. 341–364.
[MV12] S. Morey and R. H. Villarreal, Edge ideals: algebraic and combinatorial properties, Progress in commutative algebra 1, de Gruyter, Berlin, 2012, pp. 85–126.
[Oht11] M. Ohtani, Graphs and ideals generated by some 2-minors, Comm. Algebra 39 (2011), no. 3, 905–917.
[Pag18] G. Pagi, Enhanced algorithms for F-pure threshold computation, Ph.D. thesis, 2018.
[Pyt] Python language reference, version 2.7, Available at http://www.python.org.
[S⁺22] W. A. Stein et al., Sage Mathematics Software (Version 9.6), The Sage Development Team, 2022, Available at http://www.sagemath.org.
[SM18] S. Saeedi Madani, Binomial edge ideals: a survey, Multigraded algebra and applications, Springer Proc. Math. Stat., vol. 238, Springer, Cham, 2018, pp. 83–94.
[ST09] T. Shibuta and S. Takagi, Log canonical thresholds of binomial ideals, Manuscripta Math. 130 (2009), no. 1, 45–61.
[TW04] S. Takagi and K. Watanabe, On F-pure thresholds, J. Algebra 282 (2004), no. 1, 278–297.
[Vel19] D. J. Velez, On F-pure thresholds: computations and relations to others invariants.
[Zwo] Y. Zwols, Online linear and integer optimization solver, Available at https://online-optimizer.appspot.com.

Invariants of Binomial Edge Ideals via Linear Programs

Abstract.

1. Introduction

Theorem A (classical).

Theorem B (König).

Theorem C.

Definition 1.1 ([HHH+10]).

Theorem 1.2 ([MTW05, Theorem 3.4]).

Theorem D.

Theorem E (Theorem 4.14, Corollary 4.18).

Conjecture 1.3.

Acknowledgments

2. Background

2.1. Linear Programs

Theorem 2.1 ([Dan63, p.125 Duality Theorem] Strong duality of linear programs).

Remark 2.2.

Theorem 2.3 ( [Dan63, p.136 Theorem 4] Complementary Slackness).

Sketch of Proof.

2.2. Binomial Edge Ideals

Proposition 2.4 ([HHH+10, Lemma 3.1, Corollary 3.9]).

Definition 2.5.

Definition 2.6.

Remark 2.7.

2.3. F-Thresholds

Definition 2.8 ([MTW05, Lemma 1.1, Remark 1.5]).

Lemma 2.9.

Lemma 2.10.

Proof.

Lemma 2.11 ([TW04, Proposition 4.5]).

Theorem 2.12 ([MSV14, Theorem 1.2]).

Remark 2.13.

Proposition 2.14 ([Vel19, Theorem 3.1.6]).

Sketch of Proof.

Remark 2.15.

Theorem 2.16 ([Luc78] Lucas’s theorem).

3. Linear Programs and Binomial Edge Ideals

3.1. Binomial Grade, Height, and Linear Programs

Proposition 3.1.

Proof.

Remark 3.2.

Lemma 3.3.

Proof.

Proposition 3.4.

Proof.

3.2. Thresholds and Linear Programs

Remark 3.5.

Proposition 3.6.

Proof.

Remark 3.7.

Example 3.8.

Proposition 3.9.

Proof.

Proposition 3.10.

Proof.

Lemma 3.11 ([MSV14, Lemma 1.2]).

Proof.

Proposition 3.12.

Proof.

Lemma 3.13.

Proof.

Observation 1.

Observation 2.

Corollary 3.14.

Proof.

Remark 3.15.

Remark 3.16.

4. Proof of Conjecture 1.3 for Block Graphs

Definition 4.1.

Proposition 4.2.

Proof.

4.1. Triangle Paths and the Two Block Property

Definition 4.3.

Example 4.4.

Remark 4.5.

Proposition 4.6.

Proof.

Corollary 4.7.

Proof.

Corollary 4.8.

Proof.

Definition 1.1 ([HHH⁺10]).

Proposition 2.4 ([HHH⁺10, Lemma 3.1, Corollary 3.9]).

6. $\operatorname{LP}_{G,\mathbb{Q}}$ and Traceable Graphs