How many ways can circles overlap? - Numberphile

I want to tell you about a really lovely problem suppose you have a circle how many ways can you draw it well there's only one way I mean we could make it bigger we could make it smaller we could move it around the paper but there's only one way so the answer for one circle is one what if you have two circles they could be inside each other they could cross each other well they could be separated so for two circles three ways and I better tell you what the rules are we don't allow this kind of thing we don't allow two circles to just kiss they've got to make up their mind they've got to overlap or they've got to be separate no that's not allowed and when we get to more circles you're not allowed to have three going through a point that's not allowed either and what's more we're doing this on a piece of paper we're doing it in technically we're doing it in the affine plane we're not doing it on the projective plane if we were doing projective geometry we could take a circle and move the center out to infinity and it would become a straight line that's not allowed all you can do is move the circles around the radii don't matter you can make in big circles little circles I mean obviously this is the same as that or this you can move them around as long as they don't cross in mirror images count the same they're the same as the original picture we know what the answer is for two circles there are three what about three circles the answer is 14 and here they are so first of all obviously we could do three in a row three circles separate from each other or we could do three that are linked or we could do a nested pair and a separate one in fact we could take any of the three that we had for two circles and wrap a circle around them so we could do that one and put a circle around it so we'd get that or I could take this one and put a circle around it and we'd get that or I could take this one and put a circle around it and we'd get that and then we could put circle next to so now we have 7 1 2 3 4 5 6 7 we're halfway there this one here can be modified a bit a Meads be meet see see could mean a and we would get something that looks like this and we get a Venn diagram a B and C and they intersect in all possible ways but there's another way that could happen we could have don't forget that doesn't matter how big or small the circles are I've drawn it maybe I should have made the overlap bigger this is almost the same as the Venn diagram except there's no point where all three meet so we're up to nine and we need five more and I'll take another bit of paper I'll start off by drawing two that overlap and then I could put a third one there in inside one but not inside the other I could put a third one there so it crosses the line where this is inside that or I could put it inside the overlap or I could put it so the intersection looks like that and then there's one more its subtly different from that one looks like that and you can see here we had these two overlapping this one the third circle was inside the points where they met here it enclosed them so these two is strictly different of course you might think that I'm now gonna go and put the circle here for example but that's the same as this so there are just five more and the total is 14 that's pretty easy but not trivial to do easy to miss one if you start doing it the question is what happens next Jonathon Wilde professor of music at McGill University he has continued the sequence out to five terms and for four there are a hundred and seventy-three ways to do it and even for three yeah the rearrangements are quite pretty but when Jonathan Wilde classified the four circles and five circles the pictures some of them are really amazing they're just brilliant I mean this is mathematics this is geometry but the results and I'd like to show you this is the complete set of arrangements of four circles you can see you start off with four disjoint circles and then they can be nested in various obvious ways but when you get to more complicated configurations some of the arrangements are really delicate remember you can make the circles as big or as small as you like look at that one and going down look at these this is a very delicate configuration so we don't know we know the answer for five even more complicated and we know nothing more we don't have an upper bound for the number we don't ever know about I think it would be great to hang to draw the pictures to all 17,000 of the first five things and hang them along the Great Wall of China it's more than long enough you know what is it thirteen thousand miles or something so we'd have plenty of space but it would look awesome now this seems like it should be easier it seems like there's something there should be just some equation for you know when when the Sunburst circles is end you have you have this equation but it's not that you know it's not that simple no I mean one thing you can do is look at the pattern of intersections say we have three circles a B and C you could ask does a meet B does a meet C does a me be beat see you can write down what's called a truth table it's described by a boolean function which says which circles intersect the trouble is if you specify the intersections that doesn't tell you how to draw them and it doesn't tell you how many ways throughout and draw them it's really tricky there may be no ways Jonathon Wilde found the some arrangements of five circles that should exist but don't conceivably you could do the following you could have four circles which were linked in sequence in a chain we've got a b c and d four circles a meets BB meet CC meets d d meets a and the fifth circle would be like this you can draw it as an ellipse but you can't draw it as a circle that's e so the intersection Hatton's the ABCD IRA told you about e meets a and B and C and D and it contains the intersection of a and D and it contains the intersection of B and C it does not contain the intersection of C and D and a and B you cannot draw that Jonathon Wilde and his co-author showed that this could not be realized with circles it can't be realized with ellipses so as I said even if you specify the way these circles meet each other what you might call the boolean the truth table showing the intersection pattern and of course as you know if you have in this case five circles you draw a column and you mark it a B C D and E and then here you put a 0 or a 1 depending on whether they meet or not so for instance here a meets be true so 1 1 naught naught naught would get a 1 so for each of the possible and here we've got 32 all binary intersection so it's a function of five boolean variables whether they meet with that particular configuration or not so then it's described by a binary vector of length 32 and so the number of them is 2 to the 32 and for each of them well maybe you can draw it maybe not and maybe you can draw it in more than one way we don't know I always like having a look at the daily challenges here on brilliant and as we scroll down there's one that caught my eye for obvious reasons because it circles circles and triangles and hexagons oh my let's have a look at this one now let many of the daily challenges it starts off with something pretty simple we've got an equilateral triangle and a regular hexagon there and it says those dark blue shaded regions are similar so how does the area of the shaded region in that hexagon compare to the one in the Triangle what do you think is that one-and-a-half times bigger two times bigger three times bigger maybe even four times bigger this is just an example of some of the content you're gonna find on brilliant besides the daily Channel there's quizzes and courses and puzzles all sorts of great stuff a lot of it's free you can go and have a look straight away or you can sign on for a premium membership that gives you access to everything and if you go to brilliant org slash numberphile they'll know you came from here and you'll get 10% off a premium membership not a bad deal that brilliant org don't forget the slash numberphile and now thanks to them for supporting this episode it's a simple problem beautiful pictures wide open [Music]

Channel: Numberphile

Views: 627,616

Rating: 4.9293199 out of 5

Keywords: numberphile, circles, overlap, intersection

Id: bRIL9kMJJSc

Length: 9min 45sec (585 seconds)

Published: Sun Apr 14 2019

Reddit Comments

[u/Lopsidation]

"We don't have an upper bound"

Here's one. The answer for n circles is at most 7 * 13^{[3n + [n choose 2] + [n choose 3] - 1]}.

For 1, 2, 3, 4, 5, and 6 circles, this gives the bounds 1183, 33787663, 163086595857367, 1729451703514152748930891, 523807869048002546094002506312012987423, and 58905027078430733329427876756536270468302610141590543616567. So this is not a very tight bound.

Here's how it works. The placements of n circles can be described by 3n parameters: the radii and the coordinates of the centers. Let F, a subset of R³ⁿ, be the set of forbidden circle placements. That is, F contains placements with tangent circles or 3 intersecting circles.

The possible ways that the circles can overlap are the connected components of R³ⁿ\F, quotiented out by symmetries like mirror symmetry and permuting the circles. So, the number of connected components of R³ⁿ\F is an upper bound to the number of ways of arranging n circles.

Now comes the trick. The forbidden set F is the union of a set of polynomial equations. There are (n choose 2) equations describing circle tangencies, and (n choose 3) equations describing 3 intersecting circles. According to Mathematica, these equations have degree 2 and 6 respectively. Now we can bust out a theorem from algebraic geometry that upper bounds the number of connected components of R³ⁿ\F.

I have no idea what the state of the art is here, but naively applying the Milnor-Thom bound gives the upper bound above.

[u/pieinabutt]

So they said a professor of music did this, which is pretty cool. I wonder why a muscian would care about a question like this

[u/lamantigatto]

His voice is oddly satisfying

[u/OGOJI]

This was posted on twitter https://imgur.com/a/9EQqRZT

My question: In the end he says there could be multiple ways to draw a combination from the truth table, so do the graphs get rid of this problem?

[u/saucecode]

I've been studying a similar question for the past few months and not making any significant progress. It's an absolute godsend to see a similar problem being studied, and has given me some new reading/research to do.

The problem I've been working on is "How many ways can axis-aligned rectangles be connected?" Unlike these overlapping circles, there's a very convenient way to represent connected rectangles as [connected bipartite] graphs, and there are some pleasing parallels in enumeration techniques. A decent procedure for enumerating through every permutation, however, has completely eluded me. This video has at least confirmed for me that there is no easy way to do this.

If you were curious, there are 20 ways to connect 3 axis-aligned rectangles https://imgur.com/a/ztcUGGh

[u/im_mister_meeseeks1]

This was mind blowing for me

[u/newwilli22]

Does anyone know why he specified that this was in the affine plane? I can't think of any difference if these were considered in the projective plane

[u/Idempotents]

From the small sample the number seems to grow closely to the number of nonisomorphic semigroups

[u/JShrub]

What if you thought about it not by drawing the diagrams, but by putting restrictions on the distance between the centers of each circle with every other circle?