Macaulay2 » Documentation
Packages » Oscillators :: Checking the codimension and irreducible decomposition of the IG ideal
next | previous | forward | backward | up | index | toc

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}
          );
 -- .301778s elapsed
 -- .364412s elapsed
 -- .542497s elapsed
 -- .297543s elapsed
 -- .318027s elapsed
 -- .364214s elapsed
 -- .631542s elapsed
 -- .543305s elapsed
 -- .570431s elapsed
 -- .377986s elapsed
 -- .272534s 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}
          );
 -- .450907s elapsed
 -- .527067s elapsed
 -- 1.08653s elapsed
 -- 1.366s elapsed
 -- .811636s elapsed
 -- 1.01964s elapsed
 -- 1.12073s elapsed
 -- 1.21134s elapsed
 -- .828737s elapsed
 -- .85714s elapsed
 -- .406983s elapsed
 -- .514965s elapsed
 -- .559375s elapsed
 -- .743024s elapsed
 -- .986392s elapsed
 -- 1.3766s elapsed
 -- 1.16544s elapsed
 -- 1.02566s elapsed
 -- 1.39964s elapsed
 -- 1.2175s elapsed
 -- .893498s elapsed
 -- 1.05555s elapsed
 -- 1.51532s elapsed
 -- 1.45849s elapsed
 -- .579121s elapsed
 -- .761839s elapsed
 -- 1.52177s elapsed
 -- .836192s elapsed
 -- .665304s elapsed
 -- .97641s elapsed
 -- 1.21321s elapsed
 -- 1.00087s elapsed
 -- .659558s elapsed
 -- 1.20782s elapsed
 -- .909482s elapsed
 -- 1.30013s elapsed
 -- 1.13824s elapsed
 -- 1.40205s elapsed
 -- 1.49412s elapsed
 -- .889525s elapsed
 -- .783182s elapsed
 -- 1.28748s elapsed
 -- 1.6106s elapsed
 -- 1.93881s elapsed
 -- 1.24388s elapsed
 -- 1.21788s elapsed
 -- 1.58206s elapsed
 -- 1.44724s elapsed
 -- 1.17731s elapsed
 -- 1.25191s elapsed
 -- 1.30103s elapsed
 -- .945009s elapsed
 -- .969241s elapsed
 -- 1.16168s elapsed
 -- .835333s elapsed
 -- 1.32782s elapsed
 -- 1.47574s elapsed
 -- 1.56902s elapsed
 -- .902833s elapsed
 -- .573987s elapsed
 -- .443809s 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.