Checking the codimension and irreducible decomposition of the IG ideal -- generating all SCT graphs on n vertices

We first construct the ideal $I_G$ for a specific graph $G$ on 5 vertices. We use the 5-cycle as the specific example.

i1 : needsPackage "Oscillators"

o1 = Oscillators

o1 : Package

i2 : needsPackage "NautyGraphs"

o2 = NautyGraphs

o2 : Package

i3 : Gstrs = generateGraphs(5, OnlyConnected => true, MinDegree => 2);

i4 : Gs = Gstrs/stringToGraph

o4 = {Graph{0 => {3, 4}   }, Graph{0 => {3, 4}      }, Graph{0 => {2, 4}   
            1 => {3, 4}            1 => {3, 4}               1 => {3, 4}   
            2 => {3, 4}            2 => {3, 4}               2 => {0, 4}   
            3 => {0, 1, 2}         3 => {0, 1, 2, 4}         3 => {1, 4}   
            4 => {0, 1, 2}         4 => {3, 0, 1, 2}         4 => {2, 0, 3,
     ------------------------------------------------------------------------
       }, Graph{0 => {2, 3}}, Graph{0 => {2, 3, 4}}, Graph{0 => {2, 3, 4}
                1 => {3, 4}         1 => {3, 4}            1 => {3, 4}   
                2 => {0, 4}         2 => {0, 4}            2 => {0, 4}   
                3 => {0, 1}         3 => {0, 1}            3 => {0, 1, 4}
     1}         4 => {2, 1}         4 => {2, 0, 1}         4 => {2, 0, 3,
     ------------------------------------------------------------------------
       }, Graph{0 => {2, 3, 4}   }, Graph{0 => {2, 3, 4}}, Graph{0 => {2, 3,
                1 => {3, 4}               1 => {2, 3, 4}         1 => {2, 3,
                2 => {0, 3, 4}            2 => {0, 1, 4}         2 => {0, 1,
                3 => {2, 0, 1, 4}         3 => {0, 1}            3 => {0, 1,
     1}         4 => {2, 0, 3, 1}         4 => {2, 0, 1}         4 => {2, 0,
     ------------------------------------------------------------------------
     4}   }, Graph{0 => {2, 3, 4}   }, Graph{0 => {1, 2, 3, 4}}}
     4}            1 => {2, 3, 4}            1 => {0, 2, 3, 4}
     4}            2 => {0, 1, 3, 4}         2 => {1, 0, 3, 4}
     4}            3 => {2, 0, 1, 4}         3 => {1, 0, 2, 4}
     1, 3}         4 => {2, 0, 1, 3}         4 => {1, 0, 2, 3}

o4 : List

i5 : G = Gs_3

o5 = Graph{0 => {2, 3}}
           1 => {3, 4}
           2 => {0, 4}
           3 => {0, 1}
           4 => {2, 1}

o5 : Graph

i6 : R = oscRing(5, Reduced => false);

i7 : IG = oscQuadrics(G, R)

o7 = ideal (x y  + x y  - x y  - x y , x y  + x y  - x y  - x y , - x y  +
             2 0    3 0    0 2    0 3   3 1    4 1    1 3    1 4     2 0  
     ------------------------------------------------------------------------
     x y  + x y  - x y , - x y  - x y  + x y  + x y , - x y  - x y  + x y  +
      0 2    4 2    2 4     3 0    3 1    0 3    1 3     4 1    4 2    1 4  
     ------------------------------------------------------------------------
     x y )
      2 4

o7 : Ideal of R

i8 : netList IG_*

     +---------------------------+
o8 = |x y  + x y  - x y  - x y   |
     | 2 0    3 0    0 2    0 3  |
     +---------------------------+
     |x y  + x y  - x y  - x y   |
     | 3 1    4 1    1 3    1 4  |
     +---------------------------+
     |- x y  + x y  + x y  - x y |
     |   2 0    0 2    4 2    2 4|
     +---------------------------+
     |- x y  - x y  + x y  + x y |
     |   3 0    3 1    0 3    1 3|
     +---------------------------+
     |- x y  - x y  + x y  + x y |
     |   4 1    4 2    1 4    2 4|
     +---------------------------+

i9 : codim IG

o9 = 4

Each $I_G$ on $n$ vertices has $n-1$ minimal generators. This particular $I_G$ has the same codimension $n-1=4$, so is a complete intersection. This ideal decomposes as an intersection of 2 prime ideals.

i10 : comps = decompose IG;

i11 : netList comps_0_*, netList comps_1_*

       +-----------+  +------------------------------------------------------
o11 = (|x y  - x y |, |x y  + x y  - x y  - x y                              
       | 4 3    3 4|  | 4 1    4 2    1 4    2 4                             
       +-----------+  +------------------------------------------------------
       |x y  - x y |  |x y  - x y  - x y  + x y                              
       | 4 2    2 4|  | 3 1    4 2    1 3    2 4                             
       +-----------+  +------------------------------------------------------
       |x y  - x y |  |x y  + x y  - x y  - x y                              
       | 3 2    2 3|  | 3 0    4 2    0 3    2 4                             
       +-----------+  +------------------------------------------------------
       |x y  - x y |  |x y  - x y  - x y  + x y                              
       | 4 1    1 4|  | 2 0    0 2    4 2    2 4                             
       +-----------+  +------------------------------------------------------
       |x y  - x y |  |y y y  + y y y  + y y y  + y y y  + y y y             
       | 3 1    1 3|  | 0 1 3    0 2 3    0 2 4    1 2 4    1 3 4            
       +-----------+  +------------------------------------------------------
       |x y  - x y |  |                                                      
       | 2 1    1 2|  |x y y  + x y y  + x y y  + x y y  + x y y  + x y y  - 
       +-----------+  | 0 1 3    0 2 3    2 1 4    0 2 4    4 2 4    1 3 4   
       |x y  - x y |  +------------------------------------------------------
       | 4 0    0 4|  |                   2                                  
       +-----------+  |x x y  - x x y  + x y  + x x y  + x x y  + x x y  + x 
       |x y  - x y |  | 0 4 2    2 4 2    4 2    0 1 3    0 2 3    1 4 3    1
       | 3 0    0 3|  +------------------------------------------------------
       +-----------+  |x x x  + x x x  + x x x  + x x x  + x x x             
       |x y  - x y |  | 0 1 3    0 2 3    0 2 4    1 2 4    1 3 4            
       | 2 0    0 2|  +------------------------------------------------------
       +-----------+
       |x y  - x y |
       | 1 0    0 1|
       +-----------+
      -----------------------------------------------------------------------
      --------------------+
                          |)
                          |
      --------------------+
                          |
                          |
      --------------------+
                          |
                          |
      --------------------+
                          |
                          |
      --------------------+
                          |
                          |
      --------------------+
         2                |
      x y                 |
       2 4                |
      --------------------+
              2           |
      x y  + x y  - x x y |
       2 4    2 4    2 4 4|
      --------------------+
                          |
                          |
      --------------------+

o11 : Sequence

i12 : comps/codim

o12 = {4, 4}

o12 : List

i13 : comps/degree

o13 = {5, 11}

o13 : List

i14 : comps/isPrime

o14 = {true, true}

o14 : List

Let's see how many graphs are not complete intersections, i.e. have codimension $\le n-2$.

i15 : # select(Gs, G -> (
          IG = oscQuadrics(G, R);
          codim IG <= #vertices G - 2
          ))

o15 = 4

i16 : for G in Gs list (
          IG = oscQuadrics(G, R);
          elapsedTime comps := decompose IG;
          {comps/codim, comps/degree}
          );
 -- .262307s elapsed
 -- .311812s elapsed
 -- .470208s elapsed
 -- .213761s elapsed
 -- .247754s elapsed
 -- .316212s elapsed
 -- .518743s elapsed
 -- .462454s elapsed
 -- .491888s elapsed
 -- .259444s elapsed
 -- .197809s elapsed

i17 : netList oo

      +---------------+---------------+
o17 = |{3, 4, 4}      |{2, 3, 5}      |
      +---------------+---------------+
      |{3, 4, 4}      |{2, 3, 5}      |
      +---------------+---------------+
      |{4, 4, 4, 4, 4}|{4, 1, 3, 3, 5}|
      +---------------+---------------+
      |{4, 4}         |{5, 11}        |
      +---------------+---------------+
      |{4, 4}         |{5, 11}        |
      +---------------+---------------+
      |{4, 4}         |{5, 11}        |
      +---------------+---------------+
      |{4, 4, 4, 4, 4}|{4, 1, 3, 3, 5}|
      +---------------+---------------+
      |{4, 4, 4, 4, 4}|{1, 3, 4, 3, 5}|
      +---------------+---------------+
      |{4, 4, 4, 4, 4}|{1, 3, 3, 4, 5}|
      +---------------+---------------+
      |{3, 4, 4}      |{2, 3, 5}      |
      +---------------+---------------+
      |{2, 4}         |{1, 5}         |
      +---------------+---------------+

i18 : n = 6

o18 = 6

i19 : Gstrs = generateGraphs(n, OnlyConnected => true, MinDegree => 2);

i20 : Gs = Gstrs/stringToGraph;

i21 : R = oscRing(n, Reduced => false);

i22 : # select(Gs, G -> (
          IG = oscQuadrics(G, R);
          codim IG <= #vertices G - 2
          ))

o22 = 15

i23 : allcomps = for G in Gs list (
          IG = oscQuadrics(G, R);
          elapsedTime comps := decompose IG;
          {comps/codim, comps/degree}
          );
 -- .362234s elapsed
 -- .458533s elapsed
 -- .984594s elapsed
 -- .968257s elapsed
 -- .622432s elapsed
 -- .815638s elapsed
 -- .909034s elapsed
 -- .978772s elapsed
 -- .746201s elapsed
 -- .705711s elapsed
 -- .321276s elapsed
 -- .433607s elapsed
 -- .544608s elapsed
 -- .678503s elapsed
 -- .840572s elapsed
 -- 1.1233s elapsed
 -- .913688s elapsed
 -- .863379s elapsed
 -- 1.0416s elapsed
 -- .899888s elapsed
 -- .691391s elapsed
 -- 1.14004s elapsed
 -- 1.54512s elapsed
 -- 1.18518s elapsed
 -- .503086s elapsed
 -- .590386s elapsed
 -- 1.30593s elapsed
 -- .626073s elapsed
 -- .562652s elapsed
 -- .789408s elapsed
 -- 1.19986s elapsed
 -- .911668s elapsed
 -- .605579s elapsed
 -- .988583s elapsed
 -- .688907s elapsed
 -- 1.01579s elapsed
 -- .880248s elapsed
 -- 1.07964s elapsed
 -- 1.1194s elapsed
 -- .7441s elapsed
 -- .646915s elapsed
 -- 1.16752s elapsed
 -- 1.54362s elapsed
 -- 1.98383s elapsed
 -- 1.14924s elapsed
 -- 1.04575s elapsed
 -- 1.40139s elapsed
 -- 1.05414s elapsed
 -- .988902s elapsed
 -- .907443s elapsed
 -- 1.04199s elapsed
 -- .693816s elapsed
 -- .708909s elapsed
 -- 1.0013s elapsed
 -- .680476s elapsed
 -- .981747s elapsed
 -- 1.25291s elapsed
 -- 1.27968s elapsed
 -- .653726s elapsed
 -- .398698s elapsed
 -- .408432s elapsed

i24 : netList ({{"codimensions", "degrees"}} | allcomps)

      +------------------------+------------------------+
o24 = |codimensions            |degrees                 |
      +------------------------+------------------------+
      |{3, 5, 5}               |{2, 4, 6}               |
      +------------------------+------------------------+
      |{3, 5, 5}               |{2, 4, 6}               |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5, 5, 5, 5}|{2, 6, 2, 4, 2, 6, 4, 6}|
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5, 5, 5, 5}|{2, 6, 2, 4, 2, 6, 4, 6}|
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5}         |{2, 2, 4, 6, 18}        |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5}         |{2, 2, 4, 6, 18}        |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5}         |{2, 2, 4, 6, 18}        |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5}         |{2, 2, 4, 6, 18}        |
      +------------------------+------------------------+
      |{4, 5, 5, 5, 5}         |{4, 2, 4, 4, 6}         |
      +------------------------+------------------------+
      |{4, 5, 5, 5, 5}         |{4, 2, 4, 4, 6}         |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5, 5, 5, 5}|{2, 6, 2, 4, 2, 6, 4, 6}|
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5}         |{2, 2, 4, 6, 18}        |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5, 5, 5, 5}|{2, 6, 2, 4, 2, 6, 4, 6}|
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5}         |{2, 2, 4, 6, 18}        |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5, 5, 5, 5}|{2, 6, 2, 4, 2, 6, 4, 6}|
      +------------------------+------------------------+
      |{4, 4, 4, 5}            |{1, 3, 3, 6}            |
      +------------------------+------------------------+
      |{4, 4, 5, 5, 5}         |{1, 3, 6, 4, 6}         |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5, 5, 5, 5}|{2, 6, 2, 4, 2, 6, 4, 6}|
      +------------------------+------------------------+
      |{4, 4, 5, 5, 5}         |{1, 3, 4, 6, 6}         |
      +------------------------+------------------------+
      |{4, 4, 4, 5}            |{1, 3, 3, 6}            |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5, 5, 5, 5}|{2, 6, 2, 2, 4, 6, 4, 6}|
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5, 5, 5, 5}|{2, 6, 2, 2, 4, 6, 4, 6}|
      +------------------------+------------------------+
      |{4, 4, 5, 5, 5}         |{1, 3, 6, 4, 6}         |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5, 5, 5}            |{4, 4, 6, 18}           |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5}         |{2, 2, 4, 6, 18}        |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5}         |{2, 2, 4, 6, 18}        |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5, 5, 5, 5}|{8, 2, 2, 2, 4, 4, 4, 6}|
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5, 5, 5, 5}|{8, 2, 2, 2, 4, 4, 4, 6}|
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5, 5, 5}            |{4, 4, 6, 18}           |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5}                  |{6, 26}                 |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5}         |{2, 2, 4, 6, 18}        |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5}         |{2, 2, 4, 6, 18}        |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5, 5, 5, 5}|{2, 6, 2, 2, 6, 4, 4, 6}|
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5}         |{2, 2, 4, 6, 18}        |
      +------------------------+------------------------+
      |{4, 4, 5, 5, 5}         |{1, 3, 6, 4, 6}         |
      +------------------------+------------------------+
      |{4, 4, 5, 5, 5}         |{1, 3, 6, 4, 6}         |
      +------------------------+------------------------+
      |{5, 5, 5, 5}            |{4, 4, 6, 18}           |
      +------------------------+------------------------+
      |{4, 4, 5, 5, 5}         |{1, 3, 4, 6, 6}         |
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5, 5, 5, 5}|{2, 6, 2, 2, 4, 6, 4, 6}|
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5, 5, 5, 5}|{2, 2, 2, 4, 6, 4, 6, 6}|
      +------------------------+------------------------+
      |{5, 5, 5, 5, 5, 5, 5, 5}|{2, 2, 2, 4, 4, 4, 8, 6}|
      +------------------------+------------------------+
      |{4, 5, 5, 5, 5}         |{4, 2, 4, 4, 6}         |
      +------------------------+------------------------+
      |{3, 5, 5}               |{2, 4, 6}               |
      +------------------------+------------------------+
      |{2, 5}                  |{1, 6}                  |
      +------------------------+------------------------+

n = 7
Gstrs = generateGraphs(n, OnlyConnected => true, MinDegree => 2);
Gs = Gstrs/stringToGraph;
R = oscRing(n, Reduced => false);
# select(Gs, G -> (
    IG = oscQuadrics(G, R);
    elapsedTime codim IG <= #vertices G - 2
    ))

The next one takes some time.

n = 8
Gstrs = generateGraphs(n, OnlyConnected => true, MinDegree => 2);
Gs = Gstrs/stringToGraph;
R = oscRing(n, Reduced => false);
# select(Gs, G -> (
    IG = oscQuadrics(G, R);
    codim IG <= #vertices G - 2
    ))

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/Oscillators/Documentation.m2:794:0.