#18484: Implement k-chordality of a matroid
-------------------------------------+-------------------------------------
Reporter: Rudi | Owner:
Type: enhancement | Status: needs_info
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:
public/matroids/k_chordal-18484 | 6f9e8633781d3843c59d8b89e333b1844c090880
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by Rudi):
Replying to [comment:12 Rudi]:
> {{{
> X = set(C)
> e = X.pop()
> for x in self._closure(X)-X: # cl(X)=cl(C), and to be a chord x
must be spanned by C
> Ax = self._circuit(X.union([x]))
> Bx = C.difference(Ax).union([x])
> if self._is_circuit(Bx):
> return True # if x is spanned by C, then A+x is the
unique circuit in C-e+x; so x is a chord iff the complementary B is a
circuit.
> }}}
> I expect that is_circuit will be faster than checking membership of
circuits (since there are very many circuits in general) but that could
perhaps be tested.
Now that i think about it again, testing `self._is_dependent(Bx)` will do,
since Bx cannot properly contain a circuit D. Otherwise, (D+Ax)-x would
contain a circuit properly contained in C, contradiction. So you do not
need the set `circuits` in there.
--
Ticket URL: <http://trac.sagemath.org/ticket/18484#comment:13>
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.
