The regularity of almost all edge ideals (Q6187710)

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}