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* -- 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.
