## Erdösproblem 3, part III

So far I found about $10$ more, what I like to call, NP-primitive counterexamples to the question asked here. When do I call a counterexample NP-primitive? When it’s easy to show (by the reasoning from the previous post) that it’s indeed a counterexample and if no (strict) subset of it is a NP-primitive counterexample. And given a NP-primitive counterexample, it’s easy to construct other easy to check counterexamples. The question now is of course: are there infinitely many NP-primitive counterexamples? Conceivably, this is not too hard. The ones I found so far:

$\{2,3,4,5,6,8,9,10,12,15,16\}$
$\{2,3,4,5,6,7,8,9,15,16,24\}$
$\{2,3,4,5,6,7,8,9,10,15,230\}$
$\{2,3,4,5,6,8,9,10,12,15,18,180\}$
$\{2,3,4,5,6,7,8,9,14,15,31,2474\}$
$\{2,3,4,5,6,7,8,9,11,15,75,8153\}$
$\{2,3,4,5,6,7,8,9,12,13,93,44155\}$
$\{2,3,4,5,6,7,8,10,12,14,60,105\}$
$\{2,3,4,5,6,7,8,10,12,15,42,210,420\}$
$\{3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,21,72,453\}$
$\{3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,21,30,154,315\}$
$\{3,4,5,6,7,8,9,10,11,12,13,14,15,18,20,24,30,840,450450\}$

And you can even make more by e.g. replacing $60$ in the fifth to last set with $120$, $140$ and $840$. A more general, and to me more sensible, conjecture of Erdös, Graham and Spencer is the following:

If $\displaystyle \sum_{i=1}^k \dfrac{1}{x_i} < N - \dfrac{1}{m}$, then the $x_i$ can be split into $N$ subsets
$A_1$, $A_2$, .., $A_n$ such that for all $j$ with $1 \le j \le N$ we have: $\displaystyle \sum_{a_i \in A_j} \dfrac{1}{a_i} \le 1$, as long as $m$ $\le 30$.

This is known for $m = \dfrac{7}{2}$ (see here) and $\{2,3,3,5,5,5,5\}$ shows that $m = 30$ is tight. Very probably this conjecture is cute enough to deserve a closer look at sometime.

EDIT: A counterexample to this last conjecture was found by Song Guo (Electronic J. of Combinatorics 15 (2008), #N43). You can find it online, if you’re interested. That paper also refers to other articles about these conjectures. The main question of finding the maximal $m$ is still open, in any case