An interactive mathematical book

Why do Shi regions know how cars park?

This explainer builds the Pak–Stanley picture from scratch. You’ll first learn the one-way-street parking model, then hyperplanes, then the special geometry of the Shi arrangement, and finally why the labels that come from crossing Shi walls are exactly parking functions.

How to read this

The side rail is always live. Drag the cars there. Every page reads the same state in a different way.

car heights → hyperplane region → pair obstructions → Pak–Stanley label → parking preferences → cars park on a one-way street

Roadmap

Part I: parking functions

Cars on a one-way street

A parking function is a list of preferred starting spaces. Car \(i\) first tries space \(a_i\). If it is occupied, the car drives forward until it finds the next open space.

Zero-based convention: spaces are \(0,1,\ldots,n-1\). After sorting \(b_1\le\cdots\le b_n\), the parking condition is \(b_k \le k-1\).

Manual parking simulator

Part I½: why parking succeeds

Why the sorted condition is the right test

Suppose you sort the preferences to get \(b_1\le b_2\le \cdots\le b_n\). Then the first \(k\) cars in this sorted list must all fit into the first \(k\) parking spaces \(0,1,\dots,k-1\). So the \(k\)-th smallest preference must satisfy \(b_k \le k-1\).

highlight k 1

Think pigeonhole principle: if the \(k\)-th smallest preference is already bigger than \(k-1\), then the first \(k\) cars are all trying to start too late, so there are not enough earlier spaces to absorb them.

First \(k\) cars versus first \(k\) spaces

Part II: hyperplanes

A hyperplane is a wall

In the plane, a hyperplane is a line. In 3D, it is an ordinary plane. An arrangement is just a finite collection of these walls, cutting space into regions.

Drag the point. The sign of a linear expression tells you which side of the wall you are on.

A region is not a single point. It is one connected chamber of space after all the walls are removed. Moving within a region does not cross any wall.

One wall, two sides

Part III: braid arrangement

Before Shi: only order matters

The braid arrangement consists of the walls \(x_i=x_j\). Crossing one of them swaps the vertical order of two cars.

For \(n=3\), the six possible orders form a hexagon: the permutohedron. Adjacent vertices differ by one neighboring swap.

Permutohedron / chamber graph

Part IV: the Shi arrangement

Add shifted walls

The Shi arrangement adds shifted walls \(x_i=x_j+1\) to the braid walls \(x_i=x_j\). For \(n=3\), we can draw the real planes in 3D.

3D Shi arrangement for \(n=3\)

Blue planes are \(0\)-planes \(x_i=x_j\). Red planes are \(1\)-planes \(x_i=x_j+1\). The black point is the current height vector, centered into the slice \(x_1+x_2+x_3=0\).

Part V: one pair at a time

The three-zone test

Fix a pair \(i<j\). The base region expects \(0<x_i-x_j<1\): car \(i\) is ahead of car \(j\), but by less than one unit. Leaving that strip creates one obstruction token.

This is the key refinement: both the \(0\)-planes and \(1\)-planes matter. Crossing \(x_i=x_j\) contributes to coordinate \(i\); crossing \(x_i=x_j+1\) contributes to coordinate \(j\).

Pair strip \(0 < x_i-x_j < 1\)

Part V½: what crossing a wall does

Crossing a plane changes exactly one coordinate

A wall crossing does not mean “a parking space became occupied.” Instead it means: one coordinate of the Pak–Stanley label changes by \(+1\), so one car starts one space later on the street.

For a fixed pair \(i<j\): crossing the blue wall \(x_i=x_j\) adds one to \(a_i\). Crossing the red wall \(x_i=x_j+1\) adds one to \(a_j\).

Before → crossing → after

Part VI: event log

Every crossed wall gives one token

The Pak–Stanley label is obtained by starting at zero and adding one token for each separating wall, using the pair rule from the previous page.

Obstruction graph

Current event log

Pair table

Part VII: Pak–Stanley label

Collapse the events into one vector

Forget which pairs caused the tokens. Remember only how many tokens each car received. That vector is the Pak–Stanley label.

This compression looks too small to remember a region. The theorem says the geometry is rigid enough that, across all regions, these labels are exactly the parking functions.

Preference buckets

Part VIII: the bridge to parking

The label becomes parking preferences

Now read the Pak–Stanley label \(a=(a_1,\ldots,a_n)\) as parking preferences: car \(i\) starts at space \(a_i\).

The obstruction tokens are not literally occupied parking spaces. They are accumulated “pushes” that tell each car how far down the one-way street to start looking.

Current label parking simulation

Part IX: why parking functions appear

The parking condition is a consistency test

A vector is a parking function exactly when, after sorting, the \(k\)-th car does not start beyond space \(k-1\). Geometrically, impossible labels would demand too many obstructions too early.

Compare the current Pak–Stanley label to the sorted parking-function test.

The theorem is not just that the counts match. The Pak–Stanley construction labels every Shi region by a parking function, and every parking function occurs exactly once.

Sorted-condition diagram

Part X: scaling up

What survives for \(n=4,5,6,\ldots\)?

The full arrangement for \(n\) cars lives in effective dimension \(n-1\), so the literal picture fades. But the local pair rule, event log, label, and one-way-street parking still make sense.

Events

Buckets

Street

Summary

References for the formal theorem: Stanley’s work on hyperplane arrangements and parking functions, and later descriptions of Pak–Stanley labeling, prove that the labels of Shi regions are exactly parking functions.