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.

Math


Combinatorica

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)

Discrete Mathematics

SIAM Journal on Discrete Mathematics

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) (pdf)
  • Brooks' Theorem and Beyond. (with Dan Cranston) (pdf) (doi)
  • Coloring graphs with dense neighborhoods. (pdf) (doi)
  • 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) (doi)

Discussiones Mathematicae Graph Theory

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)

About

as a child, i was obsessed with machine intelligence. i coded a strong chess AI (codenamed Betsy) and experimented with using neural networks in Betsy, both for the static evaluation at leaf nodes and within the tree for pruning. the networks learned from self-play to get about as good as my hand-tuned functions (discounting the slowdown incurred by sigmoid evaluation). i concluded that to do better, i would need to use raw game state data instead of the set of features i preselected as network inputs; unfortunately, this was 2000 and i did not have nearly enough processing power to do so.

to avoid spinning my wheels while waiting for faster hardware, i decided to put my machine intelligence ambitions on hold and study mathematics instead. my first year as a math major was spent abroad at utrecht university in the netherlands. my dutch was pretty poor, but luckily all the math textbooks were in english. learning to learn from just a textbook was painful at first, but this method of learning has been indispensable ever since.

in 2005 i felt the pull of making real things and left my math phd program (where i was researching fun things like quantum groups) to work for a defense contractor. we simulated nuclear weapons effects like damage caused to hardware by electromagnetic pulse. this work was interesting, but for family reasons, after about a year, i moved to colorado and took a job for a subsidiary of goldman sachs.

the goldman sachs job was not particularly exciting and i had lots of downtime. i had just read the book the man who loved only numbers about paul erdős; a homeless math genius that traveled around for decades to work on hard problems with other discrete mathematicians. i decided to use my work downtime to teach myself graph theory and see if i was smart enough to play with these discrete mathematicians. this was in 2007, it took three years and a lot more than just my work downtime, but in 2010 i made a breakthrough, proving a conjecture of two prominent graph theorists (alexandr kostochka and hal kierstead). i made arrangements with kierstead to come out to arizona state and finish my phd.

now it is 2019, i have satisfied my curiosity about playing with erdős's friends and achieved the best possible erdős number of 2 (since erdős no longer lives). neural networks are all over the news, now called deep learning, researchers are having great success; hardware is now fast enough and there are massive amounts of data to play with. it is past time for me to get back to my childhood obsession.