[In late 2015], László Babai, of the University of Chicago, announced that he had come up with a new algorithm for the “graph isomorphism” problem, one of the most tantalizing mysteries in computer science.
The Washington Post has a puzzle to see how well you understand social networks. The day’s political issue: whether baseball caps are fashionable. More explanation and the solution below the jump. [more inside]
Alcazar is a neat little path-finding logic game. There are also printable puzzles, strategy tips and metapuzzles to be had. [more inside]
Mathematican John Urschel has coauthored (along with colleagues at Penn State and Tufts) a paper on computing the Fiedler vector of graph Laplacians that has recently been accepted by the Journal of Computational Mathematics. He will also be playing on the Baltimore Ravens offensive line next September. [more inside]
A hive plot (slides) is a beautiful and compelling way to visualize multiple, complex networks, without resorting to "hairball" graphs that are often difficult to qualitatively compare and contrast. [more inside]
So you're me and you're in math class and you're learning about graph theory, a subject too interesting to be included in most grade school's curricula so maybe you're in some special program or maybe you're in college and were somehow not scarred for life by your grade school math teachers. [more inside]
Let's say you're me and you're in math class, and you're supposed to be learning about factoring. Trouble is, your teacher is too busy trying to convince you that factoring is a useful skill for the average person to know with real-world applications ranging from passing your state exams all the way to getting a higher SAT score and unfortunately does not have the time to show you why factoring is actually interesting. It's perfectly reasonable for you to get bored in this situation. So like any reasonable person, you start doodling.[more inside]
"the scale-free network modeing paradigm is largely inconsistent with the engineered nature of the Internet..." For a decade it's been conventional wisdom that the Internet has a scale-free topology, in which the number of links emanating from a site obeys a power law. In other words, the Internet has a long tail; compared with a completely random network, its structure is dominated by a few very highly connected nodes, while the rest of the web consists of a gigantic list of sites attached to hardly anything. Among its other effects, this makes the web highly vulnerable to epidemics. The power law on the internet has inspired a vast array of research by computer scientists, mathematicians, and engineers. According to an article in this month's Notices of the American Math Society, it's all wrong. How could so many scientists make this kind of mistake? Statistician Cosma Shalizi explains how people see power laws when they aren't there: "Abusing linear regression makes the baby Gauss cry."