Convert graph into ideal in polynomial ring

graph
ideal

asked 2016-01-12 12:12:15 +0200

selva
45 ●2 ●7

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

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2016-01-12 13:50:53 +0200

tmonteil
27333 ●31 ●203 ●514 http://wiki.sagemath.o...

updated 2016-01-12 13:52:58 +0200

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

Comments

Great answer! But how do we convert the list L to a polynomial object in the ring R?

vidyarthi ( 2023-03-13 16:09:18 +0200 )edit

add a comment

answered 2016-01-12 19:41:14 +0200

slelievre
17654 ●22 ●160 ●348 http://carva.org/samue...

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

add a comment

Your Answer

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

Add Answer

Convert graph into ideal in polynomial ring

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Convert graph into ideal in polynomial ring edit

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Convert graph into ideal in polynomial ring