Extensions, modular cuts

[Stefan van Zwam]

Hi all,

I'm doing another pass of docstring editing to get our code accepted into Sage, and ran into the extension() method. It claims to require only a list of subsets, but actually seems to require a "modular cut". I don't think there is explicit code at present to compute the modular cut generated by a collection of subsets... maybe we should add it?

Note that I put "modular cut" in quotes. What is defined to be a "modular cut" in extension.pyx is actually a linear subclass:

Enumerate modular cuts of a given matroid. A modular cut is a collection

    of hyperplanes (flats of rank `r - 1` where `r` is the rank of the

    matroid) with the property that no modular triple of hyperplanes has

    exactly two members in the modular cut. A triple of hyperplanes in a

    matroid of rank r is modular if its intersection has rank `r - 2`.

For the sake of avoiding confusion, I think we shouldn't use the term "modular cut" unless we mean what we say. But somehow "linear subclass" doesn't sound very attractive either. What shall we do?

--Stefan. 

[Gordon Royle]

I think that the terminology is what it is, and we just have to use it. Linear subclass doesn't seem noticeably unpleasant!

[Rudi Pendavingh]

Hi all,

Yes, what we use are really linear subclasses, but they do correspond 1-1 to modular cuts: each linear subclass is the set of hyperplanes of a unique modular cut. So in my mind, a linear subclass is simply a compressed representation of a modular cut. And I like to call objects by their purpose, not their data structure.

But if calling them modular cuts causes confusion, then we should change the name. Then perhaps the docstring should point out the 1-1 correspondence somewhere, since I do think modular cuts are more widely used.

Best,

Rudi

--
 
---
You received this message because you are subscribed to the Google Groups "sage-matroid" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-matroid...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Stefan van Zwam]

Hi,

Ok, I'll change the terminology to linear subclass where necessary, add appropriate documentation, and in the user-exposed methods I will add some functionality that allows the use of modular cuts instead of linear subclasses. It's going to take a bit of work, but the options to the extension() method seem a bit half-baked anyway.

--Stefan.

[Rudi Pendavingh]

Hi Stefan,

if you want to expose modular cuts to the end user rather than linear subclasses, I propose doing so via a wrapper class for CutNode. This way, you avoid the actual construction of the full list of flats in that modular cut, unless there is a specific user request to create all those flats. The most likely use of a modular cut will still be to create extensions. It does not make sense to slow down this process with the automatic creation of a bunch of flats that you never look at again.

So this will entail:
- writing a wrapper class ModularCut storing a CutNode, and an __in__ method for that class (and perhaps also an iterator)
- rewriting ModularCuts so that it returns such ModularCut objects (specifically, the __get__() method), and
- rewiting the BasisMatroid.extension() method so that it also accepts a ModularCut as input. You can actually skip the construction of hyperplanes this way.

If it can wait until La Vaquerie I'm happy to do that work myself, but right now I'm completely swamped. But actually I don't think this will be more work than you have set out to do now -- the functionality you have planned will just become methods in the ModularCut class rather than somewhere else in the code.

--Rudi

[Stefan van Zwam]

Hi all,

What I want to do right now is the minimum amount of work to get our code accepted into Sage. Going through the documentation, I noticed that extension() currently purports to do the following:

cpdef extension(self, element=None, subsets=None):
r"""
Return an extension of the matroid.

An *extension* of `M` by an element `e` is a matroid `M'` such that
`M' \setminus e = M`. The element ``element`` is placed such that it
lies in the :meth:`closure <sage.matroids.matroid.Matroid.closure>` of
each set in ``subsets``.

INPUT:

- ``element`` -- (default: ``None``) the label of the new element. If
not specified, a new label will be generated automatically.
- ``subsets`` -- (default: ``None``) a set of subsets of the matroid.
The extension should be such that the new element is in the span of
each of these. If not specified, the element is assumed to be in the
span of no set (so it will be a coloop).

But in the implementation it does this:

# TODO: turn ``subsets`` into a set of hyperplanes
hyperplanes = subsets

I think that in order to satisfy the specification of the method, we will have to compute the entire modular cut generated by "subsets", right? So I added a method that does just that (also useful when checking for clones -- I actually wrote that code for my research a while back). Apart from that I'm perfectly happy to use only linear subclasses, and perfectly happy to call them just that (with plenty of explaining and cross references in the documentation).

Cheers,

Stefan.

[Rudi Pendavingh]

On 9 jun. 2013, at 21:31, Stefan van Zwam <stefan...@gmail.com> wrote:

> But in the implementation it does this:
>
> # TODO: turn ``subsets`` into a set of hyperplanes
> hyperplanes = subsets
>
> I think that in order to satisfy the specification of the method, we will have to compute the entire modular cut generated by "subsets", right

No, the method presently works as specified.

There is no need to create the actual modular cut from the 'subsets'. In the initializer of class ModularCuts, the hyperplanes containing at least one of the elements of 'subsets' are put in a set H, say. Then, the inclusionwise minimal linear subclass containing H is created directly.

I must have missed that this TODO was there, else I would have removed it.

---Rudi

[Stefan van Zwam]

On 9 jun. 2013, at 16:06, Rudi Pendavingh wrote:

>
>
> On 9 jun. 2013, at 21:31, Stefan van Zwam <stefan...@gmail.com> wrote:
>
>> But in the implementation it does this:
>>
>> # TODO: turn ``subsets`` into a set of hyperplanes
>> hyperplanes = subsets
>>
>> I think that in order to satisfy the specification of the method, we will have to compute the entire modular cut generated by "subsets", right
>
> No, the method presently works as specified.

Is that true? When I try to put an element in parallel to 'c', I get

sage: M = matroids.named_matroids.Fano()
sage: N = M.extension('z', subsets=['c'])
sage: N.rank('cz')
2

I agree that ModularCuts works as you claim, but the method extension() doesn't pass through it. It simply calls _extension, which assumes it's already dealing with a linear subclass.

The question is what's more expensive: compute the modular cut generated by the given subsets, or set up a ModularCuts instance and get the first member? For the time being I'll go with the former solution, just so we get something that works. Speedups in this method are for later (I'll put in a TODO reminder).

--Stefan.

[Rudi Pendavingh]

Hi Stefan,

I misread your mail, thought you were talking about extensionS(). Now I have no 'efficiency' objections ... BasisMatroid._extension() will also still be available.

The minimal linear subclass will also do in this case, but computing the entire modular cut may not be a very slow way to get there. You could consider throwing away the non-hyperplanes before passing to _extension().

Cheers,
Rudi