For the past few years I've been carrying around a small notebook to jot down notes from talks, research ideas, expenses, etc. (I guess I could do it on my phone but I prefer pen and paper.) I like writing with fountain pens, but don't care to carry around an expensive one: I don't feel I need to impress people with how much I spend on accessories, and I don't want to worry about losing it. I had been using disposable Pilot Varsity pens, but occasionally (especially if I took them on airplanes) I would end up with ink all over my fingers, so I recently tried switching to an inexpensive refillable pen, the Lamy Safari (fine point, with refilling attachment and Noodler's forest green ink). Below is a comparison of how my notes look with the two pens:

( Read more...Collapse )

I still don't know if these pens are more reliable in the air, but on the whole I'd say this is a big step up in writing quality.

Today's new Wikipedia articles: Hanner polytopes and Kalai's 3^d conjecture.

The 3^d conjecture states that a centrally symmetric d-dimensional polytope must have at least 3^d faces (of all dimensions including the d-dimensional polytope itself as a face but not including the –1-dimensional empty set). For instance, the cube has 8 vertices, 12 edges, 6 squares, and 1 cube as faces; 8 + 12 + 6 + 1 = 27 = 3³.

The Hanner polytopes include the cubes, are closed under Cartesian products and duality, and if the conjecture is true have the fewest possible numbers of faces of all centrally symmetric d-dimensional polytopes. They also have some other interesting properties. In 3d there are only the cube and the octahedron, but in higher dimensions there are a lot more of them.

I have another new preprint: Combinatorial Pair Testing: Distinguishing Workers from Slackers (with Mike Goodrich and Dan Hirschberg), arXiv:1305.0110, to appear at WADS.

The story in this one is that we have students in a pair programming class, some of whom will do the work and some of whom will let their partner do all the work. But if two of the slackers get paired together, we can catch them, because then nobody does the work. So how do we choose partners for the assignments to be sure of catching everyone, with an assumption that only a small fraction of the students are slackers?

Actually, we started out working on a different (but related) puzzle. We've been having a weekly tea with our theory students and faculty, at which we drink tea and also try to solve puzzles. The first one from the Puzzle TOAD is on distinguishing engineers (who always tell the truth) from managers (who will either tell the truth or lie, whichever of the two will confuse you the most) using as as few questions as possible about who is whom. It caught our attention at one of these teas, especially after we had some ideas for solving part 3 and saw that there was no official solution already given. Sadly, someone else with a time machine already got there first, so we had to find something else to work on.

Speaking of time machines, if you like time travel movies and get a chance to see Young Gun In The Time, do. It's a fun South Korean time-travel detective farce. I'd like to rewatch it to get a clearer idea of exactly what happened, but at this point the easiest way to do that seems to be to find a time machine of my own.

If you make a graph with a vertex for each permutation of length n, and an edge for two permutations related by a swap of adjacent values, it looks like this:



It has some nice properties: it's a Hamiltonian partial cube with isometric dimension n(n − 1)/2, and the graph of an n − 1-dimensional polytope (the permutohedron) There's an easy way to compute distances in this graph (count the inversions). But what if we consider a subset of the permutations, the ones avoiding the permutation pattern 213?

( Read more...Collapse )

I have a new preprint out with Michael Bannister and Sergio Cabello, "Parameterized complexity of 1-planarity", arXiv:1304.5591, to appear at WADS.

( Read more...Collapse )

The list of accepted papers for WADS 2013 is out. No abstracts, just titles and authors, but some of the papers can be found online elsewhere as preprints. (Not mine yet, but soon.)

The Dagstuhl workshop I just attended included an art exhibit, Bending Reality: Where arc and science meet, of maps and illustrations featuring curved graphs; I had several pieces in it. It was lots of fun to see images such as this one and this one printed out in a large size (70 x 100 cm) and framed as art, rather than just used as technical illustrations.

The space the exhibit was shown in consisted of four long corridors with lots of natural light from windows into an atrium area; it worked well for viewing the art, but not so well for photographing the exhibit (and my failure to bring a wide angle lens didn't help, either). Anyway, the images in the show are all better viewed directly online rather than as photographs of framed printouts. So I only kept a few photos as an impression of what the exhibit was like.



Supposedly there's a plan to make a web site of the exhibit catalog; I'll link it here once it exists.
See also André Schulz's blog post on the metro maps in the exhibit.

As airplane reading to and from my recent trip to Dagstuhl, I used a review copy of Lance Fortnow's new popularization of the P vs NP problem, The Golden Ticket: P, NP, and the Search for the Impossible. It's well written and explains the problem well in layman's terms, something I think has been sorely needed.

As Lance carefully explains towards the end of Chapter 7, the inference from the assertion that we can only find a complete solution to an NP-complete problem by performing a brute force search of all solutions, to the assertion that P ≠ NP, forms one of the most common ways of writing a fallacious solution of the P vs NP problem. It is fallacious not because it is an invalid inference, but because it does not get rid of the need to prove something difficult: it might not be true that brute force search is the best way we can solve such problems. But it was a little disappointing that Lance did not go on to say that it is already proven that a naive brute force search is not always the best solution. Indeed, several times Lance seems to imply the equally fallacious reverse inference, from P ≠ NP to the idea that the best complete solution to an NP-complete problem must be a brute force search. For instance, this attitude is embodied in his equation of NP-completeness to "Perebor". This recent CACM article provides a welcome antidote, by describing several instances of surprising solutions to NP-complete problems that are not brute force searches and that are significantly faster than brute force (although of course not polynomial).

Despite this quibble (and smaller ones, for instance: who but a theoretician would recommend Floyd–Warshall for finding all-pairs unweighted shortest paths when one can just use repeated breadth first searches?) I think this book has an important role to play, in clearly explaining to the rest of the world just why computer scientists find the P vs NP problem so interesting and important.

I'm in Dagstuhl this week for a workshop on Drawing Graphs and Maps with Curves. I gave a talk today surveying the use of curved edges in graph drawing, which may be older than you might think. For instance, did you know that arc diagrams, named from a 2002 paper by Wattenberg in information visualization, actually go back to two papers from the 1960s on crossing minimization? Here are my talk slides.

...and a nice bowl my aunt and uncle brought us — thanks, Geoff and Josephine!



I still haven't found an easy way to obtain these outside NZ.

My car dealer was clueless and my internet searches were fruitless, but I've finally fixed the issues I was having with my driving music. It was all Apple's fault. In the hope that this reaches someone else with the same problem, I'm posting my story here.

I have a large library of pop music of various genres on my iPod, and I usually listen to it in random mode. It was working fine that way via the headphones. But my new Mini Cooper comes with a sound system that I can plug the iPod into, simultaneously powering the iPod and providing a digital feed of music to the car sound system. It shows me what it's playing on the car display, and it allows me to control the iPod from the dash or (for simple things like skipping to the next song) from the steering wheel. Much nicer than the usual auxiliary input jack. I'm guessing that some other car makes, especially BMWs, also use a similar system.

The problem was, about half of the time my car stereo was displaying the wrong song title. This wouldn't be so bad, but it was also getting other bad metadata (in particular the length of the song), causing it to cut the song short or run long into the next track and then cut that short. I was thinking maybe it was a firmware bug in the stereo that that would need me to take it in for an upgrade, or a bad line in the connector cable, or something. But no. This week, I tried reformatting the iPod and reloading all of its music. Now it works perfectly. So I assume some internal index on the iPod (used by the digital connection but not when I'm on headphones) had somehow become corrupted, that iTunes never noticed the corruption, and that reloading it rebuilt that index from scratch in an uncorrupted form.

In any case, the short version is: car stereo showing the wrong song title? Reformat your iPod.

An involution is a permutation that equals its inverse; thought of another way, it's a matching on an n-vertex complete graph, where a position in the permutation is mapped to its partner in the matching (or itself if it is unmatched). Here are the 26 involutions on 5 elements (26 is a telephone number, the numbers that count involutions):

( Read more...Collapse )

The crossing number of a graph is the minimum number of edge crossings with which it can be drawn. A lot of research in graph drawing has involved algorithms or heuristics for minimizing this number, because drawings with more crossings tend to be less understandable.

The traditional story of crossing numbers is that they began with Turán's "brick factory problem", named after the brick factory in which Hungarian mathematician Pál Turán was imprisoned by the Nazis during World War II, and his musings on how to design a system of tracks that would have as few crossings as possible. But it turns out (as I found today while looking for something else) the same problem was percolating at the same time in an entirely different field of study: sociology. In 1934, J. L. Moreno invented the sociogram, and in 1944, Urie Bronfenbrenner wrote (about how to place the vertices in such a drawing): "The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines." Crossing numbers!

I haven't yet tracked down an online copy of Moreno's original publication, or what he says about vertex placement in it (the 1953 second edition is here), but Bronfenbrenner's can be found at JSTOR: Bronfenbrenner, Urie (1944). "The graphic presentation of sociometric data". Sociometry 7 (3): 283–289.

I've been working on a new Wikipedia article on circular layouts in graph drawing, and I wanted to say something in it about Planarity, a puzzle that involves moving the vertices of a graph drawing around, starting from a circular layout, to show that the graph is planar. However, despite the existence of quite a bit of academic work that explicitly states that it's inspired by Planarity, I couldn't find any published source that describes the initial layout of the puzzle.

( Several near missesCollapse )

In the absence of good enough sources for the circularity of its layouts, I ended up mentioning Planarity in a see-also link of the circular layout article, rather than actually including it in the main text of the article. It's obvious to anyone who spends any amount of time playing Planarity that its initial layout is circular. But sometimes, being obvious isn't enough: you have to say it.

In contrast to Cayley permutations, Stirling permutations turn out to be very easy to generate by very small modifications to the Steinhaus–Johnson–Trotter algorithm.

A Stirling permutation is a permutation of a multiset with two copies of each value, with the property that between these two copies only larger values can appear. In particular, the two largest values must appear consecutively. The algorithm simply sweeps this consecutive largest pair back and forth across the sequence, recursing when the largest pair reaches one of the ends of the sequence. Each step is a swap of two items that are two positions apart; it isn't possible to move the two largest items by a swap of contiguous items.

For details see the updated PADS.Permutations.

I was up in the Bay Area this weekend with my family for a memorial service for my wife's cousin Erik Cassel, who died recently at a young age. Before leaving we stopped by Stevens Creek Park, a place I used to visit frequently long ago when I lived in Cupertino, and where my brother-in-law now works. Some photos.

A Cayley permutation of order n (so named by Mor and Fraenkel in 1984) is a sequence of n positive integers whose set of values forms an interval [1,k] for some k ≤ n; for instance the ones for which k = n are just the usual permutations. The number of Cayley permutations is counted by the ordered Bell numbers, but how can the permutations themselves be generated efficiently?

( Read more...Collapse )

Predatory publishers that pretend to peer-review your papers (but really accept all comers to maximize their profits) lead to sad-but-funny situations like this one: Onion article about a children's menu found on the back of the original copy of the U.S. Constitution cited seriously by scientific article.

It may be entertaining, but it's not good for the literature for it to be cluttered up with this sort of cargo-cult imitation of research, and it's not good for universities and academics (and the students they teach) to be pressured into publishing this sort of junk in order to keep up a pretense of being a research university. (Also, before you say that impact factors will sort these things out, someone on the post I found this on has already commented that this journal's impact factor is pretty high; impact factors are easily manipulated and there's a lot of motivation for doing so.)

I made a preprint out of my earlier post here on grid minors in damaged grids: it is arXiv:1303.1136.

Somewhere along the way I learned of an interesting related result in infinite graph theory, Halin's grid theorem. In finite graphs the size of the largest grid minor is bounded above and below by (two different) functions of the treewidth, and the treewidth of a finite graph may be characterized by the maximum order of a haven, a certain kind of strategy for a cops-and-robbers game on the graph. In infinite graphs this breaks down, because a haven with infinite order exists whenever the graph has an infinite path (even if its treewidth is one and it has no nontrivial grid minors). Rather, the infinite-order havens correspond to the ends of the graph (equivalence classes of infinite paths that, intuitively, all go the same direction, in the sense that one can bounce back and forth between any two equivalent paths infinitely often). An end is "thick" if it includes an infinite set of disjoint paths, and Halin's theorem states that a graph has a thick end if and only if it has an infinite grid minor.

Because of the tight connections between havens, treewidth, and grid minors in finite graphs, and the less-direct but still present connections between havens, ends, and infinite grid minors, it makes me think that maybe there should be something like a haven but more constrained, or a different parameterization of havens than their order, that should work for both finite and infinite graphs, that gives both upper and lower bounds on the size of the grid minor for graphs in which this is bounded, and that could distinguish those graphs from the graphs in which all grid minors are finite but with unbounded size, and from the graphs with infinite grid minors.

Let's say that a permutation on the numbers from 1 to n is k-universal if its subsequences of k items have all of the k! possible different patterns that they could have. For instance, 25314 is 3-universal: the six possible patterns 123, 132, 213, 231, 312, and 321 appear in it as 234, 253, 314, 231, 514, and 531 respectively. How short can a k-universal pattern be?

It's not hard to find upper and lower bounds within a constant factor of each other. In one direction, the sequence k, 2k, 3k, ... k−1, 2k−1, 3k−1, ..., k−2, 2k−2, 3k−2, ... etc of length k² is universal. (This is the same tilted grid pattern that gives the lower bound in the Erdős–Szekeres theorem.) In the other direction, the length n of the universal permutation must be at least some constant times k², in order for it to have at least k! different subsets of size k. But what is the constant?

A computer search found that there is no 4-universal permutation on 8 items (the best is 51862473 which has 23 out of the 24 possible patterns), but the 9-item permutation 162975384 is universal. So the sequence of lengths of the shortest k-universal patterns begins 1, 3, 5, 9, ... But although there are simple quadratically-growing sequences like ceiling((k^2+1)/2) that begin like this, it's not really long enough to identify this in OEIS and see whether it matches anything known.