The regularity of almost all edge ideals.

A fruitful contemporary paradigm in graph theory is that almost all graphs that do not contain a certain subgraph have common structural characteristics. An example is the well-known result saying that almost all triangle-free graphs are bipartite. The "almost" is crucial, without it such theorems do not hold. In this paper we transfer this paradigm to commutative algebra and make use of deep graph theoretic results. A key tool is the critical graphs introduced relatively recently by Balogh and Butterfield, who proved that almost all graphs not containing a critical subgraph have common structural characteristics analogous to being bipartite. For a graph G , let I G denote its edge ideal, the monomial ideal generated by x i x j for every edge ij of G. In this paper we study the graded Betti numbers of I G , which are combinatorial invariants that measure the complexity of a minimal free resolution of I G. The Betti numbers of the form β i , 2 i + 2 constitute the "main diagonal" of the Betti table. It is well known that for edge ideals any Betti number 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 β i , j be a parabolic Betti number on the r -th row of the Betti table, for r ≥ 3. We prove that almost all graphs G with β i , j (I G) = 0 can be partitioned into r − 2 cliques and one independent set. In particular, for almost all graphs G with β i , j (I G) = 0 , the regularity of I G is r − 1. [ABSTRACT FROM AUTHOR]