#18484: Implement k-chordality of a matroid
------------------------------------+------------------------
Reporter: Rudi | Owner:
Type: enhancement | Status: new
Priority: minor | Milestone: sage-6.8
Component: matroid theory | Resolution:
Keywords: chord | Merged in:
Authors: Travis Scrimshaw | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
------------------------------------+------------------------
Comment (by Rudi):
Replying to [comment:6 tscrim]:
> It's better to not create a new ticket, but instead just push a new
branch.
>
I tried, but apparently I was using the wrong command. Just `git trac push
18484` from my new branch was rejected. I did not see how to scrap the
existing branch.
> Anyways, I'm going to recycle this ticket for k-chordality of a matroid
(code to follow shortly, probably tomorrow).
Will your algorithm check that definition directly? If so, a matroid M of
rank >k is k-chordal if and only if it's rank-k truncation T is, since M
and T will have the same collection of length `<= k` circuits:
`T=BasisMatroid(groundset = M.groundset(), nonbases =
M.dependent_r_sets(k), rank = k)`
To get all the circuits of length at most k in that truncation T, you
could use `T.nonspanning_circuits()`. If the rank is much higher than k,
this will be faster than listing all the circuits of the original matroid
by `M.circuits()` and scrapping the long ones.
If that rank-k truncation T is k-chordal, then how far is T from being
binary? Is there a binary matroid B, a matroid N and an element e so that
N\e = T, N/e = B?
--
Ticket URL: <http://trac.sagemath.org/ticket/18484#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" 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-trac.
For more options, visit https://groups.google.com/d/optout.
