Erdős number

7 results back to index

pages: 262 words: 65,959

The Simpsons and Their Mathematical Secrets by Simon Singh


Albert Einstein, Andrew Wiles, Benoit Mandelbrot, cognitive dissonance, Erdős number, Georg Cantor, Grace Hopper, Isaac Newton, John Nash: game theory, mandelbrot fractal, Menlo Park, Norbert Wiener, P = NP, Paul Erdős, probability theory / Blaise Pascal / Pierre de Fermat, Richard Feynman, Richard Feynman, Schrödinger's Cat, Simon Singh, Stephen Hawking, Wolfskehl Prize, women in the workforce

In short, Hopper’s hardheaded, applied, technology-driven, industrial, military mode of mathematics was utterly different from Erdős’s purist devotion to numbers, yet Hopper has an Erdős number of just 4. This is because she published papers with her doctoral supervisor Øystein Ore, whose other students included the eminent group theorist Marshall Hall, who co-authored a paper with the distinguished British mathematician Harold R. Davenport, who had published with Erdős. So, how does Jeff Westbrook rank in terms of his Erdős number? He started publishing research papers while working on his PhD in computer science at Princeton University. As well as writing his 1989 thesis, titled “Algorithms and Data Structures for Dynamic Graph Algorithms,” he co-authored papers with his supervisor Robert Tarjan. In turn, Tarjan has published with Maria Klawe, who collaborated with Paul Erdős. This gives Westbrook a very respectable Erdős number of just 3. However, this does not make him a clear winner among the writers on The Simpsons.

Surprisingly, he has a Bacon number of 4, because he appeared in N Is a Number (1993), a documentary about his life, which also featured Tomasz Luczak, who was in The Mill and the Cross (2011) with Rutger Hauer, who was in Wedlock (1991) with Preston Maybank, who was in Novocaine (2001) with Kevin Bacon. His Erdős number, for obvious reasons, is 0, so Erdős has a combined Erdős-Bacon number of 4—not quite enough to match Reznick. And, finally, what about Kevin Bacon’s Erdős-Bacon number? Bacon, being Bacon, has a Bacon number of 0. As yet, he does not have an Erdős number. In theory, he might develop a passion for number theory and collaborate on a research paper with someone who already has an Erdős number of 1. This would give him an unbeatably low Erdős-Bacon number of 2. CHAPTER 6 Lisa Simpson, Queen of Stats and Bats When the Simpsons made their television debut as part of The Tracey Ullman Show, their individual personalities were not quite as developed as they are today.

He fueled his brain with coffee and amphetamines in order to maximize his mathematical output, and he often repeated a notion first posited by his colleague Alfréd Rényi: “A mathematician is a machine for turning coffee into theorems.” In six degrees of Paul Erdős, connections are made via co-authored articles, typically mathematical research papers. Anybody who has co-authored a paper directly with Erdős is said to have an Erdős number of 1. Similarly, mathematicians who have co-authored a paper with someone who has co-authored a paper with Erdős are said to have an Erdős number of 2, and so on. Via one chain or another, Erdős can be connected to almost any mathematician in the world, regardless of their field of research. Take Grace Hopper (1906–92) for example. She built the first compiler for a computer programming language, inspired the development of the programming language COBOL, and popularized the term bug to describe a defect in a computer after finding a moth trapped in the Mark II computer at Harvard University.


pages: 379 words: 113,656

Six Degrees: The Science of a Connected Age by Duncan J. Watts


Berlin Wall, Bretton Woods, business process, corporate governance, Drosophila, Erdős number, experimental subject, Frank Gehry, Geoffrey West, Santa Fe Institute, invisible hand, Long Term Capital Management, market bubble, Milgram experiment, Murray Gell-Mann, Network effects, new economy, Norbert Wiener, Paul Erdős, rolodex, Ronald Coase, Silicon Valley, supply-chain management, The Nature of the Firm, The Wealth of Nations by Adam Smith, Toyota Production System, transaction costs, transcontinental railway, Y2K

Erdos, being not only a great (and extremely prolific) mathematician but also something of a celebrity in the mathematics community, was thought to be the center of the math world in much the same way that Bacon was for the world of movie actors. As a result, if you have published a paper with Erdos, you get to have an Erdos number of one. If you haven’t published a paper with Erdos but you have written one with someone who has, then you have an Erdos number of two. And so on. So the question is, “What is your Erdos number?” and the object of the game is to have the smallest number possible. Of course, if your Erdos number is one, then the problem is trivial. And even if you have an Erdos number of two, it isn’t too bad. Erdos was a famous guy, so anyone who had worked with him would probably have mentioned it. But when the Erdos number becomes more than two, the problem gets hard, because even if you know your collaborators rather well, in general you don’t know everybody else with whom they have collaborated.

., and Milgram, S. Acquaintance networks between racial groups—application of the small world method. Journal of Personality and Social Psychology, 15(2), 101 (1970). Is Six a Big or a Small Number? The problem of Erdos numbers has been studied extensively by the mathematician Jerry Grossman, who maintains a Web page on the subject at An early summary of his work is Grossman, J. W., and Ion, P. D. F. On a portion of the well-known collaboration graph. Congressus Numerantium, 108, 129–131 (1995). Some more recent work on Erdos numbers is by Batagelj, V., and Mrvar, A. Some analyses of Erdos collaboration graph. Social Networks, 22(2), 173–186 (2000). Other evidence that small-world networks can make problem-solving harder, rather than easier, is presented in Walsh, T.

Just as someone living in Manhattan might drive east to LaGuardia Airport in order to take a flight to the West Coast, the optimal choice of network path might initially take you in what appears to be the wrong direction. But unlike the drive to the airport, you don’t have a complete map of the route in your mind, so the equivalent of driving east to fly west is not so obviously a good idea. As small as it sounds at first, six can therefore be a big number. In fact, when it comes to directed searches, any number over two is effectively large, as Steve discovered one day when a reporter asked him what his Erdos number was. He figured it out eventually—it’s four—but he wasted two full days in the process. (I remember because I was trying to get him to do something else and he was too preoccupied even to talk.) If this sounds like just another way for mathematicians to avoid doing a real job, directed searches do have a serious side. From surfing links on the Web to locating a data file on a peer-to-peer network, or even trying to find the right person to answer a technical or administrative question, we frequently find ourselves searching for information by performing a series of directed queries, often running into frustrating dead ends or wondering if we might have taken a shorter route.


pages: 442 words: 39,064

Why Stock Markets Crash: Critical Events in Complex Financial Systems by Didier Sornette


Asian financial crisis, asset allocation, Berlin Wall, Bretton Woods, Brownian motion, capital asset pricing model, capital controls, continuous double auction, currency peg, Deng Xiaoping, discrete time, diversified portfolio, Elliott wave, Erdős number, experimental economics, financial innovation, floating exchange rates, frictionless, frictionless market, full employment, global village, implied volatility, index fund, invisible hand, John von Neumann, joint-stock company, law of one price, Louis Bachelier, mandelbrot fractal, margin call, market bubble, market clearing, market design, market fundamentalism, mental accounting, moral hazard, Network effects, new economy, oil shock, open economy, pattern recognition, Paul Erdős, quantitative trading / quantitative finance, random walk, risk/return, Ronald Reagan, Schrödinger's Cat, short selling, Silicon Valley, South Sea Bubble, statistical model, stochastic process, Tacoma Narrows Bridge, technological singularity, The Coming Technological Singularity, The Wealth of Nations by Adam Smith, Tobin tax, total factor productivity, transaction costs, tulip mania, VA Linux, Y2K, yield curve

Most practicing mathematicians are familiar with the definition of the Erdös number [178]. Paul Erdös (1913–1996), the widely traveled and incredibly prolific Hungarian mathematician, wrote at least 1,400 mathematical research papers in many different areas, many in collaboration with others. His Erdös number is 0 by definition. Erdös’s coauthors have Erdös number 1. There are 507 people with Erdös number 1. People other than Erdös who have written a joint paper with someone with Erdös number 1 but not with Erdös have Erdös number 2 and so on. There are currently 5897 people with Erdös number 2. If there is no chain of coauthorships connecting someone with Erdös, then that person’s Erdös number is said to be infinite. The present author has Erdös number 3; that is, I have published with a colleague who has published with another colleague who has written a paper with Erdös.

The present author has Erdös number 3; that is, I have published with a colleague who has published with another colleague who has written a paper with Erdös. There is a mathematical conjecture that the graph of mathematicians organized around the vertex defined by Erdös himself and connected to him contains almost all present-day publishing mathematicians and has a not very large diameter; that is, the largest finite Erdös number is 15, while the average value is about 47 [179, 33]. The explanation of the “small world” effect is illustrated in Figure 6.1, which shows all the collaborators of the author of [313, 314] and all the collaborators of those collaborators, that is, all his first and second neighbors in the collaboration network of scientists. As the figure shows, M. E. J. Newman has 26 first neighbors and 623 second neighbors. As the increase in numbers of neighbors with distance continues at this impressive rate, it takes only a few steps to reach a size comparable to the whole population of scientists, hence the “small-world” effect. 175 .P. .M.

Stock return volatility during the crash of 1987, Journal of Portfolio Management 16, 69–71. 175. Gray, S. F. (1996). Regime-switching in Australian short-term interest rates, Accounting & Finance 36, 65–88. 176. Greenspan, A. (1997). Federal Reserve’s semiannual monetary policy report, before the Committee on Banking, Housing, and Urban Affairs, U.S. Senate, February 26. 177. Greenspan, A. (1998). Is there a new economy? California Management Review 41 (1), 74–85. 178. Grossman, J. The Erdos Number Project, erdoshp.html. 179. Grossman, J. W. and Ion, P. D. F. (1995). On a portion of the well-known collaboration graph, Congressus Numerantium 108, 129–131. 180. Grossman, S. and Stiglitz, J. E. (1980). On the impossibility of informationally efficient markets, American Economic Review 70, 393–408. 181. Grou, P. (1987, 1995). L’aventure économique (L’Harmattan, Paris), p. 160. 182.


pages: 349 words: 95,972

Messy: The Power of Disorder to Transform Our Lives by Tim Harford


affirmative action, Air France Flight 447, Airbnb, airport security, Albert Einstein, Amazon Mechanical Turk, Amazon Web Services, Atul Gawande, autonomous vehicles, banking crisis, Barry Marshall: ulcers, Basel III, Berlin Wall, British Empire, Broken windows theory, call centre, Cass Sunstein, Chris Urmson, cloud computing, collateralized debt obligation, crowdsourcing, deindustrialization, Donald Trump, Erdős number, experimental subject, Ferguson, Missouri, Filter Bubble, Frank Gehry, game design, global supply chain, Googley, Guggenheim Bilbao, high net worth, Inbox Zero, income inequality, Internet of things, Jane Jacobs, Jeff Bezos, Loebner Prize, Louis Pasteur, Mark Zuckerberg, Menlo Park, Merlin Mann, microbiome, out of africa, Paul Erdős, Richard Thaler, Rosa Parks, self-driving car, side project, Silicon Valley, Silicon Valley startup, Skype, Steve Jobs, Steven Levy, Stewart Brand, telemarketer, the built environment, The Death and Life of Great American Cities, Turing test, urban decay

Erdős had a more important spell to weave: the Hungarian wizard was quite simply the most prolific collaborator in the history of science. The web of cooperation around the world and across the twentieth century spreads so far it is measured in an honorific unit: the “Erdős number.” People who wrote articles jointly with Erdős himself are said by mathematicians to have an Erdős number of one. Over five hundred people enjoy this distinction. If you wrote a paper with one of them, your Erdős number is two. Over forty thousand people have Erdős numbers of three or less, all spinning in intellectual orbit around this astonishing man. Erdős’s achievement as the linchpin of so many mathematical partnerships is unsurpassed and perhaps unsurpassable. Think for a moment about his five hundred collaborating authors: each one represents Erdős’s launching into a serious piece of intellectual teamwork—a peer-reviewed scientific paper—with a stranger.

., p. 81. 3. Winston A. Reynolds, “The Burning Ships of Hernán Cortés,” Hispania 42, no. 3 (September 1959), pp. 317–324. 4. Paul Hoffman, The Man Who Loved Only Numbers (London: Fourth Estate, 1999), p. 49. 5. Bruce Schechter, My Brain Is Open: The Mathematical Journeys of Paul Erdős (Oxford: Oxford University Press, 1998), p. 182. Also see the Erdős Number Project at Oakland University: The Erdős number graph continues to evolve because mathematicians continue to publish research based on their collaborations with Erdős, crediting him as a coauthor. 6. Jukka-Pekka Onnela et al., “Analysis of a Large-Scale Weighted Network of One-to-One Human Communication,” February 19, 2007, 7. Mark Granovetter, “The Strength of Weak Ties,” American Journal of Sociology 78, no. 6 (May 1973), pp. 1360–1380, and his Getting a Job: A Study of Contacts and Careers (Chicago: University of Chicago Press, 1974). 8.


pages: 295 words: 66,824

A Mathematician Plays the Stock Market by John Allen Paulos


Benoit Mandelbrot, Black-Scholes formula, Brownian motion, business climate, butterfly effect, capital asset pricing model, correlation coefficient, correlation does not imply causation, Daniel Kahneman / Amos Tversky, diversified portfolio, Donald Trump, double entry bookkeeping, Elliott wave, endowment effect, Erdős number, Eugene Fama: efficient market hypothesis, four colour theorem, George Gilder, global village, greed is good, index fund, invisible hand, Isaac Newton, John Nash: game theory, Long Term Capital Management, loss aversion, Louis Bachelier, mandelbrot fractal, margin call, mental accounting, Nash equilibrium, Network effects, passive investing, Paul Erdős, Ponzi scheme, price anchoring, Ralph Nelson Elliott, random walk, Richard Thaler, Robert Shiller, Robert Shiller, short selling, six sigma, Stephen Hawking, transaction costs, ultimatum game, Vanguard fund, Yogi Berra

If A and B appeared together in X, and B and C appeared together in Y, then A is linked to C via these two movies. Although they may not know of Kevin Bacon and his movies, most mathematicians are familiar with Paul Erdös and his theorems. Erdös, a prolific and peripatetic Hungarian mathematician, wrote hundreds of papers in a variety of mathematical areas during his long life. Many of these had co-authors, who are therefore said to have Erdös number 1. Mathematicians who have written a joint paper with someone with Erdös number 1 are said to have Erdos number 2, and so on. Ideas about such informal networks lead naturally to the network of all networks, the Internet, and to ways to analyze its structure, shape, and “diameter.” How, for example, are the Internet’s nearly 1 billion web pages connected? What constitutes a good search strategy? How many links does the average web page contain?


pages: 236 words: 50,763

The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow


Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Andrew Wiles, Claude Shannon: information theory, cloud computing, complexity theory, Erdős number, four colour theorem, Gerolamo Cardano, Isaac Newton, John von Neumann, linear programming, new economy, NP-complete, Occam's razor, P = NP, Paul Erdős, Richard Feynman, Richard Feynman, smart grid, Stephen Hawking, traveling salesman, Turing machine, Turing test, Watson beat the top human players on Jeopardy!, William of Occam

This is why mathematicians derive fame from finding clever ways to prove mathematical statements. It can even be difficult to find ways to make simple logical expressions true. From that problem came a theory that links most of the NP problems together, a story we tell in the next chapter. A Solution to the Icosian Game Figure 3-18. Icosian Solution. * I have written papers with three different co-authors of Paul Erdős, giving me an Erdős number of 2. With Erdős’s 1996 passing, my chances of reducing my Erdős number are slim. I have had no acting experience (or talent) and do not have a Bacon number. Chapter 4 THE HARDEST PROBLEMS IN NP A psychologist decides to run an experiment with a mathematician. The psychologist puts the mathematician in a one-room wooden hut that has some kindling on the floor, a table, and a bucket of water on the table. The psychologist lights the kindling on fire.


pages: 434 words: 135,226

The Music of the Primes by Marcus Du Sautoy


Ada Lovelace, Andrew Wiles, Arthur Eddington, Augustin-Louis Cauchy, computer age, Dava Sobel, Dmitri Mendeleev, Eratosthenes, Erdős number, four colour theorem, Georg Cantor, German hyperinflation, global village, Henri Poincaré, Isaac Newton, Jacquard loom, Jacquard loom, music of the spheres, New Journalism, Paul Erdős, Richard Feynman, Richard Feynman, Search for Extraterrestrial Intelligence, Simon Singh, Solar eclipse in 1919, Stephen Hawking, Turing machine, William of Occam, Wolfskehl Prize, Y2K

One was an entirely self-sufficient loner who wrote only one joint paper in his life, with the Indian mathematician Saravadam Chowla, and that somewhat against his will. The other took collaboration to such an extreme that mathematicians talk of their Erdos number, the number of co-authors that link them to a paper with Erdos. Mine is 3, which means I’ve written a paper with someone who’s written a paper with someone who’s written a paper with Erdos. Since Chowla was one of Erdos’s 507 co-authors, Selberg’s one joint paper that he ever wrote gave him an Erdos number of 2. Over five thousand mathematicians have an Erdos number of 2. After this refusal, as Selberg admits, ‘things got out of hand’. By 1947 Erdos had built up an extensive network of collaborators and correspondents. He would keep them up to date with his mathematical progress by firing off postcards.