Unexpected Connections In Mathematics
Connections in mathematics: games and graphs
John Nash is famous for his creation of what has become one of the central notions of modern game theory—his concept of what is a “solution” for a non-zero sum game. For this work he was awarded the Nobel Prize in Economic Sciences in 1994, along with John Harsanyi and Reinhard Selten.
Today I wish to talk about connections between problems in mathematics that are surprising.
Nash is famous for three things: his wonderful work on game theory, his wonderful embedding theorem, and his unfortunate illness that made him unable to work for most of his adult life. His embedding theorem proves that every Riemannian manifold can be isometrically embedded into some Euclidean space. This is a deep result—way out of my area of expertise. But the core is that a Riemannian manifold is defined abstractly without assuming that it lies in any ambient Euclidean space. Nash’s theorem proved that such a manifold could always be embedded into a Euclidean space. His original proof was quite difficult; later the proof was unravelled and it was shown that it depended on a new implicit function theorem.
One wonders what other great results he could have proved had he not been ill for so long.
During his illness he was a well known “figure” who spent much of his time at the main Princeton Library, Firestone. My wife, Judith Norback, has told me she often would see him, since she spent many days at the library. Her research required a great deal of “lit” review. I almost never saw him, since I spent my library time at the main mathematical library, which was located across campus.
Roger Myerson has written a paper on Nash’s life and work. Myerson points out that Nash’s work on game theory spread slowly. It started with a short note in the Proceedings of the National Academy of Sciences, which was published in 1950. His concept of what is a solution to a non-zero sum game is elegant, but elegant or not it did not cause immediate excitement. It is useful to remember this in our own research: often it takes a long time for others to appreciate the importance of a new result. Even the great John von Neumann did not acknowledge Nash’s concept quickly: Myerson states this:
The short perfunctory reference to Nash’s work in the preface to the 1953 edition of von Neumann and Morgenstern’s book is particularly disappointing.
Either von Neumann and Oskar Morgenstern did not understand the importance of Nash’s achievement, or 
Connections
In science, especially mathematics, it is reasonable to expect that different areas of research, even if they are “far” apart, may have interesting connections. Part of this is due to the beauty and power of mathematical ideas—there often is no precise demarcation between areas. Often a problem can be viewed, for example, as a question about a group, or a graph, or a set. Each view may yield different insights into a problem, and may eventually yield enough different insights to allow the problem to be solved; this fusion of ideas is often very powerful. We expect and welcome these connections between disparate areas, since they usually enrich both of them: ideas and methods from one can flow into the other. These expectations aside, we are still sometimes taken aback by unexpected connections.
One of the most exciting events in mathematics is when an area that seems very far from another one helps solve a problem there. For a concrete example: if the question, 
It is these connections that are the most exciting and the most fun. They do happen. Here are two that come to mind, I will add one that is the main point of discussion in a moment.
A recent book review in the Bulletin of the AMS is a great source of very interesting comments on the nature of connections. The review, by Joan Birman, is on braids, knots, and links. Birman is one of the world experts in this area, and has written a beautiful summary of some of the unexpected connections that this area has made with other parts of mathematics. I strongly recommend that you read her piece—perhaps I will discuss it in the future.
The Connection
The connection I wish to discuss is between game theory and a crypto-type problem. The latter is the so-called planted clique problem. Lorenz Minder and Dan Vilenchik have proved a neat theorem that connects this two areas—I find the connection surprising, and one that could have important consequences. (I should have pointed out that Elad Hazan and Robert Krauthgamer actually made the first connection here.)
In order to state their theorem I have to first explain what the planted clique problem is. It sounds a bit like a botanical problem, but is a natural question about the difficulty of solving the well known clique problem. Of course we have known for a long time that determining whether or not a graph has a clique of size 
Dick Karp first asked, in 1976, whether or not one could find a clique of size 
Lack of progress can often suggest that we modify our goals; hence the introduction of the planted clique problem. This problem is this: take a 
The connection of Minder and Vilenchik is to relate this problem to Nash solutions. In particular they prove:
Theorem: There exists a positive constant
so that if there is a polynomial time algorithm that finds in a two-player game the
-best
, then there is a probabilistic polynomial time algorithm that distinguishes with high probability between two graphs:
in
and
, an arbitrary graph on
nodes with a clique of size
.
Roughly, any good approximation algorithm for even approximate Nash equilibrium yields insights into the planted clique problem. As always take a look at their paper to see the details, and the proof. I find this connection pretty interesting—I hope you do too.
Open Problems
What are your favorite unexpected connections in mathematics?
[Edited]
The connection between the hidden clique problem and eps-Nash is due to Hazan and Krauthgamer (SODA 2009). Minder-Vilenchik is a quantitative improvement of the original result.
JamesL
Thanks,
Somehow messed the citation up thanks. Here is a link to their paper.
The DPRM (or Matiyasevich’s) theorem: that the recursively enumerable sets are precisely the Diophantine sets. This opens a floodgate of shocking connections between computability theory, algebra, and analysis.
I think you mean the MRDP theorem.
hi, i was interested in a quantum game theory algorthim system where one could project from above 0, and 1 on a basket ball court and place microchips on each player and create an algorthim with all the players movments through out the game on the court,then place the data in a data base and find the numbers that equal the winning lotto ticket numbers after the game ,and which player had the ball tocreate the winning position,this could then be used to adjust the economy.terry fraser calgary
Xamuel’s theme of “shocking” mathematical connections is IMHO a fruitful one.
Shocking mathematical insights exemplify Dick’s “Flaming Arrow” phenomenon … Are They Allowed To Do That?. Moreover, there is a strong bandwagon effect: if your colleagues/competitors start shooting flaming arrows, then you want to shoot some too.
Leonid Gurvits’ proof that the quantum separability problem is NP-hard is one of my favorite shocking connections. Gurvits proof came as a shock to mathematicians and physicists who had grown accustomed to thinking of information—both classical and quantum—as a “natural” quantity, in both the mathematical and physical senses of that word (as established by Claude Shannon). Thus Gurvits’ proof that quantum entanglement is unquantifiable by any feasible-to-compute measure came as a major shock to many researchers.
One reason why people find Gurvits’ theorem to be shocking—in common with many of complexity-theoretic results—is set forth in a terrific Chauvenet Lecture by Saunders Mac Lane: Hamiltonian mechanics and geometry (1970). In essence, Mac Lane argues that a mathematician’s notion of “naturality” and a physicists notion of “physicality” are really the the same notion, and that this identity arises because both mathematicians and physicists require that their understanding be coordinate-independent.
Mac Lane’s explanation is the best one I know for what Wigner called “The unreasonable effectiveness of mathematics in the natural sciences.” Namely, whenever we try to formalize our physical understanding in a coordinate-free way, we are led to natural mathematics. This helps us understand why so many essays by renowned mathematicians celebrate the study of physical systems as a vital source of mathematical inspiration; a few examples (from among very many) are von Neumann in The mathematician (1948), Dyson in Missed opportunities (1972), Tao in What is good mathematics? (2007), Bill Thurston in Daina Taimina’s Crocheting adventures in the hyperbolic plane, Gelfand and Arnold in We do not choose mathematics as our profession, it chooses us (2009) … and of course, pretty much every lecture that Richard Feynman ever gave.
Dick’s post mentions several recent works that similarly embody this duality of physicality and naturality. Roger Myerson’s Nash Equilibrium and the History of Economic Theory explicitly reviews the grounding of Nash’s research in practical economics and game strategy. Joan Birman’s review of Braid Groups and Ordering Braids similarly emphasizes Gauss’ mathematical studies of physical links, knots, and braids … all of which terms were in common use by sailors, spinners, blacksmiths, and weavers long before they entered the mathematical lexicon.
The preceding essays span 51 years, and their uniformity is striking: they describe a richly-elaborated two-party game that mathematicians and physicists have been playing with great success via stable strategies.
Nowadays, however, the rules and resources of the math-physics game have irretrievably altered by “shocking” results of complexity-theory pioneers like Gödel, Shannon, and Turing, and by the more recent, and similarly “shocking”, results from people like Gurvits (relating to separability) and Candes/Tao (relating to compressibility).
Three-player games are generically richer than two-player game—richer in rules, richer in strategies, and richer in resources. Exactly how this game will be played in the 21st century is still unclear—the 20th century strategies are no longer stable, and new strategies are still evolving. But what is clear is that the 21st century game will be larger and richer for everyone: scientists, mathematicians, and engineers.
Thus, we can all be reasonably confident of a STEM future that is better … shockingly better. Good! 🙂
I always like it when independence results creep out of set theory and into other areas, like the Whitehead problem and Naimark’s problem. I get the feeling this is going to come up repeatedly in various areas of mathematics. Yet it always seems totally unexpected and exciting.
This is a new one, but definitely my favorite. Ashay Dharwadker and Vladimir Khachatryan submitted a very interesting paper about predicting the Higg’s Boson mass using the Standard Model with the Four Color Theorem. Of course, the boson hasn’t been found yet, so it has yet to be tested. If it turns out to be true, that is an amazing application of graph theory. The first link to a more lay-person friendly version of the article, for folks like me. The second is a link to the arXiv paper, for the more technically inclined.
http://www.science20.com/quantum_diaries_survivor/guest_post_vladimir_khachatryan_higgs_mass_fourcolour_theorem
http://arxiv.org/abs/0912.5189
This might even be correct! There is a rumor now that the Higgs mass might indeed be 125 Gev.
http://blog.vixra.org/2011/12/02/higgs-rumour-anaylsis-points-to-125-gev/
I am having the proof of P=NP. I have got the algorithm to solve the problems of NP class as like of P class.
I am a second year student of Indian Institute of Technology. And after Vinay’s Proof of P!=NP I had a look inside the problem and devoted some time of mine towards that and got the results.
Having a proof that P=NP is pretty much a license to print money, assuming the fixed exponent isn’t too large. See Russell Impagliazzo’s paper “A Personal View of Average-Case Complexity”, particularly section 2.1 “Algorithmica” to get some general ideas on what to work on next. Assuming you’re not killed first, you’ll probably become the world’s first trillionaire.
You note that von Neumann did not appreciate Nash’s work. Similarly, he did not seem to appreciate Turing’s work on computation. Here is a quote from an article about von Neumann in http://www.velocityguide.com/computer-history/john-von-neumann.html :
In Cambridge and then in Princeton he came across the young Alan Turing — even providing him a job as an assistant in 1938. But he plainly paid little attention to Turing’s classic 1936 report on Turing machines and the concept of universal computation, writing in a recommendation letter on June 1, 1937 that “[Turing] has done good work on … theory of almost periodic functions and theory of continuous groups”.
According to David Leavitt’s biography of Turing, Von Neumann asserted—in conversations with colleagues—that after Gödel’s work appeared in 1931, he (von Neumann) never read another article on mathematical logic.
I thought the connection between PDE’s and topology, allowing for the Poincare conjecture to be solved, was pretty fascinating. I also love how Bernoulli numbers, Gamma, knot invariants, and a few other things always seem to show up in random places.