**diff options**

author | Release Manager <release@sagemath.org> | 2016-05-23 00:08:03 +0200 |
---|---|---|

committer | Volker Braun <vbraun.name@gmail.com> | 2016-05-23 00:08:03 +0200 |

commit | ce6b3dfe0903593b58ddb28b6d2104f196f95875 (patch) | |

tree | d35e988819e6c840cfb90b269bc3910924193893 | |

parent | Trac #20647: Python 3.5.1 (diff) | |

parent | fix a wrong doctest (diff) |

Trac #14666: Test if a weight function is generic for a given matroid

Reported by darij on http://trac.sagemath.org/sage_trac/ticket/7477 :
Feature suggestion, if not already implemented: a method to test if a
given weight function is generic, i. e., has exactly one maximizing
basis. Of course, this is easy thanks to the exchange graph, as one only
needs to find a maximizing basis and then check that all its exchange
neighbours have strictly smaller weight. This function is useful to some
Hopf-algebraic constructions.
URL: http://trac.sagemath.org/14666
Reported by: Stefan
Ticket author(s): Tara Fife
Reviewer(s): Darij Grinberg

-rw-r--r-- | src/sage/combinat/ncsf_qsym/qsym.py | 4 | ||||

-rw-r--r-- | src/sage/combinat/sf/sfa.py | 6 | ||||

-rw-r--r-- | src/sage/combinat/sf/witt.py | 2 | ||||

-rw-r--r-- | src/sage/matroids/matroid.pxd | 2 | ||||

-rw-r--r-- | src/sage/matroids/matroid.pyx | 319 |

5 files changed, 316 insertions, 17 deletions

diff --git a/src/sage/combinat/ncsf_qsym/qsym.py b/src/sage/combinat/ncsf_qsym/qsym.py index 07598d5..0d1e47b 100644 --- a/src/sage/combinat/ncsf_qsym/qsym.py +++ b/src/sage/combinat/ncsf_qsym/qsym.py @@ -13,7 +13,7 @@ REFERENCES: .. [GriRei2014] Darij Grinberg, Victor Reiner, *Hopf algebras in combinatorics*, - 30 September 2014. :arxiv:`1409.8356v1`. + 25 August 2015. :arxiv:`1409.8356v3`. .. [Mal1993] Claudia Malvenuto, *Produits et coproduits des fonctions quasi-symetriques et de l'algebre des descentes*, @@ -2876,7 +2876,7 @@ class QuasiSymmetricFunctions(UniqueRepresentation, Parent): the `n`-fold concatenation of this Lyndon word with itself, occurring `n!` times in that shuffle power. But this can be deduced from Section 2 of [Rad1979]_. See also - Chapter 6 of [GriRei2014]_, specifically Theorem 6.99, for a + Chapter 6 of [GriRei2014]_, specifically Theorem 6.107, for a complete proof.) More precisely, he showed that `\mathrm{QSym}` is generated, as a free commutative `\mathbf{k}`-algebra, by the elements `\lambda^n(M_I)`, where diff --git a/src/sage/combinat/sf/sfa.py b/src/sage/combinat/sf/sfa.py index ed4ade0..7a50838 100644 --- a/src/sage/combinat/sf/sfa.py +++ b/src/sage/combinat/sf/sfa.py @@ -1008,7 +1008,7 @@ class SymmetricFunctionsBases(Category_realization_of_parent): basis ``self``. These functions are defined below. The Carlitz-Shareshian-Wachs symmetric functions have been - introduced in [GriRei2014]_, Exercise 2.84, as + introduced in [GriRei2014]_, Exercise 2.87, as refinements of a certain particular case of chromatic quasisymmetric functions defined by Shareshian and Wachs. Their definitions are as follows: @@ -1030,7 +1030,7 @@ class SymmetricFunctionsBases(Category_realization_of_parent): X_{n, d, s} = \sum_{w \in W(n, d, s)} x_w . This is a symmetric function (according to - [GriRei2014]_, Exercise 2.84(b)), and for `s = 0` equals + [GriRei2014]_, Exercise 2.87(b)), and for `s = 0` equals the `t^d`-coefficient of the descent enumerator of Smirnov words of length `n` (an example of a chromatic quasisymmetric function which happens to be symmetric -- @@ -1049,7 +1049,7 @@ class SymmetricFunctionsBases(Category_realization_of_parent): `w = (w_1, w_2, \ldots, w_n) \in W(n, d, s)`. These three power series `U_{n, d, s}`, `V_{n, d, s}` and `W_{n, d, s}` are symmetric functions as well - ([GriRei2014]_, Exercise 2.84(c)). Their sum is + ([GriRei2014]_, Exercise 2.87(c)). Their sum is `X_{n, d, s}`. REFERENCES: diff --git a/src/sage/combinat/sf/witt.py b/src/sage/combinat/sf/witt.py index 7af7a2f..e550bca 100644 --- a/src/sage/combinat/sf/witt.py +++ b/src/sage/combinat/sf/witt.py @@ -28,7 +28,7 @@ class SymmetricFunctionAlgebra_witt(multiplicative.SymmetricFunctionAlgebra_mult denoted by `(x_{\lambda})` in [HazWitt1]_, section 9.63, and by `(q_{\lambda})` in [DoranIV1996]_. We will denote this basis by `(w_{\lambda})` (which is precisely how it is denoted in - [GriRei2014]_, Exercise 2.76(d)). It is a multiplicative basis + [GriRei2014]_, Exercise 2.79(d)). It is a multiplicative basis (meaning that `w_{\emptyset} = 1` and that every partition `\lambda` satisfies `w_{\lambda} = w_{\lambda_1} w_{\lambda_2} w_{\lambda_3} \cdots`, diff --git a/src/sage/matroids/matroid.pxd b/src/sage/matroids/matroid.pxd index eb4fc8e..1325ddc 100644 --- a/src/sage/matroids/matroid.pxd +++ b/src/sage/matroids/matroid.pxd @@ -171,6 +171,8 @@ cdef class Matroid(SageObject): # optimization cpdef max_weight_independent(self, X=*, weights=*) cpdef max_weight_coindependent(self, X=*, weights=*) + cpdef is_max_weight_independent_generic(self, X=*, weights=*) + cpdef is_max_weight_coindependent_generic(self, X=*, weights=*) cpdef intersection(self, other, weights=*) cpdef _intersection(self, other, weights) cpdef _intersection_augmentation(self, other, weights, Y) diff --git a/src/sage/matroids/matroid.pyx b/src/sage/matroids/matroid.pyx index e33522c..52fc77e 100644 --- a/src/sage/matroids/matroid.pyx +++ b/src/sage/matroids/matroid.pyx @@ -120,6 +120,7 @@ additional functionality (e.g. linear extensions). - Optimization - :meth:`max_weight_independent() <sage.matroids.matroid.Matroid.max_weight_independent>` - :meth:`max_weight_coindependent() <sage.matroids.matroid.Matroid.max_weight_coindependent>` + - :meth:`is_max_weight_independent_generic() <sage.matroids.matroid.Matroid.is_max_weight_independent_generic>` - :meth:`intersection() <sage.matroids.matroid.Matroid.intersection>` - :meth:`intersection_unweighted() <sage.matroids.matroid.Matroid.intersection_unweighted>` @@ -1448,7 +1449,7 @@ cdef class Matroid(SageObject): cpdef closure(self, X): """ - Return the closure of a set. + Return the closure of a set ``X``. A set is *closed* if adding any extra element to it will increase the rank of the set. The *closure* of a set is the smallest closed set @@ -1481,9 +1482,10 @@ cdef class Matroid(SageObject): r""" Return the ``k``-closure of ``X``. - A set `S` is `k`-*closed* if the closure of any `k` element subsets - is contained in `S`. The `k`-*closure* of a set `X` is the smallest - `k`-closed set containing `X`. + A subset `S` of the groundset is `k`-*closed* if the closure of + any subset `T` of `S` satisfying `|T| \leq k` is contained in `S`. + The `k`-*closure* of a set `X` is the smallest `k`-closed set + containing `X`. INPUT: @@ -1674,7 +1676,7 @@ cdef class Matroid(SageObject): cpdef max_coindependent(self, X): """ - Compute a maximal coindependent subset. + Compute a maximal coindependent subset of ``X``. A set is *coindependent* if it is independent in the dual matroid. A set is coindependent if and only if the complement is *spanning* @@ -1709,7 +1711,7 @@ cdef class Matroid(SageObject): cpdef coclosure(self, X): """ - Return the coclosure of a set. + Return the coclosure of a set ``X``. A set is *coclosed* if it is closed in the dual matroid. The *coclosure* of `X` is the smallest coclosed set containing `X`. @@ -1832,7 +1834,8 @@ cdef class Matroid(SageObject): r""" Return the set of loops of the matroid. - A *loop* is a one-element dependent set. + A *loop* is an element `u` of the groundset such that the + one-element set `\{ u \}` is dependent. OUTPUT: @@ -1850,7 +1853,7 @@ cdef class Matroid(SageObject): cpdef is_independent(self, X): r""" - Check if a subset is independent in the matroid. + Check if a subset ``X`` is independent in the matroid. INPUT: @@ -1878,7 +1881,7 @@ cdef class Matroid(SageObject): cpdef is_dependent(self, X): r""" - Check if a subset is dependent in the matroid. + Check if a subset ``X`` is dependent in the matroid. INPUT: @@ -2061,8 +2064,9 @@ cdef class Matroid(SageObject): r""" Return the set of coloops of the matroid. - A *coloop* is a one-element cocircuit. It is a loop of the dual of the - matroid. + A *coloop* is an element `u` of the groundset such that the + one-element set `\{ u \}` is a cocircuit. In other words, a coloop + is a loop of the dual of the matroid. OUTPUT: @@ -6408,6 +6412,299 @@ cdef class Matroid(SageObject): res.discard(e) return frozenset(res) + cpdef is_max_weight_independent_generic(self, X=None, weights=None): + r""" + Test if only one basis of the subset ``X`` has maximal + weight. + + The *weight* of a subset ``S`` is ``sum(weights(e) for e in S)``. + + + INPUT: + + - ``X`` -- (default: the ground set of ``self``) a subset of + ``self.groundset()`` (given as a list, tuple or set). + - ``weights`` -- a dictionary or function mapping the elements of + ``X`` to nonnegative weights. + + OUTPUT: + + Boolean. + + ALGORITHM: + + The greedy algorithm. If a weight function is given, then sort the elements + of ``X`` by decreasing weight, and otherwise use the ordering in which ``X`` + lists its elements. Then greedily select elements if they are independent + of all that was selected before. If an element is not independent of the + previously selected elements, then we check if it is independent with the + previously selected elements with higher weight. + + + EXAMPLES:: + + sage: from sage.matroids.advanced import setprint + sage: M = matroids.named_matroids.Fano() + sage: M.is_max_weight_independent_generic() + False + + sage: def wt(x): + ....: return x + ....: + sage: M = matroids.Uniform(2, 8) + sage: M.is_max_weight_independent_generic(weights=wt) + True + sage: M.is_max_weight_independent_generic(weights={x: x for x in M.groundset()}) + True + sage: M.is_max_weight_independent_generic() + False + + Here is an example from [GriRei2014]_ (Example 7.56 in v3):: + + sage: A = Matrix(QQ, [[ 1, 1, 0, 0], + ....: [-1, 0, 1, 1], + ....: [ 0, -1, -1, -1]]) + sage: M = Matroid(A) + sage: M.is_max_weight_independent_generic() + False + sage: M.is_max_weight_independent_generic(weights={0: 1, 1: 3, 2: 3, 3: 2}) + True + sage: M.is_max_weight_independent_generic(weights={0: 1, 1: 3, 2: 2, 3: 2}) + False + sage: M.is_max_weight_independent_generic(weights={0: 2, 1: 3, 2: 1, 3: 1}) + True + """ + res = [] + r = 0 + if X is None: + X = self.groundset() + else: + if not self.groundset().issuperset(X): + raise ValueError("input is not a subset of the groundset.") + if len(X) == 0: + return True + + # If there are no weights, then our elements are already in weakly + # decreasing order. + if weights is None: + Y = list(X) + for e in Y: + res.append(e) + if self._rank(res) > r: + r += 1 + else: + del res[-1] + if self._rank([e]) >= 1: + return False + return True + + + # Construct ``Y``: a list of all elements of ``X`` + # in order of weakly decreasing weight. + # and a dictionary that gives the weights of the elements of ``X``. + else: + wt = [] + wt_dic = {} + try: + for e in X: + wt.append((weights[e], e)) + wt_dic[e] = weights[e] + except (IndexError, TypeError, ValueError): + try: + wt = [] + for e in X: + wt.append((weights(e), e)) + wt_dic[e] = weights(e) + except (TypeError, ValueError): + raise TypeError("the weights argument does not seem to be a collection of weights for the set X.") + + wt = sorted(wt, reverse=True) + if wt[-1][1] < 0: + raise ValueError("nonnegative weights were expected.") + Y = [e for (w, e) in wt] + + # ``res`` is a partially built maximal weighted basis. Namely, + # at the beginning of each iteration of the for-loop below, + # ``res`` is a maximal weighted basis of the set of all elements + # of ``Y`` already iterated over (in the order in which they have + # appeared in ``Y``). + # ``smres`` is the list of the elements of ``res`` that have + # strictly larger weight than ``e`` (at least, after the first + # if-clause). + # If ``smres`` is independent when ``e`` was not added to ``res``, + # then ``e`` could have been added to ``res`` if we made different + # choices in the greedy algorithm, so the maximal weight basis is + # not unique. Conversely, if every ``e`` that is iterated over + # but dependent on ``res`` at the time of its iteration is + # already dependent on ``smres``, the our maximal weight basis is + # unique. + smres = [] + for e in Y: + if len(res) >= 1: # This guarantees that ``smres`` is the elements of ``res`` that have strictly larger weight than ``e``. + if wt_dic[e] < wt_dic[res[-1]]: + smres=res[:] + res.append(e) + if self._rank(res) > r: + r += 1 + else: + smres.append(e) + if self._rank(smres) >= len(smres): + return False + del smres[-1] + del res[-1] + return True + + cpdef is_max_weight_coindependent_generic(self, X=None, weights=None): + r""" + Test if only one cobasis of the subset ``X`` has maximal + weight. + + The *weight* of a subset ``S`` is ``sum(weights(e) for e in S)``. + + INPUT: + + - ``X`` -- (default: the ground set of ``self``) a subset of + ``self.groundset()`` (given as a list, tuple or set). + - ``weights`` -- a dictionary or function mapping the elements of + ``X`` to nonnegative weights. + + OUTPUT: + + Boolean. + + ALGORITHM: + + The greedy algorithm. If a weight function is given, then sort the elements + of ``X`` by increasing weight, and otherwise use the ordering in which ``X`` + lists its elements. Then greedily select elements if they are coindependent + of all that was selected before. If an element is not coindependent of the + previously selected elements, then we check if it is coindependent with the + previously selected elements with higher weight. + + + EXAMPLES:: + + sage: from sage.matroids.advanced import setprint + sage: M = matroids.named_matroids.Fano() + sage: M.is_max_weight_coindependent_generic() + False + + sage: def wt(x): + ....: return x + ....: + sage: M = matroids.Uniform(2, 8) + sage: M.is_max_weight_coindependent_generic(weights=wt) + True + sage: M.is_max_weight_coindependent_generic(weights={x: x for x in M.groundset()}) + True + sage: M.is_max_weight_coindependent_generic() + False + + sage: M=matroids.Uniform(2,5) + sage: wt={0: 1, 1: 1, 2: 1, 3: 2, 4: 2} + sage: M.is_max_weight_independent_generic(weights=wt) + True + sage: M.dual().is_max_weight_coindependent_generic(weights=wt) + True + + + + Here is an example from [GriRei2014]_ (Example 7.56 in v3):: + + sage: A = Matrix(QQ, [[ 1, 1, 0, 0], + ....: [-1, 0, 1, 1], + ....: [ 0, -1, -1, -1]]) + sage: M = Matroid(A) + sage: M.is_max_weight_coindependent_generic() + False + sage: M.is_max_weight_coindependent_generic(weights={0: 1, 1: 3, 2: 3, 3: 2}) + True + sage: M.is_max_weight_coindependent_generic(weights={0: 1, 1: 3, 2: 2, 3: 2}) + False + sage: M.is_max_weight_coindependent_generic(weights={0: 2, 1: 3, 2: 1, 3: 1}) + False + """ + res = [] + r = 0 + if X is None: + X = self.groundset() + else: + if not self.groundset().issuperset(X): + raise ValueError("input is not a subset of the groundset.") + if len(X) == 0: + return True + + # If there are no weights, then our elements are already in weakly + # decreasing order. + if weights is None: + Y = list(X) + for e in Y: + res.append(e) + if self._corank(res) > r: + r += 1 + else: + del res[-1] + if self._corank([e]) >= 1: + return False + return True + + + # Construct ``Y``: a list of all elements of ``X`` + # in order of weakly decreasing weight. + # and a dictionary that gives the weights of the elementns of X. + else: + wt = [] + wt_dic = {} + try: + for e in X: + wt.append((weights[e], e)) + wt_dic[e] = weights[e] + except (IndexError, TypeError, ValueError): + try: + wt = [] + for e in X: + wt.append((weights(e), e)) + wt_dic[e] = weights(e) + except (TypeError, ValueError): + raise TypeError("the weights argument does not seem to be a collection of weights for the set X.") + + wt = sorted(wt, reverse = True) + if wt[-1][1] < 0: + raise ValueError("nonnegative weights were expected.") + Y = [e for (w, e) in wt] + + # ``res`` is a partially built maximal weighted cobasis. Namely, + # at the beginning of each iteration of the for-loop below, + # ``res`` is a maximal weighted cobasis of the set of all elements + # of ``Y`` already iterated over (in the order in which they have + # appeared in ``Y``). + # ``smres`` is the list of the elements of ``res`` that have + # strictly larger weight than ``e`` (at least, after the first + # if-clause). + # If ``smres`` is coindependent when ``e`` was not added to ``res``, + # then ``e`` could have been added to ``res`` if we made different + # choices in the greedy algorithm, so the maximal weight cobasis is + # not unique. Conversely, if every ``e`` that is iterated over + # but codependent on ``res`` at the time of its iteration is + # already codependent on ``smres``, the our maximal weight cobasis + # is unique. + smres = [] + for e in Y: + if len(res) >= 1: # This guarantees that ``smres`` is the elements of ``res`` that have strictly larger weight than ``e``. + if wt_dic[e] < wt_dic[res[-1]]: + smres=res[:] + res.append(e) + if self._corank(res) > r: + r += 1 + else: + smres.append(e) + if self._corank(smres) >= len(smres): + return False + del smres[-1] + del res[-1] + return True + + cpdef intersection(self, other, weights=None): r""" Return a maximum-weight common independent set. |