divisors that could be realised from a firing script. That is,
M(G) -div→ Div(G) -quotient→ Pic(G) → 0
Z^n -L→ Z^n -quotient'→ cok(L) ~= Z^n/Im L → 0
- The quotient map
quotient is surjective.
- The map
quotient' is also surjective
§ Dollar game in terms of laplacian
given a divisor , does there exist a vector
such that ?
Clearly, this is some sort of linear inequality. So, we expect polytopes
to show up! Since is an integer point, we want integer points in polytopes.
§ Kernel of laplacian in connected graph: all 1s vector
- first of all, see that lending by everyone in has no effect: everyone lends to all their neighbours, and all their neighbours lend to them, having zero net effect.
- Stated in terms of the firing script, this means that is in the kernel of : the firing script creates a zero divisor. If we choose a basis, this is the all 1s vector.
- In terms of the laplacian, this is stating that the all ones vector is in the kernel of the laplacian.
§ Kernel of laplacian in connected graph: constant functions (TODO)
Suppose we have a script such that .
This feels sheafy to me, in terms of "locally constant".
§ Reduced laplacian: Configurations on
We build reduced laplacians to relate the jacobian (degree zero elements of divisor class group)
and the laplacian.
Fix a vertex . Define . A configuration
on with respect to is an element of the subgroup
so we simply forget the value at . Alternatively, we set the value of
to zero and continue will our divisor definitions.
We can perform lending and borrowing on a configuration divisor, by simply
not tracking data at .
§ 3: Winning
§ q-reduced configurations
We wish to solve the game by benelovence: have vertices lend to adjacent vertices.
Here are the steps to convert such an intuition to a real algorithm:
In the end, if is no longer in debt, we win. Otherwise, is unwinnable.
- Start with a divisor we want to find an effective divisor that is linearly equivalent to (ie, there exists a series of moves to convert to ).
- Pick some benelovent vertex . Call the source. Let be the non source vertices.
- Let lend so much money to the non-source-vertices, such that the non-source-vertices, sharing amongst themselves, are out of debt.
- Now only is in debt from this giving. makes no lending or borrowing moves. The non-source-vertices must get out of debt. Find a such that if everyone in lends, then no one in go into debt. Make the corresponding set-lending move. Repeat until no such remains. The resulting divisor is said to be -reduced.
§ Superstable configuration
Let . It is called superstable if and has
no legal non-empty set firings. That is, for each non-empty ,
we have some such that firing would cause to go into debt;
that is, .
§ Decomposition of divisor into superstable configuration
Every divisor can be written as where .
In this form, is -reduced iff is superstable! This follows
from the definition of -reduced: there is no subset which can be fired such
that stays out of debt. Now, if , then we win, from what we know
of -reduced configurations.
§ 4: Acylic orientations
An orientation of a graph makes each edge directed. We think of edges now as
tuples as an edge from to . We denote and
to be the source and sink vertices of the orientation.
§ Acylic orientations
An orientation is acyclic if there are no cycles. Every acylic orientation
must have at least one sink and a source. It must have at least one source .
Assume the acyclic orientation does not have any sources.
§ Acylic orientation has at least one source
Pick any vertex . If it is a source, done. If it is not a source, it has a parent.
Go to parent that has NOT BEEN PICKED YET, repeat check. We will eventually:
Thus all acyclic orientations have at least one source.
- Find a source vertex (vertex with no parent)
- All parents of current vertex have been picked (ie, we find a cycle). Can't happen.
§ Indegree sequence of an acyclic orientation.
If is an orientation, define
That is, to each , associate the number of edges whose end is at .
§ WRONG: Acylic orientation determined by indegree sequence?
The book claims that acyclic orientation is determined by the indegree sequence.
I don't believe this. Consider the graph :
Now consider :
- This has indegrees .
- This has indegrees but the graphs are not equal!
§ Acylic orientation determined by indegree sequence
OK, the above is not what the book claims. The book claims that two orientations
, of the same graph are equal if their indegree sequences
This is believeable, because if the orientations point differently, their
indegrees will change.
- Proof strategy: induction on number of vertices + forcing sources to be the same + creating new sources by removing current sources.
- Theorem is immediate with only one vertex. Assume holds for . Now we have a graph with vertices. Find source in acyclic orientation . This has no incoming edges, so has indegree zero. This must be the same in since and have the same indegree sequence.
- Now remove the sources that are structurally equal. We get a graph of of (n-1) vertices, and we get and by removing the sources from . Since we must have that since removing the same source from both graphs modifes the orientations the same way. Recurse into .
§ Divisor for an orientation
For an orientation we define a divisor as:
§ 5: Riemann roch
§ The rank function
In one sense, the “degree of winnability” of the dollar game is measured by the size
of complete linear systems: is “more winnable” than if
. Instead of measuring , we choose to
define another function, the rank, that measures "stability/robustness of winnability"
- Fist, if is unwinnable: iff
- Next, if is barely winnable. That is, is winnable, but there is some vertex such that is unwinnable. That is, is barely winnable if the ability to win at can be destroyed by a single vertex losing a dollar.
- In general, for , define that is at least winnable if the dollar game is winnable strating from all divisors obtained from by removing dollars. Formally, this becomes:
This means that if there is some divisor of degree such that is
§ is upper bounded by degree:
§ if is of degree 0, then rank is 0 iff is principal
§ : adding a dollar can increase rank by at most 1
§ : rank is super-linear.
§ Lower bound on rank:
Won't prove this here, depends on other results (if , then is winnable)
§ Canonical divisor
For any orientation , define to be the reversed orientation. Now
define the canonical divisor to be . See that
for every :