# Convert graph into ideal in polynomial ring

Let $G = (V (G), E(G))$ denote a finite simple (no loops or multiple edges) undirected graph with vertices $V (G) =\ {x_1 ,\ldots, x_n }$ and edge set $E(G)$ . By identifying the vertices with the variables in the polynomial ring $R = k[x_1 ,\ldots, x_n ]$ (where $k$ is a field), we can associate to each simple graph $G$ a monomial ideal $I(G) = ({ x_i x_j |{x_i , x_j } \in E(G)})$

How to convert graph into ideal in sage ? Suppose $G$ is cycle graph. can i get ideal with generator $(x_1x_2,x_2x_3,x_3x_4,x_4x_5,x_1x_5)$ in $k[x_1,\ldots ,x_5]$ Please give some hint.

edit retag close merge delete

Sort by » oldest newest most voted

You have first to create your polynomial ring with variables names being the vertices of your graph. But since some vertices are usually numbers (thougt they can be other Sage objects), and since the variable names must start with a letter, i propose to name them x_i where i is the string representing each vertex:

sage: G = graphs.PetersenGraph()
sage: R = PolynomialRing(QQ,['x_'+str(i) for i in G.vertices()])
sage: R
Multivariate Polynomial Ring in x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9 over Rational Field
sage: R.inject_variables()
Defining x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9


Then you can define the list of polynomials that define your ideal:

sage: L = [R('x_'+str(i)) * R('x_'+str(j)) for i,j in G.edges(labels=False)]


Then you can construct your ideal:

sage: I = R.ideal(L)
sage: I
Ideal (x_0*x_1, x_0*x_4, x_0*x_5, x_1*x_2, x_1*x_6, x_2*x_3, x_2*x_7, x_3*x_4, x_3*x_8, x_4*x_9, x_5*x_7, x_5*x_8, x_6*x_8, x_6*x_9, x_7*x_9) of Multivariate Polynomial Ring in x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9 over Rational Field

more

You could do the following.

sage: k = QQ
sage: n = 10
sage: R = PolynomialRing(k, 'x', n)
sage: R
Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 over Rational Field
sage: R.inject_variables()
Defining x0, x1, x2, x3, x4, x5, x6, x7, x8, x9
sage: verts = R.gens()
sage: edges = [(x1, x2), (x3, x7), (x4, x9)]
sage: G = Graph([verts, edges], format='vertices_and_edges')
sage: G
Graph on 10 vertices
sage: J = R.ideal([a * b for a, b in G.edges(labels=False)])
sage: J
Ideal (x4*x9, x3*x7, x1*x2) of Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 over Rational Field

more