\textsc{MAX MIN} vertex cover and the size of Betti tables (Q2660135)

Let \(K\) be a field and \(S=K[x_1,\ldots,x_n]\) be the polynomial ring in \(n\) variables over \(K\). There is a natural correspondence between quadratic squarefree monomial ideals of \(S\) and finite simple graphs with \(n\) vertices. To every simple graph \(G\) with vertex set \(V_G=\big\{x_1, \ldots, x_n\big\}\) and edge set \(E_G\), one associates its edge ideal defined by \(I(G)=\langle x_ix_j: \{x_i,x_j\}\in E_G\rangle\). The paper under review is motivated by the following question: Given a positive integer \(n\), for which pairs of integers \((p,r)\), does there exist a graph \(G\) on \(n\) vertices such that \(\mathrm{pd}(S/I(G))=p\) and \(\mathrm{reg}(S/I(G))=r\)? As the first result, it is proved that for every graph \(G\) on \(n\) vertices, the inequality \(\mathrm{pd}(S/I(G))\geq 2\sqrt{n}-2\) holds. Next, it is shown that if \(\mathrm{pd}(S/I(G))=2\sqrt{n}-2\), then either \(G=2K_2\) or \(\mathrm{reg}(S/I(G))=1\). Finally, the authors prove that the spectrum of \(\mathrm{pd}(S/I(G))\) for all graphs \(G\) with \(\mathrm{reg}(S/I(G))=1\), is precisely \([2\sqrt{n}-2, n - 1]\cap \mathbb{Z}\). As a consequence, it is shown that for any pair of positive integers \((p,r)\) such that \(r\leq n/2\) and \[2\sqrt{n-2(r-1)} +r-3\leq p\leq n - r,\] there exists a graph on \(n\) vertices such that \((\mathrm{pd}(S/I(G)),\mathrm{reg}(S/I(G))) = (p,r)\).