Wikipedia:Reference desk/Archives/Mathematics/2018 July 29

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 29

Coloring 3-dimensional maps

Has anyone experienced with 3-dimensional maps so that no touching regions are the same?? Here's a proof that 4 is the minimum needed for a 2-dimensional map:

To prove it's impossible with one color, we simply need the statement that there's more than one region. That's easy!

Proving it's impossible with 2 colors is also easy; when 3 regions meet at a point, each one needs a different color.

Proving it's impossible with 3 colors is harder. If you read too much into the requirement, you might think that the presence of a 4-region vertex makes 3 colors impossible, but it doesn't! Why?? Regions that meet at a point may be colored the same; regions that have a line border must be colored differently. So we didn't prove 3 colors are impossible.

But 3 is still less than 4, so we still need a proof that 3 colors don't suffice. Examine a region surrounded entirely by other regions and color it red. The regions it borders (assuming it has no points where 4 or more regions meet) have to alternate (green-blue-green-blue.) If the total number is even it works, but if it's odd it doesn't work, proving that 3 colors are not sufficient, and thus 4 colors are necessary.

But what about coloring regions in 3-dimensional space?? What's the minimum number of colors needed?? (Note the definition of touching regions. Regions that touch must have a plane border; regions that meet at a point or line border may be colored the same.) Georgia guy (talk) 00:26, 29 July 2018 (UTC)

You can construct maps that require an arbitrary number of colors: simply take the the complete graph on n vertices and convert that into a map. Being in 3 dimensions means each region can border every other region, and you'll need n colors. –Deacon Vorbis (carbon • videos) 00:35, 29 July 2018 (UTC)

Can you show me a 3-dimensional map where 50 colors are needed?? Please note the definition of regions that touch. Two regions that touch means regions that have a plane border, such as 2 cubes that make a rectangular prism. Georgia guy (talk) 00:37, 29 July 2018 (UTC)

See the last paragraph of Four color theorem#Generalizations. PrimeHunter (talk) 00:41, 29 July 2018 (UTC)

(edit conflict) Just use $K_{50},$ the complete graph on 50 vertices. If you like, just imagine each region as a bead with 49 bits of string emanating, and have each bit of string attached to every other bit of string. The strings can have a bit of thickness and touch each other in a disk-shaped region. –Deacon Vorbis (carbon • videos) 00:45, 29 July 2018 (UTC)

What if the question is limited to partitions into convex regions? —Tamfang (talk) 06:17, 29 July 2018 (UTC)

In that section in the article it refers to a paper showing that even just using cuboids all oriented the same way one can need an arbitrarily large number of colors. Dmcq (talk) 09:07, 29 July 2018 (UTC)

How to approximate changes in edit count with changes in Wikipedia ranking

This is a question of curiosity on my part. It refers to the following Chart: Wikipedia:List of Wikipedians by number of edits. Every so often, I check my "standing" on that chart. I review my "rank number" and my "number of edits". The other day, I noticed something. I said to myself: It looks like every time I add another 100 edits, I move up in rank about 10 ranks. (I just now made up those hypothetical numbers. But, at the time, I had made an observation to that effect, with "real numbers".) So, my question: If one were to examine that chart as a whole -- not just for me, individually, but for anyone at all -- is there some mathematical approximation that can be calculated? Such that the approximation would state: "For every _____ additional edits made, a Wikipedia editor can expect to rise up approximately _____ rankings." Just curious. Thanks. Joseph A. Spadaro (talk) 14:47, 29 July 2018 (UTC)

Such a rule of thumb would only hold over relatively narrow regions. As you go up in ranks, individual ranks tend to be spaced farther apart, and as you go down, they tend to be spaced closer together. As far as how to approximate things like this, you would want to know approximately how edit counts are distributed. I'd suspect it might follow something like Zipf's law, but I could be way off, and I'm not enough of a statistician to really know how to check how well that would work. –Deacon Vorbis (carbon • videos) 15:19, 29 July 2018 (UTC)

Thanks. Joseph A. Spadaro (talk) 14:46, 2 August 2018 (UTC)