independentSets(Matroid,ZZ) -- independent subsets of a matroid

Synopsis

Function: independentSets
Usage:

independentSets(M, s)

independentSets M
Inputs:
- M, a matroid,
- s, an integer,
Optional inputs:
- Limit => ..., default value infinity,
Outputs:
- a list, of independent sets in M

Description

A subset of the ground set is called independent if it is contained in a basis, or equivalently, does not contain a circuit. This method returns certain independent subsets of the ground set, depending on the input:

If an integer $s$ is provided, then all independent subsets of size $s$ in $M$ are returned.

If a subset $S$ of the ground set of $M$ is given, then all maximal independent subsets of $S$ are returned.

If neither a size $s$ nor a subset $S$ is given, then all independent sets of M is returned (which may be quite large).

i1 : M = matroid({a,b,c,d},{{a,b},{a,c}})

o1 = a "matroid" of rank 2 on 4 elements

o1 : Matroid

i2 : independentSets(M, 2)

o2 = {set {0, 1}, set {0, 2}}

o2 : List

i3 : independentSets(M, set{1,2,3})

o3 = {set {1}, set {2}}

o3 : List

i4 : netList independentSets M

     +----------+
o4 = |set {}    |
     +----------+
     |set {0}   |
     +----------+
     |set {1}   |
     +----------+
     |set {0, 1}|
     +----------+
     |set {2}   |
     +----------+
     |set {0, 2}|
     +----------+

i5 : V = specificMatroid "vamos"

o5 = a "matroid" of rank 4 on 8 elements

o5 : Matroid

i6 : I3 = independentSets(V, 3)

o6 = {set {5, 6, 3}, set {5, 7, 3}, set {6, 7, 3}, set {5, 6, 7}, set {5, 6,
     ------------------------------------------------------------------------
     2}, set {5, 2, 7}, set {6, 2, 7}, set {5, 1, 6}, set {5, 1, 7}, set {1,
     ------------------------------------------------------------------------
     6, 7}, set {0, 5, 6}, set {0, 5, 7}, set {0, 6, 7}, set {4, 6, 3}, set
     ------------------------------------------------------------------------
     {4, 7, 3}, set {4, 6, 7}, set {4, 6, 2}, set {4, 2, 7}, set {4, 1, 6},
     ------------------------------------------------------------------------
     set {4, 1, 7}, set {4, 0, 6}, set {4, 0, 7}, set {1, 6, 3}, set {1, 7,
     ------------------------------------------------------------------------
     3}, set {0, 6, 3}, set {0, 7, 3}, set {1, 6, 2}, set {1, 2, 7}, set {0,
     ------------------------------------------------------------------------
     6, 2}, set {0, 2, 7}, set {4, 5, 3}, set {4, 5, 7}, set {4, 5, 2}, set
     ------------------------------------------------------------------------
     {4, 5, 1}, set {4, 0, 5}, set {5, 2, 3}, set {2, 7, 3}, set {5, 1, 3},
     ------------------------------------------------------------------------
     set {0, 5, 3}, set {5, 1, 2}, set {0, 5, 2}, set {0, 5, 1}, set {0, 1,
     ------------------------------------------------------------------------
     7}, set {4, 2, 3}, set {4, 1, 3}, set {4, 0, 3}, set {4, 1, 2}, set {4,
     ------------------------------------------------------------------------
     0, 2}, set {4, 0, 1}, set {1, 2, 3}, set {0, 2, 3}, set {0, 1, 3}, set
     ------------------------------------------------------------------------
     {0, 1, 2}, set {4, 5, 6}, set {6, 2, 3}, set {0, 1, 6}}

o6 : List

i7 : #I3

o7 = 56

Ways to use this method: