diff options
authorRelease Manager <>2016-05-23 00:08:03 +0200
committerVolker Braun <>2016-05-23 00:08:03 +0200
commitce6b3dfe0903593b58ddb28b6d2104f196f95875 (patch)
parentTrac #20647: Python 3.5.1 (diff)
parentfix a wrong doctest (diff)
Trac #14666: Test if a weight function is generic for a given matroid
Reported by darij on : 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: Reported by: Stefan Ticket author(s): Tara Fife Reviewer(s): Darij Grinberg
5 files changed, 316 insertions, 17 deletions
diff --git a/src/sage/combinat/ncsf_qsym/ b/src/sage/combinat/ncsf_qsym/
index 07598d5..0d1e47b 100644
--- a/src/sage/combinat/ncsf_qsym/
+++ b/src/sage/combinat/ncsf_qsym/
@@ -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/ b/src/sage/combinat/sf/
index ed4ade0..7a50838 100644
--- a/src/sage/combinat/sf/
+++ b/src/sage/combinat/sf/
@@ -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}`.
diff --git a/src/sage/combinat/sf/ b/src/sage/combinat/sf/
index 7af7a2f..e550bca 100644
--- a/src/sage/combinat/sf/
+++ b/src/sage/combinat/sf/
@@ -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