3
$\begingroup$

A Venn diagram is a diagram that shows all possible logical relations between a finite collection of different sets. (https://en.m.wikipedia.org/wiki/Venn_diagram)

It is easy to make a Venn diagram for three sets. Just draw three circles as shown in the figure. For four sets, it is getting more difficult. There are lot of possible ways making a Venn diagram for 4 sets (just check the wikipedia or imagine with four ellipses), but it is impossible to make it with four circles. But why?

I only know that it is impossible. I can prove it but my solution is really complicated (maybe wrong as well), but I think there might be an easy, beautiful solution.

Please help! Thanks in advance!enter image description here

$\endgroup$
  • $\begingroup$ With ellipses you can get four or five: en.wikipedia.org/wiki/… $\endgroup$ – Will Jagy Sep 16 '18 at 20:55
  • $\begingroup$ it's not clean, but it's very possible $\endgroup$ – Saketh Malyala Sep 16 '18 at 20:56
  • $\begingroup$ This isn't a set-theory issue and in set theory we don't care if the sets are circles, just that they intersect into $2^k$ sections each representing a state of being or not being in each of the $k$ sets. And you can (probably) always do that with some twisty curves as Donald Sputtlewit's answer implies. But for circes this is a purely geometric question. I think if you consider the points of intersection and three points determining a circle you get a contradiction. The hardest part would consistantly naming your 14 point of intersection. $\endgroup$ – fleablood Sep 16 '18 at 21:21
  • $\begingroup$ Well, I stand corrected. There is a simple set theory answer. As Lord Shark's answer shows. $\endgroup$ – fleablood Sep 16 '18 at 23:27
3
$\begingroup$

Two circles can intersect in at most two points. If you have $n-1$ circles, then adding an $n$-th will introduce at most $2n-2$ new intersections, and so the number of regions can increase by at most $2n-2$.

With three circles, one has at most eight regions (why?). Adding a fourth will increase the number of regions by at most six, so we get at most fourteen regions. Not enough.

$\endgroup$
  • $\begingroup$ @fleablood Unless the new circle is contained entirely within one region, the $k$ points of intersections of the new circle with the old circle divide the new circle into $k$ segments, each of which crosses a region of the old arrangement dividing it into two new regions. So the number of regions gained is at most $k$. Splutterwit's answer is bogus, as the red curve isn't a circle. There is no way adding a fourth circle can give eight new intersections. $\endgroup$ – Angina Seng Sep 16 '18 at 21:29
  • $\begingroup$ @fleablood You don't need as many intersections as regions, since one circle gives you two regions with zero intersections. But to get the next six regions you need six intersections.Donald Splutterwit got eight intersections by intersecting the lower right circle four times. $\endgroup$ – David K Sep 16 '18 at 22:01
  • $\begingroup$ Okay, I misunderstood your argument. $\endgroup$ – fleablood Sep 16 '18 at 23:24
  • $\begingroup$ Your argument is really clever once I got it. $\endgroup$ – fleablood Sep 16 '18 at 23:31
1
$\begingroup$

This question was asked before on stackexachange. The answer is to use Eulers relation for plane graphs: http://www.ams.org/notices/200611/ea-wagon.pdf

faces = 2 + edges - vertices

Two circles can intersect at at most 2 points. Thus 4 circles intersect at at most 2 + 4 + 6 = 12 points (you have to start with one vertex by default, to make Eulers formula hold). The version with 12 intersections should have the most faces, every time you have less intersections, you also have less faces (I hope thats right, I am tired).

max faces = 2 + edges - 12

So we only have to figure out the number of edges a graph of four circles can possibly have. Assume you have a graph of n circles and you add one circle. This will add new edges, depending on how many new vertices we have. On the new circle itself it will add at most 2n new edges. Every time the new circle "cuts through" an existing edge, he will devide this edge, creating at most one more in total. Thus, at most 2n + 2n = 4n new edges.

Start with one circle: 1 edge

Two circles: at most 1 + 4 = 5 edges

Three circles: a most 5 + 4 * 2 = 8 + 5 = 13 edges

Four circles: at most 13 + 4 * 3 = 25 edges

thus, max faces = 2 + max edges - 12 <= 2 + 25 - 12 = 15.

It seems like I overcalculated the number of possible new edges in the step from one to two circles. This is because the two new intersections must devide the same existing edge (there is only one) and therefore creating only one new edge on the first circle (+ the two on the second circle, thus at most three new edges in total). So the number of edges four circles can have at most is actually 24. But 25 is good enough to show that the diagram is impossible.

I hope I didn t write completely nonsense. Its pretty late now. Youre welcome to correct :) Eulers Formula is really elegant though, so you should be happy using it in one way or other.

Edit: I just realized there is a problem with Eulers Formula if you start with only one circle. So it is probably better two start with two. But the argument should look similar then, maybe +/- 1 face. gn8

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.