# Today's reading

Below are links to a couple of interesting-looking recent arXiv preprints.

**Very Large Graphs** by László Lovász, arXiv:0902.0132. This is a survey on the theory of graphs that are so large that they cannot be accurately described: as an early example, Lovász mentions the futility of asking whether the web graph has an even or odd number of vertices. This leads to questions involving models of random graphs, property testing (is this graph near or far from a graph having a given property rather than does it exactly have the property), and tools for property testing (Szemerédi's partition of graphs into nearly regular subgraphs). So to me it seems to be very much a STOC/FOCS flavored survey of this area: it doesn't include much about the sorts of power laws and phase transitions that get physicists excited, it doesn't cover web engineering approaches for dealing with large graphs such as Google's pagerank, and the survey of random graph models fails to mention the exponential random graph model (ERGM or p* model) that seems to be quite popular among social scientists. But with its biases clear, this seems to be a very useful overview of the field.

**A Revision of the Proof of the Kepler Conjecture** by Hales, Harrison, McLaughlin, Nipkow, Obua, and Zumkeller, arXiv:0902.0350. The Kepler conjecture states that the way to pack as many unit spheres into a large region of space is possible is to use the face-centered cubic pattern; this can be described in several ways but one of them is to pack a layer of spheres in a square grid, then pack another layer on top of the holes of the first layer, etc. Tom Hales proved it in 1998, but the proof was long and computerized and messy. It turns out that Hales and his co-authors are still working on the problem, trying to clean up the proof. The goal seems to be, not so much getting something that a human can read and understand, but rather getting the proof into a form that can be verified by automated proof checkers (as has, apparently, already been done for the four-color theorem, which is with the Kepler conjecture and the classification of finite simple groups one of the standard examples of a big ugly proof). There's a lot of work involved and this paper merely provides an overview of it.

In other news, I visited Harvard last week for the STOC PC meeting; see Michael Mitzenmacher's long series of blog posts about the program committee meeting and the reviewing process for some flavor of what that was like. Or if'd rather just look at some pretty geometric pictures and movies, how about myriahedral projections, Jack van Wijk's unfoldings of the earth's surface (via MF).