betaFeedback

WorksMathematics

Discrete Spoilers: Introducing Abstract Undergraduate Mathematics Using Graph Theory

Abstract

Students often have serious difficulties with many key concepts of the undergraduate mathematics curriculum. We argue that many of these difficulties can be eased by explicitly separating the key ideas from the technical details. To do so, we present finite graphs as a setting where the basic concepts appear more transparently, because on a graph most proofs only require basic techniques from linear algebra. We illustrate this approach in three areas that cover a large part of the curriculum. First, we explain basic operators from vector calculus, such as the gradient and the divergence, through the incidence matrix of a graph. Second, we show that the diffusion equation has a simple solution on a graph. We also solve the graph Dirichlet problem, in which the values at some vertices are fixed. Third, we introduce a second incidence matrix that illustrates homology, cohomology and the Helmholtz decomposition in a simple way. Finally, we outline how to apply this approach to other branches of mathematics.

Introduction

In 1750, in a letter to Goldbach, Euler stated that a polyhedron with VV vertices, EE edges and FF faces satisfies V−E+F=2V-E+F=2 [1]. This identity was “proven” by him soon after, and again by Cauchy in 1813. Yet that same year Lhuilier found polyhedra that did not satisfy the formula [2], such as a polyhedron with the shape of a picture frame, for which V−E+F=0V-E+F=0 (Figure 1). These counterexamples forced mathematicians to change the statement of the theorem, its proof and even the definition of a polyhedron. Lhuilier himself showed that a polyhedron with gg tunnels satisfies V−E+F=2−2gV-E+F=2-2g. Later, Poincaré generalized the alternating sum V−E+FV-E+F to the Euler characteristic of a general space and related it to the Betti numbers of the space [1]. Overall, the full understanding of Euler’s formula required more than a century of collective work.

Figure 1. Left, a cube. Right, a polyhedron in the shape of a beveled picture frame, with a square tunnel through the middle. Below each polyhedron, the numbers VV, EE and FF of vertices, edges and faces, and the value of V−E+FV-E+F compared with 2. Dashed lines are hidden edges.

This history is a good illustration of the way mathematics advances. Mathematicians start from concrete cases, such as the cube and other convex polyhedra, make a conjecture and look for a proof. Using counterexamples, they can also refine the hypotheses that the theorem needs. At the end of the process, once they understand the problem, they extract a definition that condenses what they have learned [3]. In many courses, however, the order is the opposite. For example, a course on algebraic topology may define the Euler characteristic of a space as “the alternating sum of the dimensions of the quotients of the kernel of each boundary map by the image of the next one” before giving any motivation or example. Do we really expect students to understand this chain of abstract concepts without any preparation? More likely, students either understand very little and become frustrated, or learn to manipulate abstract concepts without understanding their meaning or the problems they are meant to solve [4]. In the latter case, they learn mathematics, but not how to think like a mathematician.

Of course, a course cannot reproduce every attempt and every counterexample that led to a definition. However, we can show students why we introduce a definition and which problem it aims to solve, before we present its technical version. In this article we argue that finite graphs are a natural setting to explore many abstract concepts of the undergraduate curriculum in this way [5, 6, 7, 8]. We see two reasons that make graphs an ideal didactic tool. First, graphs are accessible. We can draw a graph, and in a proof we can draw each step of the argument and see what it means on a particular graph. Hence a student can explore mathematical arguments with much less abstraction, in the same spirit as the exploration of concrete cases that we described above. Second, and most importantly, on a finite graph, the study of operators acting on functions reduces to the study of matrices acting on vectors. Hence the theorems that characterize these operators are based on linear algebra, a subject that students already know well, and the proofs are short and intuitive.

Therefore, if we first teach a problem in a discrete setting, the student can put all their mental effort into the problem itself. Why is the question interesting? How do we translate it into mathematical language? Which ideas lead to a proof? Only after the student has understood the object of study and the ideas behind it can we introduce the continuous version and the difficulties that require new mathematical tools (compactness, completeness, etc.). We can see a problem on a graph as a discrete spoiler of the more general problem: the graph version gives away the key idea, the “click” in the student’s mind, without all the development needed to reach it in the more difficult setting. Graph versions are also discrete spoilers, because the student realizes only later, with the hard version of the problem, that they were foreshadowing something important. In the rest of this article, we exemplify this approach in three areas of the curriculum: vector calculus, partial differential equations and algebraic topology. In § 2, we build the gradient and the divergence of a graph from its incidence matrix BB, with a model of opinions in a social network as motivation, and study the four fundamental subspaces of BB. In § 3, we solve this model, which is the graph version of the diffusion equation, and the analogous problem with zealots (people who never change their opinion), which is the graph version of the Dirichlet problem. In § 4, we build a curl by looking at the triangles of the graph and obtain homology, cohomology and the complete Helmholtz decomposition of the edge space. In § 5, we outline how to apply the same approach to other branches of mathematics. We end in Section 6 with a discussion of earlier work and of the limits of our approach.

Calculus on a graph

We start by motivating our framework with a question from everyday life. Several people discuss a topic, for example the quality of a film, with every person having an initial opinion on the film. Every day, each person talks only with his or her friends, and after each conversation the opinions of the two friends are closer than before. The pairs of friends form a graph G=(V,E)G=(V,E), with a set VV of vertices, one for each person, and a set EE of edges, one for each pair of friends. We will assume that GG is undirected, unweighted and simple (no loops or multiple edges). We write nn for the number of vertices and mm for the number of edges. How do the opinions change in time? Do all the people reach an agreement, and on which opinion?

To answer these questions, we need a mathematical description of the opinions and a rule for the way in which they change. We will assume that the opinion of the person at each vertex vv at time tt is a real number xv(t)x_v(t), with large numbers for a good opinion and small numbers for a bad one. Mathematically, this assumption corresponds, at each time tt, to a function from VV to R\mathbb{R} that assigns the real number xv(t)x_v(t) to each vertex vv. Since VV is finite, this function is determined by its nn values xv(t)x_v(t), so we can identify it with the vector x(t)∈Rnx(t) \in\mathbb{R}^n and the space of all opinions with Rn\mathbb{R}^n. This finite description is very different from the case of functions from R\mathbb{R} to R\mathbb{R}, which form a space of infinite dimension and require formal tools from real analysis, such as suprema or Cauchy sequences. Already at this point, we see that working on a graph greatly reduces the technical tools that we need to do mathematics.1

For the rule that governs the evolution, we will assume that the opinions change in the simplest possible way. People change their opinion only through conversations with their friends. In a conversation, each friend is influenced by the other in the same way, so the two opinions move toward each other by the same amount. In particular, the friend with the larger opinion lowers it, while the friend with the smaller opinion raises it. Two friends with very different opinions have more to argue about than two friends who almost agree, so their opinions change faster. To model these assumptions, we introduce a flow of opinion along each edge, from the larger opinion to the smaller one, proportional to the difference between the two opinions. In other words, the flow along each edge is proportional to a discrete version of the derivative of the opinions.

How can we define a discrete derivative? In one dimension, the derivative of a function xx at a point vv is the limit of (x(v+ε)−x(v))/ε(x(v+\varepsilon)-x(v))/\varepsilon as ε→0\varepsilon\to0. But on a graph, this limit has no meaning, because two vertices cannot be infinitely close. The smallest distance between two vertices is one, so we set ε=1\varepsilon=1 and identify the point v+εv+\varepsilon with a neighbor of vv, say, ww. The derivative of xx along the edge (v,w)(v,w) is then the difference xw−xvx_w-x_v. Note that the discrete derivative is a linear map between functions on two different sets, namely from functions on the vertices, in Rn\mathbb{R}^n, to functions on the edges, in Rm\mathbb{R}^m. In the continuum, the gradient also maps a function to a different kind of object, a vector field. However, the function and the vector field are defined on the same domain, so many students do not notice this change. On a graph, in contrast, this change is much more explicit, because the two functions are defined on different sets.

Our definition of the discrete derivative still has a problem. An undirected edge between vv and ww has no preferred endpoint, so we could equally take the difference xv−xwx_v-x_w. The first difference corresponds to the orientation of the edge from vv to ww, and the second one to the reverse. Which of the two should we choose? It turns out that the choice does not matter, as long as we use the same orientation throughout [9], so we will choose an arbitrary orientation for each edge. Figure 2 shows one such choice in an example with five people (we will refer to this graph as the house graph because of its shape). So, in summary, if we write t(e)t(e) for the vertex where an edge ee starts, the tail of ee, and h(e)h(e) for the vertex where it ends, the head of ee, then the discrete derivative of xx along ee, which we call the gradient of xx along ee and denote by (∇x)e(\nabla x)_e, is

The house graph, with one person at each vertex and an edge between each pair of friends

Figure 2. The house graph, with one person at each vertex and an edge between each pair of friends. Each edge is given an arbitrary orientation.

(∇x)e=xh(e)−xt(e).(\nabla x)_e=x_{h(e)}-x_{t(e)}.

The gradient is linear in xx. On a graph, every linear operator on the functions on the vertices is a matrix, so we can write the gradient as the product of a matrix and the vector xx. What does this matrix look like? First, it must clearly be rectangular, with mm rows and nn columns. Since each row ee computes a difference between the two endpoints of ee, it must have a value 11 in column h(e)h(e), −1-1 in column t(e)t(e) and zeros elsewhere. For example, for the house graph with the orientation of Figure 2, the matrix of the gradient is

(−11000−101000−101000−11000−101000−11)(1)\begin{pmatrix} -1 & 1 & 0 & 0 & 0 \\ -1 & 0 & 1 & 0 & 0 \\ 0 & -1 & 0 & 1 & 0 \\ 0 & 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 0 & 1 \\ 0 & 0 & 0 & -1 & 1 \tag*{(1)} \end{pmatrix}

Now that we have a notion of gradient, we can define the flow of opinion as the vector f=−∇x∈Rm\mathbf{f}=-\nabla x\in\mathbb{R}^{m}. Each component fef_e is the amount of opinion that moves along the edge ee per unit of time, positive if opinion moves from t(e)t(e) to h(e)h(e) and negative otherwise. We choose this definition by analogy with Fourier’s law, according to which the flow of heat is F=−∇u\mathbf{F}=-\nabla u, with uu the temperature.

Our next goal is to combine the flows to deduce how the opinion at each vertex changes. The opinion at vertex vv changes at a rate equal to the net flow into vv, which is

∑e: h(e)=vfe−∑e: t(e)=vfe\sum_{e:\,h(e)=v} f_e-\sum_{e:\,t(e)=v} f_e

We identify this net flow with minus the divergence of ff at vv, −(div⁡f)v-(\operatorname{div} f)_v, by analogy with the continuum. Note that div⁡\operatorname{div} maps functions on the edges to functions on the vertices. We can once again find the matrix associated with this linear operator. Each row vv has the entry 11 in the columns of the edges that start at vv, the entry −1-1 in the columns of the edges that end at vv, and zeros elsewhere. For the house graph with the orientation of Figure 2, the matrix of the divergence is

(110000−1010000−1011000−1−1010000−1−1)\begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ -1 & 0 & 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 1 & 1 & 0 \\ 0 & 0 & -1 & -1 & 0 & 1 \\ 0 & 0 & 0 & 0 & -1 & -1 \end{pmatrix}

But this matrix is minus the transpose of (1)! We defined the gradient as a discrete derivative and the divergence as a balance of flows, and yet the two operators have the same matrix up to a transpose and a sign. This identity is true for every graph, and as a result a single matrix is enough to describe both operators. We call the incidence matrix of the graph the n×mn \times m matrix BB with Bve=1B_{ve}=1 if v=h(e)v=h(e), Bve=−1B_{ve}=-1 if v=t(e)v=t(e) and Bve=0B_{ve}=0 otherwise, so that ∇=BT\nabla=B^{T} and div⁡=−B\operatorname{div}=-B. We use the name incidence because the nonzero entries of each column ee of BB indicate the two vertices incident to ee.

The four fundamental subspaces of BB

Before we go back to our model of opinions, let us see what the matrix BB tells us about the graph. Like any other matrix, BB has four fundamental subspaces, namely the kernel and the image of BB and of its transpose [10]. Do these subspaces contain information about the graph? We will see that, indeed, they describe its connected components, its cycles and its cuts.

We can find the kernel of BTB^{T} directly. A vector x∈Rnx \in\mathbb{R}^{n} satisfies BTx=0B^{T}x=0 if and only if it has the same value at the two endpoints of every edge. In that case, xx has the same value along every path, so it must be constant on each connected component. Conversely, every vector that is constant on each connected component satisfies BTx=0B^{T}x=0. Hence dim⁡ker⁡BT=c\dim\ker B^{T}=c, where cc is the number of connected components of the graph. In our model of opinions, the opinion vectors in ker⁡BT\ker B^{T} produce no flow. Once we know the kernel of BTB^{T}, we obtain the image of BB for free, as the two subspaces are orthogonal complements in Rn\mathbb{R}^{n}, so im⁡B\operatorname{im} B consists of the vectors with zero sum on each connected component. This has a natural interpretation in our opinion model. BfBf represents the net change in opinions induced by a flow ff. Each flow transfers opinion from one vertex to another without changing the component’s total, so only opinion changes that preserve these totals are admissible. im⁡B\operatorname{im} B consists precisely of the admissible opinion changes.

Let us now look at the kernel of BB. Since B=−div⁡B=-\operatorname{div}, this kernel contains the flows with zero divergence, that is, the flows for which the total flow that enters each vertex is equal to the total flow that leaves it. The simplest way to obtain such a flow is to send one unit of flow around a cycle of the graph. We describe this flow with the vector γ∈Rm\gamma\in\mathbb{R}^{m} that is equal to 11 on the edges of the cycle whose orientation agrees with the direction of the flow, to −1-1 on the other edges of the cycle and to 00 elsewhere. By construction, this flow belongs to ker⁡B\ker B, and it can be proven that analogous flows around each cycle of the graph span the kernel of BB [9]. From now on, we will call every vector γ∈Rm\gamma\in\mathbb{R}^{m} with Bγ=0B\gamma=0 a cycle. For example, on the house graph, the flows around the square and through the roof are the cycles γ1=(1,−1,1,−1,0,0)T\gamma_1=(1,-1,1,-1,0,0)^{T} and γ2=(0,0,0,1,−1,1)T\gamma_2=(0,0,0,1,-1,1)^{T}. In our model, a cycle is a flow that does not change any opinion.

Finally, let us look at the image of BTB^{T}. To construct vectors in im⁡BT\operatorname{im} B^{T}, we can choose opinion vectors xx and apply BTB^{T} to them. Consider the indicator vector xx of a subset AA, which takes the value 1 on the vertices in AA and 0 on the vertices in its complement AcA^{c}. With this choice, an edge can have nonzero flow only if it connects AA to AcA^{c}. The set of edges connecting a vertex subset to its complement is called a cut in graph theory. Since every cut can be obtained from such a choice of xx, the space im⁡BT\operatorname{im} B^{T} is spanned by all cut vectors, that is, by the vectors BTxB^{T}x with xx an indicator vector. Figure 3 shows the cut of A={1,2}A = \{1, 2\} in the house graph, together with one vector in each of the other three subspaces.

Figure 3. Illustration of the four fundamental subspaces of the incidence matrix BB of the house graph, with the numbering and orientation of the left panel. For each subspace, we show one vector, both as a column vector and on the graph. For vectors of the vertex space Rn\mathbb{R}^{n}, we write each entry inside its vertex and draw a thick border around the vertices with nonzero entries. For vectors of the edge space Rm\mathbb{R}^{m}, we draw the edges with nonzero entries with thick lines and write these entries next to them. Top left, a constant opinion vector, in ker⁡BT\ker B^{T}. Top right, the change of the opinions produced by one unit of flow along e5e_{5}, in im⁡B\operatorname{im} B. Bottom left, the cut that separates the vertices 1 and 2 from the other vertices, in im⁡BT\operatorname{im} B^{T}, which is also the flow produced by the opinion vector equal to 1 on the vertices 1 and 2 and to 0 on the other vertices. Bottom right, a flow with zero divergence, that is, a cycle, in ker⁡B\ker B. In the two bottom panels, the flow on an edge is positive if it goes in the direction of the orientation of the edge in the left panel, and negative otherwise.

We can now put all these pieces together to see how any flow on a graph can be decomposed. Since im⁡BT\operatorname{im} B^{T} and ker⁡B\ker B are orthogonal complements in Rm\mathbb{R}^{m}, every flow is, in a unique way, the sum of a gradient and a cycle. This is the graph version of the Helmholtz decomposition of a vector field into a gradient and a divergence-free field [6]. Students of vector calculus often meet the Helmholtz decomposition without a proof, since it requires tools that are typically introduced later in the curriculum. Here, in contrast, we obtain it directly from a basic result in linear algebra, namely that every vector decomposes uniquely into components belonging to two orthogonal complementary subspaces.

Diffusion dynamics on a graph

Let us now go back to our model of opinions. In this section, we will assume that GG is connected. In Section 2, we saw that the rate of change of the opinions is minus the divergence of the flow, which we can now write as dx/dt=−div⁡f=Bfdx/dt = -\operatorname{div} f = Bf. If we substitute the definition of the flow, f=−∇x=−BTxf=-\nabla x=-B^{T}x, we obtain

dxdt=−BBTx.(2)\frac{dx}{dt}=-BB^{T}x. \tag*{(2)}

We call the n×nn \times n matrix L=BBTL=BB^{T} the Laplacian of the graph, so that (2) becomes the diffusion equation dx/dt=−Lxdx/dt=-Lx. We choose these names to mimic the continuum, where the operator div⁡∘∇\operatorname{div}\circ\nabla is the Laplace operator Δ\Delta and the equation ∂u/∂t=Δu\partial u/\partial t=\Delta u is the diffusion equation. LL is clearly symmetric, because LT=(BBT)T=BBT=LL^{T}=(BB^{T})^{T}=BB^{T}=L, and positive semidefinite, because xTLx=(BTx)T(BTx)=∥BTx∥2≥0x^{T}Lx=(B^{T}x)^{T}(B^{T}x)=\lVert B^{T}x\rVert^{2}\ge0 for every x∈Rnx\in\mathbb{R}^{n}. We call the quantity

E(x)=xTLx=∥BTx∥2=∑e(xh(e)−xt(e))2\mathcal{E}(x)=x^{T}Lx=\lVert B^{T}x\rVert^{2}=\sum_{e}(x_{h(e)}-x_{t(e)})^{2}

the energy of xx, by analogy with the elastic energy of a network of springs placed on the edges. In our model, E(x)\mathcal{E}(x) measures the total disagreement of the opinions xx. It vanishes if and only if BTx=0B^{T}x=0, that is, if and only if x∈ker⁡BTx\in\operatorname{ker}B^{T}. Since GG is connected, ker⁡BT\operatorname{ker}B^{T} is spanned by the vector 1∈Rn\mathbf{1}\in\mathbb{R}^{n} with all entries equal to one. This implies that Lx=0Lx=0 only for the multiples of 1\mathbf{1}, so 00 is an eigenvalue of LL and its only eigenvectors are the multiples of 1\mathbf{1}. Moreover, the total opinion ∑vxv=1Tx\sum_{v}x_{v}=\mathbf{1}^{T}x does not change in time, because dx/dt=Bfdx/dt=Bf belongs to the image of BB, whose vectors have zero sum.

The solution of the linear system of ODEs (2) is x(t)=e−tLx(0)x(t)=e^{-tL}x(0), with e−tL=∑k=0∞(−tL)k/k!e^{-tL}=\sum_{k=0}^{\infty}(-tL)^{k}/k!. To analyze this exponential, we will write LL in an orthonormal basis of eigenvectors φ1,…,φn\varphi_{1},\ldots,\varphi_{n}, with eigenvalues λ1≤⋯≤λn\lambda_{1}\le\cdots\le\lambda_{n}. Because LL is positive semidefinite, all these eigenvalues are nonnegative. We expand the vector of initial opinions in this basis, x(0)=∑kckφkx(0)=\sum_{k}c_{k}\varphi_{k}, with ck=⟨x(0),φk⟩c_{k}=\langle x(0),\varphi_{k}\rangle and ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle the usual inner product. Since e−tLφk=e−λktφke^{-tL}\varphi_{k}=e^{-\lambda_{k}t}\varphi_{k}, we obtain

x(t)=e−tLx(0)=∑k=1ncke−λktφk.x(t)=e^{-tL}x(0)=\sum_{k=1}^{n}c_{k}e^{-\lambda_{k}t}\varphi_{k}.

Each component with λk>0\lambda_{k}>0 decays exponentially at a rate equal to its eigenvalue. Since GG is connected, the only zero eigenvalue is λ1\lambda_{1}, with φ1=1/n\varphi_{1}=\mathbf{1}/\sqrt{n}. Hence, for large tt, x(t)x(t) converges to c1φ1c_{1}\varphi_{1}. In plain words, the opinion dynamics reach a steady state in which everybody agrees. This answers the question of § 2 about whether all the people reach an agreement. As for the opinion on which they agree, every opinion converges to c1/n=1n∑vxv(0)c_{1}/\sqrt{n}=\frac{1}{n}\sum_{v}x_{v}(0), the average of the initial opinions.

Before we continue, let us look at these results from the point of view of a course on partial differential equations. While solving the model, we have derived with very little effort the graph versions of four important properties: the gradient and minus the divergence are adjoints of one another, the Laplacian is a positive semidefinite operator, the total opinion is conserved and the opinions converge to their average. All these facts follow from the factorization L=BBTL=BB^{T} and from basic results of linear algebra. In contrast, the analog results in the continuum require tools and derivations that are far from elementary. For example, to prove that the gradient and minus the divergence are adjoint, that is, that ∫Ω∇u⋅F=−∫Ωudiv⁡F\int_{\Omega}\nabla u\cdot F=-\int_{\Omega}u\operatorname{div}F for a function uu and a vector field FF on a domain Ω⊂Rd\Omega\subset\mathbb{R}^{d}, we need to assume that Ω\Omega is bounded with a smooth boundary ∂Ω\partial\Omega, that uu and FF are smooth enough, and that uu vanishes on ∂Ω\partial\Omega. Similarly, proving that −Δ-\Delta, with zero boundary values, has a basis of eigenfunctions with positive eigenvalues requires tools from functional analysis, such as the characterization of compact self-adjoint operators [11]. We hope the reader is thus convinced that the difficulties in the continuum come from the technicalities of analysis, not from the diffusion process itself.

Zealots and the Dirichlet problem

Let us now change the model. Suppose that some people, the zealots, never change their opinion. A zealot still talks with his or her friends and influences them. However, nobody influences the opinion of a zealot. We write SS for the set of vertices of the zealots and II for the set of the other, influenceable, vertices. The opinion at each vertex s∈Ss \in S is a fixed number zsz_s, so the model becomes

dxvdt=−(Lx)vfor v∈I,xs=zsfor s∈S.\frac{dx_v}{dt}=-(Lx)_v \quad\text{for } v \in I,\qquad x_s=z_s \quad\text{for } s \in S.

We will focus on the stationary states of this model, which fulfill dxv/dt=0dx_v/dt=0 for every v∈Iv \in I, that is,

xs=zsfor s∈S,(Lx)v=0for v∈I.(3)x_s=z_s \quad\text{for } s \in S,\qquad(Lx)_v=0 \quad\text{for } v \in I. \tag*{(3)}

In the continuum, (3) is the Dirichlet problem, in which we look for a function uu with Δu=0\Delta u=0 in a domain Ω\Omega and given values on its boundary ∂Ω\partial\Omega. The zealots are the graph version of the boundary [5].

To interpret the condition (Lx)v=0(Lx)_v=0 in (3), let us see how the operator LL acts on the opinion vector xx. Using the definitions of discrete gradient and divergence, we obtain

(Lx)v=∑e:h(e)=v(xv−xt(e))−∑e:t(e)=v(xh(e)−xv)=∑w∼v(xv−xw).(Lx)_v=\sum_{e:h(e)=v}(x_v-x_{t(e)})-\sum_{e:t(e)=v}(x_{h(e)}-x_v)=\sum_{w\sim v}(x_v-x_w).

with w∼vw\sim v meaning that vv and ww are neighbors. Denoting by dvd_v the degree of vv and xˉv\bar{x}_v the average opinion of its neighbors, we can express (Lx)v(Lx)_v as

(Lx)v=dv(xv−xˉv).(4)(Lx)_v=d_v(x_v-\bar{x}_v). \tag*{(4)}

Hence, the condition (Lx)v=0(Lx)_v=0 states that the opinion at each vertex is the average of the opinions at the neighbors of vv. We say that xx is harmonic at vv if (Lx)v=0(Lx)_v=0.

Ordering the vertices so that those of II come first, we can write the linear system (3) in matrix form as

\begin{pmatrix} L_{II} & L_{IS} \\ 0 & \mathrm{Id} \end{pmatrix} \begin{pmatrix} x_I \\ x_S \end{pmatrix} = \begin{pmatrix} 0 \\ z \end{pmatrix}. \tag*{(5)}\end{pmatrix}

with LIIL_{II} and LISL_{IS} the submatrices of LL with rows in II and columns in II and in SS, respectively, xIx_I and xSx_S the vectors of the opinions in II and in SS, zz the vector of the opinions of the zealots, and Id\mathrm{Id} the identity matrix. The unknowns xIx_I satisfy the system LIIxI=−LISzL_{II}x_I=-L_{IS}z, in which the opinions of the zealots act as the inhomogeneous term. The structure of the solutions depends only on the invertibility of LIIL_{II}. Without zealots, LII=LL_{II}=L is singular and the system has infinitely many solutions, corresponding to the multiples of 11 discussed earlier in this section. With zealots, in contrast, LIIL_{II} is invertible and the system has exactly one solution. To prove this, let us show that the kernel of LIIL_{II} is trivial. Let y∈R∣I∣y \in\mathbb{R}^{|I|} satisfy LIIy=0L_{II}y=0, and let y~∈Rn\tilde{y}\in\mathbb{R}^n be equal to yy on II and to 00 on SS. Then E(y~)=y~TLy~=yTLIIy=0\mathcal{E}(\tilde{y})=\tilde{y}^{T}L\tilde{y}=y^{T}L_{II}y=0, so y~\tilde{y} is constant, and since y~\tilde{y} vanishes on the nonempty set SS, we obtain y~=0\tilde{y}=0 and therefore y=0y=0.2 Since LIIL_{II} is square, it is then invertible, and the system (5) has exactly one solution, xI=−LII−1LISzx_I=-L_{II}^{-1}L_{IS}z.

We have shown with relative ease that the Dirichlet problem on a graph has exactly one solution. In the continuum, uniqueness is still simple to prove, but existence is notoriously difficult. The reason is that, on a graph, we implicitly used uniqueness (the kernel of LIIL_{II} is trivial) to obtain existence (the system has a solution for any inhomogeneous term, i.e., LIIL_{II} is a surjective map). But in infinite dimension, a linear map with trivial kernel need not be surjective.3 A course on partial differential equations therefore must prove existence with other arguments. The standard method obtains the solution as the minimizer of the energy ∫Ω∣∇u∣2\int_{\Omega}|\nabla u|^2 in a Hilbert space of functions with finite energy, and then uses regularity theory to show that this minimizer is a smooth harmonic function [11].

We end this section with a historical note. The idea of minimizing the energy goes back to Riemann, who in 1851 used it to prove the existence of a solution of the Dirichlet problem. In the proof, he assumed that some function with the given boundary values attains the minimum energy. But in 1870, Weierstrass gave an example of an energy with an infimum that no function attains, showing that Riemann’s proof had a gap. This gap was closed by Hilbert in 1900 [12]. Hence the existence of a minimizer, which on a graph can be proven by a first-year undergraduate, occupied Riemann, Weierstrass and Hilbert for half a century. Perhaps Riemann should have started with a graph.

Topology on a graph

In Section 2, we saw how the four fundamental subspaces of the incidence matrix BB describe the connected components, the cycles and the cuts of a graph. Less obviously, we can also use incidence matrices to describe the holes of a graph. The study of holes, called homology, is a central topic of algebraic topology. In the continuum, homology requires difficult tools like chain complexes [13]. However, if we formulate the problem on a graph, we can once again derive the key results using only linear algebra. The price to pay is that we need a new type of incidence matrix.

Our new matrix can be derived from the third basic operator of vector calculus, the curl. In the continuum, the curl measures how much a field circulates around infinitesimal closed paths. On a graph we cannot build infinitesimal loops, so we use the closest proxies for them: triangles. The curl of a flow should therefore return its circulation around each triangle of the graph.4 To compute this circulation, we give each triangle an arbitrary orientation (clockwise or counterclockwise), as we did with the edges, and add the flows on its three edges, with a plus sign if the orientation of the edge agrees with that of the triangle and a minus sign otherwise. As with the gradient and the divergence, we can write this operator as a matrix, which we will denote by B2T∈Rk×mB_2^T\in\mathbb{R}^{k\times m}, where kk is the number of triangles in the graph. Each row of this matrix indicates the three edges of one triangle, with the entry 11 or −1-1 depending on whether the orientation of the edge agrees with that of the triangle, and 00 elsewhere. For example, the house graph has a single triangle, the roof, with the edges e4e_4, e5e_5 and e6e_6. If we orient it as 3→4→5→33\to4\to5\to3, then

B2T=(0001−11).B_2^T=(0\quad0\quad0\quad1\quad-1\quad1).

On the other hand, the transpose B2B_2 maps a vector w∈Rkw\in\mathbb{R}^k, with one circulation per triangle, to the flow B2wB_2w that these circulations produce on the edges. To distinguish B2B_2 from the incidence matrix BB of Section 2, from now on we will write B1B_1 for the latter.

What happens if we multiply B1B_1 and B2B_2? To answer this question, let us take a vector of circulations w∈Rkw \in\mathbb{R}^k and the flow f=B2wf = B_2w that it produces on the edges. B1fB_1f then captures minus the divergence, i.e. the net amount of the flow ff that accumulates at the vertex. But a flow that only circulates around triangles cannot accumulate at any vertex (all the flow that enters a vertex through one of its edges must leave it through the next edge of the triangle). Hence B1B2w=B1f=0B_1B_2w = B_1f = 0 for every w∈Rkw \in\mathbb{R}^k, so

B1B2=0.(6)B_1B_2 = 0. \tag*{(6)}

There is a profound interpretation of this identity. We can think of the two endpoints of an edge as its boundary. Similarly, the three edges of a triangle form its boundary. In these terms, the identity B1B2=0B_1B_2 = 0 says that the boundary of the boundary of a triangle is zero. This statement is the graph version of one of the central identities of advanced mathematics, “the boundary of a boundary is zero”, which is the starting point of homology.

The identity B1B2=0B_1B_2 = 0 also connects with seemingly unrelated identities from vector calculus. First, as we saw above, B1B2=0B_1B_2 = 0 means that a circulation cannot accumulate flow at the vertices. Hence it is the graph version of the identity div⁡∘curl⁡=0\operatorname{div} \circ\operatorname{curl} = 0. Second, if we take transposes, we obtain B2TB1T=0B_2^{T}B_1^{T} = 0. Since B1TB_1^{T} is the gradient and B2TB_2^{T} is the curl, this transposed identity is the graph version of curl⁡∘∇=0\operatorname{curl} \circ\nabla= 0. In terms of the fundamental subspaces, the two identities are the inclusions im⁡B2⊆ker⁡B1\operatorname{im} B_2 \subseteq\operatorname{ker} B_1 (every flow induced by circulations has zero divergence) and im⁡B1T⊆ker⁡B2T\operatorname{im} B_1^{T} \subseteq\operatorname{ker} B_2^{T} (every gradient flow has zero curl).

In vector calculus on R3\mathbb{R}^3, it is well known that the converse statements are also true: every field with zero curl is a gradient, and every field with zero divergence is the curl of another field. On a graph, however, the reverse inclusions can fail. For example, on the house graph, the cycle γ1\gamma_1 around the square has zero divergence but is not in im⁡B2\operatorname{im} B_2 (every flow of the form B2wB_2w is zero on the edges that do not belong to a triangle, while γ1\gamma_1 is nonzero on e1e_1, e2e_2 and e3e_3). This example shows that im⁡B2\operatorname{im} B_2 can be smaller than ker⁡B1\operatorname{ker} B_1, so there are nonzero cycles in ker⁡B1∩(im⁡B2)⊥\operatorname{ker} B_1 \cap(\operatorname{im} B_2)^\perp. Using the property (im⁡B2)⊥=ker⁡B2T(\operatorname{im} B_2)^\perp= \operatorname{ker} B_2^{T}, we can express this space as

H=ker⁡B1∩ker⁡B2T.(7)H = \operatorname{ker} B_1 \cap\operatorname{ker} B_2^{T}. \tag*{(7)}

(7) highlights that the flows in HH have simultaneously zero divergence and zero curl. We will call these flows harmonic. At first glance, the existence of these flows looks paradoxical. How can a flow neither accumulate at a vertex (zero divergence) nor go in circles (zero curl)? The way out of this paradox is that the curl B2TB_2^{T} only measures the circulation around triangles. A harmonic flow has zero circulation there, but it may circulate around longer cycles. What’s more, we can exploit these flows to extract structural information about the graph, like the location of its holes. For example, on the house graph, the harmonic flows (proportional to γ1+γ2/3\gamma_1 + \gamma_2/3) go around the square, the only hole, but split at the roof to force the circulation around the triangle to vanish.

A skeptical reader might doubt that this notion of hole captures the same idea as the empty center of a ring. However, mathematicians as early as Riemann have used the continuum analog of this definition to characterize holes [14]: a surface has a hole if we can find a closed curve on it that does not bound any part of the surface, that is, a closed curve that we cannot write as a sum of small loops within the region enclosed by the curve. To better understand why such a curve detects a hole, let us try to express the circulation along this curve, which we will call a global circulation, as a sum of local circulations, that is, circulations along small loops inside the region that it encloses. We will do this on two surfaces, a disk and a ring (Figure 4). For the disk (top left panel), any two neighboring local circulations go along their shared boundary in opposite directions and cancel out there. Thus, if we fill the whole disk with local circulations, they cancel everywhere except on the boundary of the disk. In other words, the global circulation along the boundary is the net effect of the local circulations in the interior.5 For the ring (top middle panel), we can apply the same argument, obtaining not one but two global circulations, one along the outer boundary and another along the inner one. For the outer global circulation, the local circulations that generate it are inside the region that it encloses, as for the disk. For the inner one, however, we run into the problem that the local circulations generating it are outside the region enclosed by it. We therefore cannot write this global circulation as a sum of local circulations in its interior. In fact, if we add local circulations on the surface of the ring, we can never obtain a global circulation along the inner boundary alone, it always comes together with one along the outer boundary circulating in the opposite direction.

Disk and ring circulations, continuous and discrete

Figure 4. Top, a disk (left) and a ring (middle) in the plane, with local counterclockwise circulations inside them, and the same ring with a flow that goes around the hole without local circulations (right). Bottom, triangulations of the disk and of the ring, with a counterclockwise circulation around each triangle (left and middle), and the harmonic flow of the triangulated ring (right), with thinner lines on the edges where its value is half. In the left and middle panels, the thick cycles are the global circulations that result from adding the local circulations.

If we triangulate the two surfaces (bottom row of Figure 4), the previous argument becomes the criterion behind Equation (7), with the cycles around the triangles in the role of the local circulations. In the triangulated disk, the cycle along the boundary is the sum of the cycles around all the triangles, so it is in im⁡B2\operatorname{im} B_2 and is not harmonic. In contrast, in the triangulated ring, we can find a harmonic flow, namely the one that goes counterclockwise along both the inner and the outer cycle, with the same value on all their edges, and it has half this value on the edges between them. By construction, this flow cannot be expressed as a sum of triangle circulations, since the circulation of this flow around every triangle is zero. In fact, looking at the bottom row of Figure 4, we can see a clear difference with the curl flow and the harmonic one: adding the circulations of all the triangles of the ring gives a flow that goes clockwise along the inner cycle (middle panel), while the harmonic flow goes counterclockwise along both cycles (right panel). Hence the holes that we found with B1B_1 and B2B_2 are analogous to the holes of the continuum.

So far, we have detected holes using im⁡B2⊆ker⁡B1\operatorname{im} B_2 \subseteq\ker B_1 and finding zero-divergence flows that cannot be expressed as combinations of cycles around triangles. But we could use im⁡B1T⊆ker⁡B2T\operatorname{im} B_1^{T} \subseteq\ker B_2^{T} and search for zero-curl flows that are not gradients. Since ker⁡B1=(im⁡B1T)⊥\ker B_1 = (\operatorname{im} B_1^{T})^\perp, the flows in ker⁡B2T\ker B_2^{T} but not in im⁡B1T\operatorname{im} B_1^{T} are again the harmonic flows (the flows in HH), so this second way of searching detects the same holes. Once again, this point of view has a counterpart in the continuum. For example, a classical way of showing that R2∖{0}\mathbb{R}^2 \setminus\{0\} has a hole is to study the field (−y,x)(x2+y2)\frac{(-y,x)}{(x^2+y^2)}. This field has zero curl, but its circulation along the unit circle is 2π2\pi, so it cannot be the gradient of any function. On a simply connected domain, the Poincaré lemma states that every field with zero curl is a gradient. Hence the existence of this field implies that its domain has a hole, which in this case is the origin. The search for holes with fields instead of curves is called cohomology. Detecting holes with curves and detecting them with fields are in fact equivalent approaches, but proving it is hard (this equivalence is known as de Rham’s theorem [15]). On a graph, however, the equivalence is an immediate consequence of the identity ker⁡B1∩(im⁡B2)⊥=H=ker⁡B2T∩(im⁡B1T)⊥\ker B_1 \cap(\operatorname{im} B_2)^\perp= H = \ker B_2^{T} \cap(\operatorname{im} B_1^{T})^\perp.

Let us now go back to Equation (7). In § 2.1, we commented that Rm=im⁡B1T⊕ker⁡B1\mathbb{R}^m = \operatorname{im} B_1^{T} \oplus\ker B_1. Moreover, we know that ker⁡B1=im⁡B2⊕H\ker B_1 = \operatorname{im} B_2 \oplus H. Hence

Rm=im⁡B1T⊕im⁡B2⊕H.(8)\mathbb{R}^m = \operatorname{im} B_1^{T} \oplus\operatorname{im} B_2 \oplus H. \tag*{(8)}

In words, every flow is, in a unique way, the sum of a gradient, a flow of circulations around triangles and a harmonic flow. Equation (8) is the complete version of the Helmholtz decomposition of § 2.1 [16, 6]. The harmonic part is nonzero only if the graph has holes, in the same way as the harmonic fields in the continuum.6

To summarize, with two incidence matrices, we have understood the identity “the boundary of a boundary is zero”, the holes of a space, the equivalence between homology and cohomology and the complete Helmholtz decomposition. In the curriculum, these results are spread over vector calculus in the first year and algebraic topology in the third year, if at all. They require chain complexes, singular homology and differential forms. On a graph, however, they are simple statements about the kernels and images of B1B_1 and B2B_2. We did not need group theory, quotients or analysis. Quite a payoff for a first course on linear algebra.

Other branches of mathematics

Analysis and topology are not the only subjects in which technical details obscure simple ideas. Many other courses of the curriculum start with a demanding definition and reach the central idea only after many technical steps. In this section, we will sketch, without complete proofs, three additional subjects in which graphs show the main ideas in a transparent way.

Geometry

On a curved surface, such as a sphere, we can still define a Laplace-like operator, called the Laplace–Beltrami operator. To define it, however, we need a Riemannian metric, which tells us how to measure lengths and angles at each point of the surface. The expression of the Laplace–Beltrami operator [17] is notoriously scary,

Δgu=1det⁡g∑i,j=12∂∂xi(det⁡g (g−1)ij∂u∂xj).\Delta_g u = \frac{1}{\sqrt{\det g}} \sum_{i,j=1}^{2} \frac{\partial}{\partial x_i} \left( \sqrt{\det g}\,(g^{-1})_{ij}\frac{\partial u}{\partial x_j} \right).

where x1,x2x_1,x_2 are local coordinates on the surface and gg is the 2×22 \times2 matrix of the metric in these coordinates. Despite the intimidating expression of Δg\Delta_g, the only new ingredient with respect to the usual Laplace operator is the metric. On a surface, we can always choose local coordinates in which gg is diagonal, with positive diagonal entries g1g_1 and g2g_2. In these coordinates, the formula becomes

Δgu=1g1g2[∂∂x1(g2g1∂u∂x1)+∂∂x2(g1g2∂u∂x2)].\Delta_g u = \frac{1}{\sqrt{g_1g_2}}\left[\frac{\partial}{\partial x_1}\left(\sqrt{\frac{g_2}{g_1}}\frac{\partial u}{\partial x_1}\right)+\frac{\partial}{\partial x_2}\left(\sqrt{\frac{g_1}{g_2}}\frac{\partial u}{\partial x_2}\right)\right].

Up to the factor 1/g1g21/\sqrt{g_1g_2}, the operator takes the derivative of uu in each direction, multiplies it by a positive weight and then takes the divergence. This is the structure of the weighted Laplacian of a graph. Let us put a positive weight wew_e on each edge ee, and let WW be the diagonal m×mm \times m matrix with the weights wew_e on its diagonal. The weighted Laplacian is then BWBTBWB^{\mathsf{T}}, with the same gradient BTB^{\mathsf{T}} as in Section 2. Hence the weights give a gentle way to study how geometry changes the properties of the Laplacian, without inverse matrices, determinants or tensors.

Probability and stochastic processes

A central object of study in probability is the Markov process, a stochastic process in which the transition probabilities depend only on the current state. In particular, Brownian motion is used to model systems like the motion of a particle in a fluid or the fluctuations of stock prices. However, many important questions about Brownian motion can only be answered by solving partial differential equations. For example, the expected time that a Brownian particle needs to leave a region is the solution of a Poisson equation with Dirichlet boundary conditions.

When the number of states of a Markov process is finite, we can model it as a directed graph, with one vertex for each state and one edge for each possible transition, weighted by its probability [18]. Many properties of the process can then be studied through the properties of this graph. For instance, the process can go from any state to any other state if and only if the graph is strongly connected. Another example is that a strongly connected process is periodic (it can return to its starting state only at multiples of some integer larger than one) if and only if the lengths of all the cycles of the graph have a common divisor larger than one.

Brownian motion, in particular, can be modeled as a random walk on a connected undirected graph in which each vertex vv moves to each of its neighbors with probability 1/dv1/d_v. Interestingly, many expected times of this random walk can be computed, once again, with the Laplacian. For example, the expected time that the walk needs to leave a set of vertices is the solution of a linear system with the same matrix LIIL_{II} as the problem with zealots of Section 3. Similarly, the expected time that the walk needs to go from a vertex ii to a vertex jj and back, called the commute time, is κ(i,j)=2m(Lii++Ljj+−2Lij+)\kappa(i,j)=2m\left(L_{ii}^{+}+L_{jj}^{+}-2L_{ij}^{+}\right), where Lij+L_{ij}^{+} are the entries of the pseudoinverse of LL [19]. Hence quantities that in the continuum require the solution of partial differential equations are, on a graph, simple expressions in terms of the Laplacian.

Optimization

Linear programming is one of the most useful tools of applied mathematics, with applications in logistics, economics, etc. A central result in the field is duality: every maximization problem has a dual minimization problem with the same optimal value. Students usually meet the dual problem as a formal recipe, which transposes the matrix of the problem and exchanges the roles of variables and constraints. The resulting problem seems to have no meaning of its own. Why should the maximum of one problem be equal to the minimum of a different one?

On a graph, both problems have a concrete meaning. Let us imagine that the edges are pipes, each with a capacity ce>0c_e > 0, and that we want to send as much water as possible from a vertex pp to a vertex qq. In the language of Section 2, we look for a flow ff with ∣fe∣≤ce\lvert f_e\rvert\le c_e on every edge and with zero divergence at every vertex other than pp and qq. The dual problem looks for the cheapest way to block the water, that is, for a cut that separates pp from qq with the smallest total capacity. Every unit of water must cross every cut, so no flow can exceed the capacity of any cut. Less obviously, the largest flow is equal to the smallest cut. This result, known as the max-flow min-cut theorem [20], is a case of linear programming duality. Moreover, the maximization problem involves the divergence BB, while the minimization problem involves the gradient BTB^T. Hence the transposition in the formal recipe of duality is simply a change of viewpoint from the divergence to the gradient.

Discussion

In this article, we have explored graphs as a setting in which to introduce key concepts of the undergraduate curriculum, such as the gradient, the divergence, the curl, the Laplacian, the diffusion equation, homology and the Helmholtz decomposition. Despite the diversity of these topics, most results were simple consequences of the properties of the kernels and images of incidence matrices. Hence, contrary to a common belief, understanding the central ideas of diffusion or homology, to name two examples, does not require an advanced knowledge of limits, function spaces or group theory. What students often perceive as difficult is not the central idea, but the analytic setting in which they first meet it. This does not mean that we should stop teaching the continuum. Instead, the continuum should come after the graph version, when the student already knows the central idea and can focus on the problems and subtleties of working over a continuum. In practice, a teacher needs only the linear algebra of a first course, so discrete spoilers can be introduced already in the second year of most curricula. A teacher can open each abstract topic with one or two lectures on its graph version, before introducing the continuous theory.

Several authors have already remarked that graphs can illustrate central results of their respective areas. For example, Doyle and Snell did so for random walks and potential theory [5], Lim for cohomology and Hodge theory [6], Knill for the theorems of Green–Stokes, Gauss–Bonnet and Poincaré–Hopf [7], and Grady and Polimeni for vector calculus and its applications to computational science [8]. Bamberg and Sternberg also introduced homology and cohomology to students of physics through electrical networks [21]. In contrast with these works, we propose graphs as a first setting for the curriculum as a whole. This proposal also challenges the widespread view that graphs should be taught primarily as models in applied mathematics. Graphs should also be leveraged in pure mathematics as a setting where a student can state a conjecture, test it on small examples and find the step where a proof fails.

A reader may object that we replace mathematics with a simplified imitation of it. Our answer is the maxim, usually attributed to Einstein, that everything should be made “as simple as possible, but not simpler”. The graph versions are more intuitive than the continuous counterpart, but they are complete, with hypotheses, theorems and proofs. Only the setting is simpler; the mathematical content is the same.

Discrete spoilers are not a universal remedy and have their limits. First, our arguments are mathematical and historical. We have not measured the effect of the approach on students, which would require an empirical study in real courses. Second, the approach works only for theories whose central idea is evident in finite dimension. For example, measure theory has a central difficulty, the existence of sets without measure, that is not present in discrete settings. Other areas, like set theory, have no graph version at all, because their central ideas already require an infinite setting.

Spoilers are dreaded because knowing the ending can be fatal to a mediocre story. In great stories, however, the question is never what happens, but how. Everyone knows that Achilles will die, that Troy will fall and that Odysseus will need twenty years to return home, and yet the Iliad and the Odyssey still move readers almost three thousand years later. Everybody who watches Tristan und Isolde knows that the lovers are doomed, but the four hours of musical longing make the final Liebestod a cathartic experience. Mathematics is one of these stories. Telling a student, before any limit or function space, that a harmonic function is the average of its neighbors, or that a hole is a cycle that bounds nothing, does not spoil analysis or topology. It motivates the student to read on. We hope that our discrete spoilers leave students eager to learn not only which results are true, but why.

Acknowledgments

The author thanks Karel Devriendt for insightful discussions. The author is also grateful to the podcast La vaca esférica, where he first heard the story of Euler’s formula as told by Lakatos, and with it the view of mathematics as a sequence of conjectures, refutations and better proofs. The author acknowledges funding from PID2022-141802NB-I00 (BASIC), funded by MCIN/AEI/10.13039/501100011033 and by “ERDF A way of making Europe”, and from Universidad Carlos III de Madrid through its Programa Propio de Investigación (Proyectos Jóvenes PPIT2025, project IDISC, 2025/00800/001).

References

  1. [1]Richeson DS. Euler’s Gem: The Polyhedron Formula and the Birth of Topology. Princeton (NJ): Princeton University Press; 2008.
  2. [2]Lhuilier S. Mémoire sur la polyédrométrie; contenant une démonstration directe du théorème d’Euler sur les polyèdres, et un examen des diverses exceptions auxquelles ce théorème est assujetti. Ann Math Pures Appl. 1812–1813; 3:169-89.
  3. [3]Lakatos I. Proofs and Refutations: The Logic of Mathematical Discovery. Worrall J, Zahar E, editors. Cambridge: Cambridge University Press; 1976.
  4. [4]Skemp R. Relational understanding and instrumental understanding. Mathematics Teaching. 1976; 77:20-6.
  5. [5]Doyle PG, Snell JL. Random Walks and Electric Networks. vol. 22 of Carus Mathematical Monographs. Washington (DC): Mathematical Association of America; 1984.
  6. [6]Lim LH. Hodge Laplacians on graphs. SIAM Rev. 2020; 62(3):685-715.arxiv.org/abs/1507.05379
  7. [7]Knill O. The theorems of Green–Stokes, Gauss–Bonnet and Poincaré–Hopf in graph theory; 2012. arXiv:1201.6049 [math.DG].arxiv.org/abs/1201.6049
  8. [8]Grady LJ, Polimeni JR. Discrete Calculus: Applied Analysis on Graphs for Computational Science. London: Springer; 2010.
  9. [9]Biggs N. Algebraic Graph Theory. 2nd ed. Cambridge Mathematical Library. Cambridge: Cambridge University Press; 1993.
  10. [10]Strang G. The fundamental theorem of linear algebra. Amer Math Monthly. 1993; 100(9):848-55.DOI
  11. [11]Evans LC. Partial Differential Equations. vol. 19 of Graduate Studies in Mathematics. 2nd ed. Providence (RI): American Mathematical Society; 2010.
  12. [12]Monna AF. Dirichlet’s Principle: A Mathematical Comedy of Errors and its Influence on the Development of Analysis. Utrecht: Oosthoek, Scheltema & Holkema; 1975.
  13. [13]Hatcher A. Algebraic Topology. Cambridge: Cambridge University Press; 2002.
  14. [14]Riemann B. Theorie der Abel’schen Functionen. J Reine Angew Math. 1857; 54:101-55.
  15. [15]de Rham G. Sur l’analyse situs des variétés à n dimensions. J Math Pures Appl. 1931; 10:115-200.
  16. [16]Eckmann B. Harmonische Funktionen und Randwertaufgaben in einem Komplex. Comment Math Helv. 1944–1945; 17:240-55.
  17. [17]Rosenberg S. The Laplacian on a Riemannian Manifold: An Introduction to Analysis on Manifolds. vol. 31 of London Mathematical Society Student Texts. Cambridge: Cambridge University Press; 1997.
  18. [18]Levin DA, Peres Y. Markov Chains and Mixing Times. 2nd ed. Providence (RI): American Mathematical Society; 2017. With contributions by Elizabeth L. Wilmer.
  19. [19]Chandra AK, Raghavan P, Ruzzo WL, Smolensky R, Tiwari P. The electrical resistance of a graph captures its commute and cover times. Comput Complexity. 1996; 6:312-40.
  20. [20]Ford LR, Fulkerson DR. Maximal flow through a network. Canad J Math. 1956; 8:399-404.
  21. [21]Bamberg P, Sternberg S. A Course in Mathematics for Students of Physics. vol. 2. Cambridge: Cambridge University Press; 1990.

Paper details

vlnc:W_u2fd8dwq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents