Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Sep 17

The 15-point obstruction

Input, range, and conclusions

The fixed input is

E=\{3^j+kj:1\leq j\leq5,\ 0\leq k\leq2\} =\{3,4,5,9,11,13,27,30,33,81,85,89,243,248,253\},

the fifteen-point example of Grow and Whicher, whose proposition supplies the hereditary ratio, rank and three-coloring facts reproduced here.

Run, from the repository root,

uv run --no-sync python wiki/research/erdos_774/evidence/grow_whicher/main.py

The checker tabulates all $2^{15}=32768$ subsets by exact subset-sum bitsets and dynamic programming. It uses the standard library and the shared root tools checker, performs no random trials and needs no external solver, and finishes in a few seconds. Its named checks cover the subset count, rank, hereditary ratio, the absence of a proper two-coloring and the one-point deletion; a failed clause exits nonzero. The checked results are

\eta(E)=\tfrac12,\qquad r(E)=8,\qquad\chi(E)=3.

There are 7568 nonempty dissociated subsets. The first three assertions independently reproduce the full-source Grow–Whicher proposition.

Linked from (3)

Evidence Finite unions of quasi-independent sets Proposition (p. 490): a 15-element set with |F| <= 2|F'| for every subset that is not a union of two quasi-independent sets

Graph