Ask Your Question

ctst's profile - activity

2023-06-21 14:00:59 +0100 received badge  Famous Question (source)
2021-08-15 04:06:03 +0100 received badge  Popular Question (source)
2020-12-26 15:23:33 +0100 received badge  Notable Question (source)
2020-11-30 20:46:44 +0100 received badge  Notable Question (source)
2020-04-15 18:50:04 +0100 received badge  Popular Question (source)
2020-04-15 06:04:46 +0100 received badge  Popular Question (source)
2018-01-23 00:14:34 +0100 commented question testing if system of inequalities has solution

The problem is, there are too many inequalities to post them here and to get there I already used a few hundreds of lines. I could give you access on CoCalc instead, there I have the fractions saved as an object. The only thing there is, that the calculation stops because of ram restrictions. (It even kills my computer when I try to run it one mine.) Since solve and solve_ineq returns the actual solutions, I hope there was a lighter method which returns only the existence of a solution.

2018-01-22 20:35:51 +0100 received badge  Associate Editor (source)
2018-01-22 20:05:31 +0100 asked a question testing if system of inequalities has solution

Hi there,

I have a big system of inequalities (~1500 inequalities, 45 variables) and want to check, if there exists a real solution to it. Trying out the 'solve' and 'solve_ineq' takes a huge amount of time or it breaks during calculation and after checking some of the questions here I even assume the solve-function is broken and sometimes gives wrong results. Does anybody know about a function/system which returns in a responsible time and reliable if there exists a solution or not (existence is enough) (I want to use this in an actual proof, so it would be useless, if I can't trust the result).

In my use case I have the variables $a1, ..., a15, b1,...,b15,c1,...,c15 \in \mathbb R^+$ and my inequalities are all of the form $$ \frac{f(a1,...,a15)}{g(c1,\dots, c15)} \geq \frac{f'(a1,\dots,a15)}{g'(c1,\dots, c15)}$$ (and same for combinations of (a,b) and (b,c)) for given linear functions $f,f',g,g'$ (i.e. multivariate polynomials with degree at most 1), so restricting to the variables $ai$ we get a system of linear inequalities (but even trying to solve these takes long/doesn't work with the solve function).

Actually more accuratly I have indexed sets $$F_{a,b} ={{(f_i,g_i) | i \in I }, F_{c,b} ={(p_i,q_i) | i \in I } ,F_{a,c} ={(r_i,s_i) | i \in I } $$ and want to show, that if there exists a solution $(a,b)$ of $$\frac{f_k(a)}{g_k(b)} = max_i \frac{f_i(a)}{g_i(b)}$$ then there exists a solution $(c)$ to $$\frac{r_k(a)}{s_k(c)} = max_i \frac{r_i(a)}{s_i(c)}$$ $$\frac{p_k(c)}{q_k(b)} = max_i \frac{p_i(c)}{q_i(b)}$$

So far I have a the follwing snippet:

#fractionAB are the saved fractions from above, a,b,c are arrays with e.g. a=[a1,a2,...,a15]
stopIt=False
for maxStretch in cands:    #cands is the index set I
    ineq=[fractionAB.get(maxStretch) >= fractionAB.get(cand)  for cand in cands]
    if solve(ineq,a+b):
         #try here if there exists a middle point on the geodesic, i.e. geodesic exists
        ineq.extend([fractionAC.get(maxStretch) >= fractionAC.get(cand)  for cand in cands])
        ineq.extend([fractionCB.get(maxStretch) >= fractionCB.get(cand)  for cand in cands])
        if not solve(ineq, a+b+c):
            stopIt=True
    print 'Tested for candidate ' , maxStretch
    if stopIt:
        break

I know, there is room for improvement e.g. at reusing to first solution from (a+b), the problem is, that even that first system pretty much kills the calculation. Also multiplying the denominators on each side doesn't seem to help.

PS: The mathjax seems to be broken on this site, since the code for leftbraces seems to vanish (hence the ugly "fix" above).

2018-01-10 19:23:05 +0100 received badge  Scholar (source)
2018-01-10 08:54:16 +0100 received badge  Self-Learner (source)
2018-01-10 04:35:53 +0100 answered a question coercion into/from subgroup or Tietze of generator change

It was quite some pain and looks pretty ugly, but this does the job, The interesting part is done in GAP but sadly most of the code is wasted for translation... Feel free to improve it (there is a lot to improve here)

#the variables we want to change (feel free to edit this block)
F.<a,b,c>= FreeGroup();
x=a*b/c;
gens=[a*b,b,b*c]

#make it compatible for translation into GAP
rank = len(gens)
xTietze= list(x.Tietze())
tgens=[list(word.Tietze()) for word in gens]
print 'x as Tietze: ', xTietze

#translate word and generators to GAP:
gap.eval('tWord := %s;; tgens:=%s;; rank:= %s;;'  %(xTietze, tgens, rank))
gap.eval('G := FreeGroup(rank);; Ggens:=GeneratorsOfGroup(G);;')
gap.eval('word:=One(G);; for i in tWord do nextLetter:=Ggens[AbsInt(i)]; if i>0 then word:=word*nextLetter; else word:=word/nextLetter; fi;  od;')
gap.eval('newGens:=[];; for tWord in tgens do newGen:=One(G);; for i in tWord do nextLetter:=Ggens[AbsInt(i)]; if i>0 then newGen:=newGen*nextLetter; else newGen:=newGen/nextLetter; fi;  od; Add(newGens, newGen); od;')
print 'conversion of new base in GAP: ', gap('newGens')
gap.eval('H:=Subgroup(G,newGens);;')
print 'x after conversion in GAP: ', gap('word')

#change the base in GAP
gap.eval('hom:=EpimorphismFromFreeGroup(H);;')
print 'written with new basis'
gap.eval('newWord := PreImagesRepresentative(hom,word);')

#and translate new Tietze-word back to sage
newTietze=gap('TietzeWordAbstractWord(newWord);').sage()
print 'back in sage as Tietze: ', newTietze
2018-01-09 21:22:59 +0100 commented question coercion into/from subgroup or Tietze of generator change

Yes, we can consider $H$ to be the full free group $F$.

Per se it is possible to write the generators as words of the other ones and vice versa (meaning if I would do it by hand I could do it). The problem here is, that I don't know beforehand which generators will be passed, so in practise we only know how to write the generators (and hence any element) of $H$ as word of the generators of $F$.

I need a word of $F$ to be looked at, as if it was in $H$ and the Tietze of it in $H$.

So far I managed the coercing by $y=H(x.gap())$. The problem here is, that as a subgroup $H$ lacks the Tietze function... Currently I tried to translate it completly to gap (via sage) and solve it there , but I can't find the proper ... (more)

2018-01-07 14:35:33 +0100 received badge  Good Question (source)
2018-01-06 16:36:54 +0100 received badge  Nice Question (source)
2018-01-06 00:53:14 +0100 asked a question coercion into/from subgroup or Tietze of generator change

Hi there,

do you know of a function, which solves the Tietze for subgroups or converts elements from parentgroup to elements of subgroup and the other way round (if possible)? Neither of the commented codes work (but I hope it is clear what I want):

F.<a,b,c> = FreeGroup()
x=a*b/c

H=F.subgroup([a*b,b,b*c])
y=H.gens()[1]*H.gens()[0]

x in H
y in F
#F(y)
#F.coerce(y)
#H.coerce(x).Tietze()
#H(x)

I am using cocalc, if this is a version thing. I know something like that exists for quotient groups (s. http://doc.sagemath.org/html/en/refer... )

In my use-case I have a free group $F$ and an element $x \in F$ in it. Now I want for a given list of generators (e.g. in above [ ab, b, bc ]) the $x$ as a word of these generators, hence I would like to see $x$ as an element in $H$ and use x.Tietze().

Another solution to my problem would be to swap the generators, but I can't see a way to do that either?

2017-12-14 02:41:20 +0100 received badge  Self-Learner (source)
2017-12-14 02:41:20 +0100 received badge  Teacher (source)
2017-12-14 02:41:17 +0100 received badge  Nice Question (source)
2017-12-13 21:55:40 +0100 received badge  Supporter (source)
2017-12-13 21:55:31 +0100 answered a question find embedded subgraphs

I felt a little bit uncomfortable with 'cycle_basis' since it gives me a basis for all sets of disjoint cycles, but I actually want a set of all simple cycles (disjoint vertices).

A non optimal solution i came up with (using the implemented path function):

def simple_cycles(Gamma):
    """
    Returns a list of all simple cycles in the given graph Gamma as lists of vertices.
    """
    G = Graph(Gamma)    #make copy of given graph
    edges = G.edges()
    cycleList =[]
    for edge in edges:
        G.delete_edge(edge)        #delete starting edge to avoid duplicates
        if edge[0]==edge[1]:         #if its loop
            cycleList.append([edge[0], edge[1]])        
        for path in G.all_paths(edge[1], edge[0]):
            if(len(path)>1):
                cycleList.append([edge[0]]+path)
    return cycleList;

Optimizations or corrections will be appreciated (e.g. the description right now is horrible). Also I am not sure how well this behaves with multiedges.

2017-12-13 18:58:10 +0100 commented answer find embedded subgraphs

First of all thanks for the quick response. After some testing I found out, that the subgraph-function doesn't recognize loops (or ignores them), not sure how it works with multi-edges, since the list are vertices (also mentioned in the manual). (I wanted to check for barbells in a graph: Barb = Graph({0:[0,1], 1:[0,1]}) Gamma = Graph({1:[1,2,4],2:[1,3,5],3:[2,3,6],4:[1,4,5],6:[3,5,6]}); subg = list(Gamma.subgraph_search_iterator(Barb)) subg == list(Gamma.subgraph_search_iterator(Graph([[0,1]]))) If you want to see an example where it breaks (it gives the edges). You don't know by any chance a fix and a homeomorphic instead of isomorphic embedding (meaning edges can be send to several edges).

2017-12-13 16:54:41 +0100 received badge  Editor (source)
2017-12-13 16:43:52 +0100 received badge  Student (source)
2017-12-13 16:30:43 +0100 asked a question find embedded subgraphs

Hi there,

is there a method to find all embedded copies of a graph in another graph, e.g. given two graphs H and G I want something like:

G = graphs.RandomGNP(10,.3)       #some graph
H = Graph({1:[1,2], 2:[1,2]})     #some other graph
list = G.find_subgraphs(H, homeomorphic=False/True)

Where the elements list are all the subgraphs in G which are isomorphic/homeomorphic to H. If this is too much to ask for, there should be at least a method to return all cycles in G (i.e. closed paths in G with each vertex at most once). Since there exists the Hamiltonian cycle method this one should exist too.

PS: In my case the graph has multiedges (and loops, but we can ignore this here).