2020-11-03 00:55:37 +0200 received badge ● Popular Question (source) 2019-03-06 10:58:16 +0200 received badge ● Popular Question (source) 2017-07-09 16:58:18 +0200 received badge ● Popular Question (source) 2017-04-20 18:31:20 +0200 received badge ● Notable Question (source) 2017-04-20 18:31:20 +0200 received badge ● Popular Question (source) 2016-06-01 15:52:19 +0200 received badge ● Notable Question (source) 2015-09-16 22:00:17 +0200 received badge ● Popular Question (source) 2014-10-01 15:31:38 +0200 received badge ● Student (source) 2014-06-29 03:15:34 +0200 marked best answer How to get an arbitrary orientation of a graph. I'VE COMPLETELY REVISED MY QUESTION I wish to take a simple undirected graph (i.e. the complete graph K_4) Arbitrarily direct said graph, and then create a line graph from the directed version of the graph. However, in Sage it appears to create a line graph that shows a connection between two edges (that are just inverses of each other), so what I really want is a line graph that doesn't give an edge connected to its own inverse. That's why I asked if we could remove cycles of length 2, but that doesn't seem to solve the problem. Here's what I am trying to work out: G = graphs.RandomGNP(4,1) GD = G.to_directed() #orients G m = GD.size() #number of edges of digraph GD LG = GD.line_graph() #the line graph of the digraph IM = identity_matrix(QQ,GD.size()) T = LG.adjacency_matrix()#returns the adjacency matrix of the line graph var('u') #defines u as a variable X=IM-u*T #defines a new matrix X Z=X.det() #defines polynomial in u aka inverse of the Ihara zeta function Z #computes determinant of X Z.coefficients(u) #extracts coefficients  considering my graph is a complete graph on 4 vertices - the coefficients should be as such: [coeff,degree of u] [1,0], [0,1], [0,2],[-8,3],[-2,4] NOTE: im only interested in coefficients up to the order of n=#of nodes in the graph, so here for K_4 obviously n=4. where the coefficient of u^3 corresponds to the negative of twice the number of triangles in K_4 where the coefficient u^4 corresponds to the negative of twice the number of squares in K_4 Here is an image of a K_4 graph minus an edge and the line graph construction of K_4 that i want 2014-06-29 03:13:06 +0200 marked best answer How would you plot these data points? (x=nodes, y=cycles) the following 3 sets of data points on the same graph: IZF (color=red): [(0,0),(1,0),(2,0),(3,35),(4,105),(5,252),(6,1260),(7,2910)] vs Actual (color=black): [(0,0),(1,0),(2,0),(3,35),(4,105),(5,252),(6,420),(7,360)] vs c_adj (color=blue): [(0,0),(1,0),(2,42),(3,210),(4,1302),(5,7770),(6,46662),(7,279930)] i'm not even sure what type graph would be appropriate, whereby you can see reasonably where each point y is, because my current plots (due to y going up to 279,930) shows the different data points coinciding, i.e. you cant differentiate between the initial datapoints. 2013-03-17 23:14:09 +0200 commented answer Empirical Data Plot awesome thanks 2013-03-17 23:13:57 +0200 marked best answer Empirical Data Plot Here is a sample of what you can do in Sage. var('a,n') model(x) = a*x^n N = [16,28,59,120] T = [0.135,0.523,7.36,248] data = zip(N,T) @interact def _(n=[1..5]): L = find_fit(data,model.subs(n=n)) show(plot(model.subs(a=L.rhs(),n=n),(x,0,120))+points(data,pointsize=20,color='black'))  See it live and in action here. Note that with four data points, of course the fifth-degree one is perfect! My guess is that here you may have (yuck) exponential growth, but without more data it's hard to be sure - definitely could also be $O(x^3)$ or $O(x^4)$ or something. 2013-03-17 21:54:19 +0200 commented answer Newton's identities in Sage what if i wanted a new formula for s_k=[c_1s_{k-1}+...+c_{k-1}s_1-kc_k] ? 2013-03-15 18:36:18 +0200 commented answer Empirical Data Plot Time = [0.135, 0.523, 2.72, 7.36, 23.2, 45.1, 96.3, 248]   Edges = [16.0, 28.0, 47.0, 59.0, 77.0, 84.0, 98.0, 120.0] -- seems like it's more like O(N^5) growth with these additional points? 2013-03-15 10:28:19 +0200 commented question Empirical Data Plot well, i just want to know the order of growth. i.e. as the edges increase what is the order of growth in terms of time taken to compute my function. 2013-03-15 08:07:41 +0200 asked a question Empirical Data Plot I wish to make a plot of N vs Time where $N=$ # of edges in a graph. i.e. i want to make an empirical estimate of the time complexity it takes to compute certain things about a graph based on its number of edges. so i guess i'm wanting to know how i can plot these data points in sage and find a polynomial that best fits? i.e. N = [(16,28,59,120)] T = [(0.135,0.523,7.36,248)] --where time is measured in seconds i'm a beginner so any help will be much appreciated. 2013-03-14 22:36:00 +0200 marked best answer Newton's identities in Sage An recursive algorithm would be quite inefficient for this problem as yout would have to recalculate all c_k coefficients in each step. The following few lines should work for your problem (if I hopefully didn't make any mistakes with the formulas): def c(k,A): c_arr=[-A.trace()] for j in range(k-1): c_arr=c_incr(c_arr,A) print c_arr return c_arr[k-1] def c_incr(c_arr, A): k=len(c_arr)+1 c_new=(A^k).trace() for c_k in c_arr: k-=1 c_new+=c_k*(A^k).trace() c_new=-1/(len(c_arr)+1)*c_new c_arr.append(c_new) return c_arr  2013-03-14 17:57:05 +0200 edited question Newton's identities in Sage EDIT I actually need: $s_k=[c_1s_{k-1}+...+c_{k-1}s_1-kc_k]$ ? could somebody help me to change tobias welch's answer so that it computes $s_k$ instead of $c_k$? END EDIT I'm combining netwon's identities with le verrier's algorithm I need some help coding the following on python. $c_k=\frac{-1}{k}(s_k+c_1s_{k-1}+c_2s_{k-2}+\dots+c_{k-1}s_1)$ where $s_k=Tr(A^k)$, for some square matrix A, $\forall k=1,2,3,\dots,n$ So, i'd like to type in $c(k)$ and python spits out the value for $c_k$ as defined above. 2013-03-14 12:51:12 +0200 commented question IndexError: list index out of range I think I may have pasted the defined functions incorrectly in to sage, i.e. it now seems to be working correctly. return c_arr[k-1] should have been in line with for j in range(k-1): 2013-03-14 12:16:57 +0200 asked a question IndexError: list index out of range i'm not sure why i'm getting an error saying list index out of range, as this defined function c(k,A) worked previously for a complete graph on 7 vertices. could anyone help me? (i've printed the code below with the error message - i need to be able to compute c(k,A) where k ranges from 1 to N and N is equal to L.order() ) sage: G =graphs.RandomNewmanWattsStrogatz(100,3,0.5) sage: D = G.to_directed() sage: L = D.line_graph() sage: L.delete_edges([((x,y,None), (y,x,None)) for x,y in G.edges( labels=None ) ]) sage: L.delete_edges([((x,y,None), (y,x,None)) for y,x in G.edges( labels=None ) ]) sage: A = L.adjacency_matrix() sage: def c(k,A): c_arr=[-A.trace()] for j in range(k-1): c_arr=c_incr(c_arr,A) print c_arr return c_arr[k-1] sage: def c_incr(c_arr, A): k=len(c_arr)+1 c_new=(A^k).trace() for c_k in c_arr: k-=1 c_new+=c_k*(A^k).trace() c_new=-1/(len(c_arr)+1)*c_new c_arr.append(c_new) return c_arr sage: c(2,A) [0, 0] 0 sage: c(3,A) [0, 0] --------------------------------------------------------------------------- IndexError Traceback (most recent call last) in () ----> 1 c(Integer(3),A) in c(k, A) 4 c_arr=c_incr(c_arr,A) 5 print c_arr ----> 6 return c_arr[k-Integer(1)] IndexError: list index out of range  2013-03-03 18:12:31 +0200 answered a question nilpotent adjacency matrix I've added another bit on: def c(k): if k<3: return 0 if k>2: return sum_of_coeffs(nil(A,k))/(2*k)  where $c(k)$ returns the number of simple cycles in G of length $k$. 2013-03-03 17:48:59 +0200 marked best answer nilpotent adjacency matrix Here's a naive answer, as I am somewhat naive (I just posted a question and, while waiting breathlessly for someone to answer it, I thought I'd just have a look at what other people are asking). No idea how efficient it is, but maybe it's a start. You can construct the ring that you want to work in as a quotient ring of a multivariate polynomial ring. You can then construct the matrix B that you want by multiplying by a diagonal matrix whose entries are the variables you want. n = 4 R = PolynomialRing(QQ, n+1, 'a') squared_vars = [t**2 for t in R.gens()] I = R.ideal(squared_vars) S = R.quotient_ring(I, 'b') def nil(A,k): B = A * diagonal_matrix(S, n, list(R.gens())[1:]) return (B**k).trace()  Edit: It turns out that OP also wants to compute the sum of the coefficients. I found it kind of tricky to compute this, largely because the quotient ring classes seem not to have a lot of the methods you'd expect. However it's possible to lift an element of the quotient ring to the obvious preimage in the original ring, and since the original ring is a plain old multivariate polynomial ring, you can do all the things you'd normally do in it, like "subs". Naturally substituting 1 for all the variables computes the sum of the coefficients: def sum_of_coeffs(x): return x.lift().subs({t:1 for t in R.gens()})  so, for instance, you could do sum_of_coeffs(nil(A,2))  which hopefully should produce the answer 10 when you run it with OP's example, for instance. This was a great question - at least, I feel like I learned a lot... :) 2013-03-03 17:48:29 +0200 received badge ● Commentator 2013-03-03 17:48:29 +0200 commented answer nilpotent adjacency matrix I also learnt a lot - thanks! i tried it on a complete graph on 7 vertices and it worked perfectly :) 2013-03-03 16:07:35 +0200 commented answer nilpotent adjacency matrix Ok, thanks. i also tried extracting the coefficients, but i'm guessing there is a special way when dealing with quotient rings, as i keep getting errors pertaining to it being a quotient ring. 2013-03-03 13:42:41 +0200 commented answer nilpotent adjacency matrix I apologise -i t works perfectly. Two things though: is it possible to start from b_1, rather than b_0? Also is there some way to return the sum of all the scalar coefficients of (B**k).trace()? 2013-03-03 08:59:48 +0200 asked a question nilpotent adjacency matrix i wish to define a nilpotent adjacency matrix. example vertex adjacency matrix of a graph ($K_4$ minus an edge) is A= [0 1 1 0] [1 0 1 1] [1 1 0 1] [0 1 1 0] where N=4 vertices so for all entries $A_{ij}$ i wish to define a function to replace the 1's by $b_j$ so for the example above i get a nilpotent matrix B= [0 $b_2$ $b_3$ 0] [$b_1$ 0 $b_3$ $b_4$] [$b_1$ $b_2$ 0 1] [0 $b_2$ $b_3$ 0] where the $b_j$ where $i,j\in${1,2,3,4} obey the following rules of multiplication: $b_jb_i=b_ib_j$ and $b_j^2=0$ (so i also need to define a function for these rules) so for the nilpotent adjacency matrix i can define matrix multiplication using the above rules for its entries i.e. $B^N$ i'd like the function to be something like nil(B,k) and for it to print the trace of $B^k$ e.g. $nil(B,2)=2b_1b_2+2b_1b_3+2b_2b_3+2b_2b_4+2b_3b_4$ i'll try to work on this myself too in the meantime, but this is probably the most complicated function i've had to do.. mainly due to redefining the adjacency matrix 2013-03-03 08:09:06 +0200 marked best answer How would you plot these data points? Use list_plot and logarithmic scale on the y-axis.