#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:
------------------------------------+------------------------
Old description:
> A matroid is k-chordal if every circuit `C` of size < k has a ''chord'',
> an element `x` of the ground set is a ''chord'' of `C` if there exists `C
> = A \cup B` such that `A \cup x, B \cup x` are circuits.
New description:
A matroid is k-chordal if every circuit `C` of size > k has a ''chord'',
an element `x` of the ground set is a ''chord'' of `C` if there exists `C
= A \cup B` such that `A \cup x, B \cup x` are circuits.
--
Comment (by tscrim):
Replying to [comment:7 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.
I use git directly:
{{{
$ git push <remote> branch_name
}}}
where `<remote>` is likely either `origin` or `trac`.
> > 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?
To begin with, I got the sign backwards on the definition of chordality.
Sorry about that, I was typing fast and didn't double-check. The
terminology comes from graphic matroids, where a graph is called k-chordal
if every cycle of length at least k has chord (a graph/matroid is called
chordal if it is 4-chordal). My current code just checks the definition
directly.
I'm not sure about the relation with binary matroids. Let me think on
that.
--
Ticket URL: <http://trac.sagemath.org/ticket/18484#comment:8>
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.
