next | previous | forward | backward | up | top | index | toc | directory | Macaulay 2 web site

numTriangles -- returns the number of triangles in a graph

Synopsis

Description

The method is based on work of Francisco-Ha-Van Tuyl, looking at the associated primes of the square of the Alexander dual of the edge ideal. The function counts the number of these associated primes of height 3.
i1 : R = QQ[x_1..x_6];
i2 : G = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6}) --5-cycle and a triangle

o2 = Graph{edges => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }}}
                       1   2     2   3     3   4     1   5     4   5     1   6     5   6
           ring => R
           vertices => {x , x , x , x , x , x }
                         1   2   3   4   5   6

o2 : Graph
i3 : numTriangles G

o3 = 1
i4 : H = completeGraph R;
i5 : numTriangles H == binomial(6,3)

o5 = true

See also

Ways to use numTriangles :