“When we try to pick out anything by itself, we find it hitched to everything else in the Universe.” - John Muir

Provide Context

Todo:

1. Start with the graph

three links per router, two links between groups

Eight routers, twelve links

Our example has eight routers and twelve links. Every router has three links, yet only two links connect the two halves of the network. We want to understand that weakness and learn how to find similar ones in larger networks.

We draw the network as a graph: a circle, called a node, represents a router, and a line, called an edge, represents a link. Two nodes joined by an edge are neighbours.^[1] The nodes are numbered 1 to 8.

A node’s number identifies it. Its position on the page only helps us see the wiring. We could slide the circles around or bend the lines without changing a single connection.

The number of neighbours a node has is its degree. Node 3 has neighbours 1, 2 and 5, so its degree is three. Every other node also has degree three. When all nodes have the same degree, the graph is called regular; ours is 3-regular.

Only two links connect the halves

Look at nodes 1–4 as one group and nodes 5–8 as another. Only edges 3–5 and 4–6 connect the groups. All traffic between the halves must cross one of those two links.

Knowing that each router has three links does not tell us how well a whole group is connected to the rest. In a larger network, a weak division like this may be hard to spot in a drawing. We need a way to study it through calculations.

Label the two groups

Give nodes 1–4 the value +1 and nodes 5–8 the value −1. These are labels we choose to mark the groups. The wiring stays the same.

The labels let us recognize a crossing link by subtracting the values at its ends:

• Same group: the values match, so their difference is zero.
• Different groups: the difference is 2 or −2, depending on which value we subtract from which.

We can now identify links between the groups using arithmetic.

The values assigned to all the nodes form a pattern. List them in node-number order and we have a vector, x. Its third entry, x₃, is the value assigned to node 3: here, +1. The node number tells us which entry to read.

All our links work in both directions and count equally. No node links to itself, and no pair has more than one link. Next we will put the wiring into matrices that compare the assigned values at connected nodes.

2. Turn the wiring into A, D and L

one comparison, written for every node

Start with one node’s comparison

Node 3 holds +1. Its neighbours 1 and 2 also hold +1, while its neighbour 5 holds −1. Subtract each neighbour’s value from node 3’s value, then add the three differences:

The two neighbours in the same group contribute zero. The neighbour in the other group contributes 2.

To see how a matrix can do this, regroup the same calculation. Collect the three copies of node 3’s value, then subtract the neighbours’ values together:

There are two parts: the node’s own value counted once per neighbour, and the sum of its neighbours’ values. We will build a matrix for each part so we can do the calculation at every node.

A: add the neighbours’ values

Start by recording the wiring. Give every node a row and a column, in node-number order. Eight nodes give us an 8 × 8 table. Put a 1 where the row’s node and the column’s node share an edge, and a 0 everywhere else. This is the adjacency matrix, A. “Adjacent” means joined by an edge.

Multiplying A by x gives a new vector, Ax, with one result per node. The notation (Ax)₃ means its third entry: the result for node 3.

Row 3 has 1s in columns 1, 2 and 5, so it adds the values at those three neighbours. The zeros leave the other values out:

So node 3’s result in Ax is 1: the sum of its neighbours’ values.

Every link works in both directions. Edge 3–5 therefore puts a 1 in row 3, column 5, and another in row 5, column 3. These matching entries make A symmetric across its main diagonal.

D: count the node’s own value once per neighbour

Now we need the other part: three copies of node 3’s own value. Its degree tells us how many copies to count.

Put each node’s degree on the main diagonal of a matrix called D, the degree matrix, and put zeros elsewhere. Each row multiplies that node’s value by its degree. For node 3:

Every node in our graph has degree three, so D multiplies every entry of x by three. We can write D = 3I, where I is the identity matrix, which returns its input unchanged.

L = D − A: combine the two parts

Dx counts each node’s own value once per neighbour. Ax adds its neighbours’ values. Subtracting the two outputs performs our original comparison at every node:

The matrix L = D − A is called the graph’s Laplacian.^[2] Its diagonal entries are the degrees. Each neighbour’s column gets −1, and every other entry is zero.

For any node i, row i adds the differences between that node’s value and each neighbour’s value. The summation sign below means “add one term for each neighbour j”:

A, D and L depend only on the wiring. We can assign new values to the nodes by changing x, and the same matrices will compare those values. Each output entry still belongs to the same node.

The differences have signs, so they can cancel. Suppose we give node 3 the value 1 and its neighbours the values 0, 1 and 2. Its result is (1 − 0) + (1 − 1) + (1 − 2) = 0. Here, zero means the node’s value equals its neighbours’ average; the individual neighbours have different values.

We now have a matrix that compares values at connected nodes. Before combining those comparisons into one measurement, we need to decide how to judge whether a division of the network is weak.

3. Measure how weakly a group connects

crossing links relative to group size

Our graph is connected: you can follow edges from any node to any other. Yet removing just two links separates it into two groups of four nodes. We want to measure how weakly a group connects to the rest of the network.

Count crossing links relative to group size

Two links connecting a group of four nodes to the rest give us 2 ÷ 4 = 0.5 crossing links per node. The same two links would mean much less connectivity per node for a group of two hundred.

We call a division into two nonempty groups a cut. To compare cuts, divide the number of crossing links by the number of nodes on the smaller side:

A lower score means fewer links connect the smaller group to the rest, relative to its size. The crossing edges are also called the group’s boundary.

Why use the smaller side?

Separate node 1 from the other seven nodes. Three links cross that division, so its score is 3 ÷ 1 = 3.

If we divided by the seven nodes on the other side, we would get 3 ÷ 7 ≈ 0.43. The same division would appear much weaker just because we chose the larger group as the denominator. Always using the smaller side gives one answer for the cut, whichever side we name first.

Find the weakest division

Our four-against-four cut scores 0.5, the lowest of the three examples above. Another division might score even lower.

The lowest score across all cuts is the graph’s edge expansion, written h(G), where G names the graph. A small h(G) means that some group has few links to the rest for its size. Finding a cut with score 0.5 gives us a candidate for that minimum.

Scoring one group is easy. Searching for the lowest score is harder because there are so many groups to try. Checking all nonempty groups of up to half the nodes means 162 candidates for eight nodes, but more than 600 billion for forty.^[3]

Our +1 and −1 labels already mark a proposed division. Next we will use those values to measure its crossing links. This will connect the cut calculation to the Laplacian and give us a way to search for useful divisions through node values.

4. Use node values to test a division

from crossing links to squared differences

Chapter 3 judged a division by its crossing links relative to group size. Our labels from Chapter 1 already tell us which links cross: +1 marks nodes 1–4, and −1 marks nodes 5–8. A crossing link joins opposite signs.

From crossing links to squared differences

For each edge, subtract the value at one end from the value at the other, then square the difference:

• Equal values: the difference is zero, so the contribution is zero.
• Values +1 and −1: the difference is 2 or −2, depending on the reading direction. Either way, its square is 4.

Squaring makes each contribution nonnegative and independent of which way we read the edge. Positive and negative differences cannot cancel.

Add the contributions, counting each edge once. We call this total the pattern’s energy, written E(x). It measures how different the values are across the graph’s edges.^[4]

With our +1 and −1 labels, energy is four times the number of crossing links. Every crossing link contributes 4; every other link contributes zero.

Compare two divisions

In our two-halves pattern, only edges 3–5 and 4–6 join opposite signs. The energy is 2 × 4 = 8.

Now alternate the signs in node-number order: +1, −1, +1, −1, and so on. We still have four nodes of each sign, but six edges cross between the groups. The energy is 6 × 4 = 24.

Here is how energy connects to Chapter 3’s cut score:

Both divisions have four nodes on each side, so fewer crossing links means both a lower cut score and lower energy. For divisions with different group sizes, we must also account for size; energy alone does not do that.

Squared differences also work when node values are not limited to +1 and −1. They make large gaps especially costly: a gap of 3 contributes 9, while three gaps of 1 contribute only 3 in total. Later we will use this calculation to look for patterns that change more gently across the links.

Optional: three pictures explaining the squared differences

The Laplacian computes the same energy

Chapter 2 gave us Lx: one result per node, found by adding its differences from its neighbours. Simply adding all the Lx entries gives zero. Each edge appears at both ends with opposite differences, so those contributions cancel.

Instead, multiply each node’s value by its own Lx result, then add. Multiplying matching entries and adding is a dot product. Here it is x · (Lx), also written xᵀLx. This is the input–output dot product from the linear algebra primer, with L as the matrix.

To see why this recovers the energy, follow just edge 3–5. It joins +1 to −1, so its squared gap is 4. In the dot product, this edge contributes at both ends:

• At node 3: its value +1 multiplies the difference +2, giving (+1) × (+2) = 2.
• At node 5: its value −1 multiplies the difference −2, giving (−1) × (−2) = 2.

Together, these give 2 + 2 = 4, exactly one squared gap for this edge. Edge 4–6 contributes another 4. Every other edge joins equal values and contributes zero.

The full calculation, using one product per node, is:

The four nonzero products add to 8, the same energy we found from the edges. This equality works for any node values:

The summation means to add one squared difference per edge. We can calculate energy directly from those gaps or through the Laplacian; both methods give the same nonnegative total.^[5]

Optional: the same edge calculation with any two values

For an edge joining nodes i and j, use their values xᵢ and xⱼ in place of +1 and −1. Its two contributions to the dot product are:

xᵢ(xᵢ − xⱼ) + xⱼ(xⱼ − xᵢ) = (xᵢ − xⱼ)²

The two endpoint contributions add to exactly one squared gap. Summing over all edges gives xᵀLx = E(x).

Next, let the values change

The labels +1 and −1 force each node into one of two groups. Allowing values between them, such as 0.3 or −0.6, lets us adjust a pattern gradually. We will look for a pattern with low energy, then use its values to suggest a division of the graph.

But shrinking every value also lowers the energy, even when the arrangement stays the same. Before searching, we need a way to compare patterns fairly. Chapter 5 sets that up.

5. Make the comparison fair

a better arrangement, or just smaller numbers?

Chapter 4 gave us energy: the total squared disagreement across the edges. We want to find node values that keep this total small. But first we need to distinguish a better arrangement from simply using smaller numbers.

Low energy alone is not enough

Give every node zero and the energy is zero. That works on any graph, so it tells us nothing about where the network might divide into groups.

Requiring different values does not solve the problem either. Our four +1 values and four −1 values give energy 8. Halve every value and the energy falls to 2: the gaps halve, so their squares become one quarter as large. We could keep shrinking the numbers without changing their arrangement.

We need to hold the overall spread fixed, then look for the arrangement with the least disagreement across edges.

Measure spread separately from energy

We will measure squared spread by subtracting the average from each node value, squaring each result, and adding them. This primer also calls that quantity variation. It measures how far the values lie from their average, regardless of which nodes are connected.

Energy uses the wiring: it adds the squared differences between values at the ends of each edge.

Rearranging the same values leaves their squared spread unchanged, but can change their energy. Chapter 4’s two patterns show the difference:

To compare any patterns fairly, we will prepare each one in two steps. Subtracting the average removes a level shared by all nodes. Rescaling fixes the squared spread, so shrinking cannot count as an improvement.

First, subtract the average

Suppose we add 10 to every value. The levels +1 and −1 become 11 and 9. Their gap is still 2, so the energy is unchanged. Their distances from the new average, 10, are also unchanged.

Subtract the average, 10, and we get +1 and −1 again. This is called centering. It gives every pattern mean zero while preserving every edge difference and the squared spread.^[6]

Mean zero means the values add up to zero. The numbers of positive and negative values need not be equal.

Then, make the squared spread equal to 1

After centering, the average is zero. Subtracting it leaves each value unchanged, so the squared spread is just the sum of the squared values.

Our eight values each have square 1, so their squares add to 8. Divide every value by √8. Each square becomes 1/8, and the eight squares now add to 8 × (1/8) = 1. The node values become approximately +0.354 and −0.354.

Every edge gap is divided by √8 too, so every squared gap is divided by 8. The grouped pattern’s energy changes from 8 to 1; the alternating pattern’s changes from 24 to 3. Both are now compared at squared spread 1.

We choose 1 for convenience; any fixed positive amount would work.^[7] It is the sum of the squares that equals 1. Each node can still have its own value.

The search now has two simple rules

An all-equal pattern becomes all zeros when centered. Its squared spread is zero, so it cannot satisfy the second rule. Any pattern with some differences can be centered and rescaled to satisfy both.

We can now search for the lowest energy while holding the squared spread fixed. A lower energy must come from how the differences are arranged across the graph.

Optional: see shifting and shrinking side by side

Optional: the formulas and a shortcut

Let x̄ be the average of the node values, and V their squared spread:

V = ∑ᵢ (xᵢ − x̄)²

Subtracting the mean preserves V and every edge difference. If V > 0, dividing the centered values by √V makes their squared spread 1 and divides their energy by V.

So energy divided by squared spread gives the energy a pattern would have after centering and rescaling. The hard split gives 8/8 = 1. Halving its values gives 2/2 = 1. Shifting them from ±1 to 9 and 11 gives 8/8 = 1, because their squared distances from the average are still the same.

When x already has mean zero, its squared spread is xᵀx. We can then write the comparison as:

R(x) = xᵀLxxᵀxhere, x contains the centered values and is nonzero

This expression is the Rayleigh quotient. It is defined for any nonzero vector, but our comparison uses centered values. For the shifted pattern, the raw sum of squares is 808, while the squared spread around its average is 8. We must subtract the average before using xᵀx as our denominator.

Optional: can an allowed pattern ever have zero energy?

On our connected graph, zero energy requires every pair of neighbours to agree. That agreement travels through the whole graph, forcing a flat pattern. Our two rules exclude it.

If the graph has disconnected pieces, each piece can hold its own constant value. The pieces can have different levels without any edge disagreement. We can then have mean zero, squared spread 1, and zero energy. This will help explain the meaning of a zero second eigenvalue in Chapter 7.

Our starting candidate is the hard split: four values of about +0.354 and four of about −0.354, with energy 1. Chapter 6 will change those values while keeping the mean zero and squared spread 1.

6. Improve the first pattern

can a gentler boundary lower the total?

Our first pattern has energy 1. We will try to lower it by bringing the values closer together where the two groups meet. The wiring stays fixed. Every pattern we compare will have mean zero and squared spread 1.

Start by finding where the disagreement is

In the hard split, nodes 1–4 all have value about +0.354, and nodes 5–8 all have value about −0.354.

All ten edges within the groups join equal values, so they contribute no energy. The two edges between the groups carry all the disagreement. Each contributes 0.5, giving total energy 1.

We will start by reducing those two gaps.

Bring the boundary values closer to zero

The crossing edges join nodes 3 to 5 and nodes 4 to 6. Call these four nodes the boundary nodes. The other four—1, 2, 7 and 8—are the interior nodes.

Move the positive boundary values down toward zero and the negative boundary values up toward zero. The ends of each crossing edge become closer in value, so those edges contribute less energy.

But now the boundary nodes differ from the interior nodes in their own group. Eight internal edges that previously contributed zero begin to contribute energy.

This is the trade-off: we reduce disagreement between the groups by creating some disagreement inside them. Because energy squares the gaps, reducing a large gap can outweigh the cost of introducing several smaller ones. We have to add the contributions to find out.

Keep the comparison fair while the values change

Moving only the boundary values toward zero would also reduce the squared spread. To keep it at 1, we must rescale all eight values.

For a first trial, make each boundary value half as large as the interior value in its group. Before rescaling, we can write this as (1, 1, ½, ½, −½, −½, −1, −1). The mean is zero, and the squares add to 4 × 1 + 4 × ¼ = 5.

Divide every value by √5 to make the squares add to 1. Here are the resulting values compared with our starting pattern:

The values shown are rounded. Positive values stay in the first group and negative values stay in the second. The boundary values move toward zero, while the interior values move farther from zero to keep the squared spread at 1. We are changing how the spread is distributed across the graph.

Use t to choose the relative size

The slider calls this boundary-to-interior ratio t:

• t = 1: boundary and interior values have equal size. This is the hard split.
• t = ½: each boundary value is half its group’s interior value.
• t = 0: every boundary value is zero.

At t = ½, the rescaled boundary values are about ±0.224, not ±½. t describes a ratio, not a node’s value. Each slider setting rescales all eight values together, preserving that ratio and keeping the squared spread at 1. The matched positive and negative values keep the mean at zero.

Try the experiment

Start at the hard split, then try t = ½ and t = 0. Watch the total energy. Orange edges show disagreement between the groups; teal edges show disagreement inside them. The displayed values have already been rescaled.

t sets the boundary values relative to the interior values. At t = ½, they are half as large. All eight values are rescaled together to keep mean 0 and squared spread 1. The wiring stays fixed.

Boundary value as a fraction of the interior value, t

1.000

Hard split, t = 1Try t = ½Try t = 0Best in this family

Energy1.000

Mean0.000

Squared spread1.000

Why moving partway helps

At t = ½, the energy on the crossing edges falls from 1 to 0.4. We have saved 0.6. The new disagreement inside the groups costs 0.4, so the total is 0.8.

The saving is larger than the new cost. Because the squared spread is still 1, the lower energy comes from redistributing the values across the graph.

Why moving all the way to zero is worse

At t = 0, the two crossing edges join zeros, so their energy is zero. But the total energy has risen to 2.

To keep the squared spread at 1, the four interior values are now +0.5, +0.5, −0.5 and −0.5. Eight edges join one of these values to a boundary value of zero. Each has a squared gap of 0.25, and eight contributions of 0.25 add up to 2.

Eliminating all disagreement between the groups creates too much disagreement inside them. Every edge contributes to the same total.

Find the best balance

Moving partway helped; moving all the way to zero went too far. Now try “Best in this family.” The lowest total in this experiment occurs at t ≈ 0.618: boundary values about 62% as large as interior values. The energy is approximately 0.764.

The columns below separate the two sources of energy:

What improved, and what stayed the same?

The pattern’s energy fell from 1 to about 0.764. Its positive nodes are still 1–4 and its negative nodes are still 5–8. Dividing by sign therefore gives the same cut: two crossing links for four nodes, with cut score 0.5.

We have found a smoother pattern on the same graph. Once the node values can differ within each group, energy accounts for those differences too; it no longer just counts crossing links. Later we will use the pattern’s values to suggest cuts.

The slider also explored only one family. It kept certain pairs of nodes equal and made the two halves mirror each other. Other patterns could give all eight nodes different values.

Could a pattern outside this family have energy below 0.764? The experiment alone cannot answer that. Chapter 7 will show why no allowed pattern can do better.

Optional: see the rescaling at t = ½

Optional: compare the four settings visually

Optional: the formula behind the experiment

Before rescaling, write the pattern as (1, 1, t, t, −t, −t, −1, −1). Its squared spread is 4 + 4t².

Eight internal edges have gap 1 − t, so their combined energy is 8(1 − t)². Two crossing edges have gap 2t, giving combined energy 8t². The other two edges, 1–2 and 7–8, join equal values and contribute zero.

Divide the energy by the squared spread to get the energy after rescaling:

E(t) = 8(1 − t)² + 8t²4 + 4t²

The numerator adds the two sources of disagreement. The denominator keeps the comparison at squared spread 1. The minimum over the slider’s settings occurs at t = (√5 − 1)/2 ≈ 0.618, with energy 3 − √5 ≈ 0.764.

7. Can any pattern do better?

why the second eigenvector wins

The slider found energy about 0.764 while keeping pairs of nodes equal and the two halves as mirror images. Could a pattern outside that family do better? We need an argument that covers every possible assignment of node values.

The key is to describe every pattern using the Laplacian’s eigenvectors. We will see why every allowed pattern’s energy is an average of their energies, and why that average cannot fall below about 0.764.

First, remember what we are comparing

A pattern assigns one value to each node. Its energy adds the squared differences across the edges.^[8] We compare patterns that follow Chapter 5’s two rules:

• Mean zero: remove the level shared by all nodes.
• Squared values adding to 1: fix the squared spread, so shrinking cannot count as an improvement.

The hard split has energy 1. The slider reached about 0.764. We want the minimum among all patterns obeying these rules.

Eigenvectors give us eight building blocks

In the linear algebra primer, our vectors had two entries. Here a vector has eight entries, one value per node. The eigenvector idea is the same: apply L, and every entry is multiplied by the same number. The pattern is an eigenvector; that multiplier is its eigenvalue.^[9]

Our edges are undirected, so L is symmetric. The spectral theorem from linear algebra tells us that we can choose eight mutually perpendicular eigenvectors and use them to describe every pattern.^[10] Each eigenvector is a whole eight-node pattern. Multiplying these patterns by coefficients and adding their matching entries lets us build any assignment of values.

We scale each eigenvector to unit length, meaning its squared entries add to 1. We name them u₁, u₂, …, u₈, ordered by their eigenvalues λ₁, λ₂, …, λ₈ from smallest to largest. The subscript identifies a pattern in this list, not a node.

For example, u₂ is the pattern we found with the slider. Applying L multiplies all its values by λ₂ ≈ 0.764:

Why a unit eigenvector’s energy equals its eigenvalue

Chapter 4 wrote energy as the dot product of a pattern and its output. For an eigenvector u, that output is λu. Its energy is therefore λ times the sum of its squared entries. We chose that sum to be 1:

u₂ is a pattern with eight entries. λ₂ is one number: its multiplier under L and, at unit length, its energy. Here are all eight eigenvalues for our graph:

These numbers come from L, which records the graph’s wiring. Different eigenvectors can have the same eigenvalue, as the four entries with energy 4 show.^[11]

Why the zero-energy pattern is set aside

The first eigenvector, u₁, is flat: every node holds the same value. Every edge joins equal values, giving energy zero.

Center it and every value becomes zero. Its squared spread is then zero, so it cannot satisfy our two rules.

The other seven eigenvectors are perpendicular to u₁. Since u₁ has the same entry everywhere, a dot product with u₁ is just a constant times the sum of the other pattern’s entries. Perpendicularity makes that dot product zero, so each of the other eigenvectors has entries that add to zero.

Adding any amount of u₁ would add a shared level. The mean-zero rule requires its coefficient to be zero, leaving u₂ through u₈ as the building blocks for allowed patterns. The lowest energy among them is about 0.764.

What happens when we mix the remaining patterns?

We still need to check whether combining these patterns could lower the energy further. Take this example:

The numbers 0.6 and 0.8 are coefficients. Each multiplies a whole eight-node pattern. Since these unit eigenvectors are perpendicular, their contributions to squared spread add:

The shares add to 1, so the mixture has squared spread 1. It also has mean zero because both building blocks do.

L only rescales each eigenvector, so the pieces remain perpendicular after applying L. Their contributions to the energy dot product add too: each squared coefficient multiplies that eigenvector’s energy.

The coefficients are 0.6 and 0.8; the energy weights are their squares, 0.36 and 0.64. These percentages describe shares of squared spread. Each building block still assigns a value to every node.

This is a weighted average: 36% at energy about 0.764 and 64% at energy 2. Mixing in the higher-energy pattern has raised the total above 0.764.

The same rule applies to any allowed mixture of u₂ through u₈. Its coefficients can be positive or negative, but their squares are nonnegative and add to 1. The energy is the weighted average of the corresponding eigenvalues.

An average cannot be smaller than the smallest number being averaged. Here that smallest energy is about 0.764. This reasoning covers every allowed pattern, because every one is a mixture of these building blocks.

There are two parts to the conclusion. No allowed pattern can go lower than the energy of u₂. And u₂ itself is allowed and reaches that energy. Together, these facts establish the minimum.

The minimum is λ₂

The smallest eigenvalue left after removing the flat pattern is λ₂. It gives the minimum energy under our two rules:

What does u₂ look like? It is the slider’s winning pattern from Chapter 6, at t ≈ 0.618.^[12] Its values, rounded to three decimal places, are:

The boundary values sit closer to zero than the interior values. That is the compromise we saw in Chapter 6: it reduces disagreement between the groups while allowing some disagreement inside them.

An eigenvector for λ₂ is called a Fiedler vector, and λ₂ is called the graph’s algebraic connectivity.^[13] Reversing every sign gives an equally good pattern, since squared differences do not change.

The slider found the best pattern because this particular family included u₂. A different restricted family might miss it. The eigenvector argument is what lets us rule out a better answer anywhere else.

Optional: the weighted-average formula for all seven patterns

Write an allowed pattern as a mixture of the seven available building blocks:

x = c₂u₂ + ⋯ + c₈u₈

The coefficients c₂ through c₈ multiply whole patterns. Perpendicularity makes their squared-length contributions add. Every pattern here has mean zero, so squared length is also squared spread. Our fixed-spread rule says:

c₂² + ⋯ + c₈² = 1

Chapter 4 wrote energy as x · Lx. L multiplies each eigenvector uᵢ by its own eigenvalue λᵢ. When we expand the dot product, terms involving two different eigenvectors vanish because those vectors are perpendicular. What remains is:

E(x) = λ₂c₂² + ⋯ + λ₈c₈²

The weights cᵢ² are nonnegative and add to 1. Every λᵢ here is at least λ₂, giving E(x) ≥ λ₂. Choosing x = u₂ gives equality.

Optional: what if the graph has more nodes, or is disconnected?

The same reasoning works for an undirected graph of any size. With 100,000 nodes, there are 100,000 building blocks. Removing the shared level leaves 99,999. The weighted-average argument still gives the minimum immediately once the eigenvalues are ordered; it does not require trying every possible pattern.

On a connected graph, zero energy forces every pair of neighbours to agree. That agreement travels through the graph until all nodes have the same value. So the flat direction is the only zero-energy direction, and λ₂ is positive.

If the graph has two disconnected pieces, each piece can hold its own constant value. One can sit above zero and the other below, chosen so the overall mean is zero. No edge connects the pieces, so no edge sees a difference. After rescaling, this is an allowed pattern with energy zero. A second zero eigenvalue appears, and λ₂ becomes zero.^[14]

We now have the node values that minimize energy. Chapter 8 asks how to use those values to propose a division into two groups. Finding the best real-valued pattern and finding the best cut are separate steps.

8. Turn the answer back into a cut

use the values to propose two groups

The minimum-energy pattern is a list of numbers. To make a cut, we still have to decide which nodes belong on each side. We will use the numbers to propose cuts, then count the original graph’s crossing edges to judge them.

Put the nodes in order by their values

An edge with a large gap between its endpoint values contributes a lot of energy. The Fiedler pattern minimizes total energy, so it tends to keep connected nodes close in value. Sorting the nodes by these values gives us a useful place to look for a division.

Sort the nodes from the most negative value to the most positive:

The values are rounded here. In this graph, the two nodes in each pair have exactly equal values.

Choose a number between two different node values. This number is the threshold: put every node whose value is below it into one group, and the remaining nodes into the other. Moving the threshold changes group membership while the wiring and node values stay fixed.

Zero is one possible threshold. The best cut may come from another gap, so we will try each gap and compare the cut scores.

Try one threshold completely

Choose −0.34, which lies between −0.425 and −0.263. Nodes 7 and 8 have value −0.425, below the threshold. Every other node has a higher value. The chosen group is therefore {7, 8}, with nodes 1–6 on the other side.

Look back at the original graph. Four edges leave {7, 8}: 5–7, 5–8, 6–7 and 6–8. The smaller group has two nodes, so the cut score is:

That is one complete candidate: the threshold proposes the groups, and the original edges determine the score.

Move it once and see what changes

Move the threshold to 0, between −0.263 and +0.263. Nodes 5 and 6 now fall below it and join the chosen group: {5, 6, 7, 8}.

The four edges we just counted no longer cross the cut. Both ends of each now lie inside the chosen group. Only edges 3–5 and 4–6 leave it.

We now have two crossing edges and four nodes on each side. The score is 2/4 = 0.5, an improvement over 2.

Adding nodes has reduced the number of crossing edges. We find the score by checking the wiring for each proposed group.

Check the remaining gap

Choose +0.34, between +0.263 and +0.425. Nodes 3 and 4 join the chosen group, giving {3, 4, 5, 6, 7, 8}, with {1, 2} on the other side.

Four edges cross this division. Although the chosen group has six nodes, the smaller group has two. The score is therefore 4/2 = 2.

Try the three positions below. Follow which nodes change sides and which original edges become crossing edges.

Choose one of the three gaps. Nodes below the threshold form the blue group; orange edges cross to the other group. The wiring and node values stay fixed. The threshold readout is rounded.

Threshold value

≈ −0.34

After the first pairAfter the second pairAfter the third pair

Crossing edges4

Smaller side2

Cut score2.000

Selected nodes: 7, 8.

Why are there only three candidates?

There are four distinct values, leaving three gaps between them. Any threshold within the same gap selects the same nodes. For example, −0.34 and −0.35 both select {7, 8}.

A threshold also cannot separate two nodes with exactly equal values. They stay together. Moving beyond all the values would put every node on one side, which is not a valid cut.

Trying the gaps in order and comparing their scores is called a sweep. With n nodes, there are at most n − 1 threshold cuts. Here we check three, out of the graph’s 127 possible cuts.^[15]

What did the sweep establish?

The second threshold gives the best cut among these three candidates, with score 0.5.

Chapter 7 proved the lowest possible pattern energy, about 0.764. The sweep found a cut score of 0.5 by checking only the cuts from this ordering. That does not establish the best score across all cuts.

We therefore have a good candidate and a new question: could a cut outside this list score much lower? Chapter 9 uses λ₂ to limit how much better an unseen cut could be.

Optional: see all three candidate cuts side by side

Optional: signs, scale, and group sizes

Reversing every sign reverses the ordering and swaps the sides of the sweep cuts. Their scores do not change. Multiplying all values by a positive number stretches the value axis while leaving the ordering and the candidate groups unchanged.

Mean zero does not require equal numbers of positive and negative entries. A few large positive values can balance many small negative ones. The balanced winning cut here comes from this graph’s symmetry.

Optional: does a sweep need to recount every edge for every cut?

No. When a node moves into the chosen group, only its incident edges can change crossing status. An edge to a node already inside stops crossing; an edge to a node still outside starts crossing. The sweep can update its crossing count as it moves.

Nodes with equal values move together, and we score the cut after the whole group has moved.

9. What the eigenvalue says about unseen cuts

could another cut be much better?

Chapter 8 found a cut with two crossing edges and four nodes on each side, giving a score of 2/4 = 0.5. Recall that h(G) is the lowest score among all cuts. We want to know how much lower an unseen cut could score.

Chapter 7 found the lowest pattern energy, λ₂ ≈ 0.764. Energy adds squared differences across edges; a cut score counts crossing edges and divides by the smaller group size. To connect the two measurements, we will turn a cut into a pattern.

A cut can be turned into a pattern

Imagine someone hands us a proposed cut. Give every node on one side the same value, and every node on the other side a different value.

Every edge within a group joins equal values, so it contributes zero energy. Only edges crossing between the groups contribute energy.

We must still follow Chapter 7’s rules. Subtract the mean, then rescale the values so their squares add up to 1. The result is an allowed pattern, so its energy cannot be below λ₂.

After centering and rescaling, the pattern’s energy can be written as two terms:

The first term is the cut score. The second counts the same crossing edges but divides by the larger group size, so it cannot be greater than the first. Adding the two terms gives at most twice the cut score. The optional calculation below derives this energy formula.

For our two halves, the terms are equal: 2/4 + 2/4 = 1. This is Chapter 6’s hard-split energy. Its cut score is 0.5, and its energy is exactly twice that. With unequal group sizes, the second term is smaller, so the energy is less than twice the score.

Every cut therefore gives us an allowed pattern satisfying:

Try an impossibly good cut

Suppose someone claims to have found a cut scoring 0.1. Our construction would turn it into an allowed pattern with energy at most 0.2.

But Chapter 7 proved that every allowed pattern has energy at least about 0.764. The proposed cut would produce a pattern below that proven minimum. Therefore, that cut cannot exist.

The same argument applies to every cut. Since the pattern’s energy is at least λ₂ and at most twice the cut score, we get:

This is the lower bound. It applies even to cuts we never examine. A sufficiently low-scoring cut would contradict the minimum energy we already know.

How close is our cut to the best possible score?

Every cut scores at least about 0.382. We also have an actual cut scoring 0.5, so the best score cannot be above 0.5. Together, these facts give:

This answers our opening question: no unseen cut can improve on 0.5 by more than about 0.118. We obtained that guarantee without checking every cut.

Does low energy also guarantee a low-scoring cut?

So far, we have gone from a cut to a pattern. The other direction asks: if λ₂ is small, must a low-scoring cut exist?

The answer is yes. The pattern’s values may change gradually across the graph, so we use a threshold sweep to look for a cut, as in Chapter 8.

An edge crosses the cut only when the threshold lies between its two endpoint values. Low energy keeps the sum of squared gaps small, and a small gap leaves only a narrow interval of thresholds that separate that edge’s endpoints.

That is the intuition. A full proof must also account for group sizes. It establishes that at least one threshold cut has a score no greater than √(2dλ₂), where d is the number of links at each node. A smaller λ₂ makes this guarantee stronger.

Cheeger’s inequality puts both directions together

For our kind of graph—undirected, with every node having the same degree d—the two guarantees can be written as:

This is a form of Cheeger’s inequality.^[16] Read its two sides separately:

• The left side limits every cut. No cut scores below λ₂/2.
• The right side guarantees that a cut exists. At least one cut scores no more than √(2dλ₂). Other cuts can score much higher.

Here d = 3. Using λ₂ ≈ 0.764, the theorem alone gives a range from about 0.382 to 2.141. Our actual cut provides the tighter upper bound of 0.5. The theorem’s upper bound is a general guarantee; a cut we find can do much better.

What establishes the exact answer?

Our range leaves open whether some cut scores between about 0.382 and 0.5. For this small graph, we can check all 127 distinct cuts. That check finds none below 0.5, establishing h(G) = 0.5 exactly.

Optional: see how cuts and node values connect

The first panel starts with our cut into two halves. The +1 and −1 values already have mean zero; the panel shows how rescaling changes their energy from 8 to 1. The second panel starts with Fiedler values and shows which edges a threshold separates.

Optional: derive the cut-pattern energy

Let the graph have n nodes. Suppose the smaller group contains s nodes, the other group contains n − s nodes, and b edges cross between them. The cut score is b/s.

Start with value 1 on the smaller group and 0 on the other group. The mean is s/n. Subtracting it gives value 1 − s/n on the smaller group and −s/n on the other. The mean is now zero, and every crossing edge still has a gap of 1.

The energy is therefore b. The total squared spread is the sum of s copies of (1 − s/n)² and n − s copies of (s/n)². This simplifies to s(n − s)/n. To find the energy after rescaling that spread to 1, divide energy by squared spread:

rescaled pattern energy
= bns(n − s) = bs + bn − s

This is the two-term formula used above. Since s ≤ n − s, the second term is no greater than b/s, the cut score. Combining this with Chapter 7’s minimum gives λ₂ ≤ rescaled pattern energy ≤ 2 × cut score.

A larger λ₂ raises the lower bound on every cut score. That makes it useful for network design: it can certify that no group has a very sparse connection to the rest. Chapter 10 explores how changing the wiring can improve that guarantee.

10. Rewire the graph to improve expansion

stronger boundaries with the same link budget

So far, we have searched a fixed graph for low-scoring cuts to find its bottlenecks. When designing a network, we want even its lowest cut score to be high. Every group containing up to half the nodes should have substantial connections to the rest, relative to its size.

The same change in perspective applies to λ₂. Within one graph, it is the lowest allowed pattern energy. When we change the wiring, a larger λ₂ raises the guaranteed lower bound on every cut score. We will compare two designs with the same number of links per router.

Keep the hardware budget fixed

Our original graph has eight routers, three links per router, and twelve links in total. Its weakest cut has two crossing links for four nodes, giving h(G) = 0.5.

Connecting every router to every other would provide more ways out, but it would also require more ports and cables. A fair comparison keeps the number of routers and links fixed, and changes which routers are connected.

In the rewired graph, the highlighted group is {1, 2, 5, 6}. Four links leave it: 1–8, 2–3, 4–5 and 6–7. There are four nodes on each side, giving a cut score of 4/4 = 1.

This cut shows that the rewired graph’s minimum score is no greater than 1. We still need to rule out a weaker boundary elsewhere.

How do we know another group is not hiding a weak boundary?

Improving one visible cut is not enough. We need a guarantee about every group. This is where Chapter 9’s lower bound becomes useful.

The rewired graph has λ₂ = 2. Therefore:

We have a cut scoring 1, and the eigenvalue proves that no cut scores below 1. Together, these establish h(G) = 1. The weakest cut score has doubled from 0.5 to 1, with twelve links in each design.

What does that guarantee mean for a group of routers? Take any group containing k nodes, up to half the network. Its crossing-edge count divided by k is at least 1, so at least k links leave that group.

For example, every group of four nodes has at least four outward links in total. Those links can be distributed unevenly among the group’s nodes.

Now ask whether the advantage survives as the network grows

A good eight-router design is useful, but real networks grow. We now keep the number of links per router fixed while increasing the number of routers. The total number of links grows with the network.

Could a large group’s outward connections fail to keep up with its size?

A ring shows how that can happen. Each router has two neighbours, whatever the ring’s size. Choose a consecutive half of an even-sized ring. Only two links leave that half:

The group gets larger while its outward connections stay at two. Its cut score keeps falling. Having the same number of neighbours at each router does not, by itself, protect against this problem.

An expander family keeps the boundary guarantee as it grows

We want every group containing up to half the nodes to retain a number of outward links proportional to its size, even as the network grows.

For example, suppose we guarantee at least half as many outward links as nodes in each such group. A group of 100 nodes would have at least 50 links out; a group of 1,000 would have at least 500. The same guarantee would hold for every graph in the growing sequence. In symbols, h(G) ≥ 0.5 throughout.

An expander family is a sequence of increasingly large graphs with the same fixed degree and this kind of guarantee: h(G) stays above one fixed positive number.^[17] The number need not be 0.5. What matters is that it does not shrink toward zero as the graphs grow.

Chapter 9 gives us a way to establish that guarantee. If λ₂ stays above a fixed positive number, then h(G) ≥ λ₂/2 gives a fixed positive lower bound on every cut score. The optional section below explains the connection in both directions.

What does this provide for a network?

With equal-capacity links, a lower bound on every group’s number of outward links also gives a lower bound on its total outward link capacity. The guarantee covers all groups, including ones that were not obvious in a drawing.

Routing still has to use those links effectively. Traffic patterns, shared paths, and forwarding choices affect the throughput that is actually achieved. Expansion tells us something about the connections the topology makes available.

Next we will see how the same spectral information appears when a paper uses adjacency eigenvalues instead of Laplacian eigenvalues.

Optional: see the group-size and ring examples

For an even ring with n nodes, a consecutive half contains n/2 nodes and has two crossing links. Its score is 2/(n/2) = 4/n, which tends toward zero as n grows.

Optional: why both sides of Cheeger matter for growing graphs

If λ₂ ≥ a for some fixed a > 0, then h(G) ≥ a/2. Conversely, if h(G) ≥ c for some fixed c > 0, the inequality h(G) ≤ √(2dλ₂) implies λ₂ ≥ c²/(2d). When d is fixed, both statements give a positive bound independent of the number of nodes.

This is what “bounded away from zero” means: there is one positive lower limit that works for the whole family, even as its graphs get larger.

11. Recognize the gap in another matrix

follow the same pattern through A and L

For our original graph, the second Laplacian eigenvalue is about 0.764. A paper using the adjacency matrix would instead report a second eigenvalue of about 2.236. Both numbers describe the same graph. We need to know which matrix a number belongs to before using it.

Because every node here has three neighbours, one subtraction translates between the two descriptions.

Recall what the two matrices do

A adds up the neighbours’ values. L takes three times the node’s own value and subtracts that sum.

Every node here has degree three, so:

Both matrices receive the same input pattern x. Once we know one output, this equation gives the other.

Try the flat pattern first

Give every node the value 1. A adds three neighbouring ones at every node, returning 3 everywhere. It multiplies the whole flat pattern by 3.

L subtracts those neighbour sums from three times each node’s own value: 3 − 3 = 0 everywhere. Its multiplier for the flat pattern is 0.

Rescaling this flat pattern to the unit vector u₁ leaves its multipliers unchanged: 3 under A and 0 under L.

Now try the winning pattern from Chapter 7

Chapter 7 found that L multiplies every entry of u₂ by about 0.764. Rearrange our rule to find what A does:

A also leaves the pattern’s proportions unchanged, multiplying every entry by about 2.236. So u₂ is an eigenvector of both matrices, with a different eigenvalue for each.

Here are the first three patterns from Chapter 7 and their multipliers:

In every row, the two multipliers add up to three. The figure connects the paired values for these same three patterns:

Which number is the spectral gap?

The adjacency value 2.236 is a multiplier. To get the spectral gap used here, subtract it from the largest adjacency eigenvalue, 3:

For A, the gap runs from its largest eigenvalue down to its second largest. For L, it runs from zero up to λ₂. Both gaps are about 0.764.

The same rule works at any fixed degree

If every node has degree d, then L = dI − A. Here I is the identity matrix, which returns its input unchanged. A pattern with adjacency multiplier α has Laplacian multiplier d − α.

We use α for an adjacency eigenvalue and λ for a Laplacian eigenvalue. List the adjacency values from largest to smallest. The largest is α₁ = d; the second largest is α₂. Subtracting each from d reverses that order, giving the Laplacian values from smallest to largest.

For the rewired graph in Chapter 10, d = 3 and λ₂ = 2. Its second adjacency eigenvalue is therefore α₂ = 3 − 2 = 1. At the same degree, a smaller α₂ gives a larger λ₂ and a stronger lower bound on every cut score.

When a paper reports an eigenvalue, identify the matrix and its scale first. For an adjacency eigenvalue on a regular graph, subtract from d before applying Chapter 9’s Laplacian bounds. The optional sections cover other conventions you may encounter.

Optional: why some papers divide the gap by the degree

L adds a node’s differences from its d neighbours. Dividing by d turns that sum into an average. For a regular graph, the matrix L/d is called the normalized Laplacian. Here we are rescaling the matrix; the node pattern stays the same.

Dividing a matrix by d divides each eigenvalue by d. If we call the second normalized eigenvalue μ₂, then:

μ₂ = λ₂/d ≈ 0.764/3 ≈ 0.255

So 0.764 and 0.255 can both describe this graph’s gap, on different scales. Check whether a reported gap has been divided by the degree before comparing numbers.

Optional: conductance measures the fraction of connections leading out

Our group of four nodes has two links leading out. Its cut score is 2/4 = 0.5 outward links per node.

We can instead measure the fraction of the group’s connections that lead outside. Count each end of a link attached to a node in the group. Four nodes with three connections each give 4 × 3 = 12 connection ends.

Five links are internal, using two ends each: ten ends in total. The two crossing links use one end each inside the group. Only those two ends lead outside.

The outward fraction is 2/12 = 1/6. For each cut, use the group with fewer connection ends. The lowest fraction across all cuts is the graph’s conductance, written φ(G).

When every node has degree d, counting connection ends multiplies each group’s node count by d. So φ(G) = h(G)/d. In our graph, φ(G) = 0.5/3 = 1/6.

The change is in the denominator: h(G) counts outward links per node; φ(G) counts the fraction of connection ends leading out. Write μ₂ = λ₂/d for the normalized eigenvalue. Dividing Chapter 9’s bounds by d gives:

μ₂/2 ≤ φ(G) ≤ √(2μ₂)

We have changed both measurements to a scale relative to degree. The relationship between cuts and eigenvalues remains.

Optional: what changes when nodes have different degrees?

L = D − A and the energy formula still hold. But there is no single degree d to subtract from every adjacency eigenvalue, so our simple translation no longer works.

For conductance, count a group’s connection ends by adding its node degrees. This sum is called its volume. A cut’s conductance is its crossing-edge count divided by the smaller of the two group volumes.

The matching pattern calculation gives each node weight equal to its degree. A node with six links counts twice as much as one with three. With dᵢ denoting node i’s degree, the two constraints become:

∑ᵢ dᵢxᵢ = 0
∑ᵢ dᵢxᵢ² = 1

The first removes the degree-weighted mean. The second fixes the degree-weighted squared spread. This calculation can be expressed using the symmetric normalized Laplacian:

D^−1/2 L D^−1/2

Assuming no isolated nodes, D^−1/2 is a diagonal matrix with entry 1/√dᵢ at node i. Multiplying on both sides scales the corresponding rows and columns. When all degrees equal d, the result is just L/d. Spielman’s text, §10.5 explains the change of coordinates behind this formula.

Optional: what the name Ramanujan adds

The gap above uses only the second-largest adjacency eigenvalue. Ramanujan is a stronger spectral condition: for a connected d-regular graph, every nontrivial adjacency eigenvalue must have absolute value at most 2√(d − 1).^[18] Absolute value means ignoring the sign, so negative eigenvalues count too. Exclude the flat pattern’s eigenvalue d; if the graph is bipartite, also exclude −d.

For degree three, the limit is 2√2 ≈ 2.828. Our original graph’s nontrivial adjacency values are √5, 1, four copies of −1, and −√5. Their absolute values all lie below that limit, so this small graph meets the condition. Its expansion is still h(G) = 0.5: the label does not mean that every cut has a high score at every size.

The limit is an important benchmark for large graphs at fixed degree. Friedman’s result allows an arbitrarily small positive amount above it, with probability tending to one as a random regular graph grows. That does not establish the exact Ramanujan condition for every sampled graph.

Chapter 12 returns to the practical goal: using well-connected graphs in a network.

12. Bring the ideas back to RNG

connect the cut guarantee to cabling and routing

RNG is a flat data-center network design that mixes planned and randomized router connections. Its use of expander graphs connects to Chapter 10’s goal: keep groups well connected with limited links per router. RNG §§1–2

What does a cut mean for traffic?

Our node values were a mathematical tool for finding weak cuts. To interpret a cut as capacity, give each link a transmission rate.

Suppose the two links between our example’s halves each carry 100 Gb/s in each direction. Traffic leaving either half has at most 2 × 100 = 200 Gb/s of boundary capacity available. Every route to the other half must cross that boundary.

Expansion measures how much boundary a group has relative to its size. A lower bound on h(G) therefore guarantees outward link capacity for every group of up to half the nodes, when links have equal capacity. The spectral gap helps establish that guarantee across the graph.

Boundary capacity sets a limit on outgoing traffic. The throughput actually achieved also depends on the routes used and the traffic sharing them.

Random-like wiring has to fit real cabling

The graph records which routers connect. A physical installation must also get the fibres between those routers.

RNG calls its wiring quasi-random. Its ShuffleBoxes map fibre pairs through passive hardware. They connect fibres without forwarding packets, so a router-to-router connection through them remains one logical link. RNG §6

The authors report that their construction retains the spectral gap of unconstrained random graphs in their analysis. RNG §6 The relevant test is whether a graph built under cabling constraints still has a strong spectral gap.

A good graph still needs a routing method

The drawing below has two routes from a to b: through p or through q. If forwarding always chooses p, the links through q carry none of that traffic. Their presence in the graph alone does not make them useful.

RNG’s routing scheme, Spraypoint, makes all source neighbours eligible first hops. Later forwarding rules guide traffic through selected intermediate routers called waypoints toward the destination. This spreads traffic across departures from the source and approaches to the destination. RNG §5

In that section of the paper, h counts eligible next hops after the first step; this primer’s h(G) means edge expansion.

What can we conclude from each result?

The spectral calculation answers a question about the wiring. To assess the complete network, we also need evidence about how traffic uses that wiring:

• Spectral gap: gives bounds on the graph’s cut scores.
• Routing analysis: estimates what the routing method achieves under its graph and traffic assumptions.
• Measurements: show performance for the configurations and traffic that were tested.

RNG develops routing models and evaluates fabrics built under practical port and forwarding-memory limits. RNG §7, §9 Those results address questions beyond the cut guarantee.

We began with two links joining two groups of routers. Node values let us measure that weakness, eigenvectors found the lowest-energy pattern, and Cheeger’s inequality connected its energy to cut scores. These tools help us assess the wiring. Cabling and routing turn that wiring into a working network.

Review

1. A graph is nodes and edges; a pattern is one value per node. A collects the neighbours’ values, D repeats a node’s own value once per link, and L = D − A asks how far a node stands above its neighbourhood.
2. A cut’s score is crossing edges divided by the smaller side. The lowest score over all groups is the edge expansion h(G), and checking every group is hopeless.
3. The energy E(x) = ∑(xᵢ − xⱼ)² = xᵀLx counts squared disagreement across links. With +1 and −1 group labels, it is 4 times the crossing edges. It is never negative.
4. Two conditions make the comparison fair: mean zero removes a shared level, and squared spread 1 prevents shrinking from counting as an improvement. Squared spread is the sum of squared distances from the mean. For a centered, nonzero pattern, dividing energy by squared spread gives the Rayleigh quotient xᵀLx / xᵀx.
5. Letting values bend helps. One number, t, moves the four boundary nodes toward zero, with a rescaling after every move. The energy falls from 1 to 0.764 at t = 0.618 and climbs to 2 at t = 0, because the interior edges start to disagree.
6. The reference patterns are the eigenvectors of L, the patterns L only rescales, and a length-1 eigenvector’s energy is its eigenvalue. Every pattern with mean zero and squared spread 1 is a mixture of u₂ to u₈ whose shares add to 1, so its energy is a weighted average of their eigenvalues and cannot fall below the smallest, λ₂. u₂, the Fiedler vector, reaches it. Here λ₂ = 3 − √5 ≈ 0.764.
7. Sort the nodes by Fiedler value, sweep a threshold through the gaps, score each cut by crossing edges over the smaller side. Four distinct values give three gaps; the second one gives 0.5. A sweep tests the prefixes of one ordering, not every group.
8. Cheeger: λ₂/2 ≤ h(G) ≤ √(2dλ₂). A cheap cut gives a cheap pattern, and a cheap pattern gives a cheap cut. Here 0.382 ≤ h(G) ≤ 0.5, and checking all 127 cuts gives exactly 0.5.
9. Expansion bounds the links leaving every group of up to half the nodes, relative to its size. Our rewiring raised h(G) from 0.5 to 1 and λ₂ from about 0.764 to 2, with twelve links in each design. For a regular graph, an adjacency eigenvalue α corresponds to a Laplacian eigenvalue λ = d − α. The topology supplies possible routes; forwarding rules determine which carry traffic.

Sources and further reading

1. Bernardi et al., RNG: Flat Datacenter Networks at Scale, version 3, 21 May 2026. The network discussion above follows this version.
2. Daniel Spielman, Spectral and Algebraic Graph Theory. A fuller development of Laplacians, the minimum argument, and graph partitioning.
3. Hoory, Linial and Wigderson, Expander Graphs and Their Applications. Expansion, spectral bounds, and the equal-degree form of Cheeger’s inequality used here.
4. Joel Friedman, A Proof of Alon’s Second Eigenvalue Conjecture and Related Problems. The near-Ramanujan behaviour of random regular graphs.
5. A Primer on Linear Algebra. Dot products, projection, eigenvectors, and the Rayleigh quotient, using a running example with one vector and one 2 × 2 matrix.

Footnotes

1. Nothing to do with charts. The word was borrowed in 1878 by J. J. Sylvester, who was drawing molecules as dots and lines and wanted a name for the drawings. ↩
2. Named after Laplace because it is the wiring-diagram cousin of his operator from physics, which also measures how far a value sits from the average of its surroundings. Books that want to be precise call this one the combinatorial Laplacian; Chapter 11 meets a cousin that divides by degree. ↩
3. For eight nodes, the nonempty groups of size at most four number 8 + 28 + 56 + 70 = 162. A four-versus-four cut appears twice in that list, once for each side, so these groups describe 127 distinct cuts. In general, n nodes have 2^(n − 1) − 1 nontrivial cuts when swapping the sides is counted as the same cut. For forty nodes, there are 618,679,078,297 groups of size at most twenty, representing 549,755,813,887 distinct cuts. ↩
4. The name comes from physics: an ideal spring stores energy proportional to the square of its stretch. Here, energy is a mathematical measure of the differences between values at connected nodes. ↩
5. A symmetric matrix whose energy is never negative is called positive semidefinite. L is symmetric because every edge runs both ways. Both facts matter in Chapter 7, where the eigenvectors take over. ↩
6. Centering removes the component along the all-equal direction. Subtracting the mean does this one value at a time. ↩
7. A centered pattern rescaled so its squared values add to 1 is called normalized. We will mostly say “rescaled”. ↩
8. Here, each undirected edge is counted once: E(x) = ∑{i,j} (xᵢ − xⱼ)² = xᵀLx. With mean zero, the squared spread is ∑ᵢ xᵢ². These are the same energy and squared spread used in Chapters 4–6. ↩
9. “Eigen” is German for “own”: a pattern the matrix treats as its own. Primer 1 drew eigenvectors as arrows that a matrix only stretched. Here each arrow has eight entries, so we read those entries as values on eight nodes. ↩
10. This is the spectral theorem, drawn in Primer 1's Chapter 8 for a 2 × 2 matrix. For eight nodes the picture has eight perpendicular directions instead of two, and nothing else changes. ↩
11. When an eigenvalue repeats, any nonzero mixture of eigenvectors belonging to it is another eigenvector with that eigenvalue. We choose perpendicular, length-1 building blocks within that space. If λ₂ repeats, several independent directions achieve the same minimum. ↩
12. The slider's pattern is an eigenvector exactly when t² + t − 1 = 0, which gives t = (√5 − 1)/2 ≈ 0.618, one over the golden ratio. The eigenvalue that comes with it is 2 − 2t = 3 − √5. ↩
13. After Miroslav Fiedler, who studied λ₂ in a 1973 paper and showed that it is zero exactly when the graph is disconnected, and that bigger values go with graphs that are harder to split. ↩
14. More generally, the number of zero Laplacian eigenvalues is the number of connected components. Each component can hold its own constant value without any edge disagreement. Centering removes one shared-level direction; if the graph is disconnected, other zero-energy directions remain. ↩
15. A threshold can be placed between consecutive distinct values. With k distinct values, there are k − 1 nontrivial threshold cuts, and k is at most the number of nodes n. These are only the cuts obtained from one ordering. Equal values stay together; reversing the ordering gives the same divisions with their sides swapped. ↩
16. Jeff Cheeger proved the original version in 1970 for curved surfaces, where it bounds the smallest vibration frequency by how thin the surface's narrowest neck is. Jozef Dodziuk, and Noga Alon with Vitali Milman, carried it over to graphs in the mid-1980s. The form used here is the one in the survey by Hoory, Linial and Wigderson, linked below. ↩
17. Early work by Leonid Bassalygo and Mark Pinsker connected expanders to sparse communication networks. In 1973, Pinsker used a probabilistic argument to show their existence, and Grigory Margulis gave the first explicit construction. See the survey by Hoory, Linial and Wigderson in Sources and further reading. ↩
18. The name is a joke that stuck: the first explicit constructions, by Lubotzky, Phillips and Sarnak and independently by Margulis in 1988, relied on a conjecture of Ramanujan's about number theory. The graphs themselves have nothing to do with him. ↩