Orlik-Solomon Algebras¶
-
class
sage.algebras.orlik_solomon.
OrlikSolomonAlgebra
(R, M, ordering=None)¶ Bases:
sage.combinat.free_module.CombinatorialFreeModule
An Orlik-Solomon algebra.
Let
be a commutative ring. Let
be a matroid with ground set
. Let
denote the set of circuits of
. Let
denote the exterior algebra over
generated by
. The Orlik-Solomon ideal
is the ideal of
generated by
for all
, where
means that the term
is being omitted. The notation
is not a coincidence, as
is actually the image of
under the unique derivation
of
which sends all
to
.
It is easy to see that
not only for circuits
, but also for any dependent set
of
. Moreover, every dependent set
of
satisfies
.
The Orlik-Solomon algebra
is the quotient
. This is a graded finite-dimensional skew-commutative
-algebra. Fix some ordering on
; then, the NBC sets of
(that is, the subsets of
containing no broken circuit of
) form a basis of
. (Here, a broken circuit of
is defined to be the result of removing the smallest element from a circuit of
.)
In the current implementation, the basis of
is indexed by the NBC sets, which are implemented as frozensets.
INPUT:
R
– the base ringM
– the defining matroidordering
– (optional) an ordering of the ground set
EXAMPLES:
We create the Orlik-Solomon algebra of the uniform matroid
and do some basic computations:
sage: M = matroids.Uniform(3, 4) sage: OS = M.orlik_solomon_algebra(QQ) sage: OS.dimension() 14 sage: G = OS.algebra_generators() sage: M.broken_circuits() frozenset({frozenset({1, 2, 3})}) sage: G[1] * G[2] * G[3] OS{0, 1, 2} - OS{0, 1, 3} + OS{0, 2, 3}
REFERENCES:
[CE01] Raul Cordovil and Gwihen Etienne. A note on the Orlik-Solomon algebra. Europ. J. Combinatorics. 22 (2001). pp. 165-170. http://www.math.ist.utl.pt/~rcordov/Ce.pdf -
algebra_generators
()¶ Return the algebra generators of
self
.These form a family indexed by the ground set
of
. For each
, the
-th element is
.
EXAMPLES:
sage: M = matroids.Uniform(2, 2) sage: OS = M.orlik_solomon_algebra(QQ) sage: OS.algebra_generators() Finite family {0: OS{0}, 1: OS{1}} sage: M = matroids.Uniform(1, 2) sage: OS = M.orlik_solomon_algebra(QQ) sage: OS.algebra_generators() Finite family {0: OS{0}, 1: OS{0}} sage: M = matroids.Uniform(1, 3) sage: OS = M.orlik_solomon_algebra(QQ) sage: OS.algebra_generators() Finite family {0: OS{0}, 1: OS{0}, 2: OS{0}}
-
degree_on_basis
(m)¶ Return the degree of the basis element indexed by
m
.EXAMPLES:
sage: M = matroids.Wheel(3) sage: OS = M.orlik_solomon_algebra(QQ) sage: OS.degree_on_basis(frozenset([1])) 1 sage: OS.degree_on_basis(frozenset([0, 2, 3])) 3
-
one_basis
()¶ Return the index of the basis element corresponding to
in
self
.EXAMPLES:
sage: M = matroids.Wheel(3) sage: OS = M.orlik_solomon_algebra(QQ) sage: OS.one_basis() == frozenset([]) True
-
product_on_basis
(a, b)¶ Return the product in
self
of the basis elements indexed bya
andb
.EXAMPLES:
sage: M = matroids.Wheel(3) sage: OS = M.orlik_solomon_algebra(QQ) sage: OS.product_on_basis(frozenset([2]), frozenset([3,4])) OS{0, 1, 2} - OS{0, 1, 4} + OS{0, 2, 3} + OS{0, 3, 4}
sage: G = OS.algebra_generators() sage: prod(G) 0 sage: G[2] * G[4] -OS{1, 2} + OS{1, 4} sage: G[3] * G[4] * G[2] OS{0, 1, 2} - OS{0, 1, 4} + OS{0, 2, 3} + OS{0, 3, 4} sage: G[2] * G[3] * G[4] OS{0, 1, 2} - OS{0, 1, 4} + OS{0, 2, 3} + OS{0, 3, 4} sage: G[3] * G[2] * G[4] -OS{0, 1, 2} + OS{0, 1, 4} - OS{0, 2, 3} - OS{0, 3, 4}
TESTS:
Let us check that
for any subset
of the ground set:
sage: G = Graph([[1,2],[1,2],[2,3],[3,4],[4,2]], multiedges=True) sage: M = Matroid(G) sage: E = M.groundset_list() sage: OS = M.orlik_solomon_algebra(ZZ) sage: G = OS.algebra_generators() sage: import itertools sage: def test_prod(F): ....: LHS = OS.subset_image(frozenset(F)) ....: RHS = OS.prod([G[i] for i in sorted(F)]) ....: return LHS == RHS sage: all( test_prod(F) for k in range(len(E)+1) ....: for F in itertools.combinations(E, k) ) True
-
subset_image
(S)¶ Return the element
of
(
== self
) corresponding to a subsetof the ground set of
.
INPUT:
S
– a frozenset which is a subset of the ground set of
EXAMPLES:
sage: M = matroids.Wheel(3) sage: OS = M.orlik_solomon_algebra(QQ) sage: BC = sorted(M.broken_circuits(), key=sorted) sage: for bc in BC: (sorted(bc), OS.subset_image(bc)) ([1, 3], -OS{0, 1} + OS{0, 3}) ([1, 4, 5], OS{0, 1, 4} - OS{0, 1, 5} - OS{0, 3, 4} + OS{0, 3, 5}) ([2, 3, 4], OS{0, 1, 2} - OS{0, 1, 4} + OS{0, 2, 3} + OS{0, 3, 4}) ([2, 3, 5], OS{0, 2, 3} + OS{0, 3, 5}) ([2, 4], -OS{1, 2} + OS{1, 4}) ([2, 5], -OS{0, 2} + OS{0, 5}) ([4, 5], -OS{3, 4} + OS{3, 5}) sage: M4 = matroids.CompleteGraphic(4) sage: OS = M4.orlik_solomon_algebra(QQ) sage: OS.subset_image(frozenset({2,3,4})) OS{0, 2, 3} + OS{0, 3, 4}
An example of a custom ordering:
sage: G = Graph([[3, 4], [4, 1], [1, 2], [2, 3], [3, 5], [5, 6], [6, 3]]) sage: M = Matroid(G) sage: s = [(5, 6), (1, 2), (3, 5), (2, 3), (1, 4), (3, 6), (3, 4)] sage: sorted([sorted(c) for c in M.circuits()]) [[(1, 2), (1, 4), (2, 3), (3, 4)], [(3, 5), (3, 6), (5, 6)]] sage: OS = M.orlik_solomon_algebra(QQ, ordering=s) sage: OS.subset_image(frozenset([])) OS{} sage: OS.subset_image(frozenset([(1,2),(3,4),(1,4),(2,3)])) 0 sage: OS.subset_image(frozenset([(2,3),(1,2),(3,4)])) OS{(1, 2), (3, 4), (2, 3)} sage: OS.subset_image(frozenset([(1,4),(3,4),(2,3),(3,6),(5,6)])) -OS{(1, 2), (5, 6), (2, 3), (1, 4), (3, 6)} + OS{(1, 2), (5, 6), (3, 4), (1, 4), (3, 6)} - OS{(1, 2), (5, 6), (3, 4), (2, 3), (3, 6)} sage: OS.subset_image(frozenset([(1,4),(3,4),(2,3),(3,6),(3,5)])) OS{(1, 2), (5, 6), (2, 3), (1, 4), (3, 5)} - OS{(1, 2), (5, 6), (2, 3), (1, 4), (3, 6)} + OS{(1, 2), (5, 6), (3, 4), (1, 4), (3, 5)} + OS{(1, 2), (5, 6), (3, 4), (1, 4), (3, 6)} - OS{(1, 2), (5, 6), (3, 4), (2, 3), (3, 5)} - OS{(1, 2), (5, 6), (3, 4), (2, 3), (3, 6)}
TESTS:
sage: G = Graph([[1,2],[1,2],[2,3],[2,3],[1,3],[1,3]], multiedges=True) sage: M = Matroid(G) sage: sorted([sorted(c) for c in M.circuits()]) [[0, 1], [0, 2, 4], [0, 2, 5], [0, 3, 4], [0, 3, 5], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [2, 3], [4, 5]] sage: OS = M.orlik_solomon_algebra(QQ) sage: OS.subset_image(frozenset([])) OS{} sage: OS.subset_image(frozenset([1, 2, 3])) 0 sage: OS.subset_image(frozenset([1, 3, 5])) 0 sage: OS.subset_image(frozenset([1, 2])) OS{0, 2} sage: OS.subset_image(frozenset([3, 4])) -OS{0, 2} + OS{0, 4} sage: OS.subset_image(frozenset([1, 5])) OS{0, 4} sage: G = Graph([[1,2],[1,2],[2,3],[3,4],[4,2]], multiedges=True) sage: M = Matroid(G) sage: sorted([sorted(c) for c in M.circuits()]) [[0, 1], [2, 3, 4]] sage: OS = M.orlik_solomon_algebra(QQ) sage: OS.subset_image(frozenset([])) OS{} sage: OS.subset_image(frozenset([1, 3, 4])) -OS{0, 2, 3} + OS{0, 2, 4}
We check on a non-standard ordering:
sage: M = matroids.Wheel(3) sage: o = [5,4,3,2,1,0] sage: OS = M.orlik_solomon_algebra(QQ, ordering=o) sage: BC = sorted(M.broken_circuits(ordering=o), key=sorted) sage: for bc in BC: (sorted(bc), OS.subset_image(bc)) ([0, 1], OS{0, 3} - OS{1, 3}) ([0, 1, 4], OS{0, 3, 5} - OS{0, 4, 5} - OS{1, 3, 5} + OS{1, 4, 5}) ([0, 2], OS{0, 5} - OS{2, 5}) ([0, 2, 3], -OS{0, 3, 5} + OS{2, 3, 5}) ([1, 2], OS{1, 4} - OS{2, 4}) ([1, 2, 3], -OS{1, 3, 5} + OS{1, 4, 5} + OS{2, 3, 5} - OS{2, 4, 5}) ([3, 4], OS{3, 5} - OS{4, 5})