So far I found about 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 in the fifth to last set with , and . A more general, and to me more sensible, conjecture of Erdös, Graham and Spencer is the following:

If , then the can be split into subsets

, , .., such that for all with we have: , as long as .

This is known for (see here) and shows that 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 is still open, in any case

### Like this:

Like Loading...

*Related*

This entry was posted on November 4, 2010 at 01:17 and is filed under Problem Solving. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

July 24, 2016 at 05:00 |

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?