4 ms·
I'm not the most mathy person in the world; can someone explain to me the following statement: "Exactly one of the following sets is in OBS4: 19x17, 18x17, 17x
by gort 17y ago
I'm not the most mathy person in the world; can someone explain to me the following statement:
"Exactly one of the following sets is in OBS4: 19x17, 18x17, 17x17."
If I've understood it correctly, OBS4 is the set of grid-sizes which are impossible. But if 17x17 were impossible, surely the bigger ones would be too?
[Edit to answer my own question: the OBS4 set seems to be made up solely of the smallest such grid-sizes that can be given without being redundant.]
- jules 17y agoSo if they say "Exactly one of a,b,c is in OBS4" then one of a,b,c is not 4-colorable?
- jrp 17y agoOBS4 is supposed to be a list of all configurations which deny 4-colorability for themselves, and any strictly larger (in both dimensions) configurations. Ie, if (19,17) is in OBS4 then (19+x,17+y) is not 4-colorable either. So given a shape (x,y) or even a more funky collection of grid points like a triangle, to know if it's 4-colorable just check for all X in OBS4, if you can fit X inside your shape.
- jules 17y agoGot it, although the more interesting property is that smaller shapes than those in OBS are 4-colorable? (because it is trivially true that if nxk cannot be colored then larger shapes can't either).
- jrp 17y agoRight, he has apparently solved and proved a short list for OBS3 with the property that X is 3-colorable if and only if X doesn't contain anything from OBS3.