Author: Michael Darrow

I’m sure you know about ordinary graph coloring, but just in case: a k-coloring of a graph assigns to each node one of k colors such that no two nodes that share an edge share a color. Most maps are shaded with a 4-coloring of their adjacency graphs, and a Sudoku puzzle is just a puzzle of finishing partial 9-coloring of the Sudoku graph.

Fractional graph coloring is a way to generalize graph coloring to fractional color amounts. For example, the pentagon graph is 5:2-colorable, and the 9-cycle is 9:4-colorable. An a:b-coloring of a graph assigns to each node b colors out of the available a such that no two nodes that share an edge share a color. Note that an n:1-coloring is just an n-coloring. Here is an example 6:2-coloring of an unnamed graph:

From any a:b-coloring, you can get a corresponding an:bn coloring by assigning each original color to n colors (as the Wikipedia article for fractional coloring shows in its image). Note that the reverse cannot be performed; the above graph that has been 6:2-colored cannot be 3-colored, and was in fact specifically chosen because of this.

I was trying to figure out the fractional chromatic number of the icosahedron graph for an earlier part of this article. First I assumed that it was 7/2, then I thought it was 18/5, then I tried 11/3. I still don’t know what it is. “Hang on,” you might be wondering, “Why are these actual fractions?” There is a way to generalize fractional graph coloring to actual fractional numbers of colors: an x-coloring (with x a real number) assigns each node of a graph to a set of real numbers with measure 1 that is a subset of the interval [0,x]¹, and no two adjacent nodes can share a color. Alternatively, you can consider the fractional chromatic number to be the minimum of the fractions you get if you interpret the coloring numbers as fractions.

An infinite graph can be constructed to have any irrational fractional chromatic number larger than 2: Find a series of fractions that converge to that number from below (If we were to do this for pi, the first three could be 3, 25/8, and 47/15), and take the disjoint union of the corresponding Kneser graph for each one.

An unproven conjecture: If some graph can be a:b-colored, and bc > ad, then it can also be c:d-colored. Equivalently: If bc > ad, then the Kneser graph KG_a,b can be c:d-colored.

1. It doesn’t actually matter if the interval is closed or open, because points have measure 0. I just think square brackets look better. ↩︎

The definition for ordinal-time cellular automata is simple:
Generation 0 is just the initial state, as it always is.
Generation n+1 is the cellular automaton applied to generation n, as it always is.
Generation A, with A being a limit ordinal, makes any cell that is alive infinitely often just before generation A be alive.

Here is a video of the blinker’s evolution in infinite-time Conway’s Game of Life up to generation ω+8:

The blinker’s evolution actually continues past the generations shown above, and it eventually stabilizes at generation ω5+25.

Other common oscillators stabilize way earlier: a toad stabilizes into a block at generation ω+3, a beacon is already stable (even though it’s oscillating), a clock stabilizes into a fleet at generation ω+8, and the n-barberpole stabilizes into a longⁿ ship at generation ω, and the pulsar stabilizes into eight blocks at generation ω+22.

No pattern has a known stabilization point past ω²2. To be clear, in this post, stabilization refers to the first generation that doesn’t stop appearing at some point.

The only known online appearances of this are https://googology.fandom.com/wiki/User_blog:LittlePeng9/Infinite_time_game_of_life, which defines it, a thread in the #misc-ca channel of the ConwayLife Lounge Discord server that has links to all of the other examples in this list, https://scratch.mit.edu/projects/1267474269/, which simulates it on random initial states for generations less than ω³ (and lets you move through the generations freely!), and this blog post.