The regularity of almost all edge ideals

DOI10.1016/J.AIM.2023.109355MaRDI QIDQ6187710zbMATH OpenOpenAlexFDO

Publication date 1 February 2024

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.07304

Betti numbers critical graphs edge ideals regularity

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Extremal problems in graph theory (05C35) Syzygies, resolutions, complexes and commutative rings (13D02) Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55)

Abstract: A fruitful contemporary paradigm in graph theory is that almost all graphs that do not contain a certain subgraph have common structural characteristics. The "almost" is crucial, without it there is no structure. In this paper we transfer this paradigm to commutative algebra and make use of deep graph theoretic results. A key tool are the critical graphs introduced by Balogh and Butterfield. We consider edge ideals

I_{G}

of graphs and their Betti numbers. The numbers of the form

constitute the "main diagonal" of the Betti table. It is well known that any Betti number

below (or equivalently, to the left of) this diagonal is always zero. We identify a certain "parabola" inside the Betti table and call parabolic Betti numbers the entries of the Betti table bounded on the left by the main diagonal and on the right by this parabola. Let

be a parabolic Betti number on the

r

-th row of the Betti table, for

r g e 3

. Our main results state that almost all graphs

G

with

can be partitioned into

r - 2

cliques and one independent set, and in particular for almost all graphs

G

with

the regularity of

I_{G}

is

r - 1

.

Review text

For a finite simple graph \(G=(V,E)\) and a field \(K\), the edge ideal of \(G\) is the ideal \(I_G=(x_ux_v\,|\,\{u,v\}\in E)\) of \(K[x_v\,|\,v\in V]\). In the paper under review, the authors study the (Castelnuovo-Mumford) regularity of \(I_G\), i.e.\ \(\mathrm{reg}(I_G)\) (\(\mathrm{reg}(M)\) is defined as \(\max\{j\,|\,\beta_{i,i+j}(M)\neq 0\mbox{ for some }i\}\)). A Betti number on the \(r\)-th row \(\beta_{i,i+r}\) is called parabolic if \(r\geq 3\) and \(r-2\leq i\leq r-2+\binom{r-1}{2}\). The main result of the paper is: Theorem. Let \(\beta_{i,i+r}\) be a parabolic Betti number. Then for almost every graph \(G\) with \(\beta_{i,i+r}(I_G)=0\), one has: (1) \(\mathrm{reg}(I_G)=r-1\); (2) every parabolic Betti number of \(I_G\) above row \(r\) is non-zero. Let us briefly give the main steps of the proof. A \(k\)-cluster is the complement of a complete \(k\)-partite graph \(K_{a_1,\ldots,a_k}\). Further, this \(k\)-cluster is parabolic if \(a_1=2\) and \(2\leq a_i\leq i\) for \(2\leq i\leq k\). Then: \begin{itemize} \item[(1)] Let \(k\geq 2\) and \(C=\overline{K_{a_1,\ldots,a_k}}\), with \(a_i\geq 2\), be a \(k\)-cluster, and \(p=a_1+\cdots+a_k-2k\). If \(\beta_{k-1+p,2k+p}(I_G)=0\), then \(G\) is \(C\)-free. \item[(2)] Every parabolic \(k\)-cluster with \(k\geq 2\) is critical (for definition see \textit{J. Balogh} and \textit{J. Butterfield}, Random Struct. Algorithms 38, No. 1--2, 100--120 (2011; Zbl 1225.05138)]). \item[(3)] Use a result of Balogh and Butterfield [loc. cit.] on the structure of almost all \(H\)-free graphs, where \(H\) is a critical graph. \end{itemize}

Recommendations

Cites work

Cited in

(3)

This page was built for publication: The regularity of almost all edge ideals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187710)