Some interpretations for algebraic invariants of edge ideals of hypergraphs via combinatorial invariants

Abstract

The present work is concerned with characterizing some algebraic invariants of edge ideals of hypergraphs. To this aim, first, we introduce some kinds of combinatorial invariants similar to matching numbers for hypergraphs. Then we compare them to each other and to previously existing ones. These invariants are used for characterizing or bounding some algebraic invariants of edge ideals of hypergraphs such as graded Betti numbers, projective dimension and Castelnouvo–Mumford regularity.

Communicated by Jason P. Bell     

Regularity 3 in edge ideals associated to bipartite graphs

We focus in this paper on edge ideals associated to bipartite graphs and give a combinatorial characterization of those having regularity 3. When the regularity is strictly bigger than 3, we determine the first step i in the minimal graded free resolution where there exists a minimal generator of degree >i+3, show that at this step the highest degree of a minimal generator is i+4, and determine the corresponding graded Betti number β _i,i+4 in terms of the combinatorics of the graph. The results are then extended to the non-square-free case through polarization. We also study a family of ideals of regularity 4 that play an important role in our main result and whose graded Betti numbers can be completely described through closed combinatorial formulas.     

Linearity defect of edge ideals and Fröberg’s theorem

Fröberg’s classical theorem about edge ideals with 2-linear resolution can be regarded as a classification of graphs whose edge ideals have linearity defect zero. Extending his theorem, we classify all graphs whose edge ideals have linearity defect at most 1. Our characterization is independent of the characteristic of the base field: The graphs in question are exactly weakly chordal graphs with induced matching number at most 2. The proof uses the theory of Betti splittings of monomial ideals due to Francisco, Hà, and Van Tuyl and the structure of weakly chordal graphs. Along the way, we compute the linearity defect of edge ideals of cycles and weakly chordal graphs. We are also able to recover and generalize previous results due to Dochtermann–Engström, Kimura and Woodroofe on the projective dimension and Castelnuovo–Mumford regularity of edge ideals.     

Some algebraic properties of hypergraphs

We consider Stanley-Reisner rings k[x ₁, …, x _n ]/I(H) where I(H) is the edge ideal associated to some particular classes of hypergraphs. For instance, we consider hypergraphs that are natural generalizations of graphs that are lines and cycles, and for these we compute the Betti numbers. We also generalize some known results about chordal graphs and study a weak form of shellability.     

Generalized multiplicities of edge ideals

We explore connections between the generalized multiplicities of square-free monomial ideals and the combinatorial structure of the underlying hypergraphs using methods of commutative algebra and polyhedral geometry. For instance, we show that the j-multiplicity is multiplicative over the connected components of a hypergraph, and we explicitly relate the j-multiplicity of the edge ideal of a properly connected uniform hypergraph to the Hilbert–Samuel multiplicity of its special fiber ring. In addition, we provide general bounds for the generalized multiplicities of the edge ideals and compute these invariants for classes of uniform hypergraphs.     

Regularity and projective dimension of edge ideals

In this paper, we study the regularity and projective dimension of edge ideals. We provide two upper bounds for the regularity of edge ideals of vertex decomposable graphs in terms of the induced matching number and the number of cycles. Also, we generalize one of the upper bounds given by Dao and Schweig for the projective dimension of hypergraphs.     

Bounding Betti numbers of bipartite graph ideals

We prove a conjectured lower bound of Nagel and Reiner on Betti numbers of edge ideals of bipartite graphs.     

Extremal Betti Numbers of Some Cohen-Macaulay Binomial Edge Ideals

We provide the regularity and the Cohen-Macaulay type of binomial edge ideals of Cohen-Macaulay cones,and we show the extremal Betti numbers of some classes of Cohen-Macaulay binomial edge ideals:Cohen-Macaulay bipartite and fan graphs.In addition,we compute the Hilbert-Poincaré series of the binomial edge ideals of some Cohen-Macaulay bipartite graphs.     

Certain variants of multipermutohedron ideals

Multipermutohedron ideals have rich combinatorial properties. An explicit combinatorial formula for the multigraded Betti numbers of a multipermutohedron ideal and their Alexander duals are known. Also, the dimension of the Artinian quotient of an Alexander dual of a multipermutohedron ideal is the number of generalized parking functions. In this paper, monomial ideals which are certain variants of multipermutohedron ideals are studied. Multigraded Betti numbers of these variant monomial ideals and their Alexander duals are obtained. Further, many interesting combinatorial properties of multipermutohedron ideals are extended to these variant monomial ideals.     

Computation of betti numbers of monomial ideals associated with cyclic polytopes

We give a combinatorial formula for the Betti numbers which appear in a minimal free resolution of the Stanley-Reisner ringk[Δ(P)]=A/I _Δ(P) of the boundary complex Δ(P) of an odd-dimensional cyclic polytopePover a fieldk. A corollary to the formula is that the Betti number sequence ofk[Δ(P)] is unimodal and does not depend on the base fieldk.     

Descent sets for symplectic groups

The edges of any hypergraph parametrize a monomial algebra called the edge subring of the hypergraph. We study presentation ideals of these edge subrings, and describe their generators in terms of balanced walks on hypergraphs. Our results generalize those for the defining ideals of edge subrings of graphs, which are well-known in the commutative algebra community, and popular in the algebraic statistics community. One of the motivations for studying toric ideals of hypergraphs comes from algebraic statistics, where generators of the toric ideal give a basis for random walks on fibers of the statistical model specified by the hypergraph. Further, understanding the structure of the generators gives insight into the model geometry.     

Path ideals of rooted trees and their graded Betti numbers

Let Γ be a rooted (and directed) tree, and let t be a positive integer. The path ideal It(Γ) is generated by monomials that correspond to directed paths of length (t−1) in Γ. In this paper, we study algebraic properties and invariants of It(Γ). We give a recursive formula to compute the graded Betti numbers of It(Γ) in terms of path ideals of subtrees. We also give a general bound for the regularity, explicitly compute the linear strand, and investigate when It(Γ) has a linear resolution.     

A note on norm ideals and the operatorX→AX−XB

For operatorsA andB on a Hilbert space ℋ, let τ denote the operator on ℒ(ℋ) defined by τ(X)=AX−XB. Several equivalent conditions are given for τ to be surjective or bounded below. Analogues of these results are given for the restrictions of τ to norm ideals, and the norms of these restrictions are estimated. The author gratefully acknowledges support by a grant from the National Science Foundation.     

Maximum degree and fractional matchings in uniform hypergraphs

Let ℋ be a family ofr-subsets of a finite setX. SetD(ℋ)= |{E:x∈E∈ℋ}|, (maximum degree). We say that ℋ is intersecting if for anyH,H′ ∈ ℋ we haveH ∩H′ ≠ 0. In this case, obviously,D(ℋ)≧|ℋ|/r. According to a well-known conjectureD(ℋ)≧|ℋ|/(r−1+1/r). We prove a slightly stronger result. Let ℋ be anr-uniform, intersecting hypergraph. Then either it is a projective plane of orderr−1, consequentlyD(ℋ)=|ℋ|/(r−1+1/r), orD(ℋ)≧|ℋ|/(r−1). This is a corollary to a more general theorem on not necessarily intersecting hypergraphs.     

Hypergraphs with large transversal number and with edge sizes at least four

Let H be a hypergraph on n vertices and m edges with all edges of size at least four. The transversal number τ(H) of H is the minimum number of vertices that intersect every edge. Lai and Chang [An upper bound for the transversal numbers of 4-uniform hypergraphs, J. Combin. Theory Ser. B, 1990, 50(1), 129–133] proved that τ(H) ≤ 2(n+m)/9, while Chvátal and McDiarmid [Small transversals in hypergraphs, Combinatorica, 1992, 12(1), 19–26] proved that τ(H) ≤ (n + 2m)/6. In this paper, we characterize the connected hypergraphs that achieve equality in the Lai-Chang bound and in the Chvátal-McDiarmid bound.     

Cellular resolutions of cointerval ideals

Minimal cellular resolutions of the edge ideals of cointerval hypergraphs are constructed. This class of d-uniform hypergraphs coincides with the complements of interval graphs (for the case d?=?2), and strictly contains the class of ‘strongly stable’ hypergraphs corresponding to pure shifted simplicial complexes. The polyhedral complexes supporting the resolutions are described as certain spaces of directed graph homomorphisms, and are realized as subcomplexes of mixed subdivisions of the Minkowski sums of simplices. Resolutions of more general hypergraphs are obtained by considering decompositions into cointerval hypergraphs.     

Extremal Betti numbers of graded ideals

The possible extremal Betti numbers of graded ideals in the polynomial ring K[x₁,…,x_n] in n variables with coefficients in a field K are studied, completing our results in [7]. In case char(K) = 0 we determine, given any integers r < n, the conditions under which there exists a graded ideal I ? K[x₁,…, x_n] with extremal Betti numbers $\beta_{k_{i}k_{i}+\ell_{i}}\ {\rm for}\ i=1,\cdots,r$ . We also treat a similar problem for squarefree lexsegment ideals.