$deg(D) \equiv \sum_{v \in V} D(v)$.
§ Borrowing and lending at a vertex $v_\star$
 Lending: $v$ gives 1 unit of money to all its neighbours
$f' = f + \sum_{vw \in E} v + w$
 Borrowing: $v$ takes 1 unit of money from all its neighbours
$f' = f + \sum_{vw \in E} + v  w$
§ Borrowing and lending on a set $S$:
 Lending on a set $S$: every vertex $v \in S$ gives 1 unit of money to all its neighbours
$f' = f + \sum_{v \in S}\sum_{vw \in E} v + w$
 Borrowing defined similarly.
 See that borrowing at a vertex $v$ is the same as lending from $V / v$.The reason being, the lending between vertices of $V/v$ will cancel, and onlylends into $v$ will be counted. This is the same as $v$ borrowing.
§ Linear equvivalence
Two divisors $D_1, D_2$ are linearly equivalent iff there is a sequence of
borrowing or lending moves that leads from $D_1$ to $D_2$. This is an
equivalence relation on the space of divisors. Equivalence class of $D_1$
is represented by $[D_1]$.
§ Partial ordering of divisors
We say that $D_1 < D_2$ if for all $v$, $D_1(v) < D_2(v)$.
§ Effective divisors
A divisor such that $\forall v, D(v) \geq 0$ is called as an effective divisor. Sometimes written
as $D \geq 0$.
Our goal is given a divisor $D$, to check if it is linearly equivalent to
a divisor $D'$ such that $D \geq 0$. If we can do so, then no one is in debt,
and we have won the game.
§ Addition of divisors
We add divisors pointwise: $(f + g)(v) \equiv f(v) + g(v)$.
This respects linear equivalence. Hence, $[D_1] + [D_2] \equiv [D_1 + D_2]$.
This makes divisors, and their equivalence classes an abelian group
§ The Picard Class Group (group of divisor classes)
The group of equivalence classes of divisors under pointwise addition is
the picard group.
§ Jacobian Class group (divisor classes of degree 0).
 Subgroup of picard group of degree 0.
 That is, all equivalence class elements of degree 0.
 This is well defined because all linearly equivalent divisors (divisors that can be gotten by lending/borrowing) all have the same degree (total money). This is becauselending/borrowing does not change the total amount of money in the market,only redistributes it.
§ Picard group decomposition in terms of Jacobian group
For each $q \in V$, there is an isomorphism of groups $\phi_q: Pic(G) \rightarrow \mathbb Z \times Jac(G)$,
where we send a divisor class $[D]$ to $\phi_q([D]) \equiv (deg(D), [D  deg(D)q]$.
 Clearly, the new divisor $[D  deg(D)q]$ has total degree $0$, since $deg(D)$has been subtracted off at $q$.
 We can recover the original divisor since we know $deg(D)$.
§ Complete linear system $[D]_{\geq 0}$
The complete linear system of $D$ is the set of all winning configurations from $D$.
That is:
$[D]_{\geq 0} \equiv \{ E \in [D] : E \geq 0 \}$
We win the game if $[D]_{\geq 0}$ is nonempty.
§ The discrete laplacian
The laplacian is the map $L: (V \rightarrow \mathbb Z) \rightarrow (V \rightarrow \mathbb Z)$
defined by:
$L(f)(v) \equiv \sum_{vw \in E} (f(v)  f(w))$
That is, $L(f)(v)$ is the total deviation of $v$ from all of its neighbours $w$.
§ Firing script
A firing script is a function $s: V \rightarrow \mathbb Z$ ($s$ for script) that
tells us how many times $v$ lends money to its neighbours).
 The collection of all firing scripts form an abelian group, and is denotedby $M(G)$. [TODO: why $M$?]
 Set lending by a subset $W \subset V$ is denoted by $\chi_W$, where $\chi_W(v) \equiv 1$ if $v \in W$and $\chi_W(v) \equiv 0$ otherwise. Written in iverson notation, we have $\chi_W(v) \equiv [v \in_? W]$.
 The effect of running a firing script $s$ on a divisor $D$ to get a divisor $D'$ is:
$\begin{aligned}
D' \equiv D + \sum_{v \in V} s(v) (v+ w) \\
\end{aligned}$
if $s: V \rightarrow \mathbb Z$ is a firing script, then the divisor of the
firing script $s$ is:
$div(s) \equiv \sum_{v \in V} s(v) (v+ w)$
 The effect of running a firing script is to replace a divisor $D$ by a newdivisor $D' = D + div(s)$. We denote this by $D \xrightarrow{s} D'$ and callthis as scriptfiring
§ div
is a group homomorphism
We see that div
is a function from $M(G) = V \rightarrow \Z$ to $Div(G) = V \rightarrow \Z$
under the map:
$div(s) \equiv \sum_{v \in V} s(v) (v+ w)$
We show that $div(s_1  s_2) = div(s_1)  div(s_2)$ thereby checking the homomorphism
property.
$\begin{aligned}
&div(s_1  s_2) = \sum_{v \in V} (s_1  s_2)(v) (v+ w) \\
&= \sum_{v \in V} (s_1(v)  s_2(v)) (v+ w) \\
&= \sum_{v \in V} s_1(v) (v+ w)  \sum_{v \in V} s_2(v) (v+ w) \\
&= div(s_1)  div(s_2)
\end{aligned}$
and is hence a group homomorphism.
§ div
produces divisors of degree 0: deg(div(s)) = 0
.
See that $div$ is balanced, in that for every $v$ we have a $+w$. This makes
the total degree zero.
§ Principal divisors: $Prin(G) \equiv div(M(G))$.
 Divisors of the form
div(s)
are called as Principal divisors. They are a subgroup of the degree 0 divisors.
 Moreover, if $D'$ is obtainable from $D$ by a series of lending and borrowing moves, then $D'  D \in Prin(G)$.
 This means that linear equivalence is a coset of the principal divisors: $[D] = D + Prin(G)$.
§ Picard, Jacobian Class group as quotients
 $Pic(G) = Div(G)/Prin(G)$.
 $Jac(G) = Div^0(G)/Prin(G)$.
 $Pic(G), Jac(G)$ are class groups because we get equivalence classes of divisors,equivalent upto principal divisors.
§ div
is same as laplacian
§ Picard group is cokernel of L
Recall that Pic(G) = Div(G)/Prin(G)
, where Prin(G)
was the collection of
divisors that could be realised from a firing script. That is,
$Prin(G) \equiv \{ div(s) : s \in V \rightarrow \mathbb Z \}$
M(G) div→ Div(G) quotient→ Pic(G) → 0
 
f g
 
v v
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 $D$, does there exist a vector $x \in \mathbb Z^V$
such that $D + Lx \geq 0$?
Clearly, this is some sort of linear inequality. So, we expect polytopes
to show up! Since $x$ 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 $V$ 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 $s_1 + s_2 + \dots s_n$is in the kernel of $div$: 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 inthe kernel of the laplacian.
§ Kernel of laplacian in connected graph: constant functions (TODO)
Suppose we have a script $s: V \rightarrow \mathbb Z$ such that $div(s) = 0$.
TODO
This feels sheafy to me, in terms of "locally constant".
§ Reduced laplacian: Configurations on $G$
We build reduced laplacians to relate the jacobian (degree zero elements of divisor class group)
and the laplacian.
Fix a vertex $q \in V$. Define $\tilde{V} \equiv V /\{q\}$. A configuration
on $G$ with respect to $q$ is an element of the subgroup
$Config(G, q) \equiv \mathbb Z \tilde{V} \subseteq ZV = Div(G)$
so we simply forget the value at $q$. Alternatively, we set the value of $q$
to zero and continue will our divisor definitions.
We can perform lending and borrowing on a configuration divisor, by simply
not tracking data at $q$.
§ 3: Winning
§ qreduced 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:
 Start with a divisor $D$ we want to find an effective divisor $E \geq 0$that $D$ is linearly equivalent to (ie, there exists a series of moves to convert $D$ to $E$).
 Pick some benelovent vertex $q \in V$. Call $q$ the source. Let $V' = V/q$ be the nonsource vertices.
 Let $q$ lend so much money to the nonsourcevertices, such that the nonsourcevertices,sharing amongst themselves, are out of debt.
 Now only $q$ is in debt from this giving. $q$ makes no lending or borrowing moves.The nonsourcevertices must get $q$ out of debt. Find a $S \subseteq V'$ such that ifeveryone in $S$ lends, then no one in $S$ go into debt. Make the corresponding setlendingmove. Repeat until no such $S$ remains. The resulting divisor is said to be $q$reduced.
In the end, if $q$ is no longer in debt, we win. Otherwise, $D$ is unwinnable.
§ Superstable configuration
Let $c \in Config(G, q)$. It is called superstable if $c \geq 0$ and has
no legal nonempty set firings. That is, for each nonempty $S \subseteq V/q$,
we have some $v \in S$ such that firing $v$ would cause $v$ to go into debt;
that is, $c(v) < outdeg_S(v)$.
§ Decomposition of divisor into superstable configuration
Every divisor can be written as $D = c + kq$ where $c \in Config(G, q) \geq 0$.
In this form, $D$ is $q$reduced iff $c$ is superstable! This follows
from the definition of $q$reduced: there is no subset $S$ which can be fired such
that $S$ stays out of debt. Now, if $q \geq 0$, then we win, from what we know
of $q$reduced configurations.
§ 4: Acylic orientations
§ Orientations
An orientation of a graph makes each edge directed. We think of edges now as
tuples $e \equiv (u, v)$ as an edge from $u$ to $v$. We denote $e^ = u$ and
$e^+ = v$ 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:
 Find a source vertex (vertex with no parent)
 All parents of current vertex have been picked (ie, we find a cycle). Can'thappen.
Thus all acyclic orientations have at least one source.
§ Indegree sequence of an acyclic orientation.
If $O$ is an orientation, define
$indeg_O(u) \equiv \{ e \in O : e^+ = u \}$
That is, to each $u$, associate the number of edges whose end is at $u$.
§ 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 $G$:
a
 
v v
b c
 This has indegrees $(a=0, b=1,c=1)$.
Now consider $H$:
a

v
b

v
c
 This has indegrees $(a=0, b=1, c=1)$ 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
$O_G$, $O'_G$ of the same graph are equal if their indegree sequences
are equal.
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 sourcesby removing current sources.
 Theorem is immediate with only one vertex. Assume holds for $n$. Now we havea graph with $(n+1)$ vertices. Find source in acyclic orientation $O_G$. This hasno incoming edges, so has indegree zero. This must be the same in $O'_G$ since$O_G$ and $O'_G$ have the same indegree sequence.
 Now remove the sources that are structurally equal. We get a graph of $H$ of(n1) vertices, and we get $O_H$ and $O'_H$ by removing the sources from $O_G, O_G'$. Since $O_G = O_G'$ we must have that $O_H = O_H'$ since removingthe same source from both graphs modifes the orientations the same way. Recurseinto $O_H, O_H'$.
§ Divisor for an orientation
For an orientation $O$ we define a divisor $D(O)$ as:
$D(O) \equiv \sum_{v \in V}(indeg_O(v)  1) v$
§ 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: $D$ is “more winnable” than $D'$ if
$[D]_{\geq 0} > [D']_{\geq 0}$. Instead of measuring $[D]_{\geq 0}$, we choose to
define another function, the rank, that measures "stability/robustness of winnability"
 Fist, $r(D) \equiv 1$ if $D$ is unwinnable: $r(D) \equiv 0$ iff $[D]_{\geq 0} = \emptyset$
 Next, $r(D) = 1$ if $D$ is barely winnable. That is, $D$ is winnable, but there is some vertex $v$ such that $D  v$ is unwinnable. That is, $r(D)$is barely winnable if the ability to win at $D$ can be destroyed by a singlevertex losing a dollar.
 In general, for $k \geq 0$, define that $r$ is at least $k$ winnable if the dollargame is winnable strating from all divisors obtained from $D$ by removing $k$dollars. Formally, this becomes:
$r(D) \geq k \iff D  E \neq \emptyset \text{for all $E \geq 0$ ($E$ effective) of degree $k$}$
This means that $r(D) = l$ if there is some divisor $E$ of degree $l+1$ such that $D  E$ is
not winnable.
§ $r(D)$ is upper bounded by degree: $r(D) \leq deg(D)$
§ if $D$ is of degree 0, then rank is 0 iff $D$ is principal
§ $r(D) \leq r(D + v) \leq r(D) + 1$: adding a dollar can increase rank by at most 1
§ $r(D + D') \geq r(D) + r(D')$: rank is superlinear.
§ Lower bound on rank: $r(D) \geq deg(D)  g$
Won't prove this here, depends on other results (if $deg(D) \geq g$, then $D$ is winnable)
§ Canonical divisor
For any orientation $O$, define $O_{rev}$ to be the reversed orientation. Now
define the canonical divisor $K$ to be $K \equiv D(O) + D(O_{rev})$. See that
for every $v \in V$:
$\begin{aligned}
K(V) = indeg_O(v) + outdeg_O(v) = deg_G(v)
\end{aligned}$
§ References