Networks of Oscillators That Synchronise Themselves - Prof. Steven Strogatz - The Archimedeans

so before we begin just a small announcement uh as you all know eureka 66 is still up for sale so please contact the committee if you would like your copy of our own magazine and this talk will be recorded i still encourage all of you to keep your camera on so today we have with us uh dr steven strogatz who's a jacob ghoul sherman professor of applied math at cornell university and he has been a martial scholar at trinity college cambridge so he was with us here for two years his research includes problems in non-linear dynamics and mathematical biology in particular the collective behavior of oscillators something which he'll be talking about today so on that note we are very glad to have you with us today stephen thank you parth i'm very happy to be back and uh archimedes is one of my favorites if not my favorite mathematician so it's a special honor to be able to speak to the archimedeans um all right let me begin by sharing my screen one of these uh fine gentlemen is actually here with us today professor alex townsend i see his face hey alex alex also spent some time at cambridge and um he is a citizen of the uk so anyway alex was the lead author on this work that i want to describe to you today about dense networks that don't manage to synchronize and sparse ones that do mike stillman is another one of our colleagues in the math department at cornell who is our third author on this paper so the setting as part mentioned i've been interested in oscillators in biology for a long time and so you've probably heard of this incredible phenomenon of fireflies in southeast asia in places like thailand or malaysia that every night gather in the mangrove trees along the rivers and tidal rivers that lead out to the sea and they will the male fireflies will start to flash in sync with one another so if you've never seen it it really is pretty amazing but um here's an example let's look in the top left you may get the sensation that it's not really perfect synchrony that they're not all flashing at the same time but but there appear to be waves of light propagating along so that is one possible coordinated behavior of the fireflies wave propagation sometimes they do seem to all flash in unison it's a little more dramatic and conspicuous in a way if you look at this next example of neurons in sync here the neurons wouldn't normally be visible as they're firing they wouldn't flash like the fireflies do but these neurons have been treated with a calcium sensitive dye so that whenever they fire when they fire then this calcium sort of lights up and you can actually see them flashing all pretty much simultaneously these are neurons that have been grown in a dish neurons taken from the thalamus or the cortex of a mammal all right so anyway there are lots of examples of synchronization in the natural world and um what we're interested in here today is under what conditions will all the oscillators in a big population end up getting in sync all flashing at the same time so the description that i'll be using frequently is a picture like this one where rather than dealing with the the details of real neurons or real fireflies um we'll think about an abstract point running around on a circle i see there's a remark in the chat already let's see if it's something i should be paying attention to yeah sorry yes that's yuri making a good comment that yes i love it if you ask questions during the talk please don't let me just um power on if you have uh you can raise your hand you could put something in the chat i will look from time to time you could even call out verbally i wouldn't mind i'd like it to be as interactive as it can be so definitely don't save your questions for the end okay yeah thank you yuri good point so anyway you know there's this thing people talk about the color wheel roygbiv red orange yellow blue green indigo violet and violet is sort of perceptually close to red so colors on the color wheel and code the phases of an oscillator moving around a limit cycle through its state space in a very nice way and so i'll make use of that we're going to represent an oscillating system by a point running around a circle and so um there you see an abstract you know just an arrow moving around a circle but notice the way the colors are changing through the color wheel so that's going to be the code that we'll use when we want to show oscillators getting in sync you'll see them behaving with the same color at the same time for instance look at the complicated graph in the lower right where you've got um lots of different oscillators at different phases the graph is showing which ones influence which other ones sort of which ones are connected to which so it's some complicated graph but and at the moment they're not in phase but if i let it run very quickly they all manage to get in phase with each other get in sync so that's the kind of behavior we're going to be interested in systems that spontaneously synchronize like that all right now the math behind this is um based on a model proposed by a japanese statistical physicist named yoshiki kuramoto who is still alive must be 80 something years old but back in 1975 he proposed a really nice elegant and mathematically tractable model of systems of oscillators that can spontaneously synchronize and so let me walk you through the main ideas of it here's our theta the angle on the circle um running around on the circle at some rate d theta by dt and it runs at a rate omega that's its natural frequency and we're going to assume that all the oscillators i going from 1 up to n so there's n of them they all have the same natural frequency omega so they would all tend to run at the same speed but there's interactions between them as encoded in this term now what's going on there is those are terms that tend to make oscillators either speed up or slow down in such a way as to bring them potentially into synchrony with each other so first of all there's a term aij which you should think of as being filled it's a matrix filled with zeros and ones zero means that i and j are not connected to each other they don't influence each other that would be like fireflies that can't see each other or neurons that are not connected by a synapse or by an electrical connection called a gap junction so if it's a zero they're not connected if it's a one they are connected with unit strength so i'm going to assume everybody is connected with the same strength if they're connected at all just a unit positive strength finally there's this sine term which is sensitive to the phases of the oscillators it knows about their thetas and it has the property that i just picture two of them to understand what's going on think of theta j and theta i as being two points on a circle like runners running around a circular track and um if j is a little bit ahead of i so that this is a slightly positive number then you would get sine of some positive number slightly positive which would itself be positive and so the net effect of that interaction would be to add a positive contribution to this omega now remember i said think of i as being a little bit behind j as they're both running around the track and so that means that this interaction will tend to make the slower one the one that's behind speed up right it gets a positive increment to its omega so to make the laggards speed up and it actually makes the um faster ones that are ahead slow down so it tends to bring them into phase that's the effect of the sign coupling uh what else to say about that i guess that's it really but maybe one other thing to mention oh yes i was going to say the aij should be symmetric so if i is connected to j with unit strength j is also connected back to i with unit strength but was there a question or a comment oh yeah sorry um can i ask um so just looking at the formula for these oscillators it seems like if uh two oscillators aren't not in phase but um and uh what's the term so in an office phase yes an antiphase then that also seems like a stable point good point interesting do we already get it if you're observing that if these phase differences are pi then there would be no is that what you're interested in yeah yes yes i was wondering do we get an effect that sometimes rather than uh coming into sync is okay it's interesting i mean you can you could certainly set up lots of thetas to be either zero or pi or to differ by amounts equal to zero or pi and then they would all run at the same omega but of course they would not be in phase and so that's an interesting issue is a state like that stable if perturbed a little would it come back to that state or would it go away and go to something else so um i mean as your question anticipates there are many possible equilibrium configurations in the sense that i mean by equilibrium not exactly equilibrium because they'd all be rotating at speed omega but but in terms of relative equal relative positions they would be in equilibrium and so we have to consider the stability of states like that as well as others that we're going to discover right good question other comments or questions okay so anyway those are the governing dynamics for our system and keep in mind i mean this n as you can see in these examples are you know 50 44 or 50. these are big dynamical systems so if you take the cambridge part it used to be a part 2 course on non-linear differential equations um or now is there a part two course called dynamical systems i suppose there probably is yeah maybe paul glenn denning teaches it or herbert huppert or someone like that um i don't know those are people who used to teach but and that's where i first learned about differential equations that course part two um that course focuses a lot on systems of dimension two or three meaning like in this in this language it'd be like two or three oscillators at the most so doing something with 50 oscillators is a kind of cutting-edge branch of dynamical systems this is a research topic that is is not the standard thing in a beginning course on the other hand because the system is so simple you'll see there's a lot we can do with it analytically okay so anyway let me show you some examples here's a complicated network a random network where every node is connected to every other node with some probability here chosen to be one-tenth so most of the edges that could be there are not present but so like i say probability one-tenth of connection between any pair and then watch what it does as i let it run you see that that's apparently sufficient to cause the system to get into sync that that level of connection now here's an interesting graph where uh there are 44 oscillators and you see a big black mess what's really going on is that there are many straight lines showing connections but there's so many in fact that you can't really see what's going on it's a very densely connected graph and yet it turns out this one will not spontaneously synchronize we've set up initial conditions where the phases run through a full cycle as you go around the ring and those phases will stay like that over time you actually get the sensation of a mexican wave running around the ring where i'm using the term mexican wave to refer to the thing that you may have seen at football games or to an american soccer games where the fans will all stand up and then sit down you know causing a wave to rotate around the stadium so you can have these mexican waves and sometimes they're stable look at this next example in the graph that just is very sparse only connected each oscillator only connected to its nearest neighbor on either side that can also support one of these mexican waves that thing will just be stable and run around and if you perturb it slightly it'll come right back so we can see lots of different kinds of behavior either dense graphs that don't synchronize sparse ones that don't dense ones that do let me see what i've got in the chat other maybe comments coming up is there a reason why we use the sine function as rubiot rather than just theta i minus theta j that's a good question yes you could certainly use a linear function meaning just get rid of the sine function like you're taught in in classical mechanics courses to take the small angle approximation for a pendulum and replace sine theta by theta so the natural question might be why don't we do that here we could just have theta j minus that theta i you could do that and you're right that would be very solvable that's a linear system that you could just quickly write down the answer for it turns out that doesn't have very rich dynamics though that system will um i think it will pretty much always synchronize so you don't get anything interesting happening there the other thing is that theta should not really be regarded as a real number you should really think of theta as belonging on the circle um and the function you know theta is itself sort of strange because of multi-valuedness between zero and two pi like should you treat those as the same state or not it's a little bit unnatural in a way to to get rid of the sign but but you could and you're right it's very solvable um let's see joe asks wouldn't that make it more complicated as well because you'd have to work mod 2 pi right getting the idea there how does the initial condition affect the equilibrium state of the two circles asks william ah these two the dense one versus the sparse one well that's a good question and that's part of what we'll be discussing right so here i've chosen the same kind of initial condition for both but we want to get a global understanding of what happens for all kinds of initial conditions so i don't want to jump ahead just yet i'll i'll be getting to that uh yes please go ahead yeah i so could it be instead of like density the the factor that decides the syncing up is the symmetry of the graph because in the other two you can think of the pull from either side being the same so it would not want to go to any particular equilibrium nice right so these are very symmetrical networks whereas this one is not could that be the me the main issue symmetry um what the honest answer to these things is that there this is a vast wilderness to explore the the behavior of large systems of coupled oscillators even though it's about 50 years old as a subject you can still ask questions like the one you just asked and we don't have full understanding even today so i will be discussing later some very highly symmetrical networks where we can make use of the symmetry to find exact results explicit results for the eigenvalues that govern stability in this problem so symmetry has its advantages and that we can do a lot of explicit you know calculations on the other hand generically you don't expect symmetry so what happens as you depart from symmetry um it's not fully understood i don't really have much to say except that you know please explore these things on your own afterward um yeah a lot to do here okay so let me let me move along then um oh where am i yes so next um this idea of global synchronization we've already seen that there can be these states like yuri asked about with zeros and pies so you can't possibly expect every point in state space meaning every combination of thetas to lead have trajectories or solutions leading to everyone in phase we know there are equilibria that you know will not have that they'll just just sit there so that would be too strong a notion of global synchronization but those points are kind of exceptional and so what we mean by globally synchronizing is that in the long run all the oscillators will end up in phase except possibly for a set of measure zero um you can't rule that out definitely have those exceptional cases but still if you were picking points at random you'd have zero chance of hitting those so in that sense they're negligible so synchrony with probability one is what we're going to mean by global synchrony and so the two questions that arise are suppose you wanted to make i mean the intuition is dense graphs tend to globally synchronize and sparse ones tend to have other attractors other types of long-term behavior but you could ask what's the sparsest graph that globally synchronizes and what's the densest one that doesn't so it turns out question one is not super interesting as posed and we can dispense with it pretty quickly um there are ways of refining question one to make it more interesting but i don't think i'll be getting to that today but but really the juicy question that we want to focus on today is this question two which is what is the densest graph that does not globally synchronize that has other attracting states at least locally attracting so this question has been studied a lot um you can see lots of results including especially lots of recent results here in 2018 there was a breakthrough by this group from new york university led by ling um alex townsend and i and mike stillman have some results just from a year ago lou and steiner burger i mean this has become hot recently so i'll tell you why as we go all right so first though the easy part sparse graphs that do globally synchronize well again let's first clean up the system as written i mean this was the system we wrote a few minutes ago and the fact that everyone has the same frequency omega suggests a kind of natural move which is to go into a rotating frame co-rotating at that frequency because then we can get rid of that omega in other words if i define a variable theta i hat to be theta i minus omega t you can see if you substituted for theta i that would produce theta i hat time derivative plus an omega and that omega will cancel this omega while in here we would just get a theta j hat minus a theta i hat because the common omega t would cancel out when subtracted so you reduce the system then to something that looks like this in terms of the theta hats you've managed to get rid of the natural frequency the advantage of that is that you know whereas if i look at this graph with all of its phases and i let it run it does some kind of complicated thing that even though it's in phase those are phases are continuing to evolve they're continuing to blink in the theta hat representation what you would see is that everyone has just come to a fixed level right all these oscillators would just converge to the same values they might be separated by two pi now remember on the circle that will not show up as any difference because they'll be the same color so here you've got a lot of reds but they do differ by 2 pi but we don't really care about that so anyway in this representation with the theta hats the problem has boiled down to looking for a true equilibrium states of a dynamical system which is a very manageable problem compared to looking for periodic solutions all right so now we've boiled it down to this little system and it has a special property which is that it is a so-called gradient system it can be written if i think of the this side as a vector you know collect i from 1 to n i write it as theta under bar hat the time derivative of this vector is given by the negative gradient of a certain potential function this expression written here with the cosines and um gradient systems have a very favorable property which is that on a gradient dynamical system you can show that the potential behaves monotonically in time as as time evolves uh the state of the system just keeps moving to lower and lower potential just flows downhill on a potential landscape ending up at an equilibrium point which is either a saddle point um or it could even be a a local minimum but that's it you can't have any kind of more complicated behavior than equilibria in the long run in a gradient dynamical system in particular you cannot have periodic behavior because the potential keeps going down as you move so you couldn't come back to your starting point because you'd be at strictly lower potential so there are no periodic solutions in gradient systems there are no strange attractors or chaos or anything interesting all you have is fixed point behavior equilibria in the long run and so that means that we can analyze the long-term behavior by just looking for equilibrium points which in this representation correspond to just setting the right-hand side to zero so we've boiled the problem down now to looking for the zeros of this complicated function and we want to in particular look at the stability of those equilibrium points and ask are they stable to small perturbations or not that's controlled by looking at the linearization of this system about its equilibrium point um which is given by something called the jacobian matrix this matrix of partial derivatives at the equilibria and so you get an expression that looks like this okay so and i mentioned earlier aij will be taken to be a symmetric matrix of zeros and ones throughout this talk and so that means that this j sub j k is itself a symmetric matrix and so why that's interesting and important to notice is that we're going to be concerned with the eigenvalues of this jacobian matrix that's what controls the stability of the equilibria and since we're dealing with a symmetric matrix there's a basic theorem in linear algebra that that the eigenvalues of a real symmetric matrix are themselves real so we don't have to think about complex eigenvalues we're just going to have either positive or negative or zero eigenvalues okay so with that in mind now we can answer this question what's the sparsest possible synchronizing graph imagine i have n vertices and i want to make this system globally synchronizing i can do it by just adding edges until i make a tree like shown below structure with no loops in it you can check that on a tree any tree is automatically globally synchronizing because you can calculate all the equilibrium points very explicitly assuming some value for the theta 1 hat then you can derive all like say knowing that this one is whatever some value in order for equilibrium to be satisfied this one here has to be either zero or pi out of phase with that one for the sine function to be satisfied right along this edge and then likewise this one has to be zero or pi out of phase with this one and you can just argue your way through the whole tree like that so the whole structure is just zeros and pies different from the initial or the the first theta but then it's easy to check the stability of all of those and the only one of those possible equilibria that's stable is the one where everybody is exactly in phase where they're all equal to theta 1. if if any of the theta j's are different from the theta one there's a eigenvalue bound um that you would learn in a nice course in linear algebra or numerical linear algebra that you can guarantee there will be an eigenvalue that's strictly positive that's greater than this certain uh ritz estimate for assert you can plug in a certain eigenvector and use this bound so anyway the point being none of these other states could possibly be stable they all have at least one positive eigenvalue so trees are the sparsest synchronizing graphs they are automatically synchronizing and you can see this tree quickly gets itself into zinc all right so trees play a special role in the rest of the analysis because if i have some complicated structure like this and then i append say a single node with a single edge or in general even if i add a tree to some complicated graph i don't want to go through this whole diagram with you here's the take home message of the diagram [Music] appending a tree doesn't change stability globally if you append a tree if the original system was globally synchronizing it will still be globally synchronizing even with the tree attached and if it was not globally synchronizing because it had other attractors the same will be true with a tree attached okay a tree doesn't change anything that that can be shown by further linear algebra kinds of arguments um rayleigh quotient and herman vials eigenvalue inequalities so here's a little example i'm running a little simulation down here or did i already run it no there um you can see something that has its little mexican wave but um having that extra node attached to it didn't do anything much right that's that's still got the mexican wave so think up or did it sync up did it sync up locally though yes this part on the tree did i mean that little edge did but the rest of it you can see still has its colors is that what you meant yeah that's what i mean good right um good maybe there's another good time to pause for further comments or questions at this stage okay so i'll keep moving the the point about trees though is not that i can add trees it's more that i can delete them so when we have complicated structures and we're interested in their stability their global synchronization properties we can sometimes answer how whether or not they're globally stable by clipping off a tree and reducing the problem to a smaller structure and then if that smaller structure is known to be globally synchronizing then we know the bigger one was too all right so next um now the good part let's look for dense graphs that don't globally synchronize so there are some things known back in 2006 i had a couple of grad students dan wiley and michelle girvin who um we were interested in these kinds of structures where you have a node connected to not just its nearest neighbors but all of its nearest neighbors out to a certain distance like in this diagram there's 32 oscillators each one is connected to 10 nearest neighbors on either side so each one has degree 20 right 10 10 connections on this side 10 on that side and that's true for everybody everyone is connected to their 10 nearest neighbors on either side it forms this pretty dense symmetrical graph and this one does not globally synchronize it supports one of these mexican waves that is attracting so there are relatively dense graphs that don't globally synchronize on the other hand if a graph is sufficiently dense it is known that it will globally synchronize so back into 1994 my student shinya watanabe and i showed that if a graph is complete meaning every node is connected to every other node with unit strength so there the degree of each vertex is just the number of oscillators minus one so the minus one you're not connected to yourself you're just connected to everybody else that's what we have we'll assume that throughout the talk um in that case the fully connected graph we could prove that that globally synchronizes and that was sort of the state of the art for a while until a really nice breakthrough result by richard taylor in australia this is not the famous richard taylor of um fermat's last theorem fame this is the less famous richard taylor who is an australian mathematician who showed that you didn't need to go to fully connected even if you were only 93 connected meaning every node is connected to at least 93 percent of all the others that ensured global synchrony no matter how the pattern of connections was laid down so you didn't have to pick a symmetrical 93 it could be any 93 or more was enough so he showed that with some nice linear algebra arguments i see a comment or question here in the chat let me see what it is if you just consider graphs like the n equals 32 and degree 20 graph is there a pattern to when it becomes synchronizing that's what we're going to do in the rest of the talk um these this class of graphs that joe asked about are circulant graphs highly symmetric graphs with this circulant symmetry and so yes i will be looking at that soon so you've anticipated where we're going if i can help you let's go ahead um is there some kind of notion of always being globally synchronous i mean um a positive density um we take a certain graph property that is dependent on the number of vertices let's say the density of the graph is um n to the power three half and then you take asymptotically and then a random graph with that and then go to infinity and then you want almost all of the graph to be thinking this is a wonderful question so you can you can read yes there are concepts like that um and i won't be touching on them today this paper i mentioned by ling and company from 2018 would be a good place to read they have some nice results about random graphs and results along the lines that you're suggesting um okay so yes these ideas can be you can give statements like like what you're asking for i think i don't know so my colleague alex townsend is here um he's shy but i might ask him to weigh in at this point do you want to say because alex has some results about random i should say random graphs since he is british alex do you want to say anything at this point about them no there's a car alarm going off behind me but uh yeah there's the the the ling paper the nyu paper uh does study random graphs and answers the exact question uh that's being made here saying if you're sufficiently dense and you let n go into infinity can you guarantee with probability one that your urdosh renni graph for example is globally synchronizing so that is exactly in this flavor of look studying random graphs uh with a certain uh connectivity property i think that's what the question was yes it sounds become completely connected when p when p with a probability of connecting two edges uh is above uh what is it uh n n over log n what is it or is it one over log what is it uh yeah just one over log n just don't forget just log one over again wait what yeah i think it's one over login and n log n n over log n is the total number of connections you need n over log n is the total number of connections so p equals one over log n so that's when it becomes connected but uh the gap is that we believe that as soon as you have a connected earth for any graph we believe with probability one it will be globally synchronizing as n goes to infinity but we don't know that for sure and the the theory that we know is that p is much the theory that rigorous theory we know is p is much larger than that so there's still a gap in our knowledge okay thank you know that's very interesting thank you both too always uh let's see so jason asked the question where does the 0.93 come from is it related to any fundamental constants well i'm not done yet no it's not related to fundamental constants um it's related to the temporary state of knowledge back in 2012 it was based on estimates um trying to control the pr where the spectrum was you know you're trying to keep this the spectrum of this certain symmetric matrix in safely in the left half plane and depending on your skill at linear algebra taylor got this bound to 0.93 but laying this paper i'm mentioning from 2018 did superior uh linear algebra by by working with matrices directly um they're just very good at this kind of work and they were able to shave the number down to 79 and then there was this incremental progress very recently where lou and steiner berger brought it down to 78.89 percent so this is what's happening right now in this field can we br how low can you bring this this constant this pre factor um within this world of deterministic graphs now the question that was asked just a minute ago will also raise this other issue of random graphs which is another interesting direction but anyway the flavor is sufficiently dense graphs will globally synchronize but how dense is dense enough so that's what we want to talk about next so um the state of the art is it's synchronizing if the vertices have all have degree greater than if everyone's connected to at least you know about 79 of the rest on the other hand i mentioned earlier that my students and i showed that there's graphs with about 68 connection to everybody else that don't globally synchronize so there keep those two numbers in mind 68 and 78 somewhere in between we think there's there should be some magic number such that above that number every graph will globally synchronize and below that number there will be counter examples so um there there was this earlier question about the kind of graphs that look like this we're going to call them wsg graphs because people do now in honor of my two students and me um wiley strogatz girvin is kind of embarrassing because they're just these trivial graphs with nearest neighbor connections out to some distance but anyway so they can support mexican waves um that can be stable ah keep doing that silly thing so there's a mexican wave on a little graph where you see each one is connected to its two nearest neighbors and also to its second nearest neighbors but not more here's one that we showed earlier with degree 20 on size 32 and that one has its mexican wave that is an attractor but notice this one's getting pretty dense this has like this number is 64 percent so getting close basically as you take this type bigger and bigger you can push this number up to 68 so the generalization of this family of graphs is um what we want to look at next these are these circulant graphs so i'll just kind of blast through this but here's where the linear algebra comes in if i try to write everything in terms of vectors so vector for the theta is a vector for the cosines that appear in the jacobian or the sines this system can be written this way in terms of the diagonal matrix of the cosines and the sines and so circulant graphs are ones that look like the ones we've just looked at that have this circular symmetry to them in linear algebra terms they have constant diagonals so these b's are either zeros and ones so like if it were all ones here for b1 that would mean everyone is connected to their first nearest neighbor on either side so it'd be ones here and ones here on the sub diagonal and then the same is true out on these farther diagonals either ones or zeros on each diagonal so examples of these kind of circular graphs are just nearest neighbor cycles fully connected complete graphs these wsg graphs where you that we've talked about anyway all of them um are diagonalizable that is we know their their eigenvalues and eigenvectors um very explicitly using the discrete fourier transform so consider a state like this this is the mexican wave written symbolically it says the first phase in this rotating frame now remember with the hats on them the first phase is zero the second phase is just some fraction of two pi so it's think of it as two pi over n right i divide two pi into n equal parts and then if p were equal to one that would be a state i would call a singly twisted state because as i go once around the whole ring i've gone through one full cycle of phase right so if you've pictured it it would look like a twisted ribbon with a full twist in it so p measures the number of twists or another way of saying it is it would be one full cycle of the red to violet color around the ring if p were two then you'd have two full cycles or two twists and so on so these are different twisted states and all of them turn out to be equilibria for these circulant graphs so i'll skip this so all the twisted states are our equilibria here are some examples of them notice this one goes through one full cycle of color this one goes through two because here you can see yellow going around i get back to yellow halfway around here i have four full cycles and each of them is a possible you know these are equilibrium states so the question is are any of those stable which of these mexican waves are stable that's one question so since we know the eigenvalues we can assess their stability there's some complicated formula but anyway you can write it down so given that we have so much knowledge of these circulant graphs and their eigenvalues we can now just brute force search over all possible circulant graphs up to let's say size 50. um going up to 50 there are more than 3 million of them different circulant graphs right i mean there's a lot of possibilities here's some examples of some so there's a lot to check but you can look for circulant graphs that would be maybe denser than anything we know about but that are still have stable mexican waves of some number of twists so that's it for each n each size try all the circular graphs of that size record the densest one that is non-synchronizing in the sense i mean all of these have a stable synchronous state don't get me wrong when i say non-synchronizing i mean they can also do something else that is stable okay so um here with n equals five that's a little one that that supports a mexican wave there you can see it doing its bit that's not very dense so what's being shown here is that number that we talked about the 68 to 78 percent anyway you get this complicated scatter plot of results maybe i should show a few more of them doing their things like here's a pretty dense one i guess that's the densest of all out to size 50. and so we get these kinds of results for the density that we can achieve just living in this sub-universe of circulant graphs now the upper bound above which we know everything is globally synchronizing is this number 79 percent that i mentioned has been slightly improved now to 78 something but basically this dashed line is this uniform upper bound above which everything is globally synchronizing if you want you can do a little better than that by sort of conditioning on n and asking what's the best upper bound using the techniques in this paper by ling but independent then you get this jagged upper bound above which everything is still guaranteed to be globally synchronizing up here but what you should be noticing is that there's this interesting no man's land or no persons land between the best information we have on the lower bound and the upper bound what's going on in between and so we don't really understand this to this day um so i'm not going to solve that for you because we don't know how that's the interesting open problem what's going on in there but we have some information and so i'm going to finish the talk by telling you what what partial results we have about what's going on in this middle territory okay so here's an interesting trick that allows for some improvement on what we can say just living in the world of circulant graphs at least what we did so far naively there's a procedure that i'm going to call twinning which is where you can take a node like say this yellow node in the box and replace it by two yellow nodes or three or as many as you like and what we're going to do then is i mean you could sort of visualize it this way imagine that this node is itself something that you could look at under a microscope and if you did that when you zoom in you discover it's not actually one node it's really two nodes but those two nodes are connected to the rest of the system in the same way that this single node is connected to the rest of the system in other words these two well they're connected to each other but like these two will also be connected to this sort of so to speak single green node right notice each yellow is connected to each green and so on and you can do that with any number so what i'm trying to say is i have a complete graph i think of each node as itself a complete graph of a certain size which is either size 1 or 2 or 3 or 10 and then i connect those complete graphs in a way that respects the original pentagon structure in this example if you do that then you can analyze the stability of this so-called twinned graph like it's a graph of complete graphs it turns out that the stability of of the twisted states for the twinned graph is the same as it was for the original graph but it's a strictly denser construction so you can given something that is globally synchronizing you can jack it up to have a higher density by doing this twinning maneuver okay so if you do that the density for the g taus this family grows up to this number one plus the degree of the original vertices divided by the size and so doing that kind of thing you can see all of these i'm now running through them they're all still supporting their mexican waves just like the original pentagon did okay but so doing that twinning construction you can take results that were sort of not very dense and then all of them become asymptotically denser so this is a way of building up to a slightly better lower bound um and so here's the best known upper bound we still have this gap of where we don't know what's going on but but using this sort of technique we can improve the best known result which was 6816 uh we can go up to well so this this is from this paper by canali and monzone they were the ones who had the twinning idea we can also do something a little more complicated twinning plus a little bit of additional edges if we add some edges in a certain elaborate but kind of contrived way we can barely improve what's known to 6828 but we're really struggling and and that's not helping us get close to this upper bound so we still have this i mean we're sort of like hungering for scraps on the table we really need a new idea to try to tighten these two bounds because i'm as again what i'm trying to do is i want the magic number which will be sharp that divides the two cases so we thought we had the answer but it turned out we were disappointed this is the way research goes we thought we constructed an example that was 75 connected asymptotically but that was nevertheless non-synchronizing we were so damn close so these graphs that that we constructed look sort of like this here's an example of one here's another example of one that's bigger you'll notice that these numbers are going up in density these have a really nice property all of their eigenvalues are not positive they're all either strictly negative but there are four zeros and those zeros are troublemakers because they don't tell you linear stability when you have zero eigenvalues you have to worry about non-linear aspects of the stability and we were hoping against hope that these states would be weakly stable that they would have you know good strong linear stability in n minus four directions and fingers crossed that they would be weakly stable in some non-linear sense in the other four directions that would give us a 75 connected counter example didn't work out that way it turns out if you let these run i mean it looks encouraging that state looks pretty stable i mean you can let it run a long time that one looks pretty stable it turns out though if you let it run long enough if you perturb away from that state by a small amount say ten to the minus six on a time scale of ten to the six if you wait a million time steps you will leak out along a weakly unstable direction and go to the boring all synchronous state so this example that we thought would work doesn't work it's so sad but it came so close that it leads us to conjecture that there might be some result out there that's asymptotically 75 connected that will in fact be stable but we don't know it's a conjecture we think there's a hope for that but we don't know so it's at the moment our best guess is 60 i mean our best result is 68.28 percent but we won't be shocked if somebody comes up with an example that's 75 all right so i only have a few minutes left and i want to just finish with this which is um the circulant graphs only take us so far let us try another strategy let us try to just exhaustively look at all kinds of different graphs with no symmetry and just see what we can say by focusing on small graphs using that thing i mentioned earlier about pruning away trees see if that can help us all right this requires very different techniques now we're going to remember we're looking at equilibria by looking at this system of equations that can be viewed from a standpoint of another branch of mathematics algebraic geometry you could write the sine functions of all these thetas as just a variable s so s sub i now means sine of theta i hat and c sub j means cosine of theta j hat and if you just do a trig identity on this from high school expanding it out you get a product of sine and cosine that means that algebraically speaking this system is a polynomial system for the equilibria it's in fact a quadratic system in the sines and cosines so our problem is to look for all equilibrium points they're roots of this big system of quadratic polynomials there's also the constraint that sine squared plus cosine squared is one for each of them so you have this big quadratic system and um wouldn't it be nice to find all the roots of that potentially very i mean like n if 50 you're dealing with a big quadratic system well because after all there's these aijs you know lots of zeros and ones still there are techniques in algebraic geometry for exactly finding all of the roots with guarantees i mean it's not just numerical in the sense of like numerical methods this is using strict results in algebraic geometry to certifiably prove that you've got every possible equilibrium every route and so our colleague this is where mike stillman comes in mike stillman is one of the world's experts in computational algebraic geometry and he has created this package macaulay too that uses grobner bases and other algebraic geometry things that i don't honestly understand but that he tells me and people who know reassure me he is getting every root the only problem is he can't do very big systems it becomes computationally intractable once the systems get too big so he can analyze like and they're also too many roots he can find every root for graphs of size like up to eight or ten or something like that but after that it's just too big still you can learn a lot by studying small examples so let's look at some small ones we know that a graph like this just two nodes that's completely connected that will synchronize by earlier results this is a tree so this will always synchronize this is fully connected so this will always synchronize right we have existing results so you can start listing what's known um trees we know synchronize this kind of thing i mean this one actually this is in fact just a tree so i don't need the pruning argument this is just one connected to sorry zero is connected to two one is connected to three you can unfold this this is just a chain of four this one though is interesting because this is a triangle with a single edge sticking out connecting to a single node so that's an example of a tree appended to a triangle i could clip off that tree and reduce to a triangle which i know is fully synchronizing by the complete graph argument so using this kind of argument i can do a lot except here's a case this is an interesting structure this is a cycle of four right if you unfold this it's just four connected in an ordinary cycle near his neighbor's cycle that's one of the problematic cases that has zero eigenvalues it has a negative semi-definite jacobian right it's not negative definite it actually has some zeros that can be proven by non-linear techniques that lee deville one of our friends came up with to show that this is in fact one of these disappointing cases where the mexican wave is weakly unstable it has a twisted wave it's unstable so this thing does globally synchronize so i'll be saying deville meaning these are candidates but they actually are disappointing they globally synchronize so finally these examples are too dense by the known upper bounds so they're ruled out and we can feed this one to mike stillman's computer package and that turns out to be ruled out what do i mean ruled out i mean all of these do not give us anything other than boring global synchrony all right so we can rule out everything up to size four now we can they all globally synchronize ho-hum now we can look at all the graphs of size five this is how many there are for undirected graphs non-isomorphic graphs of size five okay you can start playing the same game and again you can rule these out by trees these by pruning this by leigh deville's argument these are two dents these are ruled out by computational algebraic geometry this is the only interesting candidate for something that might have another attractor and it does this is the known pentagon that has a mexican wave okay but we already knew that so that didn't tell us anything and by the way this is not very dense so this is not of great interest but at least it's something that has another attracting state okay now you go to size 6. there start to be lots of graphs but again you can rule them out by the various arguments leaving you with three candidates and those three candidates are interesting if you look at them the first one has a mexican wave the second one is a mexican wave with a stub attached to it and the third one is something new the third one we're calling an exotic mexican wave there you can see it's a triangle attached to a pentagon and that actually has a structure that is not a boring mexican wave that one actually does something that we didn't know about before so mike stillman discovered that one for us through his methods unfortunately it's still very sparse and so using twinning and adding and all those i mean this doesn't help us there are some examples that could potentially help us that would give us dense enough structures but so far they've all turned out to be disappointing so we we have not really been able to use these methods to um improve on our best known result so far so that's as far as we've gotten we don't know what the densest graph is that does not synchronize um and i you know part of me wishes i could tell you the answer but part of me is happy that i can't because it's more fun this way right there's things for you all to do and maybe one of you will come up with a good idea for for beating the world record okay thanks a lot i'm happy to take any other questions or comments this is really interesting and yes if anyone has any questions please do ask um i think i'll start off now okay sure can you say something about um so you mentioned that as a problem of finding sparse graphs the decent crisis is boring if post is the way we did it but um how do you make it more interesting what type of things can we yes that's right it can become very interesting i did not plan on showing you this in this talk but i think if i jump out of this talk and open up a different one i could show you i really ought to add one more picture to this talk um i don't think i have it here do i no um excuse me for one second while i close this one and show you an other a different version of this talk where i have a picture that's relevant let's see here um so here's a version of the talk that alex gave which has a certain diagram i want to show so let me find it i think it's down it's in here it's one of these hidden ones there is that visible still i have something on the screen for you yeah can i not play that happens if i say play come on what do i need to do alex you need to say on uh unskip so if you want to skip okay you come back let's see hold on i need to go out of here sorry i'm not the best at zoom alternatively i can screen if you want i mean i could show it at this small scale if people can see it maybe i don't need to worry too um yuri is this visible to you yes this is not good enough i mean let me do that okay so the way of making a question interesting is allow one loop rather than saying a tree i mean trees are boring for the reasons i gave suppose you say what if i have a cycle like this and now i ask i mean we know that cycles can have these mexican waves but how many edges do i need to add to a cycle in order to destroy all the mexican waves stability i mean does that question make sense to you to destabilize all the mexican waves how many what's the fewest number of edges i could add to destabilize all of them and so our answer is that um we have found examples of graphs that are of size 2 to the m um but whose connectivity is asked you know this number i was talking about earlier that was 68 or 78 we can basically add so few edges just a logarithmically small number of edges that the density is effectively zero it's as if each one is so in other words nobody is connected to a an asymptotically nonzero fraction of the rest of the graph it's only logarithmic rather than growing like n and yet we we can destabilize all the twisted states so here's an example of such a very sparse graph um this one with 32 but degree only nine and none of the twisted states are stable for this so i guess if i play that i don't know will anything happen no not really but anyway trust me that none of the twisted states are stable for this um we believe that all these graphs are globally synchronizing however we don't have a proof of it because all we did was rule out the twisted states we did not rule out all the other possible attractors which could be some of these weird states of the type that mike stillman can find but that we don't have formulas for so so that's an interesting question what are the what's the smallest number of edges you could add to a cycle to be sure to destabilize everything we think that it's asymptotically zero will will be enough just logarithmically small number of edges would suffice yeah thank you yeah okay but we as i say we don't have a proof of that does anyone else have any questions yeah maybe if i can go ahead sure yeah um have anything been attempted with trying to instead of having normal um what are they called the matrices for the class so adjacency matrices you have weighted adjacency matrices because i could imagine if you have a system where you have you know a large clique that should all kind of stay correlated and do the same thing and you want to replace it by one point which is connected to all the others multiple times um we have not done that that's of course a very good idea we've we've done the absolutely minimal thing where all the edges are one or zero and including weights of course opens a big universe of possibilities um there there is some literature about weighted graphs and all but not in this context as far as i'm aware so that would be an open area i i'm not i mean alex do you know of anything or does anyone else i don't know if results in that direction well i know of nothing i mean it's going to get a lot more it's going to get a lot harder if we can't yeah simple problem and we haven't even attempted the more tricky yeah well i thought maybe it should be a good idea to simplify just because well at least if you have a large clique in like this kind of system does the clique tend to be in phase always yes i mean it would it just depends on how the members are connected to anyone else besides the clique so i mean one thing i've thought of as a to try to salvage that 75 result that i mentioned um i have proposed but we haven't done this yet that what if we allowed three strengths if we allowed zero one and epsilon or negative epsilon i mean i think there's something wrong with our formulation the sun the thing that's killing us and causing these zero eigenvalues is that the sine function has some extra symmetries in it it's extra degenerate we just have one harmonic you know from the standpoint of fourier series the sine function is very special it has one term in the fourier series so i think either we should make the sine function more general like we should perturb it with epsilon sine of 2 phi or or epsilon plus other harmonics or we should make the edge weights not have to be strictly zero if we allowed some epsilons i think any of those kind of perturbations would bring us into i think we could prove a lot of the results we want and then show that our result with the 75 percent is sort of an edge case as epsilon goes to zero and we haven't done this but i think that would work on the other hand you could view it as cheating because we've changed the problem so that's the question i mean we would still like to solve the original problem and we don't know how yet but it might be a good strategy to enlarge the problem as you've suggested misha by allowing weights and i think it might be productive to just barely allow some epsilons um along with the zeros that might be something you could do thank you but but you could allow much more general weights too no thank you interesting answer yeah or maybe negative epsilons i think that might be helpful i'm not sure right now we have only zeros and positive weights on a related note so could you bring up the exotic mexican wave i think it's oh yes sure so that was from the one yeah okay yeah i'll find it that's from this talk and let's see so that's back yeah uh here yeah okay would you like to see it again um yeah that'll be nice sure good okay yes did you want to i think what has happened is the the three the triangle on the top has synchronized up right and so what my what i was trying to get at was if we could somehow group up the parts that get locally synchronous and then if we would consider this triangle as a singular node then what we are left with is a four cycle but now the triangle is somehow adding a weight to the pull so that the four cycle becomes a stable equilibrium of the mexican wave so um it's an interesting idea but i don't believe it's true that these are actually all in phase i agree that looks like they're all red at the moment but um i think that they are slightly out of phase um it's not that these three can be collapsed to a node this came up the last time i gave this talk and alex came in and rescued me i think he said that because he's the one that computed this or made these movies these are now let's see the phase difference between these what what did you tell me alex these are 80 degrees out of phase yeah the ones on the outer loop are 80 degrees out of phase so like if i call this one zero this would be 80 this would be another 80 this way like negative 80. yeah and then the two on the on the triangle not not that edge but the one on the outside edges yeah that's 20 degrees out of phase 20. so yeah it's almost like two cycles struggling both with their own they're trying to make two mexican waves stable at the same time but neither one quite achieves yeah i mean so i tend to think of it as a triangle attached to a pentagon but alex has this nice point of view that this is a hexagon competing with a pentagon uh and that they each the hexagon and the pentagon are each trying to have their own mexican waves but yeah so these are not i mean what so these two are these two actually in phase no they're 40 degrees they are actually 40. yeah i think you should play that and then this is 20 here 20 on those edges 40 here and then 80 on all of those yeah right huh that adds up right 4 times 80 would be 320 plus another 40 makes 360. right so so 80 yeah 80 80 80 80 40 and then 2020 instead of 40. and we can do larger examples where we stick two big cycles together with the connecting edge so like like a figure of eight and gets get globals get uh patterns forming just like this one okay yeah it's not too hard to make all kinds of interesting patterns with sparse graphs it's it's hard to make them with dense graphs that's the problem but yeah it's interesting isn't it yeah yeah let's see i see something going on in the chat which is um jan asks has there been any more precise comparisons between these graphs and physical systems of synchronizing oscillators not yet yeah not yet so this is extremely idealized for instance picking the all the frequencies to be exactly equal that gives us the gradient structure but in real life you know the frequencies will be slightly off and so any physical example will have non-identical frequencies and same thing with the edges won't all be exactly the same strength so we're really living in a pure mathematical world here but but still you know you can find a lot of literature about i mentioned kurumoto who gave us this this class of problems to think about kurumoto's model has been shown to relate to um superconducting devices called joseph's injunctions so i've done some work on them myself those are relevant to um detection of very tiny magnetic fields and so if you look up the literature on joseph's and junk actually josephson is a cambridge professor it's very appropriate we should be talking about brian josephson he's ice to my knowledge still alive brian josephson is a nobel laureate for his work on the discovery of what's now called the josephson effect done at the cavendish labs um back in 1960s he got his nobel prize in 1973 when he was only 33 years old i think and so yeah professor josephson is a great expert on superconductivity and he predicted this funny effect that if you have two super conductors very closely spaced by a with an insulator in between them cooper pairs of electrons can tunnel across this insulating gap it would be classically forbidden but quantum mechanically it's allowed and it leads to these amazing effects that are now called josephson effects that have lots of applications in of superconducting technology to all kinds of things detection of tiny electric currents magnetic fields they're used for instance to detect in a patient with epilepsy where they have an epileptic focus in part of their brain diseased tissue that could cause an epileptic seizure doctors can put helmets on these people and non-invasively detect where the abnormal currents are in the brain using the josephson effect to detect these tiny magnetic fields caused by these currents anyway so um i mention all that because in the josephson effect the sine function actually comes out of the quantum mechanics so it really is correct to see the sine function in that context but anyway let's see jason says is it going to look very different if the edge strengths are scaled up or down uniformly no that wouldn't make any difference so the zeros and ones don't cause any harm if we had zeros and twos it would be the same thing we can scale that out it will just change the time scale joe asks i said before that having x instead of sine x would be less interesting yeah are there other functions that give particularly interesting results well that's not really known um i would think for instance if you did sawtooth functions or triangle waves rather than sine waves that would still be probably pretty tractable you might even be able to do some piecewise linear analysis on that or or step functions might be tractable um but not much is known a lot has been done mainly with the sign function for good and evil it would really be helpful to do other functions it's kind of ridiculous the way research goes that that people make progress in one direction and everyone goes down that path very deeply but if you just stray off into a different path which is something that undergraduates are very good at you'll probably start making discoveries immediately you know because people have group think it's ridiculous so um you should do that seriously i mean the person who started the whole subject was my mentor whose name was art winfrey and so kuromoto was building on art winfrey's work and winfrey did all of this when he was an undergraduate actually at cornell um back in the 1960s he was the first one to study large systems of coupled oscillators which previous generations thought was totally hopeless because these big non-linear systems couldn't be analyzed but winfrey made a lot of discoveries because he was an undergraduate who didn't know better so you know let that be a lesson to you and if you want to read more about some of these people and their history i wrote a whole book about this called sync um not sync like kitchen sync sync like getting in sync sync and um you can learn more about who winfrey was and who kuromoto was and and this whole story it's it's pretty exciting okay so i think we should probably stop i've kept you long enough okay but i'm happy to take other questions um some some of the graphs you have shown if you consider the fireflies they cannot form into that graph uh-huh because why why do you say that about the fireflies um so if a point is connected so in terms of the fireflies if a firefly is connected to some of the other fireplace then these among those fireflies they should be connected some of them so imagine uh the fireflies connected to that particular five line it's like uh the points on the sphere then some of the points on the sphere will have a distance uh less than one which can be identified as connected okay interesting yeah so so i think if i understand your point you're you're saying that we haven't really talked about spatial structure particularly like we should be thinking about distance and spatial connectivity not just pure abstract graph connectivity um yeah i mean like in the case of the fireflies they often assemble themselves in trees along a one-dimensional riverbank you could approximate the problem by thinking of a chain one-dimensional chain of oscillators with certain maybe local networks in the chain or something and those often do support wave propagation but you could have more exotic things anyway it's it's really interesting to think about oscillators arranged on cubic lattices in three dimensions or on you mentioned spheres you could put them on any structure you want you could put them on manifolds and let them look at their neighbors out to a certain distance so there's a lot to do and people have done a lot but there's a lot remaining to be done another thing that's interesting is not if we use fireflies but if we use crickets i'm not i don't remember do we have crickets in england like in cambridge on a summer night would you hear crickets chirping you might right or or not i certainly we have them in ithaca new york but i mean why i mentioned crickets or i don't know if you would call them is that a standard concept i don't know where crickets live yeah okay so crickets can chirp in unison right they will sing and chorus in unison some species do and um but there this time delay due to the finite speed of sound is interesting so another generalization is to think of time delays in the propagation of signals um here we've assumed everything is conveyed instantaneously but that's not really true the speed of light is fast but the speed of sound is not so interesting questions would be like imagine a a group of people in a stadium and they're trying to clap in unison but there's a it's a very big stadium so the people far across from you sound time delayed right you don't hear their clap even if they're in sync with you it doesn't sound like that so thinking about these problems in the framework of time delay would be another very interesting problem much more complicated though you could also think of problems as uh spin hamiltonians right because the kurumoto model basically describes the process of gradient descent to like the minimum of the spin xy hamiltonian nice yes yes this is a very um dissipative dynamics if you did a hamiltonian dynamics excuse me it's a day of lecturing i'm losing it was your suggestion to think more about the hamiltonian version of this problem instead of the gradient version well i guess so i mean they're they're basically equivalent aren't they uh well hamiltonian systems conserve energy whereas these are are losing energy the gradient systems are dissipative right so if you had a second derivative if i had theta double dot rather than theta dot then you would be doing the hamiltonian version of the problem you would have a conserved energy so i maybe i should have said at the outset um these are extremely dissipative systems these these um are losing energy they are not you have to think of them as um sort of driven and damped they are not conservative systems so if we had replaced the theta dot like yeah it's a strange class of systems from the standpoint of classical mechanics you mentioned the xy model in magnets or xy spin systems so those are often studied in the dissipative limit where it'd be effectively like the spins have zero mass but if you have significant inertia so that there's a second derivative term an m theta double dot term that's another whole universe with different properties and if you have no damping then there are no attractors so the hamiltonian version of the kuramoto model would be complicated because the long-term dynamics of hamiltonian systems is more subtle than the long-term dynamics of dissipative systems but that's still interesting i mean you could try to do that problem too on all the various graphs and you know spatial structure so you can see there's a lot to play with here um but yes good good question what does energy correspond to in this setting the energy in the problem that we were doing yeah what what exactly is well if we okay so yeah let me go back to the governing equations we'll see um let's escape no oh wait what's happening why am i i would like to be able to scroll well i can always do it this way i suppose so um okay so yeah if you look at this system up here um you could sort of think of this classically mechanically as these terms like i i want to write m theta double dot like think of this as mechanically a damping term right this is a velocity so if i had a constant in front of it times a velocity that's sort of like a particle moving through a viscous medium experiencing a stokes drag proportional to velocity so you could kind of think of a damping term a frictional damping term a constant times a velocity there's an invisible mass times a theta double dot which would be a inertia term i'm trying to write f equals m a right so the ma would be this invisible mass times theta double dot there's a friction force there's this driving force so this omega is like a constant torque which is trying to make everything spin around on a circle and then this is a coupling interaction some kind of weird coupling force due to effectively like non-linear springs so the earlier question from the student who said get rid of the sine function and just make these thetas that would be like torsional springs between any pair of oscillators if you want to think of it as a mechanical analog and so anyway as to the question of what is the energy the the potential that i wrote down could be thought of as the potential energy stored in the springs except these are kind of like non-linear springs because of the sine function and there would be an energy associated with the work done by the torque there would be energy dissipated due to this viscous damping and then there would be kinetic energy due to the inertia which is not visible because the masses are all zero so yeah so there is a definitely a mechanical analog of all this in energy terms okay thanks a lot i think we should probably not keep you any longer very good okay oh it was a great audience thank you guys yeah thank you to everyone who came here and thank you once again so much professor strogatz it was a very interesting talk

Channel: The Archimedeans

Views: 5,196

Keywords:

Id: e5xxdNeNkmE

Length: 82min 18sec (4938 seconds)

Published: Tue Nov 03 2020