Functions and classes for mathematical sandpiles.
Version: 2.4
AUTHOR:
MAJOR CHANGES
NEW METHODS
Sandpile: avalanche_polynomial, genus, group_gens, help, jacobian_representatives, markov_chain, picard_representatives, smith_form, stable_configs, stationary_density, tutte_polynomial.
SandpileConfig: burst_size, help.
SandpileDivisor: help, is_linearly_equivalent, is_q_reduced, is_weierstrass_pt, polytope, polytope_integer_pts, q_reduced, rank, simulate_threshold, stabilize, weierstrass_div, weierstrass_gap_seq, weierstrass_pts, weierstrass_rank_seq.
DEPRECATED
SandpileDivisor.linear_system, SandpileDivisor.r_of_D, sandlib method, complete_sandpile, grid_sandpile, triangle_sandpile, aztec_sandpile, random_digraph, random_tree, glue_graphs, admissible_partitions, firing_vector, min_cycles.
MINOR CHANGES
EXAMPLES:
For general help, enter Sandpile.help(), SandpileConfig.help(), and SandpileDivisor.help(). Miscellaneous examples appear below.
A weighted directed graph given as a Python dictionary:
sage: from sage.sandpiles import *
sage: g = {0: {}, 1: {0: 1, 2: 1, 3: 1}, 2: {1: 1, 3: 1, 4: 1}, 3: {1: 1, 2: 1, 4: 1}, 4: {2: 1, 3: 1}}
The associated sandpile with 0 chosen as the sink:
sage: S = Sandpile(g,0)
Or just:
sage: S = Sandpile(g)
A picture of the graph:
sage: S.show()
The relevant Laplacian matrices:
sage: S.laplacian()
[ 0 0 0 0 0]
[-1 3 -1 -1 0]
[ 0 -1 3 -1 -1]
[ 0 -1 -1 3 -1]
[ 0 0 -1 -1 2]
sage: S.reduced_laplacian()
[ 3 -1 -1 0]
[-1 3 -1 -1]
[-1 -1 3 -1]
[ 0 -1 -1 2]
The number of elements of the sandpile group for S:
sage: S.group_order()
8
The structure of the sandpile group:
sage: S.invariant_factors()
[1, 1, 1, 8]
The elements of the sandpile group for S:
sage: S.recurrents()
[{1: 2, 2: 2, 3: 2, 4: 1},
{1: 2, 2: 2, 3: 2, 4: 0},
{1: 2, 2: 1, 3: 2, 4: 0},
{1: 2, 2: 2, 3: 0, 4: 1},
{1: 2, 2: 0, 3: 2, 4: 1},
{1: 2, 2: 2, 3: 1, 4: 0},
{1: 2, 2: 1, 3: 2, 4: 1},
{1: 2, 2: 2, 3: 1, 4: 1}]
The maximal stable element (2 grains of sand on vertices 1, 2, and 3, and 1 grain of sand on vertex 4:
sage: S.max_stable()
{1: 2, 2: 2, 3: 2, 4: 1}
sage: S.max_stable().values()
[2, 2, 2, 1]
The identity of the sandpile group for S:
sage: S.identity()
{1: 2, 2: 2, 3: 2, 4: 0}
An arbitrary sandpile configuration:
sage: c = SandpileConfig(S,[1,0,4,-3])
sage: c.equivalent_recurrent()
{1: 2, 2: 2, 3: 2, 4: 0}
Some group operations:
sage: m = S.max_stable()
sage: i = S.identity()
sage: m.values()
[2, 2, 2, 1]
sage: i.values()
[2, 2, 2, 0]
sage: m + i # coordinate-wise sum
{1: 4, 2: 4, 3: 4, 4: 1}
sage: m - i
{1: 0, 2: 0, 3: 0, 4: 1}
sage: m & i # add, then stabilize
{1: 2, 2: 2, 3: 2, 4: 1}
sage: e = m + m
sage: e
{1: 4, 2: 4, 3: 4, 4: 2}
sage: ~e # stabilize
{1: 2, 2: 2, 3: 2, 4: 0}
sage: a = -m
sage: a & m
{1: 0, 2: 0, 3: 0, 4: 0}
sage: a * m # add, then find the equivalent recurrent
{1: 2, 2: 2, 3: 2, 4: 0}
sage: a^3 # a*a*a
{1: 2, 2: 2, 3: 2, 4: 1}
sage: a^(-1) == m
True
sage: a < m # every coordinate of a is < that of m
True
Firing an unstable vertex returns resulting configuration:
sage: c = S.max_stable() + S.identity()
sage: c.fire_vertex(1)
{1: 1, 2: 5, 3: 5, 4: 1}
sage: c
{1: 4, 2: 4, 3: 4, 4: 1}
Fire all unstable vertices:
sage: c.unstable()
[1, 2, 3]
sage: c.fire_unstable()
{1: 3, 2: 3, 3: 3, 4: 3}
Stabilize c, returning the resulting configuration and the firing vector:
sage: c.stabilize(True)
[{1: 2, 2: 2, 3: 2, 4: 1}, {1: 6, 2: 8, 3: 8, 4: 8}]
sage: c
{1: 4, 2: 4, 3: 4, 4: 1}
sage: S.max_stable() & S.identity() == c.stabilize()
True
The number of superstable configurations of each degree:
sage: S.h_vector()
[1, 3, 4]
sage: S.postulation()
2
the saturated homogeneous toppling ideal:
sage: S.ideal()
Ideal (x1 - x0, x3*x2 - x0^2, x4^2 - x0^2, x2^3 - x4*x3*x0, x4*x2^2 - x3^2*x0, x3^3 - x4*x2*x0, x4*x3^2 - x2^2*x0) of Multivariate Polynomial Ring in x4, x3, x2, x1, x0 over Rational Field
its minimal free resolution:
sage: S.resolution()
'R^1 <-- R^7 <-- R^15 <-- R^13 <-- R^4'
and its Betti numbers:
sage: S.betti()
0 1 2 3 4
------------------------------------
0: 1 1 - - -
1: - 2 2 - -
2: - 4 13 13 4
------------------------------------
total: 1 7 15 13 4
Some various ways of creating Sandpiles:
sage: S = sandpiles.Complete(4) # for more options enter ``sandpile.TAB``
sage: S = sandpiles.Wheel(6)
A multidigraph with loops (vertices 0, 1, 2; for example, there is a directed edge from vertex 2 to vertex 1 of weight 3, which can be thought of as three directed edges of the form (2,3). There is also a single loop at vertex 2 and an edge (2,0) of weight 2):
sage: S = Sandpile({0:[1,2], 1:[0,0,2], 2:[0,0,1,1,1,2], 3:[2]})
Using the graph library (vertex 1 is specified as the sink; omitting this would make the sink vertex 0 by default):
sage: S = Sandpile(graphs.PetersenGraph(),1)
Distribution of avalanche sizes:
sage: S = sandpiles.Grid(10,10)
sage: m = S.max_stable()
sage: a = []
sage: for i in range(1000):
....: m = m.add_random()
....: m, f = m.stabilize(True)
....: a.append(sum(f.values()))
....:
sage: p = list_plot([[log(i+1),log(a.count(i))] for i in [0..max(a)] if a.count(i)])
sage: p.axes_labels(['log(N)','log(D(N))'])
sage: t = text("Distribution of avalanche sizes", (2,2), rgbcolor=(1,0,0))
sage: show(p+t,axes_labels=['log(N)','log(D(N))'])
Working with sandpile divisors::
sage: S = sandpiles.Complete(4)
sage: D = SandpileDivisor(S, [0,0,0,5])
sage: E = D.stabilize(); E
{0: 1, 1: 1, 2: 1, 3: 2}
sage: D.is_linearly_equivalent(E)
True
sage: D.q_reduced()
{0: 4, 1: 0, 2: 0, 3: 1}
sage: S = sandpiles.Complete(4)
sage: D = SandpileDivisor(S, [0,0,0,5])
sage: E = D.stabilize(); E
{0: 1, 1: 1, 2: 1, 3: 2}
sage: D.is_linearly_equivalent(E)
True
sage: D.q_reduced()
{0: 4, 1: 0, 2: 0, 3: 1}
sage: D.rank()
2
sage: D.effective_div()
[{0: 0, 1: 0, 2: 0, 3: 5},
{0: 0, 1: 4, 2: 0, 3: 1},
{0: 0, 1: 0, 2: 4, 3: 1},
{0: 1, 1: 1, 2: 1, 3: 2},
{0: 4, 1: 0, 2: 0, 3: 1}]
sage: D.effective_div(False)
[[0, 0, 0, 5], [0, 4, 0, 1], [0, 0, 4, 1], [1, 1, 1, 2], [4, 0, 0, 1]]
sage: D.rank()
2
sage: D.rank(True)
(2, {0: 2, 1: 1, 2: 0, 3: 0})
sage: E = D.rank(True)[1] # E proves the rank is not 3
sage: E.values()
[2, 1, 0, 0]
sage: E.deg()
3
sage: rank(D - E)
-1
sage: (D - E).effective_div()
[]
sage: D.weierstrass_pts()
(0, 1, 2, 3)
sage: D.weierstrass_rank_seq(0)
(2, 1, 0, 0, 0, -1)
sage: D.weierstrass_pts()
(0, 1, 2, 3)
sage: D.weierstrass_rank_seq(0)
(2, 1, 0, 0, 0, -1)
Bases: sage.graphs.digraph.DiGraph
Class for Dhar’s abelian sandpile model.
The constant configuration with all values set to \(k\).
INPUT:
k – integer
OUTPUT:
SandpileConfig
EXAMPLES:
sage: s = sandpiles.Diamond()
sage: s.all_k_config(7)
{1: 7, 2: 7, 3: 7}
The divisor with all values set to \(k\).
INPUT:
k – integer
OUTPUT:
SandpileDivisor
EXAMPLES:
sage: S = sandpiles.House()
sage: S.all_k_div(7)
{0: 7, 1: 7, 2: 7, 3: 7, 4: 7}
The avalanche polynomial. See NOTE for details.
INPUT:
multivariable – (default: True) boolean
OUTPUT:
polynomial
EXAMPLES:
sage: s = sandpiles.Complete(4)
sage: s.avalanche_polynomial()
9*x0*x1*x2 + 2*x0*x1 + 2*x0*x2 + 2*x1*x2 + 3*x0 + 3*x1 + 3*x2 + 24
sage: s.avalanche_polynomial(False)
9*x0^3 + 6*x0^2 + 9*x0 + 24
Note
For each nonsink vertex \(v\), let \(x_v\) be an indeterminate. If \((r,v)\) is a pair consisting of a recurrent \(r\) and nonsink vertex \(v\), then for each nonsink vertex \(w\), let \(n_w\) be the number of times vertex \(w\) fires in the stabilization of \(r + v\). Let \(M(r,v)\) be the monomial \(\prod_w x_w^{n_w}\), i.e., the exponent records the vector of \(n_w\) as \(w\) ranges over the nonsink vertices. The avalanche polynomial is then the sum of \(M(r,v)\) as \(r\) ranges over the recurrents and \(v\) ranges over the nonsink vertices. If multivariable is False, then set all the indeterminates equal to each other (and, thus, only count the number of vertex firings in the stabilizations, forgetting which particular vertices fired).
The Betti table for the homogeneous toppling ideal. If verbose is True, it prints the standard Betti table, otherwise, it returns a less formated table.
INPUT:
verbose – (default: True) boolean
OUTPUT:
Betti numbers for the sandpile
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: S.betti()
0 1 2 3
------------------------------
0: 1 - - -
1: - 2 - -
2: - 4 9 4
------------------------------
total: 1 6 9 4
sage: S.betti(False)
[1, 6, 9, 4]
The support-complexes with non-trivial homology. (See NOTE.)
OUTPUT:
list (of pairs [divisors, corresponding simplicial complex])
EXAMPLES:
sage: S = Sandpile({0:{},1:{0: 1, 2: 1, 3: 4},2:{3: 5},3:{1: 1, 2: 1}},0)
sage: p = S.betti_complexes()
sage: p[0]
[{0: -8, 1: 5, 2: 4, 3: 1}, Simplicial complex with vertex set (1, 2, 3) and facets {(1, 2), (3,)}]
sage: S.resolution()
'R^1 <-- R^5 <-- R^5 <-- R^1'
sage: S.betti()
0 1 2 3
------------------------------
0: 1 - - -
1: - 5 5 -
2: - - - 1
------------------------------
total: 1 5 5 1
sage: len(p)
11
sage: p[0][1].homology()
{0: Z, 1: 0}
sage: p[-1][1].homology()
{0: 0, 1: 0, 2: Z}
Note
A support-complex is the simplicial complex formed from the supports of the divisors in a linear system.
The minimal burning configuration.
OUTPUT:
dict (configuration)
EXAMPLES:
sage: g = {0:{},1:{0:1,3:1,4:1},2:{0:1,3:1,5:1}, \
3:{2:1,5:1},4:{1:1,3:1},5:{2:1,3:1}}
sage: S = Sandpile(g,0)
sage: S.burning_config()
{1: 2, 2: 0, 3: 1, 4: 1, 5: 0}
sage: S.burning_config().values()
[2, 0, 1, 1, 0]
sage: S.burning_script()
{1: 1, 2: 3, 3: 5, 4: 1, 5: 4}
sage: script = S.burning_script().values()
sage: script
[1, 3, 5, 1, 4]
sage: matrix(script)*S.reduced_laplacian()
[2 0 1 1 0]
Note
The burning configuration and script are computed using a modified version of Speer’s script algorithm. This is a generalization to directed multigraphs of Dhar’s burning algorithm.
A burning configuration is a nonnegative integer-linear combination of the rows of the reduced Laplacian matrix having nonnegative entries and such that every vertex has a path from some vertex in its support. The corresponding burning script gives the integer-linear combination needed to obtain the burning configuration. So if \(b\) is the burning configuration, \(\sigma\) is its script, and \(\tilde{L}\) is the reduced Laplacian, then \(\sigma\cdot \tilde{L} = b\). The minimal burning configuration is the one with the minimal script (its components are no larger than the components of any other script for a burning configuration).
The following are equivalent for a configuration \(c\) with burning configuration \(b\) having script \(\sigma\):
- \(c\) is recurrent;
- \(c+b\) stabilizes to \(c\);
- the firing vector for the stabilization of \(c+b\) is \(\sigma\).
A script for the minimal burning configuration.
OUTPUT:
dict
EXAMPLES:
sage: g = {0:{},1:{0:1,3:1,4:1},2:{0:1,3:1,5:1},\
3:{2:1,5:1},4:{1:1,3:1},5:{2:1,3:1}}
sage: S = Sandpile(g,0)
sage: S.burning_config()
{1: 2, 2: 0, 3: 1, 4: 1, 5: 0}
sage: S.burning_config().values()
[2, 0, 1, 1, 0]
sage: S.burning_script()
{1: 1, 2: 3, 3: 5, 4: 1, 5: 4}
sage: script = S.burning_script().values()
sage: script
[1, 3, 5, 1, 4]
sage: matrix(script)*S.reduced_laplacian()
[2 0 1 1 0]
Note
The burning configuration and script are computed using a modified version of Speer’s script algorithm. This is a generalization to directed multigraphs of Dhar’s burning algorithm.
A burning configuration is a nonnegative integer-linear combination of the rows of the reduced Laplacian matrix having nonnegative entries and such that every vertex has a path from some vertex in its support. The corresponding burning script gives the integer-linear combination needed to obtain the burning configuration. So if \(b\) is the burning configuration, \(s\) is its script, and \(L_{\mathrm{red}}\) is the reduced Laplacian, then \(s\cdot L_{\mathrm{red}}= b\). The minimal burning configuration is the one with the minimal script (its components are no larger than the components of any other script for a burning configuration).
The following are equivalent for a configuration \(c\) with burning configuration \(b\) having script \(s\):
- \(c\) is recurrent;
- \(c+b\) stabilizes to \(c\);
- the firing vector for the stabilization of \(c+b\) is \(s\).
The canonical divisor. This is the divisor with \(\deg(v)-2\) grains of sand on each vertex (not counting loops). Only for undirected graphs.
OUTPUT:
SandpileDivisor
EXAMPLES:
sage: S = sandpiles.Complete(4)
sage: S.canonical_divisor()
{0: 1, 1: 1, 2: 1, 3: 1}
sage: s = Sandpile({0:[1,1],1:[0,0,1,1,1]},0)
sage: s.canonical_divisor() # loops are disregarded
{0: 0, 1: 0}
Warning
The underlying graph must be undirected.
A dictionary of dictionaries representing a directed graph.
OUTPUT:
dict
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: S.dict()
{0: {1: 1, 2: 1},
1: {0: 1, 2: 1, 3: 1},
2: {0: 1, 1: 1, 3: 1},
3: {1: 1, 2: 1}}
sage: S.sink()
0
The genus: (# non-loop edges) - (# vertices) + 1. Only defined for undirected graphs.
OUTPUT:
integer
EXAMPLES:
sage: sandpiles.Complete(4).genus()
3
sage: sandpiles.Cycle(5).genus()
1
A Groebner basis for the homogeneous toppling ideal. It is computed with respect to the standard sandpile ordering (see ring).
OUTPUT:
Groebner basis
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: S.groebner()
[x3*x2^2 - x1^2*x0, x2^3 - x3*x1*x0, x3*x1^2 - x2^2*x0, x1^3 - x3*x2*x0, x3^2 - x0^2, x2*x1 - x0^2]
A minimal list of generators for the sandpile group. If verbose is False then the generators are represented as lists of integers.
INPUT:
verbose – (default: True) boolean
OUTPUT:
list of SandpileConfig (or of lists of integers if verbose is False)
EXAMPLES:
sage: s = sandpiles.Cycle(5)
sage: s.group_gens()
[{1: 1, 2: 1, 3: 1, 4: 0}]
sage: s.group_gens()[0].order()
5
sage: s = sandpiles.Complete(5)
sage: s.group_gens(False)
[[2, 2, 3, 2], [2, 3, 2, 2], [3, 2, 2, 2]]
sage: [i.order() for i in s.group_gens()]
[5, 5, 5]
sage: s.invariant_factors()
[1, 5, 5, 5]
The size of the sandpile group.
OUTPUT:
integer
EXAMPLES:
sage: S = sandpiles.House()
sage: S.group_order()
11
The number of superstable configurations in each degree. Equivalently, this is the list of first differences of the Hilbert function of the (homogeneous) toppling ideal.
OUTPUT:
list of nonnegative integers
EXAMPLES:
sage: s = sandpiles.Grid(2,2)
sage: s.hilbert_function()
[1, 5, 15, 35, 66, 106, 146, 178, 192]
sage: s.h_vector()
[1, 4, 10, 20, 31, 40, 40, 32, 14]
List of Sandpile-specific methods (not inherited from Graph). If verbose, include short descriptions.
INPUT:
verbose – (default: True) boolean
OUTPUT:
printed string
EXAMPLES:
sage: Sandpile.help()
For detailed help with any method FOO listed below,
enter "Sandpile.FOO?" or enter "S.FOO?" for any Sandpile S.
all_k_config -- The constant configuration with all values set to k.
all_k_div -- The divisor with all values set to k.
avalanche_polynomial -- The avalanche polynomial.
betti -- The Betti table for the homogeneous toppling ideal.
betti_complexes -- The support-complexes with non-trivial homology.
burning_config -- The minimal burning configuration.
burning_script -- A script for the minimal burning configuration.
canonical_divisor -- The canonical divisor.
dict -- A dictionary of dictionaries representing a directed graph.
genus -- The genus: (# non-loop edges) - (# vertices) + 1.
groebner -- A Groebner basis for the homogeneous toppling ideal.
group_gens -- A minimal list of generators for the sandpile group.
group_order -- The size of the sandpile group.
h_vector -- The number of superstable configurations in each degree.
help -- List of Sandpile-specific methods (not inherited from Graph).
hilbert_function -- The Hilbert function of the homogeneous toppling ideal.
ideal -- The saturated homogeneous toppling ideal.
identity -- The identity configuration.
in_degree -- The in-degree of a vertex or a list of all in-degrees.
invariant_factors -- The invariant factors of the sandpile group.
is_undirected -- Is the underlying graph undirected?
jacobian_representatives -- Representatives for the elements of the Jacobian group.
laplacian -- The Laplacian matrix of the graph.
markov_chain -- The sandpile Markov chain for configurations or divisors.
max_stable -- The maximal stable configuration.
max_stable_div -- The maximal stable divisor.
max_superstables -- The maximal superstable configurations.
min_recurrents -- The minimal recurrent elements.
nonsink_vertices -- The nonsink vertices.
nonspecial_divisors -- The nonspecial divisors.
out_degree -- The out-degree of a vertex or a list of all out-degrees.
picard_representatives -- Representatives of the divisor classes of degree d in the Picard group.
points -- Generators for the multiplicative group of zeros of the sandpile ideal.
postulation -- The postulation number of the toppling ideal.
recurrents -- The recurrent configurations.
reduced_laplacian -- The reduced Laplacian matrix of the graph.
reorder_vertices -- A copy of the sandpile with vertex names permuted.
resolution -- A minimal free resolution of the homogeneous toppling ideal.
ring -- The ring containing the homogeneous toppling ideal.
show -- Draw the underlying graph.
show3d -- Draw the underlying graph.
sink -- The sink vertex.
smith_form -- The Smith normal form for the Laplacian.
solve -- Approximations of the complex affine zeros of the sandpile ideal.
stable_configs -- Generator for all stable configurations.
stationary_density -- The stationary density of the sandpile.
superstables -- The superstable configurations.
symmetric_recurrents -- The symmetric recurrent configurations.
tutte_polynomial -- The Tutte polynomial.
unsaturated_ideal -- The unsaturated, homogeneous toppling ideal.
version -- The version number of Sage Sandpiles.
zero_config -- The all-zero configuration.
zero_div -- The all-zero divisor.
The Hilbert function of the homogeneous toppling ideal.
OUTPUT:
list of nonnegative integers
EXAMPLES:
sage: s = sandpiles.Wheel(5)
sage: s.hilbert_function()
[1, 5, 15, 31, 45]
sage: s.h_vector()
[1, 4, 10, 16, 14]
The saturated homogeneous toppling ideal. If gens is True, the generators for the ideal are returned instead.
INPUT:
gens – (default: False) boolean
OUTPUT:
ideal or, optionally, the generators of an ideal
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: S.ideal()
Ideal (x2*x1 - x0^2, x3^2 - x0^2, x1^3 - x3*x2*x0, x3*x1^2 - x2^2*x0, x2^3 - x3*x1*x0, x3*x2^2 - x1^2*x0) of Multivariate Polynomial Ring in x3, x2, x1, x0 over Rational Field
sage: S.ideal(True)
[x2*x1 - x0^2, x3^2 - x0^2, x1^3 - x3*x2*x0, x3*x1^2 - x2^2*x0, x2^3 - x3*x1*x0, x3*x2^2 - x1^2*x0]
sage: S.ideal().gens() # another way to get the generators
[x2*x1 - x0^2, x3^2 - x0^2, x1^3 - x3*x2*x0, x3*x1^2 - x2^2*x0, x2^3 - x3*x1*x0, x3*x2^2 - x1^2*x0]
The identity configuration. If verbose is False, the configuration are converted to a list of integers.
INPUT:
verbose – (default: True) boolean
OUTPUT:
SandpileConfig or a list of integers If verbose is False, the configuration are converted to a list of integers.
EXAMPLES:
sage: s = sandpiles.Diamond()
sage: s.identity()
{1: 2, 2: 2, 3: 0}
sage: s.identity(False)
[2, 2, 0]
sage: s.identity() & s.max_stable() == s.max_stable()
True
The in-degree of a vertex or a list of all in-degrees.
INPUT:
v – (optional) vertex name
OUTPUT:
integer or dict
EXAMPLES:
sage: s = sandpiles.House()
sage: s.in_degree()
{0: 2, 1: 2, 2: 3, 3: 3, 4: 2}
sage: s.in_degree(2)
3
The invariant factors of the sandpile group.
OUTPUT:
list of integers
EXAMPLES:
sage: s = sandpiles.Grid(2,2)
sage: s.invariant_factors()
[1, 1, 8, 24]
Is the underlying graph undirected? True if \((u,v)\) is and edge if and only if \((v,u)\) is an edge, each edge with the same weight.
OUTPUT:
boolean
EXAMPLES:
sage: sandpiles.Complete(4).is_undirected()
True
sage: s = Sandpile({0:[1,2], 1:[0,2], 2:[0]}, 0)
sage: s.is_undirected()
False
Representatives for the elements of the Jacobian group. If verbose is False, then lists representing the divisors are returned.
INPUT:
verbose – (default: True) boolean
OUTPUT:
list of SandpileDivisor (or of lists representing divisors)
EXAMPLES:
For an undirected graph, divisors of the form s - deg(s)*sink as s varies over the superstables forms a distinct set of representatives for the Jacobian group.:
sage: s = sandpiles.Complete(3)
sage: s.superstables(False)
[[0, 0], [0, 1], [1, 0]]
sage: s.jacobian_representatives(False)
[[0, 0, 0], [-1, 0, 1], [-1, 1, 0]]
If the graph is directed, the representatives described above may by equivalent modulo the rowspan of the Laplacian matrix:
sage: s = Sandpile({0: {1: 1, 2: 2}, 1: {0: 2, 2: 4}, 2: {0: 4, 1: 2}},0)
sage: s.group_order()
28
sage: s.jacobian_representatives()
[{0: -5, 1: 3, 2: 2}, {0: -4, 1: 3, 2: 1}]
Let \(\tau\) be the nonnegative generator of the kernel of the transpose of the Laplacian, and let \(tau_s\) be it sink component, then the sandpile group is isomorphic to the direct sum of the cyclic group of order \(\tau_s\) and the Jacobian group. In the example above, we have:
sage: s.laplacian().left_kernel()
Free module of degree 3 and rank 1 over Integer Ring
Echelon basis matrix:
[14 5 8]
Note
The Jacobian group is the set of all divisors of degree zero modulo the integer rowspan of the Laplacian matrix.
The Laplacian matrix of the graph. Its rows encode the vertex firing rules.
OUTPUT:
matrix
EXAMPLES:
sage: G = sandpiles.Diamond()
sage: G.laplacian()
[ 2 -1 -1 0]
[-1 3 -1 -1]
[-1 -1 3 -1]
[ 0 -1 -1 2]
Warning
The function laplacian_matrix should be avoided. It returns the indegree version of the Laplacian.
The sandpile Markov chain for configurations or divisors. The chain starts at state. See NOTE for details.
INPUT:
OUTPUT:
generator for Markov chain (see NOTE)
EXAMPLES:
sage: s = sandpiles.Complete(4)
sage: m = s.markov_chain([0,0,0])
sage: m.next() # random
{1: 0, 2: 0, 3: 0}
sage: m.next().values() # random
[0, 0, 0]
sage: m.next().values() # random
[0, 0, 0]
sage: m.next().values() # random
[0, 0, 0]
sage: m.next().values() # random
[0, 1, 0]
sage: m.next().values() # random
[0, 2, 0]
sage: m.next().values() # random
[0, 2, 1]
sage: m.next().values() # random
[1, 2, 1]
sage: m.next().values() # random
[2, 2, 1]
sage: m = s.markov_chain(s.zero_div(), [0.1,0.1,0.1,0.7])
sage: m.next().values() # random
[0, 0, 0, 1]
sage: m.next().values() # random
[0, 0, 1, 1]
sage: m.next().values() # random
[0, 0, 1, 2]
sage: m.next().values() # random
[1, 1, 2, 0]
sage: m.next().values() # random
[1, 1, 2, 1]
sage: m.next().values() # random
[1, 1, 2, 2]
sage: m.next().values() # random
[1, 1, 2, 3]
sage: m.next().values() # random
[1, 1, 2, 4]
sage: m.next().values() # random
[1, 1, 3, 4]
Note
The closed sandpile Markov chain has state space consisting of the configurations on a sandpile. It transitions from a state by choosing a vertex at random (according to the probability distribution distrib), dropping a grain of sand at that vertex, and stabilizing. If the chosen vertex is the sink, the chain stays at the current state.
The open sandpile Markov chain has state space consisting of the recurrent elements, i.e., the state space is the sandpile group. It transitions from the configuration \(c\) by choosing a vertex \(v\) at random according to distrib. The next state is the stabilization of \(c+v\). If \(v\) is the sink vertex, then the stabilization of \(c+v\) is defined to be \(c\).
Note that in either case, if distrib is specified, its length is equal to the total number of vertices (including the sink).
REFERENCES:
| [Levine2014] | Lionel Levine. Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle, Communications in Mathematical Physics. |
The maximal stable configuration.
OUTPUT:
SandpileConfig (the maximal stable configuration)
EXAMPLES:
sage: S = sandpiles.House()
sage: S.max_stable()
{1: 1, 2: 2, 3: 2, 4: 1}
The maximal stable divisor.
OUTPUT:
SandpileDivisor (the maximal stable divisor)
EXAMPLES:
sage: s = sandpiles.Diamond()
sage: s.max_stable_div()
{0: 1, 1: 2, 2: 2, 3: 1}
sage: s.out_degree()
{0: 2, 1: 3, 2: 3, 3: 2}
The maximal superstable configurations. If the underlying graph is undirected, these are the superstables of highest degree. If verbose is False, the configurations are converted to lists of integers.
INPUT:
verbose – (default: True) boolean
OUTPUT:
tuple of SandpileConfig
EXAMPLES:
sage: s = sandpiles.Diamond()
sage: s.superstables(False)
[[0, 0, 0],
[0, 0, 1],
[1, 0, 1],
[0, 2, 0],
[2, 0, 0],
[0, 1, 1],
[1, 0, 0],
[0, 1, 0]]
sage: s.max_superstables(False)
[[1, 0, 1], [0, 2, 0], [2, 0, 0], [0, 1, 1]]
sage: s.h_vector()
[1, 3, 4]
The minimal recurrent elements. If the underlying graph is undirected, these are the recurrent elements of least degree. If verbose is False, the configurations are converted to lists of integers.
INPUT:
verbose – (default: True) boolean
OUTPUT:
list of SandpileConfig
EXAMPLES:
sage: s = sandpiles.Diamond()
sage: s.recurrents(False)
[[2, 2, 1],
[2, 2, 0],
[1, 2, 0],
[2, 0, 1],
[0, 2, 1],
[2, 1, 0],
[1, 2, 1],
[2, 1, 1]]
sage: s.min_recurrents(False)
[[1, 2, 0], [2, 0, 1], [0, 2, 1], [2, 1, 0]]
sage: [i.deg() for i in s.recurrents()]
[5, 4, 3, 3, 3, 3, 4, 4]
The nonsink vertices.
OUTPUT:
list of vertices
EXAMPLES:
sage: s = sandpiles.Grid(2,3)
sage: s.nonsink_vertices()
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)]
The nonspecial divisors. Only for undirected graphs. (See NOTE.)
INPUT:
verbose – (default: True) boolean
OUTPUT:
list (of divisors)
EXAMPLES:
sage: S = sandpiles.Complete(4)
sage: ns = S.nonspecial_divisors()
sage: D = ns[0]
sage: D.values()
[-1, 0, 1, 2]
sage: D.deg()
2
sage: [i.effective_div() for i in ns]
[[], [], [], [], [], []]
Note
The “nonspecial divisors” are those divisors of degree \(g-1\) with empty linear system. The term is only defined for undirected graphs. Here, \(g = |E| - |V| + 1\) is the genus of the graph (not counted loops as part of \(|E|\)). If verbose is False, the divisors are converted to lists of integers.
Warning
The underlying graph must be undirected.
The out-degree of a vertex or a list of all out-degrees.
INPUT:
v - (optional) vertex name
OUTPUT:
integer or dict
EXAMPLES:
sage: s = sandpiles.House()
sage: s.out_degree()
{0: 2, 1: 2, 2: 3, 3: 3, 4: 2}
sage: s.out_degree(2)
3
Representatives of the divisor classes of degree \(d\) in the Picard group. (Also see the documentation for jacobian_representatives.)
INPUT:
OUTPUT:
list of SandpileDivisors (or lists representing divisors)
EXAMPLES:
sage: s = sandpiles.Complete(3)
sage: s.superstables(False)
[[0, 0], [0, 1], [1, 0]]
sage: s.jacobian_representatives(False)
[[0, 0, 0], [-1, 0, 1], [-1, 1, 0]]
sage: s.picard_representatives(3,False)
[[3, 0, 0], [2, 0, 1], [2, 1, 0]]
Generators for the multiplicative group of zeros of the sandpile ideal.
OUTPUT:
list of complex numbers
EXAMPLES:
The sandpile group in this example is cyclic, and hence there is a single generator for the group of solutions.
sage: S = sandpiles.Complete(4)
sage: S.points()
[[1, I, -I], [I, 1, -I]]
The postulation number of the toppling ideal. This is the largest weight of a superstable configuration of the graph.
OUTPUT:
nonnegative integer
EXAMPLES:
sage: s = sandpiles.Complete(4)
sage: s.postulation()
3
The recurrent configurations. If verbose is False, the configurations are converted to lists of integers.
INPUT:
verbose – (default: True) boolean
OUTPUT:
list of recurrent configurations
EXAMPLES:
sage: r = Sandpile(graphs.HouseXGraph(),0).recurrents()
sage: r[:3]
[{1: 2, 2: 3, 3: 3, 4: 1}, {1: 1, 2: 3, 3: 3, 4: 0}, {1: 1, 2: 3, 3: 3, 4: 1}]
sage: sandpiles.Complete(4).recurrents(False)
[[2, 2, 2],
[2, 2, 1],
[2, 1, 2],
[1, 2, 2],
[2, 2, 0],
[2, 0, 2],
[0, 2, 2],
[2, 1, 1],
[1, 2, 1],
[1, 1, 2],
[2, 1, 0],
[2, 0, 1],
[1, 2, 0],
[1, 0, 2],
[0, 2, 1],
[0, 1, 2]]
sage: sandpiles.Cycle(4).recurrents(False)
[[1, 1, 1], [0, 1, 1], [1, 0, 1], [1, 1, 0]]
The reduced Laplacian matrix of the graph.
OUTPUT:
matrix
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: S.laplacian()
[ 2 -1 -1 0]
[-1 3 -1 -1]
[-1 -1 3 -1]
[ 0 -1 -1 2]
sage: S.reduced_laplacian()
[ 3 -1 -1]
[-1 3 -1]
[-1 -1 2]
Note
This is the Laplacian matrix with the row and column indexed by the sink vertex removed.
A copy of the sandpile with vertex names permuted. After reordering, vertex \(u\) comes before vertex \(v\) in the list of vertices if \(u\) is closer to the sink.
OUTPUT:
Sandpile
EXAMPLES:
sage: S = Sandpile({0:[1], 2:[0,1], 1:[2]})
sage: S.dict()
{0: {1: 1}, 1: {2: 1}, 2: {0: 1, 1: 1}}
sage: T = S.reorder_vertices()
The vertices 1 and 2 have been swapped:
sage: T.dict()
{0: {1: 1}, 1: {0: 1, 2: 1}, 2: {0: 1}}
A minimal free resolution of the homogeneous toppling ideal. If verbose is True, then all of the mappings are returned. Otherwise, the resolution is summarized.
INPUT:
verbose – (default: False) boolean
OUTPUT:
free resolution of the toppling ideal
EXAMPLES:
sage: S = Sandpile({0: {}, 1: {0: 1, 2: 1, 3: 4}, 2: {3: 5}, 3: {1: 1, 2: 1}},0)
sage: S.resolution() # a Gorenstein sandpile graph
'R^1 <-- R^5 <-- R^5 <-- R^1'
sage: S.resolution(True)
[
[ x1^2 - x3*x0 x3*x1 - x2*x0 x3^2 - x2*x1 x2*x3 - x0^2 x2^2 - x1*x0],
[ x3 x2 0 x0 0] [ x2^2 - x1*x0]
[-x1 -x3 x2 0 -x0] [-x2*x3 + x0^2]
[ x0 x1 0 x2 0] [-x3^2 + x2*x1]
[ 0 0 -x1 -x3 x2] [x3*x1 - x2*x0]
[ 0 0 x0 x1 -x3], [ x1^2 - x3*x0]
]
sage: r = S.resolution(True)
sage: r[0]*r[1]
[0 0 0 0 0]
sage: r[1]*r[2]
[0]
[0]
[0]
[0]
[0]
The ring containing the homogeneous toppling ideal.
OUTPUT:
ring
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: S.ring()
Multivariate Polynomial Ring in x3, x2, x1, x0 over Rational Field
sage: S.ring().gens()
(x3, x2, x1, x0)
Note
The indeterminate xi corresponds to the \(i\)-th vertex as listed my the method vertices. The term-ordering is degrevlex with indeterminates ordered according to their distance from the sink (larger indeterminates are further from the sink).
Draw the underlying graph.
INPUT:
kwds – (optional) arguments passed to the show method for Graph or DiGraph
EXAMPLES:
sage: S = Sandpile({0:[], 1:[0,3,4], 2:[0,3,5], 3:[2,5], 4:[1,1], 5:[2,4]})
sage: S.show()
sage: S.show(graph_border=True, edge_labels=True)
Draw the underlying graph.
INPUT:
kwds – (optional) arguments passed to the show method for Graph or DiGraph
EXAMPLES:
sage: S = sandpiles.House()
sage: S.show3d()
The sink vertex.
OUTPUT:
sink vertex
EXAMPLES:
sage: G = sandpiles.House()
sage: G.sink()
0
sage: H = sandpiles.Grid(2,2)
sage: H.sink()
(0, 0)
sage: type(H.sink())
<type 'tuple'>
The Smith normal form for the Laplacian. In detail: a list of integer matrices \(D, U, V\) such that \(ULV = D\) where \(L\) is the transpose of the Laplacian, \(D\) is diagonal, and \(U\) and \(V\) are invertible over the integers.
OUTPUT:
list of integer matrices
EXAMPLES:
sage: s = sandpiles.Complete(4)
sage: D,U,V = s.smith_form()
sage: D
[1 0 0 0]
[0 4 0 0]
[0 0 4 0]
[0 0 0 0]
sage: U*s.laplacian()*V == D # laplacian symmetric => tranpose not necessary
True
Approximations of the complex affine zeros of the sandpile ideal.
OUTPUT:
list of complex numbers
EXAMPLES:
sage: S = Sandpile({0: {}, 1: {2: 2}, 2: {0: 4, 1: 1}}, 0)
sage: S.solve()
[[-0.707107 + 0.707107*I, 0.707107 - 0.707107*I], [-0.707107 - 0.707107*I, 0.707107 + 0.707107*I], [-I, -I], [I, I], [0.707107 + 0.707107*I, -0.707107 - 0.707107*I], [0.707107 - 0.707107*I, -0.707107 + 0.707107*I], [1, 1], [-1, -1]]
sage: len(_)
8
sage: S.group_order()
8
Note
The solutions form a multiplicative group isomorphic to the sandpile group. Generators for this group are given exactly by points().
Generator for all stable configurations. If smax is provided, then the generator gives all stable configurations less than or equal to smax. If smax does not represent a stable configuration, then each component of smax is replaced by the corresponding component of the maximal stable configuration.
INPUT:
smax – (optional) SandpileConfig or list representing a SandpileConfig
OUTPUT:
generator for all stable configurations
EXAMPLES:
sage: s = sandpiles.Complete(3)
sage: a = s.stable_configs()
sage: a.next()
{1: 0, 2: 0}
sage: [i.values() for i in a]
[[0, 1], [1, 0], [1, 1]]
sage: b = s.stable_configs([1,0])
sage: list(b)
[{1: 0, 2: 0}, {1: 1, 2: 0}]
The stationary density of the sandpile.
OUTPUT:
rational number
EXAMPLES:
sage: s = sandpiles.Complete(3)
sage: s.stationary_density()
10/9
sage: s = Sandpile(digraphs.DeBruijn(2,2),'00')
sage: s.stationary_density()
9/8
Note
The stationary density of a sandpile is the sum \(\sum_c (\deg(c) + \deg(s))\) where \(\deg(s)\) is the degree of the sink and the sum is over all recurrent configurations.
REFERENCES:
The superstable configurations. If verbose is False, the configurations are converted to lists of integers. Superstables for undirected graphs are also known as G-parking functions.
INPUT:
verbose – (default: True) boolean
OUTPUT:
list of SandpileConfig
EXAMPLES:
sage: sp = Sandpile(graphs.HouseXGraph(),0).superstables()
sage: sp[:3]
[{1: 0, 2: 0, 3: 0, 4: 0}, {1: 1, 2: 0, 3: 0, 4: 1}, {1: 1, 2: 0, 3: 0, 4: 0}]
sage: sandpiles.Complete(4).superstables(False)
[[0, 0, 0],
[0, 0, 1],
[0, 1, 0],
[1, 0, 0],
[0, 0, 2],
[0, 2, 0],
[2, 0, 0],
[0, 1, 1],
[1, 0, 1],
[1, 1, 0],
[0, 1, 2],
[0, 2, 1],
[1, 0, 2],
[1, 2, 0],
[2, 0, 1],
[2, 1, 0]]
sage: sandpiles.Cycle(4).superstables(False)
[[0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 1]]
The symmetric recurrent configurations.
INPUT:
orbits - list of lists partitioning the vertices
OUTPUT:
list of recurrent configurations
EXAMPLES:
sage: S = Sandpile({0: {},
....: 1: {0: 1, 2: 1, 3: 1},
....: 2: {1: 1, 3: 1, 4: 1},
....: 3: {1: 1, 2: 1, 4: 1},
....: 4: {2: 1, 3: 1}})
sage: S.symmetric_recurrents([[1],[2,3],[4]])
[{1: 2, 2: 2, 3: 2, 4: 1}, {1: 2, 2: 2, 3: 2, 4: 0}]
sage: S.recurrents()
[{1: 2, 2: 2, 3: 2, 4: 1},
{1: 2, 2: 2, 3: 2, 4: 0},
{1: 2, 2: 1, 3: 2, 4: 0},
{1: 2, 2: 2, 3: 0, 4: 1},
{1: 2, 2: 0, 3: 2, 4: 1},
{1: 2, 2: 2, 3: 1, 4: 0},
{1: 2, 2: 1, 3: 2, 4: 1},
{1: 2, 2: 2, 3: 1, 4: 1}]
Note
The user is responsible for ensuring that the list of orbits comes from a group of symmetries of the underlying graph.
The Tutte polynomial. Only defined for undirected sandpile graphs.
OUTPUT:
polynomial
EXAMPLES:
sage: s = sandpiles.Complete(4)
sage: s.tutte_polynomial()
x^3 + y^3 + 3*x^2 + 4*x*y + 3*y^2 + 2*x + 2*y
sage: s.tutte_polynomial().subs(x=1)
y^3 + 3*y^2 + 6*y + 6
sage: s.tutte_polynomial().subs(x=1).coefficients() == s.h_vector()
True
The unsaturated, homogeneous toppling ideal.
OUTPUT:
ideal
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: S.unsaturated_ideal().gens()
[x1^3 - x3*x2*x0, x2^3 - x3*x1*x0, x3^2 - x2*x1]
sage: S.ideal().gens()
[x2*x1 - x0^2, x3^2 - x0^2, x1^3 - x3*x2*x0, x3*x1^2 - x2^2*x0, x2^3 - x3*x1*x0, x3*x2^2 - x1^2*x0]
The version number of Sage Sandpiles.
OUTPUT:
string
EXAMPLES:
sage: Sandpile.version()
Sage Sandpiles Version 2.4
sage: S = sandpiles.Complete(3)
sage: S.version()
Sage Sandpiles Version 2.4
The all-zero configuration.
OUTPUT:
SandpileConfig
EXAMPLES:
sage: s = sandpiles.Diamond()
sage: s.zero_config()
{1: 0, 2: 0, 3: 0}
The all-zero divisor.
OUTPUT:
SandpileDivisor
EXAMPLES:
sage: S = sandpiles.House()
sage: S.zero_div()
{0: 0, 1: 0, 2: 0, 3: 0, 4: 0}
Bases: dict
Class for configurations on a sandpile.
Add one grain of sand to a random vertex. Optionally, a probability distribution, distrib, may be placed on the vertices or the nonsink vertices. See NOTE for details.
INPUT:
distrib – (optional) list of nonnegative numbers summing to 1 (representing a prob. dist.)
OUTPUT:
SandpileConfig
EXAMPLES:
sage: s = sandpiles.Complete(4)
sage: c = s.zero_config()
sage: c.add_random() # random
{1: 0, 2: 1, 3: 0}
sage: c
{1: 0, 2: 0, 3: 0}
sage: c.add_random([0.1,0.1,0.8]) # random
{1: 0, 2: 0, 3: 1}
sage: c.add_random([0.7,0.1,0.1,0.1]) # random
{1: 0, 2: 0, 3: 0}
We compute the “sizes” of the avalanches caused by adding random grains of sand to the maximal stable configuration on a grid graph. The function stabilize() returns the firing vector of the stabilization, a dictionary whose values say how many times each vertex fires in the stabilization.:
sage: S = sandpiles.Grid(10,10)
sage: m = S.max_stable()
sage: a = []
sage: for i in range(1000):
....: m = m.add_random()
....: m, f = m.stabilize(True)
....: a.append(sum(f.values()))
....:
sage: p = list_plot([[log(i+1),log(a.count(i))] for i in [0..max(a)] if a.count(i)])
sage: p.axes_labels(['log(N)','log(D(N))'])
sage: t = text("Distribution of avalanche sizes", (2,2), rgbcolor=(1,0,0))
sage: show(p+t,axes_labels=['log(N)','log(D(N))'])
Note
If distrib is None, then the probability is the uniform probability on the nonsink vertices. Otherwise, there are two possibilities:
(i) the length of distrib is equal to the number of vertices, and distrib represents a probability distribution on all of the vertices. In that case, the sink may be chosen at random, in which case, the configuration is unchanged.
(ii) Otherwise, the length of distrib must be equal to the number of nonsink vertices, and distrib represents a probability distribution on the nonsink vertices.
Warning
If distrib != None, the user is responsible for assuring the sum of its entries is 1 and that its length is equal to the number of sink vertices or the number of nonsink vertices.
The burst size of the configuration with respect to the given vertex.
INPUT:
v – vertex
OUTPUT:
integer
EXAMPLES:
sage: s = sandpiles.Diamond()
sage: [i.burst_size(0) for i in s.recurrents()]
[1, 1, 1, 1, 1, 1, 1, 1]
sage: [i.burst_size(1) for i in s.recurrents()]
[0, 0, 1, 2, 1, 2, 0, 2]
Note
To define c.burst(v), if \(v\) is not the sink, let \(c'\) be the unique recurrent for which the the stabilization of \(c' + v\) is \(c\). The burst size is then the amount of sand that goes into the sink during this stabilization. If \(v\) is the sink, the burst size is defined to be 1.
REFERENCES:
The degree of the configuration.
OUTPUT:
integer
EXAMPLES:
sage: S = sandpiles.Complete(3)
sage: c = SandpileConfig(S, [1,2])
sage: c.deg()
3
The difference with the maximal stable configuration.
OUTPUT:
SandpileConfig
EXAMPLES:
sage: S = sandpiles.Cycle(3)
sage: c = SandpileConfig(S, [1,2])
sage: S.max_stable()
{1: 1, 2: 1}
sage: c.dualize()
{1: 0, 2: -1}
sage: S.max_stable() - c == c.dualize()
True
The recurrent configuration equivalent to the given configuration. Optionally, return the corresponding firing vector.
INPUT:
with_firing_vector – (default: False) boolean
OUTPUT:
SandpileConfig or [SandpileConfig, firing_vector]
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: c = SandpileConfig(S, [0,0,0])
sage: c.equivalent_recurrent() == S.identity()
True
sage: x = c.equivalent_recurrent(True)
sage: r = vector([x[0][v] for v in S.nonsink_vertices()])
sage: f = vector([x[1][v] for v in S.nonsink_vertices()])
sage: cv = vector(c.values())
sage: r == cv - f*S.reduced_laplacian()
True
Note
Let \(L\) be the reduced Laplacian, \(c\) the initial configuration, \(r\) the returned configuration, and \(f\) the firing vector. Then \(r = c - f\cdot L\).
The equivalent superstable configuration. Optionally, return the corresponding firing vector.
INPUT:
with_firing_vector – (default: False) boolean
OUTPUT:
SandpileConfig or [SandpileConfig, firing_vector]
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: m = S.max_stable()
sage: m.equivalent_superstable().is_superstable()
True
sage: x = m.equivalent_superstable(True)
sage: s = vector(x[0].values())
sage: f = vector(x[1].values())
sage: mv = vector(m.values())
sage: s == mv - f*S.reduced_laplacian()
True
Note
Let \(L\) be the reduced Laplacian, \(c\) the initial configuration, \(s\) the returned configuration, and \(f\) the firing vector. Then \(s = c - f\cdot L\).
Fire the given script. In other words, fire each vertex the number of times indicated by sigma.
INPUT:
sigma – SandpileConfig or (list or dict representing a SandpileConfig)
OUTPUT:
SandpileConfig
EXAMPLES:
sage: S = sandpiles.Cycle(4)
sage: c = SandpileConfig(S, [1,2,3])
sage: c.unstable()
[2, 3]
sage: c.fire_script(SandpileConfig(S,[0,1,1]))
{1: 2, 2: 1, 3: 2}
sage: c.fire_script(SandpileConfig(S,[2,0,0])) == c.fire_vertex(1).fire_vertex(1)
True
Fire all unstable vertices.
OUTPUT:
SandpileConfig
EXAMPLES:
sage: S = sandpiles.Cycle(4)
sage: c = SandpileConfig(S, [1,2,3])
sage: c.fire_unstable()
{1: 2, 2: 1, 3: 2}
Fire the given vertex.
INPUT:
v – vertex
OUTPUT:
SandpileConfig
EXAMPLES:
sage: S = sandpiles.Cycle(3)
sage: c = SandpileConfig(S, [1,2])
sage: c.fire_vertex(2)
{1: 2, 2: 0}
List of SandpileConfig methods. If verbose, include short descriptions.
INPUT:
verbose – (default: True) boolean
OUTPUT:
printed string
EXAMPLES:
sage: SandpileConfig.help()
Shortcuts for SandpileConfig operations:
~c -- stabilize
c & d -- add and stabilize
c * c -- add and find equivalent recurrent
c^k -- add k times and find equivalent recurrent
(taking inverse if k is negative)
For detailed help with any method FOO listed below,
enter "SandpileConfig.FOO?" or enter "c.FOO?" for any SandpileConfig c.
add_random -- Add one grain of sand to a random vertex.
burst_size -- The burst size of the configuration with respect to the given vertex.
deg -- The degree of the configuration.
dualize -- The difference with the maximal stable configuration.
equivalent_recurrent -- The recurrent configuration equivalent to the given configuration.
equivalent_superstable -- The equivalent superstable configuration.
fire_script -- Fire the given script.
fire_unstable -- Fire all unstable vertices.
fire_vertex -- Fire the given vertex.
help -- List of SandpileConfig methods.
is_recurrent -- Is the configuration recurrent?
is_stable -- Is the configuration stable?
is_superstable -- Is the configuration superstable?
is_symmetric -- Is the configuration symmetric?
order -- The order of the equivalent recurrent element.
sandpile -- The configuration's underlying sandpile.
show -- Show the configuration.
stabilize -- The stabilized configuration.
support -- The vertices containing sand.
unstable -- The unstable vertices.
values -- The values of the configuration as a list.
Is the configuration recurrent?
OUTPUT:
boolean
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: S.identity().is_recurrent()
True
sage: S.zero_config().is_recurrent()
False
Is the configuration stable?
OUTPUT:
boolean
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: S.max_stable().is_stable()
True
sage: (2*S.max_stable()).is_stable()
False
sage: (S.max_stable() & S.max_stable()).is_stable()
True
Is the configuration superstable?
OUTPUT:
boolean
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: S.zero_config().is_superstable()
True
Is the configuration symmetric? Return True if the values of the configuration are constant over the vertices in each sublist of orbits.
INPUT:
orbits – list of lists of vertices
OUTPUT:
boolean
EXAMPLES:
sage: S = Sandpile({0: {},
....: 1: {0: 1, 2: 1, 3: 1},
....: 2: {1: 1, 3: 1, 4: 1},
....: 3: {1: 1, 2: 1, 4: 1},
....: 4: {2: 1, 3: 1}})
sage: c = SandpileConfig(S, [1, 2, 2, 3])
sage: c.is_symmetric([[2,3]])
True
The order of the equivalent recurrent element.
OUTPUT:
integer
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: c = SandpileConfig(S,[2,0,1])
sage: c.order()
4
sage: ~(c + c + c + c) == S.identity()
True
sage: c = SandpileConfig(S,[1,1,0])
sage: c.order()
1
sage: c.is_recurrent()
False
sage: c.equivalent_recurrent() == S.identity()
True
The configuration’s underlying sandpile.
OUTPUT:
Sandpile
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: c = S.identity()
sage: c.sandpile()
Diamond sandpile graph: 4 vertices, sink = 0
sage: c.sandpile() == S
True
Show the configuration.
INPUT:
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: c = S.identity()
sage: c.show()
sage: c.show(directed=False)
sage: c.show(sink=False,colors=False,heights=True)
The stabilized configuration. Optionally returns the corresponding firing vector.
INPUT:
with_firing_vector – (default: False) boolean
OUTPUT:
SandpileConfig or [SandpileConfig, firing_vector]
EXAMPLES:
sage: S = sandpiles.House()
sage: c = 2*S.max_stable()
sage: c._set_stabilize()
sage: '_stabilize' in c.__dict__
True
sage: S = sandpiles.House()
sage: c = S.max_stable() + S.identity()
sage: c.stabilize(True)
[{1: 1, 2: 2, 3: 2, 4: 1}, {1: 2, 2: 2, 3: 3, 4: 3}]
sage: S.max_stable() & S.identity() == c.stabilize()
True
sage: ~c == c.stabilize()
True
The vertices containing sand.
OUTPUT:
list - support of the configuration
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: c = S.identity()
sage: c
{1: 2, 2: 2, 3: 0}
sage: c.support()
[1, 2]
The unstable vertices.
OUTPUT:
list of vertices
EXAMPLES:
sage: S = sandpiles.Cycle(4)
sage: c = SandpileConfig(S, [1,2,3])
sage: c.unstable()
[2, 3]
The values of the configuration as a list. The list is sorted in the order of the vertices.
OUTPUT:
list of integers
boolean
EXAMPLES:
sage: S = Sandpile({'a':[1,'b'], 'b':[1,'a'], 1:['a']},'a')
sage: c = SandpileConfig(S, {'b':1, 1:2})
sage: c
{1: 2, 'b': 1}
sage: c.values()
[2, 1]
sage: S.nonsink_vertices()
[1, 'b']
Bases: dict
Class for divisors on a sandpile.
The support-complex. (See NOTE.)
OUTPUT:
simplicial complex
EXAMPLES:
sage: S = sandpiles.House()
sage: p = SandpileDivisor(S, [1,2,1,0,0]).Dcomplex()
sage: p.homology()
{0: 0, 1: Z x Z, 2: 0}
sage: p.f_vector()
[1, 5, 10, 4]
sage: p.betti()
{0: 1, 1: 2, 2: 0}
Note
The “support-complex” is the simplicial complex determined by the supports of the linearly equivalent effective divisors.
Add one grain of sand to a random vertex.
INPUT:
distrib – (optional) list of nonnegative numbers representing a probability distribution on the vertices
OUTPUT:
SandpileDivisor
EXAMPLES:
sage: s = sandpiles.Complete(4)
sage: D = s.zero_div()
sage: D.add_random() # random
{0: 0, 1: 0, 2: 1, 3: 0}
sage: D.add_random([0.1,0.1,0.1,0.7]) # random
{0: 0, 1: 0, 2: 0, 3: 1}
Warning
If distrib is not None, the user is responsible for assuring the sum of its entries is 1.
The Betti numbers for the support-complex. (See NOTE.)
OUTPUT:
dictionary of integers
EXAMPLES:
sage: S = sandpiles.Cycle(3)
sage: D = SandpileDivisor(S, [2,0,1])
sage: D.betti()
{0: 1, 1: 1}
Note
The “support-complex” is the simplicial complex determined by the supports of the linearly equivalent effective divisors.
The degree of the divisor.
OUTPUT:
integer
EXAMPLES:
sage: S = sandpiles.Cycle(3)
sage: D = SandpileDivisor(S, [1,2,3])
sage: D.deg()
6
The difference with the maximal stable divisor.
OUTPUT:
SandpileDivisor
All linearly equivalent effective divisors. If verbose is False, the divisors are converted to lists of integers. If with_firing_vectors is True then a list of firing vectors is also given, each of which prescribes the vertices to be fired in order to obtain an effective divisor.
INPUT:
OUTPUT:
list (of divisors)
EXAMPLES:
sage: s = sandpiles.Complete(4)
sage: D = SandpileDivisor(s,[4,2,0,0])
sage: D.effective_div()
[{0: 0, 1: 6, 2: 0, 3: 0},
{0: 0, 1: 2, 2: 4, 3: 0},
{0: 0, 1: 2, 2: 0, 3: 4},
{0: 1, 1: 3, 2: 1, 3: 1},
{0: 2, 1: 0, 2: 2, 3: 2},
{0: 4, 1: 2, 2: 0, 3: 0}]
sage: D.effective_div(False)
[[0, 6, 0, 0],
[0, 2, 4, 0],
[0, 2, 0, 4],
[1, 3, 1, 1],
[2, 0, 2, 2],
[4, 2, 0, 0]]
sage: D.effective_div(with_firing_vectors=True)
[({0: 0, 1: 6, 2: 0, 3: 0}, (0, -2, -1, -1)),
({0: 0, 1: 2, 2: 4, 3: 0}, (0, -1, -2, -1)),
({0: 0, 1: 2, 2: 0, 3: 4}, (0, -1, -1, -2)),
({0: 1, 1: 3, 2: 1, 3: 1}, (0, -1, -1, -1)),
({0: 2, 1: 0, 2: 2, 3: 2}, (0, 0, -1, -1)),
({0: 4, 1: 2, 2: 0, 3: 0}, (0, 0, 0, 0))]
sage: a = _[0]
sage: a[0].values()
[0, 6, 0, 0]
sage: vector(D.values()) - s.laplacian()*a[1]
(0, 6, 0, 0)
sage: D.effective_div(False, True)
[([0, 6, 0, 0], (0, -2, -1, -1)),
([0, 2, 4, 0], (0, -1, -2, -1)),
([0, 2, 0, 4], (0, -1, -1, -2)),
([1, 3, 1, 1], (0, -1, -1, -1)),
([2, 0, 2, 2], (0, 0, -1, -1)),
([4, 2, 0, 0], (0, 0, 0, 0))]
sage: D = SandpileDivisor(s,[-1,0,0,0])
sage: D.effective_div(False,True)
[]
Fire the given script. In other words, fire each vertex the number of times indicated by sigma.
INPUT:
sigma – SandpileDivisor or (list or dict representing a SandpileDivisor)
OUTPUT:
SandpileDivisor
EXAMPLES:
sage: S = sandpiles.Cycle(3)
sage: D = SandpileDivisor(S, [1,2,3])
sage: D.unstable()
[1, 2]
sage: D.fire_script([0,1,1])
{0: 3, 1: 1, 2: 2}
sage: D.fire_script(SandpileDivisor(S,[2,0,0])) == D.fire_vertex(0).fire_vertex(0)
True
Fire all unstable vertices.
OUTPUT:
SandpileDivisor
EXAMPLES:
sage: S = sandpiles.Cycle(3)
sage: D = SandpileDivisor(S, [1,2,3])
sage: D.fire_unstable()
{0: 3, 1: 1, 2: 2}
Fire the given vertex.
INPUT:
v – vertex
OUTPUT:
SandpileDivisor
EXAMPLES:
sage: S = sandpiles.Cycle(3)
sage: D = SandpileDivisor(S, [1,2,3])
sage: D.fire_vertex(1)
{0: 2, 1: 0, 2: 4}
List of SandpileDivisor methods. If verbose, include short descriptions.
INPUT:
verbose – (default: True) boolean
OUTPUT:
printed string
EXAMPLES:
sage: SandpileDivisor.help()
For detailed help with any method FOO listed below,
enter "SandpileDivisor.FOO?" or enter "D.FOO?" for any SandpileDivisor D.
Dcomplex -- The support-complex.
add_random -- Add one grain of sand to a random vertex.
betti -- The Betti numbers for the support-complex.
deg -- The degree of the divisor.
dualize -- The difference with the maximal stable divisor.
effective_div -- All linearly equivalent effective divisors.
fire_script -- Fire the given script.
fire_unstable -- Fire all unstable vertices.
fire_vertex -- Fire the given vertex.
help -- List of SandpileDivisor methods.
is_alive -- Is the divisor stabilizable?
is_linearly_equivalent -- Is the given divisor linearly equivalent?
is_q_reduced -- Is the divisor q-reduced?
is_symmetric -- Is the divisor symmetric?
is_weierstrass_pt -- Is the given vertex a Weierstrass point?
linear_system -- The complete linear system (deprecated: use "polytope_integer_pts").
polytope -- The polytope determinining the complete linear system.
polytope_integer_pts -- The integer points inside divisor's polytope.
q_reduced -- The linearly equivalent q-reduced divisor.
r_of_D -- The rank of the divisor (deprecated: use "rank", instead).
rank -- The rank of the divisor.
sandpile -- The divisor's underlying sandpile.
show -- Show the divisor.
simulate_threshold -- The first unstabilizable divisor in the closed Markov chain.
stabilize -- The stabilization of the divisor.
support -- List of vertices at which the divisor is nonzero.
unstable -- The unstable vertices.
values -- The values of the divisor as a list.
weierstrass_div -- The Weierstrass divisor.
weierstrass_gap_seq -- The Weierstrass gap sequence at the given vertex.
weierstrass_pts -- The Weierstrass points (vertices).
weierstrass_rank_seq -- The Weierstrass rank sequence at the given vertex.
Is the divisor stabilizable? In other words, will the divisor stabilize under repeated firings of all unstable vertices? Optionally returns the resulting cycle.
INPUT:
cycle – (default: False) boolean
OUTPUT:
boolean or optionally, a list of SandpileDivisors
EXAMPLES:
sage: S = sandpiles.Complete(4)
sage: D = SandpileDivisor(S, {0: 4, 1: 3, 2: 3, 3: 2})
sage: D.is_alive()
True
sage: D.is_alive(True)
[{0: 4, 1: 3, 2: 3, 3: 2}, {0: 3, 1: 2, 2: 2, 3: 5}, {0: 1, 1: 4, 2: 4, 3: 3}]
Is the given divisor linearly equivalent? Optionally, returns the firing vector. (See NOTE.)
INPUT:
OUTPUT:
boolean or integer vector
EXAMPLES:
sage: s = sandpiles.Complete(3)
sage: D = SandpileDivisor(s,[2,0,0])
sage: D.is_linearly_equivalent([0,1,1])
True
sage: D.is_linearly_equivalent([0,1,1],True)
(1, 0, 0)
sage: v = vector(D.is_linearly_equivalent([0,1,1],True))
sage: vector(D.values()) - s.laplacian()*v
(0, 1, 1)
sage: D.is_linearly_equivalent([0,0,0])
False
sage: D.is_linearly_equivalent([0,0,0],True)
()
Note
Is the divisor \(q\)-reduced? This would mean that \(self = c + kq\) where \(c\) is superstable, \(k\) is an integer, and \(q\) is the sink vertex.
OUTPUT:
boolean
EXAMPLES:
sage: s = sandpiles.Complete(4)
sage: D = SandpileDivisor(s,[2,-3,2,0])
sage: D.is_q_reduced()
False
sage: SandpileDivisor(s,[10,0,1,2]).is_q_reduced()
True
For undirected or, more generally, Eulerian graphs, \(q\)-reduced divisors are linearly equivalent if and only if they are equal. The same does not hold for general directed graphs:
sage: s = Sandpile({0:[1],1:[1,1]})
sage: D = SandpileDivisor(s,[-1,1])
sage: Z = s.zero_div()
sage: D.is_q_reduced()
True
sage: Z.is_q_reduced()
True
sage: D == Z
False
sage: D.is_linearly_equivalent(Z)
True
Is the divisor symmetric? Return True if the values of the configuration are constant over the vertices in each sublist of orbits.
INPUT:
orbits – list of lists of vertices
OUTPUT:
boolean
EXAMPLES:
sage: S = sandpiles.House()
sage: S.dict()
{0: {1: 1, 2: 1},
1: {0: 1, 3: 1},
2: {0: 1, 3: 1, 4: 1},
3: {1: 1, 2: 1, 4: 1},
4: {2: 1, 3: 1}}
sage: D = SandpileDivisor(S, [0,0,1,1,3])
sage: D.is_symmetric([[2,3], [4]])
True
Is the given vertex a Weierstrass point?
INPUT:
v – (default: sink) vertex
OUTPUT:
boolean
EXAMPLES:
sage: s = sandpiles.House()
sage: K = s.canonical_divisor()
sage: K.weierstrass_rank_seq() # sequence at the sink vertex, 0
(1, 0, -1)
sage: K.is_weierstrass_pt()
False
sage: K.weierstrass_rank_seq(4)
(1, 0, 0, -1)
sage: K.is_weierstrass_pt(4)
True
Note
The vertex \(v\) is a (generalized) Weierstrass point for divisor \(D\) if the sequence of ranks \(r(D - nv)\) for \(n = 0, 1, 2, \dots\) is not \(r(D), r(D)-1, \dots, 0, -1, -1, \dots\)
The complete linear system (deprecated: use polytope_integer_pts).
OUTPUT:
dict - {num_homog: int, homog:list, num_inhomog:int, inhomog:list}
EXAMPLES:
sage: S = Sandpile({0: {},
....: 1: {0: 1, 3: 1, 4: 1},
....: 2: {0: 1, 3: 1, 5: 1},
....: 3: {2: 1, 5: 1},
....: 4: {1: 1, 3: 1},
....: 5: {2: 1, 3: 1}}
....: )
sage: D = SandpileDivisor(S, [0,0,0,0,0,2])
sage: D.linear_system() # optional - 4ti2
{'homog': [[1, 0, 0, 0, 0, 0], [-1, 0, 0, 0, 0, 0]],
'inhomog': [[0, 0, 0, 0, 0, -1], [0, 0, -1, -1, 0, -2], [0, 0, 0, 0, 0, 0]],
'num_homog': 2,
'num_inhomog': 3}
Note
If \(L\) is the Laplacian, an arbitrary \(v\) such that \(v\cdot L\geq -D\) has the form \(v = w + t\) where \(w\) is in inhomg and \(t\) is in the integer span of homog in the output of linear_system(D).
Warning
This method requires 4ti2.
The polytope determinining the complete linear system.
OUTPUT:
polytope
EXAMPLES:
sage: s = sandpiles.Complete(4)
sage: D = SandpileDivisor(s,[4,2,0,0])
sage: p = D.polytope()
sage: p.inequalities()
(An inequality (-3, 1, 1) x + 2 >= 0,
An inequality (1, 1, 1) x + 4 >= 0,
An inequality (1, -3, 1) x + 0 >= 0,
An inequality (1, 1, -3) x + 0 >= 0)
sage: D = SandpileDivisor(s,[-1,0,0,0])
sage: D.polytope()
The empty polyhedron in QQ^3
Note
For a divisor \(D\), this is the intersection of (i) the polyhedron determined by the system of inequalities \(L^t x \leq D\) where \(L^t\) is the transpose of the Laplacian with (ii) the hyperplane \(x_{\mathrm{sink\_vertex}} = 0\). The polytope is thought of as sitting in \((n-1)\)-dimensional Euclidean space where \(n\) is the number of vertices.
The integer points inside divisor’s polytope. The polytope referred to here is the one determining the divisor’s complete linear system (see the documentation for polytope).
OUTPUT:
tuple of integer vectors
EXAMPLES:
sage: s = sandpiles.Complete(4)
sage: D = SandpileDivisor(s,[4,2,0,0])
sage: D.polytope_integer_pts()
((-2, -1, -1),
(-1, -2, -1),
(-1, -1, -2),
(-1, -1, -1),
(0, -1, -1),
(0, 0, 0))
sage: D = SandpileDivisor(s,[-1,0,0,0])
sage: D.polytope_integer_pts()
()
The linearly equivalent \(q\)-reduced divisor.
INPUT:
verbose – (default: True) boolean
OUTPUT:
SandpileDivisor or list representing SandpileDivisor
EXAMPLES:
sage: s = sandpiles.Complete(4)
sage: D = SandpileDivisor(s,[2,-3,2,0])
sage: D.q_reduced()
{0: -2, 1: 1, 2: 2, 3: 0}
sage: D.q_reduced(False)
[-2, 1, 2, 0]
Note
The divisor \(D\) is \(qreduced if `D = c + kq\) where \(c\) is superstable, \(k\) is an integer, and \(q\) is the sink.
The rank of the divisor (deprecated: use rank, instead). Returns \(r(D)\) and, if verbose is True, an effective divisor \(F\) such that \(|D - F|\) is empty.
INPUT:
verbose – (default: False) boolean
OUTPUT:
integer r(D) or tuple (integer r(D), divisor F)
EXAMPLES:
sage: S = Sandpile({0: {},
....: 1: {0: 1, 3: 1, 4: 1},
....: 2: {0: 1, 3: 1, 5: 1},
....: 3: {2: 1, 5: 1},
....: 4: {1: 1, 3: 1},
....: 5: {2: 1, 3: 1}}
....: )
sage: D = SandpileDivisor(S, [0,0,0,0,0,4]) # optional - 4ti2
sage: E = D.r_of_D(True) # optional - 4ti2
sage: E # optional - 4ti2
(1, {0: 0, 1: 1, 2: 0, 3: 1, 4: 0, 5: 0})
sage: F = E[1] # optional - 4ti2
sage: (D - F).values() # optional - 4ti2
[0, -1, 0, -1, 0, 4]
sage: (D - F).effective_div() # optional - 4ti2
[]
sage: SandpileDivisor(S, [0,0,0,0,0,-4]).r_of_D(True) # optional - 4ti2
(-1, {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: -4})
The rank of the divisor. Optionally returns an effective divisor \(E\) such that \(D - E\) is not winnable (has an empty complete linear system).
INPUT:
with_witness – (default: False) boolean
OUTPUT:
integer or (integer, SandpileDivisor)
EXAMPLES:
sage: S = sandpiles.Complete(4)
sage: D = SandpileDivisor(S,[4,2,0,0])
sage: D.rank()
3
sage: D.rank(True)
(3, {0: 3, 1: 0, 2: 1, 3: 0})
sage: E = _[1]
sage: (D - E).rank()
-1
Riemann-Roch theorem::
sage: D.rank() - (S.canonical_divisor()-D).rank() == D.deg() + 1 - S.genus()
True
Riemann-Roch theorem::
sage: D.rank() - (S.canonical_divisor()-D).rank() == D.deg() + 1 - S.genus()
True
sage: S = Sandpile({0:[1,1,1,2],1:[0,0,0,1,1,1,2,2],2:[2,2,1,1,0]},0) # multigraph with loops
sage: D = SandpileDivisor(S,[4,2,0])
sage: D.rank(True)
(2, {0: 1, 1: 1, 2: 1})
sage: S = Sandpile({0:[1,2], 1:[0,2,2], 2: [0,1]},0) # directed graph
sage: S.is_undirected()
False
sage: D = SandpileDivisor(S,[0,2,0])
sage: D.effective_div()
[{0: 0, 1: 2, 2: 0}, {0: 2, 1: 0, 2: 0}]
sage: D.rank(True)
(0, {0: 0, 1: 0, 2: 1})
sage: E = D.rank(True)[1]
sage: (D - E).effective_div()
[]
Note
The rank of a divisor \(D\) is -1 if \(D\) is not linearly equivalent to an effective divisor (i.e., the dollar game represented by \(D\) is unwinnable). Otherwise, the rank of \(D\) is the largest integer \(r\) such that \(D - E\) is linearly equivalent to an effective divisor for all effective divisors \(E\) with \(\deg(E) = r\).
The divisor’s underlying sandpile.
OUTPUT:
Sandpile
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: D = SandpileDivisor(S,[1,-2,0,3])
sage: D.sandpile()
Diamond sandpile graph: 4 vertices, sink = 0
sage: D.sandpile() == S
True
Show the divisor.
INPUT:
EXAMPLES:
sage: S = sandpiles.Diamond()
sage: D = SandpileDivisor(S,[1,-2,0,2])
sage: D.show(graph_border=True,vertex_size=700,directed=False)
The first unstabilizable divisor in the closed Markov chain. (See NOTE.)
INPUT:
distrib – (optional) list of nonnegative numbers representing a probability distribution on the vertices
OUTPUT:
SandpileDivisor
EXAMPLES:
sage: s = sandpiles.Complete(4)
sage: D = s.zero_div()
sage: D.simulate_threshold() # random
{0: 2, 1: 3, 2: 1, 3: 2}
sage: n(mean([D.simulate_threshold().deg() for _ in range(10)])) # random
7.10000000000000
sage: n(s.stationary_density()*s.num_verts())
6.93750000000000
Note
Starting at self, repeatedly choose a vertex and add a grain of sand to it. Return the first unstabilizable divisor that is reached. Also see the markov_chain method for the underlying sandpile.
The stabilization of the divisor. If not stabilizable, return an error.
INPUT:
with_firing_vector – (default: False) boolean
EXAMPLES:
sage: s = sandpiles.Complete(4)
sage: D = SandpileDivisor(s,[0,3,0,0])
sage: D.stabilize()
{0: 1, 1: 0, 2: 1, 3: 1}
sage: D.stabilize(with_firing_vector=True)
[{0: 1, 1: 0, 2: 1, 3: 1}, {0: 0, 1: 1, 2: 0, 3: 0}]
List of vertices at which the divisor is nonzero.
OUTPUT:
list representing the support of the divisor
EXAMPLES:
sage: S = sandpiles.Cycle(4)
sage: D = SandpileDivisor(S, [0,0,1,1])
sage: D.support()
[2, 3]
sage: S.vertices()
[0, 1, 2, 3]
The unstable vertices.
OUTPUT:
list of vertices
EXAMPLES:
sage: S = sandpiles.Cycle(3)
sage: D = SandpileDivisor(S, [1,2,3])
sage: D.unstable()
[1, 2]
The values of the divisor as a list. The list is sorted in the order of the vertices.
OUTPUT:
list of integers
boolean
EXAMPLES:
sage: S = Sandpile({'a':[1,'b'], 'b':[1,'a'], 1:['a']},'a')
sage: D = SandpileDivisor(S, {'a':0, 'b':1, 1:2})
sage: D
{'a': 0, 1: 2, 'b': 1}
sage: D.values()
[2, 0, 1]
sage: S.vertices()
[1, 'a', 'b']
The Weierstrass divisor. Its value at a vertex is the weight of that vertex as a Weierstrass point. (See SandpileDivisor.weierstrass_gap_seq.)
INPUT:
verbose – (default: True) boolean
OUTPUT:
SandpileDivisor
EXAMPLES:
sage: s = sandpiles.Diamond()
sage: D = SandpileDivisor(s,[4,2,1,0])
sage: [D.weierstrass_rank_seq(v) for v in s]
[(5, 4, 3, 2, 1, 0, 0, -1),
(5, 4, 3, 2, 1, 0, -1),
(5, 4, 3, 2, 1, 0, 0, 0, -1),
(5, 4, 3, 2, 1, 0, 0, -1)]
sage: D.weierstrass_div()
{0: 1, 1: 0, 2: 2, 3: 1}
sage: k5 = sandpiles.Complete(5)
sage: K = k5.canonical_divisor()
sage: K.weierstrass_div()
{0: 9, 1: 9, 2: 9, 3: 9, 4: 9}
The Weierstrass gap sequence at the given vertex. If weight is True, then also compute the weight of each gap value.
INPUT:
OUTPUT:
list or (list of list) of integers
EXAMPLES:
sage: s = sandpiles.Cycle(4)
sage: D = SandpileDivisor(s,[2,0,0,0])
sage: [D.weierstrass_gap_seq(v,False) for v in s.vertices()]
[(1, 3), (1, 2), (1, 3), (1, 2)]
sage: [D.weierstrass_gap_seq(v) for v in s.vertices()]
[((1, 3), 1), ((1, 2), 0), ((1, 3), 1), ((1, 2), 0)]
sage: D.weierstrass_gap_seq() # gap sequence at sink vertex, 0
((1, 3), 1)
sage: D.weierstrass_rank_seq() # rank sequence at the sink vertex
(1, 0, 0, -1)
Note
The integer \(k\) is a Weierstrass gap for the divisor \(D\) at vertex \(v\) if the rank of \(D - (k-1)v\) does not equal the rank of \(D - kv\). Let \(r\) be the rank of \(D\) and let \(k_i\) be the \(i\)-th gap at \(v\). The Weierstrass weight of \(v\) for \(D\) is the sum of \((k_i - i)\) as \(i\) ranges from \(1\) to \(r + 1\). It measure the difference between the sequence \(r, r - 1, ..., 0, -1, -1, ...\) and the rank sequence \(\mathrm{rank}(D), \mathrm{rank}(D - v), \mathrm{rank}(D - 2v), \dots\)
The Weierstrass points (vertices). Optionally, return the corresponding rank sequences.
INPUT:
with_rank_seq – (default: False) boolean
OUTPUT:
tuple of vertices or list of (vertex, rank sequence)
EXAMPLES:
sage: s = sandpiles.House()
sage: K = s.canonical_divisor()
sage: K.weierstrass_pts()
(4,)
sage: K.weierstrass_pts(True)
[(4, (1, 0, 0, -1))]
Note
The vertex \(v\) is a (generalized) Weierstrass point for divisor \(D\) if the sequence of ranks \(r(D - nv)\) for \(n = 0, 1, 2, \dots`\) is not \(r(D), r(D)-1, \dots, 0, -1, -1, \dots\)
The Weierstrass rank sequence at the given vertex. Computes the rank of the divisor \(D - nv\) starting with \(n=0\) and ending when the rank is \(-1\).
INPUT:
v – (default: sink) vertex
OUTPUT:
tuple of int
EXAMPLES:
sage: s = sandpiles.House()
sage: K = s.canonical_divisor()
sage: [K.weierstrass_rank_seq(v) for v in s.vertices()]
[(1, 0, -1), (1, 0, -1), (1, 0, -1), (1, 0, -1), (1, 0, 0, -1)]
The partitions of the vertices of \(S\) into \(k\) parts, each of which is connected.
INPUT:
S – Sandpile
k – integer
OUTPUT:
list of partitions
EXAMPLES:
sage: S = sandpiles.Cycle(4)
sage: P = [admissible_partitions(S, i) for i in [2,3,4]]
doctest:...: DeprecationWarning:
Importing admissible_partitions from here is deprecated. If you need to use it, please import it directly from sage.sandpiles.sandpile
See http://trac.sagemath.org/18618 for details.
sage: P
[[{{0}, {1, 2, 3}},
{{0, 2, 3}, {1}},
{{0, 1, 3}, {2}},
{{0, 1, 2}, {3}},
{{0, 1}, {2, 3}},
{{0, 3}, {1, 2}}],
[{{0}, {1}, {2, 3}},
{{0}, {1, 2}, {3}},
{{0, 3}, {1}, {2}},
{{0, 1}, {2}, {3}}],
[{{0}, {1}, {2}, {3}}]]
sage: for p in P:
... sum([partition_sandpile(S, i).betti(verbose=False)[-1] for i in p])
doctest:...: DeprecationWarning:
Importing partition_sandpile from here is deprecated. If you need to use it, please import it directly from sage.sandpiles.sandpile
See http://trac.sagemath.org/18618 for details.
6
8
3
sage: S.betti()
0 1 2 3
------------------------------
0: 1 - - -
1: - 6 8 3
------------------------------
total: 1 6 8 3
The aztec diamond graph.
INPUT:
n – integer
OUTPUT:
dictionary for the aztec diamond graph
EXAMPLES:
sage: aztec_sandpile(2)
doctest:...: DeprecationWarning:
Importing aztec_sandpile from here is deprecated. If you need to use it, please import it directly from sage.sandpiles.sandpile
See http://trac.sagemath.org/18618 for details.
{'sink': {(-3/2, -1/2): 2,
(-3/2, 1/2): 2,
(-1/2, -3/2): 2,
(-1/2, 3/2): 2,
(1/2, -3/2): 2,
(1/2, 3/2): 2,
(3/2, -1/2): 2,
(3/2, 1/2): 2},
(-3/2, -1/2): {'sink': 2, (-3/2, 1/2): 1, (-1/2, -1/2): 1},
(-3/2, 1/2): {'sink': 2, (-3/2, -1/2): 1, (-1/2, 1/2): 1},
(-1/2, -3/2): {'sink': 2, (-1/2, -1/2): 1, (1/2, -3/2): 1},
(-1/2, -1/2): {(-3/2, -1/2): 1,
(-1/2, -3/2): 1,
(-1/2, 1/2): 1,
(1/2, -1/2): 1},
(-1/2, 1/2): {(-3/2, 1/2): 1, (-1/2, -1/2): 1, (-1/2, 3/2): 1, (1/2, 1/2): 1},
(-1/2, 3/2): {'sink': 2, (-1/2, 1/2): 1, (1/2, 3/2): 1},
(1/2, -3/2): {'sink': 2, (-1/2, -3/2): 1, (1/2, -1/2): 1},
(1/2, -1/2): {(-1/2, -1/2): 1, (1/2, -3/2): 1, (1/2, 1/2): 1, (3/2, -1/2): 1},
(1/2, 1/2): {(-1/2, 1/2): 1, (1/2, -1/2): 1, (1/2, 3/2): 1, (3/2, 1/2): 1},
(1/2, 3/2): {'sink': 2, (-1/2, 3/2): 1, (1/2, 1/2): 1},
(3/2, -1/2): {'sink': 2, (1/2, -1/2): 1, (3/2, 1/2): 1},
(3/2, 1/2): {'sink': 2, (1/2, 1/2): 1, (3/2, -1/2): 1}}
sage: Sandpile(aztec_sandpile(2),'sink').group_order()
4542720
Note
This is the aztec diamond graph with a sink vertex added. Boundary vertices have edges to the sink so that each vertex has degree 4.
The sandpile on the complete graph with n vertices.
INPUT:
n – positive integer
OUTPUT:
Sandpile
EXAMPLES:
sage: K = sandpiles.Complete(5)
sage: K.betti(verbose=False)
[1, 15, 50, 60, 24]
Creates a digraph with divisors as vertices and edges between two divisors \(D\) and \(E\) if firing a single vertex in \(D\) gives \(E\).
INPUT:
S – Sandpile
eff – list of divisors
OUTPUT:
DiGraph
EXAMPLES:
sage: S = sandpiles.Cycle(6)
sage: D = SandpileDivisor(S, [1,1,1,1,2,0])
sage: eff = D.effective_div()
sage: firing_graph(S,eff).show3d(edge_size=.005,vertex_size=0.01)
If \(D\) and \(E\) are linearly equivalent divisors, find the firing vector taking \(D\) to \(E\).
INPUT:
OUTPUT:
tuple (representing a firing vector from D to E)
EXAMPLES:
sage: S = sandpiles.Complete(4)
sage: D = SandpileDivisor(S, {0: 0, 1: 0, 2: 8, 3: 0})
sage: E = SandpileDivisor(S, {0: 2, 1: 2, 2: 2, 3: 2})
sage: v = firing_vector(S, D, E)
doctest:...: DeprecationWarning: firing_vector() will soon be removed. Use SandpileDivisor.is_linearly_equivalent() instead.
See http://trac.sagemath.org/18618 for details.
doctest:...: DeprecationWarning: May 25, 2015: Replaced by SandpileDivisor.is_linearly_equivalent.
See http://trac.sagemath.org/18618 for details.
sage: v
(0, 0, 2, 0)
The divisors must be linearly equivalent:
sage: vector(D.values()) - S.laplacian()*vector(v) == vector(E.values())
True
sage: firing_vector(S, D, S.zero_div())
Error. Are the divisors linearly equivalent?
Glue two graphs together.
INPUT:
- g, h – dictionaries for directed multigraphs
- glue_h, glue_g – dictionaries for a vertex
OUTPUT:
dictionary for a directed multigraph
EXAMPLES:
sage: x = {0: {}, 1: {0: 1}, 2: {0: 1, 1: 1}, 3: {0: 1, 1: 1, 2: 1}}
sage: y = {0: {}, 1: {0: 2}, 2: {1: 2}, 3: {0: 1, 2: 1}}
sage: glue_x = {1: 1, 3: 2}
sage: glue_y = {0: 1, 1: 2, 3: 1}
sage: z = glue_graphs(x,y,glue_x,glue_y)
doctest:...: DeprecationWarning:
Importing glue_graphs from here is deprecated. If you need to use it,
please import it directly from sage.sandpiles.sandpile
See http://trac.sagemath.org/18618 for details.
sage: z
{0: {},
'x0': {0: 1, 'x1': 1, 'x3': 2, 'y1': 2, 'y3': 1},
'x1': {'x0': 1},
'x2': {'x0': 1, 'x1': 1},
'x3': {'x0': 1, 'x1': 1, 'x2': 1},
'y1': {0: 2},
'y2': {'y1': 2},
'y3': {0: 1, 'y2': 1}}
sage: S = Sandpile(z,0)
sage: S.h_vector()
[1, 6, 17, 31, 41, 41, 31, 17, 6, 1]
sage: S.resolution()
'R^1 <-- R^7 <-- R^21 <-- R^35 <-- R^35 <-- R^21 <-- R^7 <-- R^1'
Note
This method makes a dictionary for a graph by combining those for \(g\) and \(h\). The sink of \(g\) is replaced by a vertex that is connected to the vertices of \(g\) as specified by glue_g the vertices of \(h\) as specified in glue_h. The sink of the glued graph is \(0\).
Both glue_g and glue_h are dictionaries with entries of the form v:w where v is the vertex to be connected to and w is the weight of the connecting edge.
The \(m\times n\) grid sandpile. Each nonsink vertex has degree 4.
INPUT:
m, n – positive integers
OUTPUT:
Sandpile with sink named sink.
EXAMPLES:
sage: G = grid_sandpile(3,4)
doctest:...: DeprecationWarning: grid_sandpile() will soon be removed. Use sandpile.Grid() instead.
See http://trac.sagemath.org/18618 for details.
doctest:...: DeprecationWarning: May 25, 2015: Replaced by sandpiles.Grid.
See http://trac.sagemath.org/18618 for details.
sage: G.dict()
{'sink': {},
(1, 1): {'sink': 2, (1, 2): 1, (2, 1): 1},
(1, 2): {'sink': 1, (1, 1): 1, (1, 3): 1, (2, 2): 1},
(1, 3): {'sink': 1, (1, 2): 1, (1, 4): 1, (2, 3): 1},
(1, 4): {'sink': 2, (1, 3): 1, (2, 4): 1},
(2, 1): {'sink': 1, (1, 1): 1, (2, 2): 1, (3, 1): 1},
(2, 2): {(1, 2): 1, (2, 1): 1, (2, 3): 1, (3, 2): 1},
(2, 3): {(1, 3): 1, (2, 2): 1, (2, 4): 1, (3, 3): 1},
(2, 4): {'sink': 1, (1, 4): 1, (2, 3): 1, (3, 4): 1},
(3, 1): {'sink': 2, (2, 1): 1, (3, 2): 1},
(3, 2): {'sink': 1, (2, 2): 1, (3, 1): 1, (3, 3): 1},
(3, 3): {'sink': 1, (2, 3): 1, (3, 2): 1, (3, 4): 1},
(3, 4): {'sink': 2, (2, 4): 1, (3, 3): 1}}
sage: G.group_order()
4140081
sage: G.invariant_factors()
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1380027]
Minimal length cycles in the digraph \(G\) starting at vertex \(v\).
INPUT:
OUTPUT:
list of lists of vertices
EXAMPLES:
sage: T = sandlib('gor')
sage: [min_cycles(T, i) for i in T.vertices()]
doctest:...: DeprecationWarning:
Importing min_cycles from here is deprecated. If you need to use it, please import it directly from sage.sandpiles.sandpile
See http://trac.sagemath.org/18618 for details.
[[], [[1, 3]], [[2, 3, 1], [2, 3]], [[3, 1], [3, 2]]]
Creates a digraph with divisors as vertices and edges between two divisors \(D\) and \(E\) if firing all unstable vertices in \(D\) gives \(E\).
INPUT:
S – Sandpile
eff – list of divisors
OUTPUT:
DiGraph
EXAMPLES:
sage: S = sandpiles.Cycle(6)
sage: D = SandpileDivisor(S, [1,1,1,1,2,0])
sage: eff = D.effective_div()
sage: parallel_firing_graph(S,eff).show3d(edge_size=.005,vertex_size=0.01)
Each set of vertices in \(p\) is regarded as a single vertex, with and edge between \(A\) and \(B\) if some element of \(A\) is connected by an edge to some element of \(B\) in \(S\).
INPUT:
S – Sandpile
p – partition of the vertices of S
OUTPUT:
Sandpile
EXAMPLES:
sage: S = sandpiles.Cycle(4)
sage: P = [admissible_partitions(S, i) for i in [2,3,4]]
sage: for p in P:
... sum([partition_sandpile(S, i).betti(verbose=False)[-1] for i in p])
6
8
3
sage: S.betti()
0 1 2 3
------------------------------
0: 1 - - -
1: - 6 8 3
------------------------------
total: 1 6 8 3
A random directed acyclic graph with num_verts vertices. The method starts with the sink vertex and adds vertices one at a time. Each vertex is connected only to only previously defined vertices, and the probability of each possible connection is given by the argument p. The weight of an edge is a random integer between 1 and weight_max.
INPUT:
- num_verts – positive integer
- p – (default: 0,5) real number such that \(0 < p \leq 1\)
- weight_max – (default: 1) positive integer
OUTPUT:
a dictionary, encoding the edges of a directed acyclic graph with sink \(0\)
EXAMPLES:
sage: d = DiGraph(random_DAG(5, .5)); d
Digraph on 5 vertices
TESTS:
Check that we can construct a random DAG with the default arguments (trac ticket #12181):
sage: g = random_DAG(5);DiGraph(g)
Digraph on 5 vertices
A random weighted digraph with a directed spanning tree rooted at \(0\). If directed = False, the only difference is that if \((i,j,w)\) is an edge with tail \(i\), head \(j\), and weight \(w\), then \((j,i,w)\) appears also. The result is returned as a Sage digraph.
INPUT:
- num_verts – number of vertices
- p – (default: 0.5) probability edges occur
- directed – (default: True) if directed
- weight_max – (default: 1) integer maximum for random weights
OUTPUT:
random graph
EXAMPLES:
sage: g = random_digraph(6,0.2,True,3)
doctest:...: DeprecationWarning: random_digraph will be removed soon. Use any of the Random* methods
from graphs() and from digraphs() instead.
See http://trac.sagemath.org/18618 for details.
sage: S = Sandpile(g,0)
sage: S.show(edge_labels = True)
TESTS:
Check that we can construct a random digraph with the default arguments (trac ticket #12181):
sage: random_digraph(5)
Digraph on 5 vertices
A random undirected tree with \(n\) nodes, no node having degree higher than \(d\).
INPUT:
n, d – integers
OUTPUT:
Graph
EXAMPLES:
sage: T = random_tree(15,3)
doctest:...: DeprecationWarning: random_tree will be removed soon. Use graphs.RandomTree() instead.
See http://trac.sagemath.org/18618 for details.
sage: T.show()
sage: S = Sandpile(T,0)
sage: U = S.reorder_vertices()
sage: U.show()
Returns the sandpile identified by selector. If no argument is given, a description of the sandpiles in the sandlib is printed.
INPUT:
selector – (optional) identifier or None
OUTPUT:
sandpile or description
EXAMPLES:
sage: sandlib()
doctest:...: DeprecationWarning: sandlib() will soon be removed. Use sandpile() instead.
See http://trac.sagemath.org/18618 for details.
Sandpiles in the sandlib:
kite : generic undirected graphs with 5 vertices
generic : generic digraph with 6 vertices
genus2 : Undirected graph of genus 2
ci1 : complete intersection, non-DAG but equivalent to a DAG
riemann-roch1 : directed graph with postulation 9 and 3 maximal weight superstables
riemann-roch2 : directed graph with a superstable not majorized by a maximal superstable
gor : Gorenstein but not a complete intersection
sage: S = sandlib('gor')
sage: S.resolution()
'R^1 <-- R^5 <-- R^5 <-- R^1'
A triangular sandpile. Each nonsink vertex has out-degree six. The vertices on the boundary of the triangle are connected to the sink.
INPUT:
n – integer
OUTPUT:
Sandpile
EXAMPLES:
sage: T = triangle_sandpile(5)
doctest:...: DeprecationWarning:
Importing triangle_sandpile from here is deprecated. If you need to use it, please import it directly from sage.sandpiles.sandpile
See http://trac.sagemath.org/18618 for details.
sage: T.group_order()
135418115000
Computes an integer matrix \(L\) with the same integer row span as \(M\) and such that \(L\) is the reduced Laplacian of a directed multigraph.
INPUT:
M – square integer matrix of full rank
OUTPUT:
integer matrix (L)
EXAMPLES:
sage: P = matrix([[2,3,-7,-3],[5,2,-5,5],[8,2,5,4],[-5,-9,6,6]])
sage: wilmes_algorithm(P)
[ 1642 -13 -1627 -1]
[ -1 1980 -1582 -397]
[ 0 -1 1650 -1649]
[ 0 0 -1658 1658]
REFERENCES:
| [Primer2013] | Perlman, Perkinson, and Wilmes. Primer for the algebraic geometry of sandpiles. Tropical and Non-Archimedean Geometry, Contemp. Math., 605, Amer. Math. Soc., Providence, RI, 2013. |