Journal of Combinatorics

Volume 10 (2019)

Number 3

Special Issue in Memory of Jeff Remmel, Part 1 of 2

Guest Editor: Nicholas A. Loehr

Combinatorics in ZFC limbo

Pages: 579 – 593



S. Gill Williamson (Department of Computer Science and Engineering, University of California at San Diego)


In their paper, Large-scale regularities of lattice embeddings of posets, Remmel and Williamson study posets and their incomparability graphs on $N^k$. Properties (1) through (3) of their main result, Theorem 1.5, are proved using Ramsey theory. The proof of Theorem 1.5 (4), however, uses Friedman’s Jump Free Theorem, a powerful ZFC independent extension of Ramsey theory. Attempts to prove Theorem 1.5 (4) within the ZFC axioms have thus far failed. This leaves the main result of the Remmel-Williamson paper in what we informally call “ZFC limbo.” In this paper we explore other results of this type. In particular, Theorem 6.2 of this paper, which we prove to be independent of ZFC, directly implies our very similar Theorem 6.3 for which we have no ZFC proof. On the basis of the close structural similarity between these two theorems, we conjecture that Theorem 6.3 is also independent of ZFC. However, Theorem 6.3 also follows directly from “subset sum is solvable in polynomial time.” Of course, if our conjecture is true, “subset sum is solvable in polynomial time” cannot be proved in ZFC.

Received 14 March 2018

Published 23 May 2019