A New Quasipolynomial Time Algorithm for Graph Isomorphisms

In case you haven't been paying attention, you may be interested in reading Jeremy Kun's post about the seminar covering the announced quasipolynomial algorithm for graph isomorphism. Once the preprint comes out and it is vetted, I hope the result does turn out to be genuine. Exciting times!

Tales from the ArXiv: "Finding a Mate With No Social Skills"

Well, the title of this paper says it all, doesn't it?

In fact, there is a wonderful ambiguity in the article title: it can either refer to finding a mate without using any social skills or, more amusingly, to finding a mate who doesn't have any social skills.

If it refers to the latter and people circulate this study widely enough, maybe people like me can finally have some hope? :)

Update (4/30/15): Here is my post on this topic for the Improbable Research blog.

NFL Offensive Lineman by Day, Spectral Graph Theorist by Night

John Urschel is not your ordinary professional football player.

He may be an NFL offensive lineman by day, but by night he is a spectral graph theorist (and numerical linear algebraist). His most recent paper, called "A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians", has now been accepted for publication in Journal of Computational Mathematics. Urschel announced via Twitter that it had been officially accepted for publication. (Based on my googling, the published version of the paper hasn't yet appeared in the journal.)

You can read a draft of Urschel's paper on the arXiv preprint server. I just wish that he used his current affiliation on the paper. That would have been fantastic.

(Tip of the cap to Francis Su.)

Update: Looking at Urschel's academic website, I see that he has prior publications. His website gives the reference for a paper on celestial mechanics. I also checked Mathematical Reviews (to find an upper bound on his Erdős Number, of course), and I see that he also has at least one more paper on spectral graph theory. (This paper isn't listed on Urschel's Penn State website, which I suppose he is no longer updating.)

Update (3/21/15): I wrote a blurb on Urschel for the Improbable Research blog.

"Graph-Theoretic" and "Graphical" Language in the Description of Marriages

This Onion article makes me realize that one can describe marriage laws very precisely using graph theory: allowing non-bipartite graphs, allowing hypergraphs, etc.

Clearly, the outcomes of the court cases ought to be written using graph-theoretic (or, to use a perhaps unfortunate pun, "graphical") language.

Note: I have no comment about self-edges.

Spectral Graph Theory: Cover Art

Here is my new cover art for the field of spectral graph theory. (I couldn't wait until Halloween to make this picture.)

Polymeric K_{3,3}

Some chemists have now constructed the graph K_{3,3} (and other tiny graphs) out of a polymer, and they seem to want to go after Königsberg next.

In related news, I think the South Side (aka: applied and related) of the Mathematical Institute now should annex the North Crystal, which just so happens to have a K_{3,3} graph as its vertices and edges.

(I'll be truely impressed, however, when somebody successfully constructs the ZKK graph using such polymers.)

An Eigencheese Sandwich

This spectral graph theory workshop is clearly getting to me: a few minutes ago, "egg and cheese sandwich" sounded like "eigencheese sandwich" to me.

The Mathematical Rainbow Connection

Kermit the Frog should be very proud of graph theorists.

What Happens in Providence Stays in Providence

I'm on my way to the airport to go to Providence, where I will be in residence at ICERM for most of the next month (though I'll be out of town for a week) as a Research Fellow in their semester program on Network Science and Graph Algorithms.

"A Method Based on Total Variation for Network Modularity Optimization Using the MBO Scheme"

One of my papers just came out in final form. Here are the details.

Title: A Method Based on Total Variation for Network Modularity Optimization Using the MBO Scheme

Authors: Huiyi Hu, Thomas Laurent, Mason A. Porter, and Andrea L. Bertozzi

Abstract: The study of network structure is pervasive in sociology, biology, computer science, and many other disciplines. One of the most important areas of network science is the algorithmic detection of cohesive groups of nodes called "communities." One popular approach to finding communities is to maximize a quality function known as modularity to achieve some sort of optimal clustering of nodes. In this paper, we interpret the modularity function from a novel perspective: we reformulate modularity optimization as a minimization problem of an energy functional that consists of a total variation term and an l_2 balance term. By employing numerical techniques from image processing and l_1 compressive sensing --- such as convex splitting and the Merriman-Bence-Osher (MBO) scheme --- we develop a variational algorithm for the minimization problem. We present our computational results using both synthetic benchmark networks and real data.


The really cool thing about this paper is what it does for "technology translation". We reformulate the modularity quality function in a way that relates it to compressive-sensing-like problems. One can thereby adapt methods from the latter to use for modularity optimization. One of the best compliments that we have received about this paper thus far occurred right after posting it on the arXiv: Somebody from the image-processing community told us that our paper was written in a language such that he could finally understand what people were doing with graphs. Given the goals of the paper, that was exactly what I wanted to hear!

Congratulations to Dr. Puck Rombach!

My Ph.D. student Puck Rombach passed her dissertation defense (aka "viva") today with "Minor Corrections". It appears to be a relatively large number of minor corrections, but they're all eminently doable and it won't take long to dot all of the i's and cross all of the t's. You can find some of Puck's work on my website, as we have coauthored several papers. Puck's thesis is on a mixture of topics from pure graph theory (equitable colorings in random graphs), networks (core-periphery structure and centralities), and a couple of things that interpolate between these two extremes. The Examiners were Colin McDiarmid (internal) on the pure side and Alex Arenas (external) on the applied side.

CONGRATULATIONS, Dr. Rombach!

Achievement Unlocked: Break Expedia's Shortest-Path Algorithm

No, Expedia, if I try to go between Ithaca and Newark with stops first to Philadelphia and then to Boston, it is not ok to insist that I do Ithaca->Newark->other city->Philadelphia when I try to go directly from Ithaca to Philly.

Actually, there was additional shortest-path failing besides that (like insisting that particular direct flights that exist for some searches don't exist for others).

Expedia really needs to hire some graph theorists!

After several failed attempts and significant frustration, I basically went and bought the tickets I wanted with Orbitz instead.

Anyway, this is what I get for trying to arrange an SFO -> Clarkson -> Cornell -> Rutgers -> SFO trip, because all three of those colleges are in the middle of bloody nowhere, except with slightly different nowheres. (That said, I am very excited about this academic trip. I will visit collaborators at Clarkson, I will be starting at a collaboration at Rutgers, and I will be visiting Cornell for the first time since I left when I graduated and will be giving a talk in the colloquium for the program from which I graduated. Awesome!)