Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
""" A catalog of posets and lattices.
Some common posets can be accessed through the ``posets.<tab>`` object::
sage: posets.PentagonPoset() Finite lattice containing 5 elements
Moreover, the set of all posets of order `n` is represented by ``Posets(n)``::
sage: Posets(5) Posets containing 5 elements
The infinite set of all posets can be used to find minimal examples::
sage: for P in Posets(): ....: if not P.is_series_parallel(): ....: break sage: P Finite poset containing 4 elements
**Catalog of common posets:**
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~posets.AntichainPoset` | Return an antichain on `n` elements. :meth:`~posets.BooleanLattice` | Return the Boolean lattice on `2^n` elements. :meth:`~posets.ChainPoset` | Return a chain on `n` elements. :meth:`~posets.Crown` | Return the crown poset on `2n` elements. :meth:`~posets.DiamondPoset` | Return the lattice of rank two on `n` elements. :meth:`~posets.DivisorLattice` | Return the divisor lattice of an integer. :meth:`~posets.IntegerCompositions` | Return the poset of integer compositions of `n`. :meth:`~posets.IntegerPartitions` | Return the poset of integer partitions of ``n``. :meth:`~posets.IntegerPartitionsDominanceOrder` | Return the lattice of integer partitions on the integer `n` ordered by dominance. :meth:`~posets.NoncrossingPartitions` | Return the poset of noncrossing partitions of a finite Coxeter group ``W``. :meth:`~posets.PentagonPoset` | Return the Pentagon poset. :meth:`~posets.PowerPoset` | Return a power poset. :meth:`~posets.RandomLattice` | Return a random lattice on `n` elements. :meth:`~posets.RandomPoset` | Return a random poset on `n` elements. :meth:`~posets.RestrictedIntegerPartitions` | Return the poset of integer partitions of `n`, ordered by restricted refinement. :meth:`~posets.SetPartitions` | Return the poset of set partitions of the set `\{1,\dots,n\}`. :meth:`~posets.ShardPoset` | Return the shard intersection order. :meth:`~posets.SSTPoset` | Return the poset on semistandard tableaux of shape `s` and largest entry `f` that is ordered by componentwise comparison. :meth:`~posets.StandardExample` | Return the standard example of a poset with dimension `n`. :meth:`~posets.SymmetricGroupAbsoluteOrderPoset` | The poset of permutations with respect to absolute order. :meth:`~posets.SymmetricGroupBruhatIntervalPoset` | The poset of permutations with respect to Bruhat order. :meth:`~posets.SymmetricGroupBruhatOrderPoset` | The poset of permutations with respect to Bruhat order. :meth:`~posets.SymmetricGroupWeakOrderPoset` | The poset of permutations of `\{ 1, 2, \ldots, n \}` with respect to the weak order. :meth:`~posets.TamariLattice` | Return the Tamari lattice. :meth:`~posets.TetrahedralPoset` | Return the Tetrahedral poset with `n-1` layers based on the input colors. :meth:`~posets.UpDownPoset` | Return the up-down poset on `n` elements. :meth:`~posets.YoungDiagramPoset` | Return the poset of cells in the Young diagram of a partition. :meth:`~posets.YoungsLattice` | Return Young's Lattice up to rank `n`. :meth:`~posets.YoungsLatticePrincipalOrderIdeal` | Return the principal order ideal of the partition `lam` in Young's Lattice.
Constructions ------------- """ #***************************************************************************** # Copyright (C) 2008 Peter Jipsen <jipsen@chapman.edu>, # Franco Saliola <saliola@gmail.com> # # Distributed under the terms of the GNU General Public License (GPL) # # This code is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU # General Public License for more details. # # The full text of the GPL is available at: # # http://www.gnu.org/licenses/ #***************************************************************************** from __future__ import print_function from six import add_metaclass, string_types
from sage.misc.classcall_metaclass import ClasscallMetaclass import sage.categories.posets from sage.combinat.permutation import Permutations, Permutation from sage.combinat.posets.posets import Poset, FinitePoset, FinitePosets_n from sage.combinat.posets.lattices import (LatticePoset, MeetSemilattice, JoinSemilattice, FiniteLatticePoset) from sage.categories.finite_posets import FinitePosets from sage.categories.finite_lattice_posets import FiniteLatticePosets from sage.graphs.digraph import DiGraph from sage.rings.integer import Integer
@add_metaclass(ClasscallMetaclass) class Posets(object): r""" A collection of posets and lattices.
EXAMPLES::
sage: posets.BooleanLattice(3) Finite lattice containing 8 elements sage: posets.ChainPoset(3) Finite lattice containing 3 elements sage: posets.RandomPoset(17,.15) Finite poset containing 17 elements
The category of all posets::
sage: Posets() Category of posets
The enumerated set of all posets on `3` elements, up to an isomorphism::
sage: Posets(3) Posets containing 3 elements
.. SEEALSO:: :class:`~sage.categories.posets.Posets`, :class:`FinitePosets`, :func:`Poset`
TESTS::
sage: P = Posets sage: TestSuite(P).run() """ @staticmethod def __classcall__(cls, n = None): r""" Return either the category of all posets, or the finite enumerated set of all finite posets on ``n`` elements up to an isomorphism.
EXAMPLES::
sage: Posets() Category of posets sage: Posets(4) Posets containing 4 elements """ except TypeError: raise TypeError("number of elements must be an integer, not {0}".format(n)) raise ValueError("number of elements must be non-negative, not {0}".format(n))
@staticmethod def BooleanLattice(n, facade=None): """ Return the Boolean lattice containing `2^n` elements.
- ``n`` (an integer) -- number of elements will be `2^n` - ``facade`` (boolean) -- whether to make the returned poset a facade poset (see :mod:`sage.categories.facade_sets`); the default behaviour is the same as the default behaviour of the :func:`~sage.combinat.posets.posets.Poset` constructor
EXAMPLES::
sage: posets.BooleanLattice(5) Finite lattice containing 32 elements """ except TypeError: raise TypeError("number of elements must be an integer, not {0}".format(n)) raise ValueError("number of elements must be non-negative, not {0}".format(n)) return LatticePoset( ([0], []) ) x in range(2**n)] category=FiniteLatticePosets(), facade=facade)
@staticmethod def ChainPoset(n, facade=None): """ Return a chain (a totally ordered poset) containing ``n`` elements.
- ``n`` (an integer) -- number of elements. - ``facade`` (boolean) -- whether to make the returned poset a facade poset (see :mod:`sage.categories.facade_sets`); the default behaviour is the same as the default behaviour of the :func:`~sage.combinat.posets.posets.Poset` constructor
EXAMPLES::
sage: C = posets.ChainPoset(6); C Finite lattice containing 6 elements sage: C.linear_extension() [0, 1, 2, 3, 4, 5]
TESTS::
sage: for i in range(5): ....: for j in range(5): ....: if C.covers(C(i),C(j)) and j != i+1: ....: print("TEST FAILED")
Check that :trac:`8422` is solved::
sage: posets.ChainPoset(0) Finite lattice containing 0 elements sage: C = posets.ChainPoset(1); C Finite lattice containing 1 elements sage: C.cover_relations() [] sage: C = posets.ChainPoset(2); C Finite lattice containing 2 elements sage: C.cover_relations() [[0, 1]] """ except TypeError: raise TypeError("number of elements must be an integer, not {0}".format(n)) raise ValueError("number of elements must be non-negative, not {0}".format(n)) format='vertices_and_edges') category=FiniteLatticePosets(), facade=facade)
@staticmethod def AntichainPoset(n, facade=None): """ Return an antichain (a poset with no comparable elements) containing `n` elements.
INPUT:
- ``n`` (an integer) -- number of elements - ``facade`` (boolean) -- whether to make the returned poset a facade poset (see :mod:`sage.categories.facade_sets`); the default behaviour is the same as the default behaviour of the :func:`~sage.combinat.posets.posets.Poset` constructor
EXAMPLES::
sage: A = posets.AntichainPoset(6); A Finite poset containing 6 elements
TESTS::
sage: for i in range(5): ....: for j in range(5): ....: if A.covers(A(i),A(j)): ....: print("TEST FAILED")
TESTS:
Check that :trac:`8422` is solved::
sage: posets.AntichainPoset(0) Finite poset containing 0 elements sage: C = posets.AntichainPoset(1); C Finite poset containing 1 elements sage: C.cover_relations() [] sage: C = posets.AntichainPoset(2); C Finite poset containing 2 elements sage: C.cover_relations() [] """ except TypeError: raise TypeError("number of elements must be an integer, not {0}".format(n)) raise ValueError("number of elements must be non-negative, not {0}".format(n))
@staticmethod def PentagonPoset(facade=None): """ Return the Pentagon poset.
INPUT:
- ``facade`` (boolean) -- whether to make the returned poset a facade poset (see :mod:`sage.categories.facade_sets`); the default behaviour is the same as the default behaviour of the :func:`~sage.combinat.posets.posets.Poset` constructor
EXAMPLES::
sage: P = posets.PentagonPoset(); P Finite lattice containing 5 elements sage: P.cover_relations() [[0, 1], [0, 2], [1, 4], [2, 3], [3, 4]]
TESTS:
This is smallest lattice that is not modular::
sage: P.is_modular() False
This poset and the :meth:`DiamondPoset` are the two smallest lattices which are not distributive::
sage: P.is_distributive() False sage: posets.DiamondPoset(5).is_distributive() False """
@staticmethod def DiamondPoset(n, facade=None): """ Return the lattice of rank two containing ``n`` elements.
INPUT:
- ``n`` -- number of elements, an integer at least 3
- ``facade`` (boolean) -- whether to make the returned poset a facade poset (see :mod:`sage.categories.facade_sets`); the default behaviour is the same as the default behaviour of the :func:`~sage.combinat.posets.posets.Poset` constructor
EXAMPLES::
sage: posets.DiamondPoset(7) Finite lattice containing 7 elements """ except TypeError: raise TypeError("number of elements must be an integer, not {0}".format(n)) raise ValueError("n must be an integer at least 3") category=FiniteLatticePosets(), facade=facade)
@staticmethod def Crown(n, facade=None): """ Return the crown poset of `2n` elements.
In this poset every element `i` for `0 \leq i \leq n-1` is covered by elements `i+n` and `i+n+1`, except that `n-1` is covered by `n` and `n+1`.
INPUT:
- ``n`` -- number of elements, an integer at least 2
- ``facade`` (boolean) -- whether to make the returned poset a facade poset (see :mod:`sage.categories.facade_sets`); the default behaviour is the same as the default behaviour of the :func:`~sage.combinat.posets.posets.Poset` constructor
EXAMPLES::
sage: posets.Crown(3) Finite poset containing 6 elements """ except TypeError: raise TypeError("number of elements must be an integer, not {0}".format(n)) raise ValueError("n must be an integer at least 2") facade=facade)
@staticmethod def DivisorLattice(n, facade=None): """ Return the divisor lattice of an integer.
Elements of the lattice are divisors of `n` and `x < y` in the lattice if `x` divides `y`.
INPUT:
- ``n`` -- an integer - ``facade`` (boolean) -- whether to make the returned poset a facade poset (see :mod:`sage.categories.facade_sets`); the default behaviour is the same as the default behaviour of the :func:`~sage.combinat.posets.posets.Poset` constructor
EXAMPLES::
sage: P = posets.DivisorLattice(12) sage: sorted(P.cover_relations()) [[1, 2], [1, 3], [2, 4], [2, 6], [3, 6], [4, 12], [6, 12]]
sage: P = posets.DivisorLattice(10, facade=False) sage: P(2) < P(5) False
TESTS::
sage: posets.DivisorLattice(1) Finite lattice containing 1 elements with distinguished linear extension """ except TypeError: raise TypeError("number of elements must be an integer, not {0}".format(n)) raise ValueError("n must be a positive integer") category=FiniteLatticePosets())
@staticmethod def IntegerCompositions(n): """ Return the poset of integer compositions of the integer ``n``.
A composition of a positive integer `n` is a list of positive integers that sum to `n`. The order is reverse refinement: `[p_1,p_2,...,p_l] < [q_1,q_2,...,q_m]` if `q` consists of an integer composition of `p_1`, followed by an integer composition of `p_2`, and so on.
EXAMPLES::
sage: P = posets.IntegerCompositions(7); P Finite poset containing 64 elements sage: len(P.cover_relations()) 192 """
@staticmethod def IntegerPartitions(n): """ Return the poset of integer partitions on the integer ``n``.
A partition of a positive integer `n` is a non-increasing list of positive integers that sum to `n`. If `p` and `q` are integer partitions of `n`, then `p` covers `q` if and only if `q` is obtained from `p` by joining two parts of `p` (and sorting, if necessary).
EXAMPLES::
sage: P = posets.IntegerPartitions(7); P Finite poset containing 15 elements sage: len(P.cover_relations()) 28 """ r""" Nested function for computing the lower covers of elements in the poset of integer partitions. """
@staticmethod def RestrictedIntegerPartitions(n): """ Return the poset of integer partitions on the integer `n` ordered by restricted refinement.
That is, if `p` and `q` are integer partitions of `n`, then `p` covers `q` if and only if `q` is obtained from `p` by joining two distinct parts of `p` (and sorting, if necessary).
EXAMPLES::
sage: P = posets.RestrictedIntegerPartitions(7); P Finite poset containing 15 elements sage: len(P.cover_relations()) 17
""" r""" Nested function for computing the lower covers of elements in the restricted poset of integer partitions. """
@staticmethod def IntegerPartitionsDominanceOrder(n): r""" Return the lattice of integer partitions on the integer `n` ordered by dominance.
That is, if `p=(p_1,\ldots,p_i)` and `q=(q_1,\ldots,q_j)` are integer partitions of `n`, then `p` is greater than `q` if and only if `p_1+\cdots+p_k > q_1+\cdots+q_k` for all `k`.
INPUT:
- ``n`` -- a positive integer
EXAMPLES::
sage: P = posets.IntegerPartitionsDominanceOrder(6); P Finite lattice containing 11 elements sage: P.cover_relations() [[[1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1]], [[2, 1, 1, 1, 1], [2, 2, 1, 1]], [[2, 2, 1, 1], [2, 2, 2]], [[2, 2, 1, 1], [3, 1, 1, 1]], [[2, 2, 2], [3, 2, 1]], [[3, 1, 1, 1], [3, 2, 1]], [[3, 2, 1], [3, 3]], [[3, 2, 1], [4, 1, 1]], [[3, 3], [4, 2]], [[4, 1, 1], [4, 2]], [[4, 2], [5, 1]], [[5, 1], [6]]] """ raise ValueError('n must be an integer')
@staticmethod def PowerPoset(n): """ Return the power poset on `n` element posets.
Elements of the power poset are all posets on the set `\{0, 1, \ldots, n-1\}` ordered by extension. That is, the antichain of `n` elements is the bottom and `P_a \le P_b` in the power poset if `P_b` is an extension of `P_a`.
These were studied in [Bru1994]_.
EXAMPLES::
sage: P3 = posets.PowerPoset(3); P3 Finite meet-semilattice containing 19 elements sage: all(P.is_chain() for P in P3.maximal_elements()) True
TESTS::
sage: P0 = posets.PowerPoset(0); P0 Finite meet-semilattice containing 1 elements sage: P0[0] Finite poset containing 0 elements sage: P1 = posets.PowerPoset(1); P1 Finite meet-semilattice containing 1 elements sage: P1[0] Finite poset containing 1 elements sage: P1[0][0] 0 """ # Todo: Make this faster.
except TypeError: raise TypeError("parameter n must be an integer, not {0}".format(n)) raise ValueError("parameter n must be non-negative, not {0}".format(n))
lambda A, B: all(B.is_lequal(x, y) for x,y in A.cover_relations_iterator()) ))
@staticmethod def RandomPoset(n, p): r""" Generate a random poset on ``n`` elements according to a probability ``p``.
INPUT:
- ``n`` - number of elements, a non-negative integer
- ``p`` - a probability, a real number between 0 and 1 (inclusive)
OUTPUT:
A poset on `n` elements. The probability `p` roughly measures width/height of the output: `p=0` always generates an antichain, `p=1` will return a chain. To create interesting examples, keep the probability small, perhaps on the order of `1/n`.
EXAMPLES::
sage: set_random_seed(0) # Results are reproducible sage: P = posets.RandomPoset(5, 0.3) sage: P.cover_relations() [[5, 4], [4, 2], [1, 2]]
.. SEEALSO:: :meth:`RandomLattice`
TESTS::
sage: posets.RandomPoset('junk', 0.5) Traceback (most recent call last): ... TypeError: number of elements must be an integer, not junk
sage: posets.RandomPoset(-6, 0.5) Traceback (most recent call last): ... ValueError: number of elements must be non-negative, not -6
sage: posets.RandomPoset(6, 'garbage') Traceback (most recent call last): ... TypeError: probability must be a real number, not garbage
sage: posets.RandomPoset(6, -0.5) Traceback (most recent call last): ... ValueError: probability must be between 0 and 1, not -0.5
sage: posets.RandomPoset(0, 0.5) Finite poset containing 0 elements """
@staticmethod def RandomLattice(n, p, properties=None): r""" Return a random lattice on ``n`` elements.
INPUT:
- ``n`` -- number of elements, a non-negative integer
- ``p`` -- a probability, a positive real number less than one
- ``properties`` -- a list of properties for the lattice. Currently implemented:
* ``None``, no restrictions for lattices to create * ``'planar'``, the lattice has an upward planar drawing * ``'dismantlable'`` (implicated by ``'planar'``) * ``'distributive'`` (implicated by ``'stone'``) * ``'stone'``
OUTPUT:
A lattice on `n` elements. When ``properties`` is ``None``, the probability `p` roughly measures number of covering relations of the lattice. To create interesting examples, make the probability near one, something like `0.98..0.999`.
Currently parameter ``p`` has no effect only when ``properties`` is not ``None``.
.. NOTE::
Results are reproducible in same Sage version only. Underlying algorithm may change in future versions.
EXAMPLES::
sage: set_random_seed(0) # Results are reproducible sage: L = posets.RandomLattice(8, 0.995); L Finite lattice containing 8 elements sage: L.cover_relations() [[7, 6], [7, 3], [7, 1], ..., [5, 4], [2, 4], [1, 4], [0, 4]] sage: L = posets.RandomLattice(10, 0, properties=['dismantlable']) sage: L.is_dismantlable() True
.. SEEALSO:: :meth:`RandomPoset`
TESTS::
sage: posets.RandomLattice('junk', 0.5) Traceback (most recent call last): ... TypeError: number of elements must be an integer, not junk
sage: posets.RandomLattice(-6, 0.5) Traceback (most recent call last): ... ValueError: number of elements must be non-negative, not -6
sage: posets.RandomLattice(6, 'garbage') Traceback (most recent call last): ... TypeError: probability must be a real number, not garbage
sage: posets.RandomLattice(6, -0.5) Traceback (most recent call last): ... ValueError: probability must be a positive real number and below 1, not -0.5
sage: posets.RandomLattice(10, 0.5, properties=['junk']) Traceback (most recent call last): ... ValueError: unknown value junk for 'properties'
sage: posets.RandomLattice(0, 0.5) Finite lattice containing 0 elements """
# Basic case, no special properties for lattice asked.
properties = set([properties]) else:
# Change this, if property='complemented' is added return posets.ChainPoset(n)
# Handling properties: planar => dismantlable, stone => distributive properties.discard('dismantlable') properties.discard('distributive')
# Test property combinations that are not implemented. raise NotImplementedError("combining 'distributive' with other properties is not implemented") raise NotImplementedError("combining 'stone' with other properties is not implemented")
D = _random_planar_lattice(n) D.relabel([i-1 for i in Permutations(n).random_element()]) return LatticePoset(D)
if properties == set(['stone']): D = _random_stone_lattice(n) D.relabel([i-1 for i in Permutations(n).random_element()]) return LatticePoset(D)
if properties == set(['distributive']): tmp = Poset(_random_distributive_lattice(n)).order_ideals_lattice(as_ideals=False) D = copy(tmp._hasse_diagram) D.relabel([i-1 for i in Permutations(n).random_element()]) return LatticePoset(D)
raise AssertionError("Bug in RandomLattice().")
@staticmethod def SetPartitions(n): r""" Return the lattice of set partitions of the set `\{1,\ldots,n\}` ordered by refinement.
INPUT:
- ``n`` -- a positive integer
EXAMPLES::
sage: posets.SetPartitions(4) Finite lattice containing 15 elements """ raise ValueError('n must be an integer')
cover_relations=True)
@staticmethod def SSTPoset(s, f=None): """ The poset on semistandard tableaux of shape ``s`` and largest entry ``f`` that is ordered by componentwise comparison of the entries.
INPUT:
- ``s`` - shape of the tableaux
- ``f`` - maximum fill number. This is an optional argument. If no maximal number is given, it will use the number of cells in the shape.
NOTE: This is a basic implementation and most certainly not the most efficient.
EXAMPLES::
sage: posets.SSTPoset([2,1]) Finite poset containing 8 elements
sage: posets.SSTPoset([2,1],4) Finite poset containing 20 elements
sage: posets.SSTPoset([2,1],2).cover_relations() [[[[1, 1], [2]], [[1, 2], [2]]]]
sage: posets.SSTPoset([3,2]).bottom() # long time (6s on sage.math, 2012) [[1, 1, 1], [2, 2]]
sage: posets.SSTPoset([3,2],4).maximal_elements() [[[3, 3, 4], [4, 4]]] """
@staticmethod def StandardExample(n, facade=None): r""" Return the partially ordered set on ``2n`` elements with dimension ``n``.
Let `P` be the poset on `\{0, 1, 2, \ldots, 2n-1\}` whose defining relations are that `i < j` for every `0 \leq i < n \leq j < 2n` except when `i + n = j`. The poset `P` is the so-called *standard example* of a poset with dimension `n`.
INPUT:
- ``n`` -- an integer `\ge 2`, dimension of the constructed poset - ``facade`` (boolean) -- whether to make the returned poset a facade poset (see :mod:`sage.categories.facade_sets`); the default behaviour is the same as the default behaviour of the :func:`~sage.combinat.posets.posets.Poset` constructor
OUTPUT:
The standard example of a poset of dimension `n`.
EXAMPLES::
sage: A = posets.StandardExample(3); A Finite poset containing 6 elements sage: A.dimension() 3
REFERENCES:
- [Gar2015]_ - [Ros1999]_
TESTS::
sage: A = posets.StandardExample(10); A Finite poset containing 20 elements sage: len(A.cover_relations()) 90
sage: P = posets.StandardExample(5, facade=False) sage: P(4) < P(3), P(4) > P(3) (False, False) """ except TypeError: raise TypeError("dimension must be an integer, not {0}".format(n)) raise ValueError("dimension must be at least 2, not {0}".format(n)) for j in range(n) if i != j]), facade=facade)
@staticmethod def SymmetricGroupBruhatOrderPoset(n): """ The poset of permutations with respect to Bruhat order.
EXAMPLES::
sage: posets.SymmetricGroupBruhatOrderPoset(4) Finite poset containing 24 elements """ for s in Permutations(n)} element_labels)
@staticmethod def SymmetricGroupBruhatIntervalPoset(start, end): """ The poset of permutations with respect to Bruhat order.
INPUT:
- ``start`` - list permutation
- ``end`` - list permutation (same n, of course)
.. note::
Must have ``start`` <= ``end``.
EXAMPLES:
Any interval is rank symmetric if and only if it avoids these permutations::
sage: P1 = posets.SymmetricGroupBruhatIntervalPoset([1,2,3,4], [3,4,1,2]) sage: P2 = posets.SymmetricGroupBruhatIntervalPoset([1,2,3,4], [4,2,3,1]) sage: ranks1 = [P1.rank(v) for v in P1] sage: ranks2 = [P2.rank(v) for v in P2] sage: [ranks1.count(i) for i in uniq(ranks1)] [1, 3, 5, 4, 1] sage: [ranks2.count(i) for i in uniq(ranks2)] [1, 3, 5, 6, 4, 1]
""" raise TypeError("Start (%s) and end (%s) must have same length." % (start, end)) raise TypeError("Must have start (%s) <= end (%s) in Bruhat order." % (start, end)) if succ_perm.bruhat_lequal(end)]
@staticmethod def SymmetricGroupWeakOrderPoset(n, labels="permutations", side="right"): r""" The poset of permutations of `\{ 1, 2, \ldots, n \}` with respect to the weak order (also known as the permutohedron order, cf. :meth:`~sage.combinat.permutation.Permutation.permutohedron_lequal`).
The optional variable ``labels`` (default: ``"permutations"``) determines the labelling of the elements if `n < 10`. The optional variable ``side`` (default: ``"right"``) determines whether the right or the left permutohedron order is to be used.
EXAMPLES::
sage: posets.SymmetricGroupWeakOrderPoset(4) Finite poset containing 24 elements """ element_labels = dict([[s,"".join(map(str,s.reduced_word_lexmin()))] for s in Permutations(n)])
def weak_covers(s): r""" Nested function for computing the covers of elements in the poset of left weak order for the symmetric group. """ return [v for v in s.bruhat_succ() if s.length() + (s.inverse().right_action_product(v)).length() == v.length()] else: r""" Nested function for computing the covers of elements in the poset of right weak order for the symmetric group. """ s.length() + (s.inverse().left_action_product(v)).length() == v.length()]
@staticmethod def TetrahedralPoset(n, *colors, **labels): r""" Return the tetrahedral poset based on the input colors.
This method will return the tetrahedral poset with n-1 layers and covering relations based on the input colors of 'green', 'red', 'orange', 'silver', 'yellow' and 'blue' as defined in [Striker2011]_. For particular color choices, the order ideals of the resulting tetrahedral poset will be isomorphic to known combinatorial objects.
For example, for the colors 'blue', 'yellow', 'orange', and 'green', the order ideals will be in bijection with alternating sign matrices. For the colors 'yellow', 'orange', and 'green', the order ideals will be in bijection with semistandard Young tableaux of staircase shape. For the colors 'red', 'orange', 'green', and optionally 'yellow', the order ideals will be in bijection with totally symmetric self-complementary plane partitions in a `2n \times 2n \times 2n` box.
INPUT:
- ``n`` - Defines the number (n-1) of layers in the poset.
- ``colors`` - The colors that define the covering relations of the poset. Colors used are 'green', 'red', 'yellow', 'orange', 'silver', and 'blue'.
- ``labels`` - Keyword variable used to determine whether the poset is labeled with integers or tuples. To label with integers, the method should be called with ``labels='integers'``. Otherwise, the labeling will default to tuples.
EXAMPLES::
sage: posets.TetrahedralPoset(4,'green','red','yellow','silver','blue','orange') Finite poset containing 10 elements
sage: posets.TetrahedralPoset(4,'green','red','yellow','silver','blue','orange', labels='integers') Finite poset containing 10 elements
sage: A = AlternatingSignMatrices(3) sage: p = A.lattice() sage: ji = p.join_irreducibles_poset() sage: tet = posets.TetrahedralPoset(3, 'green','yellow','blue','orange') sage: ji.is_isomorphic(tet) True """ except TypeError: raise TypeError("n must be an integer.") raise ValueError("n must be greater than 2.") raise ValueError("Color input must be from the following: 'green', 'red', 'yellow', 'orange', 'silver', and 'blue'.")
# shard intersection order import sage.combinat.shard_order ShardPoset = staticmethod(sage.combinat.shard_order.shard_poset)
# Tamari lattices import sage.combinat.tamari_lattices TamariLattice = staticmethod(sage.combinat.tamari_lattices.TamariLattice)
@staticmethod def CoxeterGroupAbsoluteOrderPoset(W, use_reduced_words=True): r""" Return the poset of elements of a Coxeter group with respect to absolute order.
INPUT:
- ``W`` -- a Coxeter group - ``use_reduced_words`` -- boolean (default: ``True``); if ``True``, then the elements are labeled by their lexicographically minimal reduced word
EXAMPLES::
sage: W = CoxeterGroup(['B', 3]) sage: posets.CoxeterGroupAbsoluteOrderPoset(W) Finite poset containing 48 elements
sage: W = WeylGroup(['B', 2], prefix='s') sage: posets.CoxeterGroupAbsoluteOrderPoset(W, False) Finite poset containing 8 elements """
@staticmethod def NoncrossingPartitions(W): """ Return the lattice of noncrossing partitions.
INPUT:
- ``W`` -- a finite Coxeter group or a Weyl group
EXAMPLES::
sage: W = CoxeterGroup(['A', 3]) sage: posets.NoncrossingPartitions(W) Finite lattice containing 14 elements
sage: W = WeylGroup(['B', 2], prefix='s') sage: posets.NoncrossingPartitions(W) Finite lattice containing 6 elements """
@staticmethod def SymmetricGroupAbsoluteOrderPoset(n, labels="permutations"): r""" Return the poset of permutations with respect to absolute order.
INPUT:
- ``n`` -- a positive integer
- ``label`` -- (default: ``'permutations'``) a label for the elements of the poset returned by the function; the options are
* ``'permutations'`` - labels the elements are given by their one-line notation * ``'reduced_words'`` - labels the elements by the lexicographically minimal reduced word * ``'cycles'`` - labels the elements by their expression as a product of cycles
EXAMPLES::
sage: posets.SymmetricGroupAbsoluteOrderPoset(4) Finite poset containing 24 elements sage: posets.SymmetricGroupAbsoluteOrderPoset(3, labels="cycles") Finite poset containing 6 elements sage: posets.SymmetricGroupAbsoluteOrderPoset(3, labels="reduced_words") Finite poset containing 6 elements """ for s in W}
@staticmethod def UpDownPoset(n, m=1): r""" Return the up-down poset on `n` elements where every `(m+1)` step is down and the rest are up.
The case where `m=1` is sometimes referred to as the zig-zag poset or the fence.
INPUT:
- ``n`` - nonnegative integer, number of elements in the poset - ``m`` - nonnegative integer (default 1), how frequently down steps occur
OUTPUT:
The partially ordered set on `\{ 0, 1, \ldots, n-1 \}` where `i` covers `i+1` if `m` divides `i+1`, and `i+1` covers `i` otherwise.
EXAMPLES::
sage: P = posets.UpDownPoset(7, 2); P Finite poset containing 7 elements sage: sorted(P.cover_relations()) [[0, 1], [1, 2], [3, 2], [3, 4], [4, 5], [6, 5]]
Fibonacci numbers as the number of antichains of a poset::
sage: [len(posets.UpDownPoset(n).antichains().list()) for n in range(6)] [1, 2, 3, 5, 8, 13]
TESTS::
sage: P = posets.UpDownPoset(0); P Finite poset containing 0 elements """ except TypeError: raise TypeError("number of elements must be an integer, not {0}".format(n)) raise ValueError("number of elements must be non-negative, not {0}".format(n)) except TypeError: raise TypeError("parameter m must be an integer, not {0}".format(m)) raise ValueError("parameter m must be positive, not {0}".format(m))
for i in range(n - 1)]
@staticmethod def YoungDiagramPoset(lam): """ Return the poset of cells in the Young diagram of a partition.
INPUT:
- ``lam`` -- a partition
EXAMPLES::
sage: P = posets.YoungDiagramPoset(Partition([2,2])); P Finite meet-semilattice containing 4 elements sage: P.cover_relations() [[(0, 0), (0, 1)], [(0, 0), (1, 0)], [(0, 1), (1, 1)], [(1, 0), (1, 1)]] """ """ Nested function that returns `True` if the cell `a` is to the left or above the cell `b` in the (English) Young diagram. """ (a[1] == b[1] - 1 and a[0] == b[0]))
@staticmethod def YoungsLattice(n): """ Return Young's Lattice up to rank `n`.
In other words, the poset of partitions of size less than or equal to `n` ordered by inclusion.
INPUT:
- ``n`` -- a positive integer
EXAMPLES::
sage: P = posets.YoungsLattice(3); P Finite meet-semilattice containing 7 elements sage: P.cover_relations() [[[], [1]], [[1], [1, 1]], [[1], [2]], [[1, 1], [1, 1, 1]], [[1, 1], [2, 1]], [[2], [2, 1]], [[2], [3]]] """
@staticmethod def YoungsLatticePrincipalOrderIdeal(lam): """ Return the principal order ideal of the partition `lam` in Young's Lattice.
INPUT:
- ``lam`` -- a partition
EXAMPLES::
sage: P = posets.YoungsLatticePrincipalOrderIdeal(Partition([2,2])) sage: P Finite lattice containing 6 elements sage: P.cover_relations() [[[], [1]], [[1], [1, 1]], [[1], [2]], [[1, 1], [2, 1]], [[2], [2, 1]], [[2, 1], [2, 2]]] """
""" Nested function returning those partitions obtained from the partition `l` by removing a single cell. """
""" Nested function returning those partitions contained in the partition `l` """ for m in lower_covers(l)]])
## RANDOM LATTICES
# Following are helper functions for random lattice generation. # There is no parameter checking, 0, 1, ..., n may or may not be a # linear extension, exact output type may vary, etc. Direct use is # discouraged. Use by posets.RandomLattice(..., properties=[...]).
def _random_lattice(n, p): """ Return a random lattice.
INPUT:
- ``n`` -- number of elements, a non-negative integer - ``p`` -- a number at least zero and less than one; higher number means more covering relations
OUTPUT:
A list of lists. Interpreted as a list of lower covers for a poset, it is a lattice with ``0..n-1`` as a linear extension.
EXAMPLES::
sage: set_random_seed(42) # Results are reproducible sage: sage.combinat.posets.poset_examples._random_lattice(7, 0.4) [[], [0], [0], [1, 2], [1], [0], [3, 4, 5]]
ALGORITHM::
We add elements one by one. We check that adding a maximal element `e` to a meet-semilattice `L` with maximal elements `M` will create a semilattice by checking that there is a meet for `e, m` for all `m \in M`. We do that by keeping track of meet matrix and list of maximal elements. """
# First add some random element as a lower cover. # Alone it can't change a semilattice to non-semilattice, # so we don't check it.
# An ad hoc solution. srqt(random()) instead of randint(0, i) # make number of coatoms closer to number of atoms.
# Check that lc_list + new is an antichain.
# Check that new has a unique meet with any maximal element.
else: # So, we found a new lower cover for i.
# Now compute new row and column to meet matrix.
def _random_dismantlable_lattice(n): """ Return a random dismantlable lattice on `n` elements.
INPUT:
- ``n`` -- number of elements, a non-negative integer
OUTPUT:
A digraph that can be interpreted as the Hasse diagram of a random dismantlable lattice. It has `0` as the bottom element and `n-1` as the top element, but otherwise `0, \ldots, n-1` *is not* usually a linear extension of the lattice.
EXAMPLES::
sage: set_random_seed(78) # Results are reproducible sage: D = sage.combinat.posets.poset_examples._random_dismantlable_lattice(10); D Digraph on 10 vertices sage: D.neighbors_in(8) [0]
ALGORITHM::
We add elements one by one by "de-dismantling", i.e. select a random pair of comparable elements and add a new element between them. """
def _random_planar_lattice(n): """ Return a random planar lattice on `n` elements.
INPUT:
- ``n`` -- number of elements, a non-negative integer
OUTPUT:
A random planar lattice. It has `0` as the bottom element and `n-1` as the top element, but otherwise `0, \ldots, n-1` *is not* usually a linear extension of the lattice.
EXAMPLES::
sage: set_random_seed(78) # Results are reproducible sage: D = sage.combinat.posets.poset_examples._random_planar_lattice(10); D Digraph on 10 vertices sage: D.neighbors_in(8) [1]
ALGORITHM::
Every planar lattice is dismantlable.
We add elements one by one like when generating dismantlable lattices, and after every addition check that we still have a planar lattice. """
def _random_distributive_lattice(n): """ Return a random poset that has `n` antichains.
INPUT:
- ``n`` -- number of elements, a non-negative integer
OUTPUT:
A random poset (as DiGraph) that has `n` antichains; i.e. a poset that's order ideals lattice has `n` elements.
EXAMPLES::
sage: g = sage.combinat.posets.poset_examples._random_distributive_lattice(10) sage: Poset(g).order_ideals_lattice(as_ideals=False).cardinality() 10
ALGORITHM:
Add elements until there are at least `n` antichains. Remove elements until there are at most `n` antichains. Repeat. """
return digraphs.Path(n-1)
D = copy(H) to_delete = H.random_vertex() for a in D.neighbors_in(to_delete): for b in D.neighbors_out(to_delete): D.add_edge(a, b) D.delete_vertex(to_delete) D.relabel({z:z-1 for z in range(to_delete + 1, D.order() + 1)}) H = HasseDiagram(D)
def _random_stone_lattice(n): """ Return a random Stone lattice on `n` elements.
INPUT:
- ``n`` -- number of elements, a non-negative integer
OUTPUT:
A random lattice (as a digraph) of `n` elements.
EXAMPLES::
sage: g = sage.combinat.posets.poset_examples._random_stone_lattice(10) sage: LatticePoset(g).is_stone() True
ALGORITHM:
Randomly split `n` to some factors. For every factor `p` generate a random distributive lattice on `p-1` elements and add a new bottom element to it. Compute the cartesian product of those lattices. """
posets = Posets |