Thread by @iowahawkblog

QTing this to avoid clogging up Mr Williams's TL; these are pretty interesting and useful math concepts. Tessellation is about diving a space in to sections (it means "tiling").

https://twitter.com/iowahawkblog/status/1465822892160126987

For example you can tessellate a flat surface with triangles or squares or hexagons or herringbone. They don't have to be same shapes, tho; state borders are one way to tessellate a map of the US.

A Voronoi tessellation is a special example involving centroids.

Voronoi tessellation starts with points on a plane, the draws the linear borders that dissect the plane equidistant between points.

example: get a map of the US, erase the borders between states, but leave the 50 state capitals on it as centroids.

If you do a Voronoi tessellation, it will draw linear borders such that there will be a new "Iowa" where everyone inside its border lives closer to Des Moines than they do to any other state capital. Same with any other redrawn state and its associated centroid.

Voronoi tessellations also occur in nature. For example it's kind of representative of how mud cracks occur on a dry lakebed.

Now onto the fun stuff of Graph Laplacians and Eigenvalues.

Discrete Graph Theory is about nodes (circles) and edges (lines that connect the circles). Examples: train stations and tracks between them, networks of all kinds- distribution networks, the internet, etc.

And of course, social networks like Facebook. Imagine a graph with FB accounts as circles, and lines indicating a friendship connection between circles.

Let's say A is friends with B & C, B & C are friends, C is friends with D, but there are no other connections between the 4.

That friend network graph can be represented in a 4x4 Laplace matrix, which is consists of a degree matrix - an adjacency matrix. For this example, the degree matrix is

2 0 0 0
0 2 0 0
0 0 2 0
0 0 0 1

(the diagonal show how many friends they have)

*oops, that third diagonal should be 3 (C is friends with A, B, and D)
the adjacency matrix shows who they're friends with:

0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0

the Laplacian is the degree matrix minus the adjacency:

2 -1 -1 0
-1 2 -1 0
-1 -1 3 -1
0 0 -1 1

Without going down a rabbit hole, Eigenvalues are a way of transforming the Laplacian matrix into independent vectors which are useful for route-finding and such.

Famous example: Six Degrees of Kevin Bacon. Imagine now a great big ol' graph where each circle is an actor, and the line shows if they've been in a movie together. You can represent it as an actor-by-actor Laplacian matrix.

The Eigenvectors of that matrix can help you solve the shortest chain of movies & actors that connect Kevin Bacon to Humphey Bogart (or any actor to any other actor).

Thank you for attending my TED talk

OK, I'mma circle back to Voronoi tessellation, because this is an interesting point. A Voronoi map *within* a state is a possible way to prevent gerrymandering, but there are some math issues you'd have to deal with.

https://twitter.com/AUTigerx89/status/1465847806707572739

For reference, here's a Voronoi map of the USA, using location of the 50 state capitals as centroids. Every point within the new states is closer to its state capital than it is to any other state capital.

Now imagine doing the same thing within each state to draw up congressional districts. If the state has 8 seats, drop 8 centroids on its map and voila, your new districts.

Problems: (1) each district needs to have nearly equal population, and (2) centroid sensitivity.

In the Voronoi USA map above, the resulting states obviously do not have equal population. New California for example has a ton more people than New Wyoming. Same thing would happen within a state.

I'll use the example of Iowa: you could choose its 4 congressional centroids as the NW-SW-NE-SE corners of the state, and the Voronoi map would basically quarter the state east-west & north-south, but with lopsided population size.

Alternatively you could choose 4 largest cities (Des Moines, Cedar Rapids, Davenport, Sioux City) as centroids, but same unequal population problem.

So for congressional redistricting, you'd want to actually solve for the location of district centroids that result in equal pop.

But now you run into the uniqueness issue: there will be a near infinitude of Voronoi maps that divide Iowa into 4 equal-population districts. You might find 4 centroids for a Voronoi map that solves it, but there will be lots of other sets of 4 centroids that work too.

I will conjecture you can make a Voronoi redistricting map unique by also minimizing the total distance of each person to their district centroid. I.e.,

Find location of N district centroids
subject to: equal pop. in districts
min: sum(pop. distance to centroid)

I leave it to bigger brains to prove that, but if you can it would result in a pretty fair redistricting: compact, regular shaped districts, without the shenanigans of gerrymanderers.

If so, I think it should be the first algorithm to become a Constitutional amendment.

I'm noticing this thread is getting fewer likes than my fart jokes

In any case hats off to John Urschel, the smartest jock in the world, who spurred this thread