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}
          );
 -- .297255s elapsed
 -- .319702s elapsed
 -- .516152s elapsed
 -- .263054s elapsed
 -- .297303s elapsed
 -- .329013s elapsed
 -- .674909s elapsed
 -- .43544s elapsed
 -- .462953s elapsed
 -- .399197s elapsed
 -- .259874s 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}
          );
 -- .424434s elapsed
 -- .47287s elapsed
 -- 1.0501s elapsed
 -- 1.28478s elapsed
 -- .718817s elapsed
 -- .981197s elapsed
 -- 1.14935s elapsed
 -- 1.12904s elapsed
 -- .807106s elapsed
 -- .85279s elapsed
 -- .362696s elapsed
 -- .515452s elapsed
 -- .524259s elapsed
 -- .833779s elapsed
 -- 1.01096s elapsed
 -- 1.44465s elapsed
 -- 1.08262s elapsed
 -- .98634s elapsed
 -- 1.27338s elapsed
 -- 1.14216s elapsed
 -- .89869s elapsed
 -- 1.18421s elapsed
 -- 1.64412s elapsed
 -- 1.37808s elapsed
 -- .536859s elapsed
 -- .679899s elapsed
 -- 1.41578s elapsed
 -- .750859s elapsed
 -- .687846s elapsed
 -- .869895s elapsed
 -- 1.0997s elapsed
 -- .950625s elapsed
 -- .640112s elapsed
 -- 1.16351s elapsed
 -- .911266s elapsed
 -- 1.16536s elapsed
 -- 1.0475s elapsed
 -- 1.32651s elapsed
 -- 1.45112s elapsed
 -- 1.18713s elapsed
 -- .710083s elapsed
 -- 1.40978s elapsed
 -- 1.82613s elapsed
 -- 2.31847s elapsed
 -- 1.61903s elapsed
 -- 1.27594s elapsed
 -- 1.81459s elapsed
 -- 1.30068s elapsed
 -- 1.05437s elapsed
 -- 1.07498s elapsed
 -- 1.17588s elapsed
 -- .903087s elapsed
 -- .931044s elapsed
 -- 1.12036s elapsed
 -- .686151s elapsed
 -- 1.20645s elapsed
 -- 1.57479s elapsed
 -- 1.5769s elapsed
 -- .785632s elapsed
 -- .467528s elapsed
 -- .431997s 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 Oscillators/Documentation.m2:794:0.