A classification of mengerian $4$-uniform hypergraphs derived from graphs

1. Introduction

Assume that $R$ is a commutative Noetherian ring and $I$ is an ideal of $R$. Then a prime ideal $\mathfrak{p}\subset R$ is an associated prime of $I$ if there exists an element $h$ in $R$ such that $\mathfrak{p}=(I{:}_{R}h)$, where $(I{:}_{R}h)=\{r\in R\mid rh\in I\}$. The set of associated primes of $I$, denoted by ${\mathrm{A}\mathrm{s}\mathrm{s}}_R(I)$, is the set of all prime ideals associated to $I$. Brodmann [3] showed that the sequence $\{{\mathrm{A}\mathrm{s}\mathrm{s}}_R(I^k){\}}_{k\ge 1}$ of associated prime ideals is stationary for large $k$. This means that there exists a positive integer $k_0$ such that ${\mathrm{A}\mathrm{s}\mathrm{s}}_R(I^k)={\mathrm{A}\mathrm{s}\mathrm{s}}_R(I^{k_0})$ for all $k\ge k_0$. The minimal such $k_0$ is called the index of stability of $I$ and ${\mathrm{A}\mathrm{s}\mathrm{s}}_R(I^{k_0})$ is called the stable set of associated prime ideals of $I$, which is denoted by ${\mathrm{A}\mathrm{s}\mathrm{s}}^{\mathrm{\infty }}(I).$

Several questions arise in the context of Brodmann’s result. An ideal $I\subset R$ is said to be normally torsion-free if, for all $k\ge 1$, we have ${\mathrm{A}\mathrm{s}\mathrm{s}}_R(I^k)\subseteq {\mathrm{A}\mathrm{s}\mathrm{s}}_R(I)$, see [24, Definition 4.3.28]. In particular, if $I$ is a square-free monomial ideal in a polynomial ring $R=K[x_1,\dots ,x_n]$ over a field $K$, then $I$ is normally torsion-free if, for all $k\ge 1$, we have ${\mathrm{A}\mathrm{s}\mathrm{s}}_R(I^k)={\mathrm{A}\mathrm{s}\mathrm{s}}_R(I)$.

Generally, finding classes of normally torsion-free ideals have been a theme of many papers, nevertheless, some classes of such ideals emanate from graph theory. Particularly, it is well-known that a finite simple undirected graph is bipartite if and only if its edge ideal is normally torsion-free, if and only if its cover ideal is normally torsion-free, see [9,23] for more information. Furthermore, in [17, Theorem 3.3], the authors stated that the Alexander dual of the monomial ideal generated by the paths of maximal lengths in a rooted starlike tree is normally torsion-free. In [13, Theorem 3.2], it has been shown that the Alexander dual of path ideals generated by all paths of length $2$ in rooted trees are normally torsion-free.

Let $G$ be an undirected and simple graph. More recently, it has been verified in [18, Theorem 2.8] that if $G$ is a strongly chordal graph, then both $NI(G)$ and $DI(G)$ are normally torsion-free, where $NI(G)$ (respectively, $DI(G)$) stands for the closed neighborhood ideal of $G$ (respectively, dominating ideal of $G$). Moreover, when $C_n$ denotes the simple cycle graph on $n$ vertices, then based on [18, Theorem 4.3], $DI(C_n)$ is normally torsion-free if and only if $n\in \{3,6,9\}$, the definitions of closed neighborhood ideals and dominating ideals and their properties can be found in [16,19].

In addition, Lemma 5.15 in [20] gives a characterization of all normally torsion-free $t$-spread principal Borel ideals. In fact, a monomial $x_{i_1}{x}_{i_2}\cdots x_{i_d}\in R=K[x_1,\dots ,x_n]$ with $i_1\le i_2\le \cdots \le i_d$ is called $t$-spread if $i_j-i_{j-1}\ge t$ for all $j=2,\dots ,d$. A monomial ideal $I$ in $R$ is called a $t$-spread monomial ideal if it is generated by $t$-spread monomials. Also, $I$ is called a $t$-spread strongly stable ideal if for all $t$-spread monomials $u\in \mathcal{G}(I)$, all $j\in \mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(u)$ and all $1\le i<j$ such that $x_i(u/x_j)$ is a $t$-spread monomial, it follows that $x_i(u/x_j)\in I$. Moreover, $I$ is called a $t$-spread principal Borel if there exists a $t$-spread monomial $u\in \mathcal{G}(I)$ such that $I$ is the smallest $t$-spread strongly stable ideal which contains $u$; we denote it as $I=B_t(u)$. By [20, Lemma 5.15(i)], if $u=x_a{x}_b{x}_n$ is a $t$-spread monomial, $I=B_t(u)$, and $b<2t+1$, then $I$ is normally torsion-free. In this direction, in [15, Theorem 4.6], the authors showed that the edge ideal of any $\mathbf{t}$-spread $d$-partite hypergraph $K_V^{\mathbf{\text{t}}}$ is normally torsion-free. More information about $t$-spread monomial ideals and vector-spread monomial ideals can be found in [7,8].

Furthermore, Herzog et. al., in [12, Corollary 4.6], proved that every transversal polymatroidal ideal is normally torsion-free. In particular, Olteanu [21] characterized all the lexsegment ideals which are normally torsion-free non-square-free monomial ideals.

In the following text, we focus on normally torsion-free square-free monomial ideals. Indeed, one of the motivations of this work originates from this fact that normally torsion-free square-free monomial ideals are closely related to Mengerian hypergraphs. A hypergraph is called Mengerian if it satisfies a certain min-max equation, which is known as the Mengerian property in hypergraph theory or has the max-flow min-cut property in integer programming. In fact, it is well-known that if $\mathcal{C}$ is a clutter, i.e. an antichain w.r.t. the partial order induced by inclusion, and $I=I(\mathcal{C})$ its edge ideal, then $I$ is normally torsion-free if and only if $I^k=I^{(k)}$ for all $k\ge 1$, where $I^{(k)}=\bigcap _{\mathfrak{p}\in \mathrm{M}\mathrm{i}\mathrm{n}(I)}(I^k{R}_{\mathfrak{p}}\cap R)$ denotes the $k$-th symbolic power of $I$, if and only if $\mathcal{C}$ is Mengerian, if and only if $\mathcal{C}$ has the max-flow min-cut (MFMC for short) property, see [24, Theorem 14.3.6] for more details.

So far, there exist two well-known classifications of Mengerian $2$-uniform hypergraphs and $3$-uniform hypergraphs derived from graphs as follows:

• ([23, Theorem 5.9]) Let $G$ be a simple undirected graph and $I$ its edge ideal. Then $G$ is bipartite if and only if $I$ is normally torsion-free.

• ([1, Theorem 3.9]) Let $G$ be a connected simple undirected graph and $t\ge 2$ be an integer, and let $J=I_3(G)$ be the cubic path ideal of $G$. Then, $J^{(n)}=J^n$ for all $n\ge 1$ if and only if $G$ is a path graph $P_t$ or $G$ is the cycle $C_{3k}$ when $k=1,2,3$.

In addition, according to [18, Proposition 3.2], the $t$-path ideals of path graphs are normally torsion-free for all $t\ge 0$.

The main aim of this work is to provide a classification of all Mengerian $4$-uniform hypergraphs derived from graphs as we will give in the following theorem:

It is possible to ask whether the techniques used in this paper can be generalized to the general case? Our computations and observations show that investigating the cases greater than $4$ is too complicated, and we may need to change our technique as in [23] the authors used the Rees Algebra and classic methods in commutative algebra for proving the case $2$, and in [1] the authors utilized the symbolic powers technique for showing the case $3$, and the present authors used the TDI (totally dual integral) method for proving the case $4$; however, we left an open question in this direction at the end of this paper, see Question 4.1.

Throughout this paper, all graphs are simple, finite, connected, and undirected. Also, any necessary definitions related to graph theory (respectively, monomial ideals) can be found in [25] (respectively, [11]).

2. Preliminaries

In what follows, we recollect some necessary definitions related to hypergraph theory, which can be found in [2,24].

A finite hypergraph $\mathcal{H}$ on a vertex set $V(\mathcal{H})=\{x_1,x_2,\dots ,x_n\}$ is a collection of hyperedges $E(\mathcal{H})=\{E_1,\dots ,E_m\}$ with $E_i\subseteq V(\mathcal{H})$ for all $i=1,\dots ,m$. The incidence matrix of $\mathcal{H}$ is an $m\times n$ matrix $A=(a_{ij})$ such that $a_{ij}=1$ if $x_j\in E_i$, and $a_{ij}=0$ otherwise. A hypergraph $\mathcal{H}$ is called simple if $E_i\subseteq E_j$ implies $i=j$. Simple hypergraphs are also known as clutters. Moreover, if $|E_i|=d$ for all $i=1,\dots ,m$, then $\mathcal{H}$ is called a $d$-uniform hypergraph. A $2$-uniform hypergraph $\mathcal{H}$ is just a finite simple graph.

Let $V(\mathcal{H})=\{x_1,x_2,\dots ,x_n\}$ and $R=K[x_1,\dots ,x_n]$ be the polynomial ring in $n$ variables over a field $K$. The edge ideal of $\mathcal{H}$ is given by $$I(\mathcal{H})=(\prod _{x_j\in E_i}{x}_j:E_i\in E(\mathcal{H})).$$

Let $G$ be a simple finite connected undirected graph. The $t$-path hypergraph of $G$, denoted by ${\mathcal{H}}_t(G)$, is a $(t+1)$-uniform hypergraph on the vertex set $V(G)$ such that $e=\{v_1,\dots ,v_{t+1}\}$ is an edge if contains a path of length $t$ in $G$. The edge ideal of ${\mathcal{H}}_t(G)$ is called the $t$-path ideal of $G$ and is denoted by $I_t(G)$. When $t=1$, then $I_1(G)$ is simply the edge ideal $I(G)$ of $G$. If there is no $t$-path in $G$, then we set $I_t(G)=0$.

To understand Theorem 2.4, we require to review the following definitions from combinatorial optimization.

For a hypergraph $\mathcal{H}$, the deletion $\mathcal{H}\setminus x$ at a vertex $x\in V(\mathcal{H})$ has the effect of setting $x=0$ in the edge ideal $I:=I(\mathcal{H})$, and the contraction $\mathcal{H}/x$ has the effect of setting $x=1$ in the edge ideal $I(\mathcal{H})$, see [24, Definition 6.5.2]. We call an ideal $I^{\prime }$ a minor of a square-free monomial ideal $I$ if $I^{\prime }$ can be obtained from $I$ by a sequence of taking quotients (=deletion) and localizations (=contraction) at the variables, refer to [24, Definition 6.5.3].

A vertex $x\in V(\mathcal{H})$ is called an isolated vertex if $\{x\}\in E(\mathcal{H})$. It follows from the definition that if $x$ is an isolated vertex of $\mathcal{H}$, then $\{x\}$ is the only edge in $\mathcal{H}$ that contains $x$. A vertex cover of $\mathcal{H}$ is a set of vertices that has a non-empty intersection with all of the edges of $\mathcal{H}$. The minimum cardinality of a vertex cover of $\mathcal{H}$ is denoted by $\tau (\mathcal{H})$, consult [2, Page 64]. It should be noted that by the correspondence between minimal primes and minimal vertex covers, $\tau (I)$ is also the height of $I$ (cf. [24, Proposition 13.1.6]).

We say the generators of a square-free monomial ideal $I$ as being independent or a matching if the corresponding edges of the associated hypergraph are pairwise disjoint; that is, the generators have disjoint supports. We denote the maximum cardinality of an independent set in $I$ by $\nu (I)$, see [2, Page 64]. Furthermore, note that a subset of the monomial generators of $I$ is independent if and only if it forms a regular sequence. Thus, $\nu (I)$ is equal to the monomial grade of $I$, denoted by $\mathfrak{m}$–$\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{d}\mathrm{e}(I)$, where the monomial grade of an ideal $I$ is the maximum length of a regular sequence of monomials in $I$, see [24, Denition 13.1.5 and Proposition 13.1.6]. By weak linear programming duality we always have $\tau (I)\ge \nu (I)$.

A square-free monomial ideal $I$ is said to satisfy the König property if $\tau (I)=\nu (I)$, refer to [24, Denition 13.1.4]. Consequently, $I$ satisfies the König property if and only if $\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{d}\mathrm{e}(I)=\mathrm{h}\mathrm{t}(I)=\mathfrak{m}$–$\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{d}\mathrm{e}(I)$. Moreover, a square-free monomial ideal $I$ has the packing property if $I$ and all of its proper minors satisfy the König property (cf. [24], Definition 14.3.16).

In 1990 [5], Michele Conforti and Gérard Cornuéjols made up the following conjecture, and it is still open.

We finally summarize all of the above notions in the following theorem.

3. Main result

Given a connected graph $G=(V,E)$ with $|V|\ge 4$, we consider the $4$-uniform hypergraph ${\mathcal{H}}_3(G)=(\mathcal{V},\mathcal{F})$ such that $e=\{v_1,v_2,v_3,v_4\}\in \mathcal{F}$ if and only if contains a path of length $3$ in $G$. Let $A$ denote the incidence matrix of ${\mathcal{H}}_3(G)$. Then ${\mathcal{H}}_3(G)$ is Mengerian if and only if the system $Ax\ge \mathbf{1}$ with $x\ge 0$ is TDI. This in particular implies that the system is integral. In this case, we call the hypergraph ideal. It should be noted that if a hypergraph is not ideal, then it is not Mengerian. Furthermore, every empty clutter is considered Mengerian.

To show Proposition 3.4 here below, we require to employ the following definition, exercise, and theorem. Given a monomial ideal $I$, we denote by $\mu (I)$ the minimal number of monomial generators of $I$.

To formulate Lemma 3.8, we need the following definitions and corollary.

As was pointed out by an anonymous referee, the above proof does not apply to the case where we have a path consisting of just one edge with double stars. Thus, we need an extra lemma.

In the remaining cases, we will show that the hypergraphs are not Mengerian because they are not ideal. For this purpose, we present in each case a fractional vertex of the covering polyhedron. We use the following well-known fact from linear programming.

Proof. The numbers indicated at the vertices clearly define a non-integral vertex. Thus, ${\mathcal{H}}_3(G)$ is neither ideal nor Mengerian.

 

In the following result we are using a result from the paper [4] which has been published hundred years ago (in 1923) and here is the first citation of this result.

A remark here what makes the case $k=8$ special is certainly in order.

Proof. If $G$ is a tree which is not a path with double stars, then it has three vertices which are adjacent to leaves. Hence, the following graph $H$ (see Figure 1) is a minor, and thus ${\mathcal{H}}_3(G)$ is not Mengerian by Lemma 3.12. If $G$ contains a triangle and is not itself a star plus an edge between two of its leaves, then we find an induced subgraph on $5$ vertices which is not Mengerian by Lemma 3.12. If $G$ contains a cycle of length $4$, again we find an induced subgraph on $5$ vertices which is not Mengerian by Lemma 3.12.

If $G$ contains a cycle of length $k\ge 6$ and $k\ne 8$, then ${\mathcal{H}}_3(G)$ is not Mengerian by Proposition 3.13. If the only cycle in $G$ is the cycle $C_8$, since $G\ne C_8$, we find a vertex adjacent to only one vertex of $C_8$, and so again we have the following graph $H$ which is not Mengerian by Lemma 3.12 as a minor. Any other cycle is a cycle of length $\ge 6$ and the hypergraph is not Mengerian by Lemma 3.14. This finishes our argument.

The main result of this paper follows combining Proposition 3.10 with Lemma 3.15.

4. Conclusion and outlook

In this paper we considered the 4-uniform hypergraphs ${\mathcal{H}}_3(G)$, where the hyperedges are defined by the vertex sets $h\in (\genfrac{}{}{0ex}{}{V}{4})$ of a graph $G=(V,E)$, that contain a path on $3$ edges. We characterized the graphs where the corresponding hypergraphs are Mengerian. Except for ${\mathcal{H}}_3(C_8)$, the corresponding matrices where all even totally unimodular. Moreover, we found a dichotomie that in this class every hypergraph is either Mengerian or the corresponding matrix is non-ideal. In view of Theorem 4.1(i) in [6], we wonder whether