Combinatorics in ZFC limbo

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.

Full Text (PDF format)

Received 14 March 2018

Published 23 May 2019