Example 2 -- jets of graphs

Jets of graphs were introduced in F. Galetto, E. Helmick, and M. Walsh, Jet graphs [GHW21]. Starting with a finite, simple graph $G$, one may construct a quadratic squarefree monomial ideal $I(G)$ (known as the \emph{edge ideal} of the graph) by converting edges to monomials. One may then consider the radical of the ideal of $s$-jets of $I(G)$, which is again a quadratic squarefree monomial ideal. The graph corresponding to this ideal is the graph of $s$-jets of $G$, denoted $\mathcal{J}_s (G)$.

Jets of graphs and hypergraphs can be obtained by applying the jets method to objects of type Graph and HyperGraph from the Macaulay2 EdgeIdeals package (which is automatically loaded by the Jets package). Consider, for example, the graph in the figure below.

i1 : R = QQ[a..e]

o1 = R

o1 : PolynomialRing

i2 : G = graph({{a,c},{a,d},{a,e},{b,c},{b,d},{b,e},{c,e}})

o2 = Graph{"edges" => {{a, c}, {b, c}, {a, d}, {b, d}, {a, e}, {b, e}, {c, e}}}
           "ring" => R
           "vertices" => {a, b, c, d, e}

o2 : Graph

We compute the first and second order jets, and list their edges.

i3 : J1G = jets(1,G); netList pack(7,edges J1G)

     +--------+--------+--------+--------+--------+--------+--------+
o4 = |{c1, a0}|{d1, a0}|{e1, a0}|{c1, b0}|{d1, b0}|{e1, b0}|{a1, c0}|
     +--------+--------+--------+--------+--------+--------+--------+
     |{b1, c0}|{e1, c0}|{a0, c0}|{b0, c0}|{a1, d0}|{b1, d0}|{a0, d0}|
     +--------+--------+--------+--------+--------+--------+--------+
     |{b0, d0}|{a1, e0}|{b1, e0}|{c1, e0}|{a0, e0}|{b0, e0}|{c0, e0}|
     +--------+--------+--------+--------+--------+--------+--------+

i5 : J2G = jets(2,G); netList pack(7,edges J2G)

     +--------+--------+--------+--------+--------+--------+--------+
o6 = |{a1, c1}|{b1, c1}|{a1, d1}|{b1, d1}|{a1, e1}|{b1, e1}|{c1, e1}|
     +--------+--------+--------+--------+--------+--------+--------+
     |{c2, a0}|{d2, a0}|{e2, a0}|{c1, a0}|{d1, a0}|{e1, a0}|{c2, b0}|
     +--------+--------+--------+--------+--------+--------+--------+
     |{d2, b0}|{e2, b0}|{c1, b0}|{d1, b0}|{e1, b0}|{a2, c0}|{b2, c0}|
     +--------+--------+--------+--------+--------+--------+--------+
     |{e2, c0}|{a1, c0}|{b1, c0}|{e1, c0}|{a0, c0}|{b0, c0}|{a2, d0}|
     +--------+--------+--------+--------+--------+--------+--------+
     |{b2, d0}|{a1, d0}|{b1, d0}|{a0, d0}|{b0, d0}|{a2, e0}|{b2, e0}|
     +--------+--------+--------+--------+--------+--------+--------+
     |{c2, e0}|{a1, e0}|{b1, e0}|{c1, e0}|{a0, e0}|{b0, e0}|{c0, e0}|
     +--------+--------+--------+--------+--------+--------+--------+

As predicted in [GHW21, Theorem 3.1], all jets have the same chromatic number.

i7 : apply({G,J1G,J2G},chromaticNumber)

o7 = {3, 3, 3}

o7 : List

By contrast, jets may not preserve the property of being co-chordal.

i8 : apply({G,J1G,J2G},x -> isChordal complementGraph x)

o8 = {true, true, false}

o8 : List

Using Fröberg's Theorem (cf. R. Fröberg, On Stanley-Reisner rings), we deduce that although the edge ideal of a graph may have a linear free resolution, the edge ideals of its jets may not have linear resolutions.

Finally, we compare minimal vertex covers of the graph and of its second order jets.

i9 : vertexCovers G

o9 = {a*b*c, a*b*e, c*d*e}

o9 : List

i10 : netList pack(2,vertexCovers J2G)

      +--------------------------+--------------------------+
o10 = |a2*b2*c2*a1*b1*c1*a0*b0*c0|a2*b2*e2*a1*b1*e1*a0*b0*e0|
      +--------------------------+--------------------------+
      |a2*b2*a1*b1*c1*a0*b0*c0*e0|a2*b2*a1*b1*e1*a0*b0*c0*e0|
      +--------------------------+--------------------------+
      |c2*d2*e2*c1*d1*e1*c0*d0*e0|a1*b1*c1*a0*b0*c0*d0*e0   |
      +--------------------------+--------------------------+
      |a1*b1*e1*a0*b0*c0*d0*e0   |c1*d1*e1*a0*b0*c0*d0*e0   |
      +--------------------------+--------------------------+

With the exception of the second row, many vertex covers arise as indicated in [GHW21, Proposition 5.2, 5.3].