summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRelease Manager <release@sagemath.org>2016-05-23 00:08:03 +0200
committerVolker Braun <vbraun.name@gmail.com>2016-05-23 00:08:03 +0200
commitce6b3dfe0903593b58ddb28b6d2104f196f95875 (patch)
treed35e988819e6c840cfb90b269bc3910924193893
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 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.py4
-rw-r--r--src/sage/combinat/sf/sfa.py6
-rw-r--r--src/sage/combinat/sf/witt.py2
-rw-r--r--src/sage/matroids/matroid.pxd2
-rw-r--r--src/sage/matroids/matroid.pyx319
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.