Ask Your Question
2

Convert graph into ideal in polynomial ring

asked 2016-01-12 05:12:15 -0500

selva gravatar image

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.

Thanks in advance

edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
2

answered 2016-01-12 06:50:53 -0500

tmonteil gravatar image

updated 2016-01-12 06:52:58 -0500

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
edit flag offensive delete link more
1

answered 2016-01-12 12:41:14 -0500

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
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-01-12 05:11:16 -0500

Seen: 90 times

Last updated: Jan 12 '16