Flats matroids#

Matroids are characterized by a set of flats, which are sets invariant under closure. The FlatsMatroid class implements matroids using this information as data.

A FlatsMatroid can be created from another matroid or from a dictionary of flats. For a full description of allowed inputs, see below. It is recommended to use the Matroid() function for a more flexible way of constructing a FlatsMatroid and other classes of matroids. For direct access to the FlatsMatroid constructor, run:

Sage

sage: from sage.matroids.flats_matroid import FlatsMatroid

Python

>>> from sage.all import *
>>> from sage.matroids.flats_matroid import FlatsMatroid

AUTHORS:

Giorgos Mousa (2024-01-01): initial version

class sage.matroids.flats_matroid.FlatsMatroid[source]#

Bases: Matroid

INPUT:

M – matroid (default: None)
groundset – list (default: None); the groundset of the matroid
flats – (default: None); the dictionary of the lists of flats (indexed by their rank), or the list of all flats, or the lattice of flats of the matroid

Note

For a more flexible means of input, use the Matroid() function.

flats(k)[source]#

Return the flats of the matroid of specified rank.

INPUT:

k – integer

OUTPUT: SetSystem

EXAMPLES:

Sage

sage: from sage.matroids.flats_matroid import FlatsMatroid
sage: M = FlatsMatroid(matroids.Uniform(3, 4))
sage: sorted(M.flats(2), key=str)
[frozenset({0, 1}),
 frozenset({0, 2}),
 frozenset({0, 3}),
 frozenset({1, 2}),
 frozenset({1, 3}),
 frozenset({2, 3})]

Python

>>> from sage.all import *
>>> from sage.matroids.flats_matroid import FlatsMatroid
>>> M = FlatsMatroid(matroids.Uniform(Integer(3), Integer(4)))
>>> sorted(M.flats(Integer(2)), key=str)
[frozenset({0, 1}),
 frozenset({0, 2}),
 frozenset({0, 3}),
 frozenset({1, 2}),
 frozenset({1, 3}),
 frozenset({2, 3})]

flats_iterator(k)[source]#

Return an iterator over the flats of the matroid of specified rank.

INPUT:

k – integer

EXAMPLES:

Sage

sage: from sage.matroids.flats_matroid import FlatsMatroid
sage: M = FlatsMatroid(matroids.Uniform(3, 4))
sage: sorted([list(F) for F in M.flats_iterator(2)])
[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]

Python

>>> from sage.all import *
>>> from sage.matroids.flats_matroid import FlatsMatroid
>>> M = FlatsMatroid(matroids.Uniform(Integer(3), Integer(4)))
>>> sorted([list(F) for F in M.flats_iterator(Integer(2))])
[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]

full_rank()[source]#

Return the rank of the matroid.

The rank of the matroid is the size of the largest independent subset of the groundset.

OUTPUT: integer

EXAMPLES:

Sage

sage: from sage.matroids.flats_matroid import FlatsMatroid
sage: M = FlatsMatroid(matroids.Theta(6))
sage: M.full_rank()
6

Python

>>> from sage.all import *
>>> from sage.matroids.flats_matroid import FlatsMatroid
>>> M = FlatsMatroid(matroids.Theta(Integer(6)))
>>> M.full_rank()
6

groundset()[source]#

Return the groundset of the matroid.

The groundset is the set of elements that comprise the matroid.

OUTPUT: frozenset

EXAMPLES:

Sage

sage: from sage.matroids.flats_matroid import FlatsMatroid
sage: M = FlatsMatroid(matroids.Theta(2))
sage: sorted(M.groundset())
['x0', 'x1', 'y0', 'y1']

Python

>>> from sage.all import *
>>> from sage.matroids.flats_matroid import FlatsMatroid
>>> M = FlatsMatroid(matroids.Theta(Integer(2)))
>>> sorted(M.groundset())
['x0', 'x1', 'y0', 'y1']

is_valid()[source]#

Test if self obeys the matroid axioms.

For a matroid defined by its flats, we check the flats axioms.

If the lattice of flats has already been computed, we instead perform the equivalent check of whether it forms a geometric lattice.

OUTPUT: boolean

EXAMPLES:

Sage

sage: Matroid(flats={0: [[]], 1: [[0], [1]], 2: [[0, 1]]}).is_valid()
True
sage: Matroid(flats={0: [''], 1: ['a', 'b'], 2: ['ab']}).is_valid()
True
sage: M = Matroid(flats={0: [[]], 1: [[0], [1]]})  # missing groundset
sage: M.is_valid()
False
sage: M = Matroid(flats={0: [''],
....:                    1: ['0','1','2','3','4','5','6','7','8','9','a','b','c'],
....:                    2: ['45','46','47','4c','56','57','5c','67','6c','7c',
....:                        '048','149','24a','34b','059','15a','25b','358',
....:                        '06a','16b','268','369','07b','178','279','37a',
....:                        '0123c','89abc'],
....:                    3: ['0123456789abc']})
sage: M.is_valid()
True
sage: from sage.matroids.flats_matroid import FlatsMatroid
sage: FlatsMatroid(matroids.catalog.NonVamos()).is_valid()
True

Python

>>> from sage.all import *
>>> Matroid(flats={Integer(0): [[]], Integer(1): [[Integer(0)], [Integer(1)]], Integer(2): [[Integer(0), Integer(1)]]}).is_valid()
True
>>> Matroid(flats={Integer(0): [''], Integer(1): ['a', 'b'], Integer(2): ['ab']}).is_valid()
True
>>> M = Matroid(flats={Integer(0): [[]], Integer(1): [[Integer(0)], [Integer(1)]]})  # missing groundset
>>> M.is_valid()
False
>>> M = Matroid(flats={Integer(0): [''],
...                    Integer(1): ['0','1','2','3','4','5','6','7','8','9','a','b','c'],
...                    Integer(2): ['45','46','47','4c','56','57','5c','67','6c','7c',
...                        '048','149','24a','34b','059','15a','25b','358',
...                        '06a','16b','268','369','07b','178','279','37a',
...                        '0123c','89abc'],
...                    Integer(3): ['0123456789abc']})
>>> M.is_valid()
True
>>> from sage.matroids.flats_matroid import FlatsMatroid
>>> FlatsMatroid(matroids.catalog.NonVamos()).is_valid()
True

If we input a list or a lattice of flats, the method checks whether the lattice of flats is geometric:

Sage

sage: Matroid(flats=[[], [0], [1], [0, 1]]).is_valid()
True
sage: Matroid(flats=['', 'a', 'b', 'ab']).is_valid()
True
sage: M = Matroid(flats=['',  # missing an extention of flat ['5'] by '6'
....:                    '0','1','2','3','4','5','6','7','8','9','a','b','c',
....:                    '45','46','47','4c','57','5c','67','6c','7c',
....:                    '048','149','24a','34b','059','15a','25b','358',
....:                    '06a','16b','268','369','07b','178','279','37a',
....:                    '0123c','89abc',
....:                    '0123456789abc'])
sage: M.is_valid()
False
sage: Matroid(matroids.catalog.Fano().lattice_of_flats()).is_valid()
True

Python

>>> from sage.all import *
>>> Matroid(flats=[[], [Integer(0)], [Integer(1)], [Integer(0), Integer(1)]]).is_valid()
True
>>> Matroid(flats=['', 'a', 'b', 'ab']).is_valid()
True
>>> M = Matroid(flats=['',  # missing an extention of flat ['5'] by '6'
...                    '0','1','2','3','4','5','6','7','8','9','a','b','c',
...                    '45','46','47','4c','57','5c','67','6c','7c',
...                    '048','149','24a','34b','059','15a','25b','358',
...                    '06a','16b','268','369','07b','178','279','37a',
...                    '0123c','89abc',
...                    '0123456789abc'])
>>> M.is_valid()
False
>>> Matroid(matroids.catalog.Fano().lattice_of_flats()).is_valid()
True

Some invalid lists of flats are recognized before calling is_valid, upon the attempted matroid definition:

Sage

sage: M = Matroid(flats=[[], [0], [1]])  # missing groundset
Traceback (most recent call last):
...
ValueError: not a join-semilattice: no top element
sage: Matroid(flats=[[0], [1], [0, 1]])  # missing an intersection
Traceback (most recent call last):
...
ValueError: not a meet-semilattice: no bottom element
sage: Matroid(flats=[[], [0, 1], [2], [0], [1], [0, 1, 2]])
Traceback (most recent call last):
...
ValueError: the poset is not ranked

Python

>>> from sage.all import *
>>> M = Matroid(flats=[[], [Integer(0)], [Integer(1)]])  # missing groundset
Traceback (most recent call last):
...
ValueError: not a join-semilattice: no top element
>>> Matroid(flats=[[Integer(0)], [Integer(1)], [Integer(0), Integer(1)]])  # missing an intersection
Traceback (most recent call last):
...
ValueError: not a meet-semilattice: no bottom element
>>> Matroid(flats=[[], [Integer(0), Integer(1)], [Integer(2)], [Integer(0)], [Integer(1)], [Integer(0), Integer(1), Integer(2)]])
Traceback (most recent call last):
...
ValueError: the poset is not ranked

lattice_of_flats()[source]#

Return the lattice of flats of the matroid.

EXAMPLES:

Sage

sage: from sage.matroids.flats_matroid import FlatsMatroid
sage: M = FlatsMatroid(matroids.catalog.Fano())
sage: M.lattice_of_flats()
Finite lattice containing 16 elements

Python

>>> from sage.all import *
>>> from sage.matroids.flats_matroid import FlatsMatroid
>>> M = FlatsMatroid(matroids.catalog.Fano())
>>> M.lattice_of_flats()
Finite lattice containing 16 elements

relabel(mapping)[source]#

Return an isomorphic matroid with relabeled groundset.

The output is obtained by relabeling each element \(e\) by mapping[e], where mapping is a given injective map. If mapping[e] is not defined, then the identity map is assumed.

INPUT:

mapping – a Python object such that mapping[e] is the new label of \(e\)

OUTPUT: matroid

EXAMPLES:

Sage

sage: from sage.matroids.flats_matroid import FlatsMatroid
sage: M = FlatsMatroid(matroids.catalog.RelaxedNonFano())
sage: sorted(M.groundset())
[0, 1, 2, 3, 4, 5, 6]
sage: N = M.relabel({'g': 'x', 0: 'z'})  # 'g': 'x' is ignored
sage: from sage.matroids.utilities import cmp_elements_key
sage: sorted(N.groundset(), key=cmp_elements_key)
[1, 2, 3, 4, 5, 6, 'z']
sage: M.is_isomorphic(N)
True

Python

>>> from sage.all import *
>>> from sage.matroids.flats_matroid import FlatsMatroid
>>> M = FlatsMatroid(matroids.catalog.RelaxedNonFano())
>>> sorted(M.groundset())
[0, 1, 2, 3, 4, 5, 6]
>>> N = M.relabel({'g': 'x', Integer(0): 'z'})  # 'g': 'x' is ignored
>>> from sage.matroids.utilities import cmp_elements_key
>>> sorted(N.groundset(), key=cmp_elements_key)
[1, 2, 3, 4, 5, 6, 'z']
>>> M.is_isomorphic(N)
True

whitney_numbers()[source]#

Return the Whitney numbers of the first kind of the matroid.

The Whitney numbers of the first kind – here encoded as a vector \((w_0=1, \ldots, w_r)\) – are numbers of alternating sign, where \(w_i\) is the value of the coefficient of the \((r-i)\)-th degree term of the matroid’s characteristic polynomial. Moreover, \(|w_i|\) is the number of \((i-1)\)-dimensional faces of the broken circuit complex of the matroid.

OUTPUT: list of integers

EXAMPLES:

Sage

sage: from sage.matroids.flats_matroid import FlatsMatroid
sage: M = FlatsMatroid(matroids.catalog.BetsyRoss())
sage: M.whitney_numbers()
[1, -11, 35, -25]

Python

>>> from sage.all import *
>>> from sage.matroids.flats_matroid import FlatsMatroid
>>> M = FlatsMatroid(matroids.catalog.BetsyRoss())
>>> M.whitney_numbers()
[1, -11, 35, -25]

whitney_numbers2()[source]#

Return the Whitney numbers of the second kind of the matroid.

The Whitney numbers of the second kind are here encoded as a vector \((W_0, ..., W_r)\), where \(W_i\) is the number of flats of rank \(i\), and \(r\) is the rank of the matroid.

OUTPUT: list of integers

EXAMPLES:

Sage

sage: from sage.matroids.flats_matroid import FlatsMatroid
sage: M = FlatsMatroid(matroids.catalog.XY13())
sage: M.whitney_numbers2()
[1, 13, 78, 250, 394, 191, 1]

Python

>>> from sage.all import *
>>> from sage.matroids.flats_matroid import FlatsMatroid
>>> M = FlatsMatroid(matroids.catalog.XY13())
>>> M.whitney_numbers2()
[1, 13, 78, 250, 394, 191, 1]