## Essentials

a mathematician and software engineer. plays with ideas and code.

### Research Highlights

30+ publications in top-tier discrete mathematics and philosophy journals. A couple of favorites:

D.W. Cranston and L. Rabern. Planar graphs are 9/2-colorable. Journal of Combinatorial Theory, 2017. This article is about coloring countries on a map so that adjacent countries receive distinct colors. It was conjectured in 1852 that any map could be colored thusly using only 4 colors. This was finally proved in 1976, but the proof is not human-checkable; it requires many hours of computer time to check thousands of cases. Finding a human-checkable proof is still an open problem. To prove that 5 colors suffice is relatively simple. We gave a human-checkable proof that 4.5 colors suffice; this means that we get to use 9 colors, but have to assign each country 2 colors.

• Settled a 20-year old conjecture on the existence of such a proof.
• Featured on Computational Complexity, a popular computer science blog by Lance Fortnow & Bill Gasarch.

B. Rabern and L. Rabern. A simple solution to the hardest logic puzzle ever. Analysis, 68(2), April 2008. Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are da and ja, in some order. You do not know which word means which.

• Showed how to trivialize the puzzle by asking questions that elicit meaningful answers from Random.
• Showed how to solve the puzzle in only two questions by using paradoxes to explode god-heads.
• This article led to the problem getting a lot of press and many follow-up papers have been written.

this interview with my phd advisor Hal Kierstead gives some idea of the type of math i tend to work on.

## Logic

#### Journal of Philosophical Logic

• Dangerous reference graphs and semantic paradoxes

#### Analysis

• A simple solution to the hardest logic puzzle ever (with Brian Rabern)

## Math

#### Journal of Combinatorial Theory, Series B

• Planar graphs are 9/2-colorable (with Dan Cranston) (pdf)
• Improved lower bounds on the number of edges in list critical and online list critical graphs (with Hal Kierstead) (pdf)
• Δ -Critical graphs with small high vertex cliques(pdf) (doi)

#### Electronic Journal of Combinatorics

• A better lower bound on average degree of k-list-critical graphs. (pdf)
• Beyond Degree Choosability (with Dan Cranston) (pdf)
• A better lower bound on average degree of 4-list-critical graphs (pdf) (ejc)
• Planar graphs have independence ratio at least 3/13 ( with Dan Cranston) (pdf)
• Painting squares in Δ^2-1 shades (with Dan Cranston) (pdf)
• A note on coloring vertex-transitive graphs (with Dan Cranston) (pdf)
• A strengthening of Brooks' Theorem for line graphs (pdf)
• The Borodin-Kostochka conjecture for graphs containing a doubly critical edge (pdf)

#### Journal of Graph Theory

• Extracting list colorings from large independent sets. (with Hal Kierstead) (pdf)
• Subcubic edge chromatic critical graphs have many edges (with Dan Cranston)
• Brooks' Theorem and Beyond. (with Dan Cranston) (pdf)
• Coloring graphs with dense neighborhoods. (pdf)
• Destroying non-complete regular components in graph partitions ( pdf) (doi)
• On hitting all maximum cliques with an independent set (pdf) (doi)

#### European Journal of Combinatorics

• Conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker. (with Dan Cranston) (pdf)

#### Journal of Pure and Applied Algebra

• Applying groebner basis techniques to group theory (doi)

#### Notes

• Unfinished graph coloring book (pdf)
• The combinatorial nullstellensatz and Schauz's coeffcient formula (pdf)
• Stiebitz's proof of Gallai's conjecture on the number of components in the high and low vertex subgraphs of critical graphs (pdf)
• Haxell's independent transversal lemma (pdf)
• The union of a forest and a star forest is 3-colorable (pdf)
• Kernel magic, Brooks' theorem and painting triangle-free graphs (pdf)

#### Manuscripts

• Edge-coloring via fixable subgraphs (with Dan Cranston) (pdf)
• The list-chromatic index of K_8 and K_10 (pdf)
• Yet another proof of Brooks' theorem (pdf)
• Coloring graphs from almost maximum degree sized palettes, Dissertation ( pdf)
• A note on vertex partitions (pdf)

## Talks

 A common generalization of Hall's theorem and Vizing's edge-coloring theorem (Miami University Colloquium) (slides) Extending Alon-Tarsi Orientations (AMS Special Session on Structural and Extremal Problems) (slides) List coloring with large maximum degree (poster) An improvement on Brooks' theorem (CU-Denver Discrete Math Seminar) (slides) Improving Brooks' theorem (The 26th Clemson Conference on Discrete Math and Algorithms, 2011) (slides)

## Data

the borodin-kostochka conjecture from the 1970s was my dissertation project. i did not prove it, but made substantial progress. the data here can be used to severely restrict possible counterexamples to the conjecture.