Georgia Institute of Technology College of Sciences

In the Rendezvous problem on the complete graph, two parties are trying to meet at some vertex at the same time, despite starting out with independent random labelings of the vertices. It is well known that the optimal strategy is for one player to wait at any vertex, while the other visits all n vertices in consecutive steps, which guarantees a rendezvous within n steps and takes (n + 1)/2 steps on average. This strategy is very far from being symmetric, however. E. Anderson and R. Weber presented a symmetric algorithm that achieves an expected meeting time of 0.829n, which has been conjectured to be optimal in the symmetric setting. We change perspective slightly: instead of trying to minimize the expected meeting time, we try to maximize the probability of successfully meeting within a specified number of timesteps. In this setting, for all time horizons that are linear in n, the Anderson-Weber strategy has a constant probability of failure. Surprisingly, we show that this is not optimal: there exists a different symmetric strategy that almost surely guarantees meeting within 4n timesteps. This bound is tight, in that the factor 4 cannot be replaced by any smaller constant. Our strategy depends on the construction of a new kind of combinatorial object that we dub”rendezvous code.”On the positive side, for T < n, we show that the probability of meeting within T steps is indeed (approximately) maximized by the Anderson-Weber strategy. Our results imply new lower bounds on the expected meeting time for any symmetric strategy, which establishes an asymptotic difference between the best symmetric and asymmetric strategies. Finally, we examine the symmetric rendezvous problem on other vertex-transitive graphs.

Though the modern analytic celestial mechanics has been existing for more than 300 years since Newton, there are still many basic questions unanswered, for instance, there is still no rigorous mathematical proof explaining why our solar system has been stable for such a long time (five billion years) hence no guarantee that it would remain stable for the next five billion years. Instead, it is known that there are various instability behaviors in the Newtonian N-body problem. In this talk, we mention three types instability behaviors in Newtonian N-body problem. The first type we will talk about is simply chaotic motions, which include for instance the oscillatory motions, in which case, one body travels back and forth between neighborhoods of zero and infinity. The second type is “organized” chaotic motions, also known as Arnold diffusion or weak turbulence. Finally, we will talk about our work on the existence of the most wild unstable behavior, non collision singularities, also called finite time blow up solution. The talk is mostly expository. Zero background on celestial mechanism or dynamical systems is needed to follow the lecture.