Hi, I have coded an initial version of k-connectivity,which works but can be improved.
The link is here https://github.com/Rajesh-Veeranki/sage -patches/blob/master/k-connectivity.py. Probably we should be using previously computed results to speeden it. Thanks Rajesh V On Wed, Mar 12, 2014 at 5:48 AM, Rajesh Veeranki <[email protected]>wrote: > Hi, > > I was busy with my academics last week,so i wasn't very active. > Now, i have written a draft of my > proposal<https://docs.google.com/document/d/1SvNraF0x9rNl4Xbpne7l7I_82H_Mz_Hkqt0Ut_Sc4Lc/pub> > . > I'm not quite sure as to what is expected ,so please have a look at it and > suggest what should be added. > I'll be adding the details of my schedule sooner. > > I have a few doubts: > > 1.For the minor testing, how do i efficiently find reduced matrix > representation for each basis.Do i need to use gauss-jordan computation for > reduced row echelon form or is there some other method? > > 2.As per my understanding, the invariants like the tutte polynomial at > (i,i), canonical partition, support graph can only be used for isomorphism > testing and not directly for minor testing.Is it so or some of these are > invariants under deletions and contractions? > > > 3.For the automorphism group computation, when we find that the generated > group is not the Aut(M), how do we decide what more nonbases to add to the > graph? > > > Thanks, > Rajesh > > > > On Sun, Mar 9, 2014 at 8:02 AM, Rajesh Veeranki <[email protected]>wrote: > >> >> Dear Rudi, >> >> On Sun, Mar 9, 2014 at 3:30 AM, Pendavingh, R.A. >> <[email protected]>wrote: >> >>> Dear Rajesh, >>> >>> I'm not sure I understand what your question is, so here's several >>> answers. >>> 1) if M is a matroid on E and N its set of nonbases, then the >>> automorphism group of the hypergraph H=(E, N) equals the automorphism group >>> of M: a permutation s of E is an automorphism of M if and only if [X is >>> dependent<=> s[X] is dependent] for each subset X of E with r(M) elements. >>> >> >> >>> 2) to test if a subgroup G of the permutation group of E contains only >>> automorphisms of a matroid M on E, it suffices to find a set of generators >>> of G, and tot test, for each generator g, if g is an automorphism of M. >>> >> >> Ah, i infact forgot about the generators.I was thinking of verifying each >> element of the subgroup.Thanks, i got the answer. >> >> Cheers, >>> Rudi >>> >>> On 8 mrt. 2014, at 16:07, "Rajesh Veeranki" <[email protected] >>> <mailto:[email protected]>> wrote: >>> >>> Dear Rudi, >>> >>> Generating nonbases hypergraph that contains the Aut(M) is clear.But >>> what i'm not clear is how do i verify if the Automorphism group of the >>> above constructed graph is generated by the automorphism group of the >>> matroid? >>> >>> Can you provide some thoughts on this. >>> >>> Thanks >>> >>> >>> On Wed, Mar 5, 2014 at 4:15 AM, Pendavingh, R.A. <[email protected] >>> <mailto:[email protected]>> wrote: >>> Dear Rajesh, >>> >>> Please call me Rudi. >>> >>> As far as i can see,the magic numbers are calculated for each reduced >>> matrix, displaying each basis. >>> OK, thanks. >>> >>> >>> Regarding, the automorphism group of a matroid, we should certainly >>> avoid the full non-bases calculation.Can you please suggest some resource,( >>> if you have something particular in mind ), for studying the hypergraphs >>> that are invariants of a matroid? >>> >>> I did not have a particular reference in mind. What I was thinking of as >>> a first attempt was, say, the hypergraph whose edges are all the flats of >>> rank k, taking O(n^k) time. That particular hypergraph I expect to work >>> well for linear matroids over small fields, also assuming that the rank of >>> these matroid is not too big compared to k. But which hypergraph to try >>> will always depend on the representation of the matroid. >>> >>> I am not sure about the BasisMatroid. Here the construction of the >>> nonbasis hypergraph is relatively inexpensive compared to the size of the >>> representation, and it seems difficult to come up with any hypergraph that >>> is faster to compute. But it may still give a speedup to avoid the >>> construction. I actually have a routine implemented that inspects the >>> nonbasis hypergraph without constructing it (running through the r-sets), >>> and which calculates, for each element e, the number of nonbases containing >>> e. Coloring the groundset elements with this information may cut down the >>> isomorphism group significantly, since all automorphism must preserve >>> color. You get this partition by calling M._basis_partition() on a >>> BasisMatroid. If you get a partition into singletons, the automorphism >>> group is clearly trivial, and perhaps other outcomes may also be exploited >>> for a speedup. Also, check out M._basis_partition2(). This does create the >>> nonbasis hypergraph as a SetSystem, but then finds an equitable partition >>> for it. In the course of that computation, a trimmed version of the >>> nonbasis hypergraph is created. This seems a better object to feed to the >>> graph automorphism group computation, since it's much smaller. >>> >>> I'm also reading your paper<http://arxiv.org/pdf/1203.0910v2.pdf> for >>> understanding the projective invariants of matrices. >>> >>> Let me know when something needs clarification. It is a technical story. >>> >>> Best, >>> Rudi >>> >>> >>> >>> -- >>> >>> >>> Rajesh Veeranki | Senior Undergraduate | C.S.E | IIT Bombay >>> >>> >> >> >> -- >> >> >> *Rajesh Veeranki** | Senior Undergraduate | **C.S.E** | **IIT Bombay* >> >> > > > -- > > > *Rajesh Veeranki** | Senior Undergraduate | **C.S.E** | **IIT Bombay* > > -- *Rajesh Veeranki** | Senior Undergraduate | **C.S.E** | **IIT Bombay* -- You received this message because you are subscribed to the Google Groups "sage-gsoc" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-gsoc. For more options, visit https://groups.google.com/d/optout.
