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

Advertisements

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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s


%d bloggers like this: