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:


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


One Response to “Erdösproblem 3, part III”

  1. Cheryl Ramirez Says:

    F*ckin’ remarkable things here. I am very glad to see your article. Thanks a lot and i am looking forward to contact you. Will you please drop me a mail?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: