Professor of Computer Science at UC Irvine, researching graph algorithms and computational geometry. Wikipedian. Amateur photographer. Father of two.
0xDE's Latest Posts
Today I've been playing with the induced subgraphs of the Clebsch graph. Several other interesting and well-known graphs can be obtained from it by deleting a small number of vertices and forming the induced subgraph of the remaining vertices. To begin with, one simple construction of the Clebsch graph is to take all length-four binary strings as vertices, and to make two strings neighbors when they differ either by a single bit or by all four bits. So it has sixteen vertices and 40 edges, and […]
Many of the talks at the Conference on Meaningfulness and Learning Spaces that I recently attended concerned (surprise!) meaningfulness. The basic idea is to provide a crude filter for bad science and bad statistics by determining whether applying a formula to data could possibly make any sense. For instance, in many computer science conference program committees, we score papers on a scale from -3 to +3 (say) and then rank the papers by averaging the scores of different reviewers (possibly […]
This week I've been attending the Conference on Meaningfulness and Learning Spaces at UC Irvine, in honor of the 80th birthday of my co-author Jean-Claude Falmagne. I believe videos of the talks will eventually be online and I'll put up a link to mine when that happens.Jean-Claude himself gave a talk, in which the following cute geometric fact came up as an example: If f(x, y) is the function that computes the length of the hypotenuse of a right triangle with side lengths x and y, then f obeys […]
Some background. Via. A longer but non-free video.
One of Oded Schramm's less-well-known but better-named results is his "monster packing theorem", a far-reaching generalization of the famous circle packing theorem of Koebe, Andreev, and Thurston. Here, a packing is a set of geometric shapes with disjoint interiors, whose intersection graph represents a given planar graph. For instance, the circle packing theorem states that every planar graph can be represented as the intersection graph of interior-disjoint circles. But what if we want to […]
Log in to leave a comment