Some links not long enough for their own separate posts:

Verizon to kill unlimited data plans for existing subscribers. As a happy user of a 3G android phone with Verizon's unlimited plan, this is causing me some apprehension: I don't want to be switched to a new plan on a new and expensive 4G phone.

Yet another instance of Goodhart's law in bibliometrics. Some journal editors are driving up the impact factors of their journals by publishing review articles that cite everything they've recently published. I hesitate to call it fraudulent because why shouldn't they write review papers? But it does seem from the details to be less about trying to help other people find the literature and more about just making numbers bigger. I still don't understand why authors and tenure committees care about impact factors at all, anyway. If you want to tell whether a paper has been having an impact, look at its own citations, not at the citations of the other papers it happens to have been published with. Via MF.

In case you are an ACM member and still haven't voted in the ACM elections (as I hadn't until today), Brighton Godfrey has helpfully collected the candidates' positions on open access and copyright. Via Sariel.

The ideal shape for a metropolitan subway system turns out to be well-connected in the city center and tree-like in the suburbs, with a fixed ratio of suburb distance to center radius.

I've been looking at cars lately. Here's a pretty and popular European car and the ruined and hit-with-an-ugly-stick American version. Why does Detroit do this to us?

And finally, a video that becomes even more impressive when you learn that its images and music were generated algorithmically from only 4k of code (via Josiah, also on BoingBoing).

A report on open-access issues in Wikipedia, Wikimedia and the "seismic shift" towards open-access research publication, has just been published in the weekly newsletter The Signpost.

The most obvious issue is: what to cite. Although there's some natural pressure towards citing open-access sources in Wikipedia just because that's what its editors can easily find, Wikipedia doesn't discriminate against closed sources. However, there's been talk of using a lock icon to distinguish more clearly between open and closed sources. It's not obvious to me that that's a distinction that can always be made easily: for instance, when the New York Times allows anyone to read a certain number of articles per month but then switches to a pay-per-view model for readers who exceed that limit, is it open access or not?

Additionally, although most discussions of open access focus on whether people can read publications without having to pay an access fee or a subscription fee, there's another issue the report brings up: licensing conditions for reuse. If papers are published under a sufficiently liberal Creative Commons license, their text and figures can be reused within Wikipedia (with proper attribution), and vice versa. But there are subtle issues here involving compatibility of different variations of the licenses.

A paper uploaded to the arXiv this evening by Anna Lubiw and Vinayak Pathak just caught my attention. I think the title speaks for itself (always a good thing for a title to do): Flip Distance Between Two Triangulations of a Point-Set is NP-complete. The proof doesn't look very hard, once you see it: a standard gadget-based reduction to a variation of the problem for polygons with holes, together with another reduction from polygons to point sets that consists of protecting the polygon edges with layers of triangles that would be too expensive to flip through.

Although it's a big step forward, the paper still doesn't resolve the question of how hard it is to compute flip distance between triangulations of a convex polygon. This remains as a big open problem, one of a small number of natural problems neither known to be polynomial time nor known to be NP-hard.

In the last few weeks the main thing I've been doing with my camera is taking pictures of the whiteboard in the lectures for my graph algorithms class (a trick I learned about from Joe Mitchell) so that the students can have some instant lecture notes. But I also found time last weekend to take a few photos at a small car show at my son's school. Here's one of a pink Cadillac that got all the schoolgirls to flock around it:

I just updated my PADS library of Python algorithms to Python 2.7. So it will no longer run on older versions of Python, but on the other hand it now appears to pass all the compatibility checks for Python 3 (although I haven't tried actually running it in Python 3).

My favorite things about upgrading from 2.6 to 2.7 are set expressions, set comprehensions and dict comprehensions. That is, you can write {1,2,3} and get a set object containing the elements 1,2,3, you can write {i:(i^1,i^2,i^4) for i in range(8)} to make a dictionary that maps each integer from 0 to 7 to its three cube neighbors (that is, in van Rossum's format for representing graphs, the graph of the cube), and you can write expressions like {v for v in avail if len(avail[v]) == 1} to make a set of the elements mapped by avail to a one-element list.

Most of my changes involved replacing the old Set package with the slightly-less-old built-in set type, and using the new comprehension syntax. One minor issue that caused me a little difficulty was that it used to be possible to compare None with other objects, which allowed it to be used as a flag value in certain cases and which also allowed expressions like map(min,L1,L2) to find the minima of items in the same positions of two lists even when the lists had different lengths, but now that causes a compatibility warning. Another thing that took me a while to figure out was issue 11796, which means that set and dict comprehensions (and in Python 3 list comprehensions) are not really usable when you're initializing class variables, because they mostly can't see the other class variables.

The iTunes music store will no longer let me buy music from them unless I fill out what they call "security questions". You know the kind: what was the first car you ever owned? What was the favorite of the cars you've owned? What was the least favorite? (These are all actual options and it lets you choose all three as your three security questions.) So anyone who knows enough about your personal history can impersonate you. For the record, I have owned a grand total of four cars, and I don't keep their brands secret from the world (for instance they've probably shown up in some of my photos).

These things always fall back to allowing you to reset your password and send you a temporary one by email, anyway. So fortunately it works to fill these things out with gibberish answers, knowing I won't remember them and nobody else will be able to guess them. I'm dreading the day when they put enough AI in the setup interface to require you to select actual makes of cars.

It makes me wonder about control issues: I would think that this one doesn't have enough degrees of freedom to both turn and propel itself. But then, I could say the same thing about a one-string kite: really all you can do is pull or let go the string, giving you only one degree of freedom to control it, but still kites can be flown and controlled. And obviously, this one can be flown as well.

(Via MF)

Sean Murphy has been doing some interesting experiments with two-dimensional cellular automata, described at his Fourier Life web site. The name comes from his use of Fourier analysis to detect replicators in cellular automaton rules: if one does a Fourier transform of the graph of live cells vs time starting from random initial conditions, replicators show up as regularly spaced peaks in the frequency domain, in contrast to oscillators which would only show up as a single peak.

Based on this technique, he's found many individual replicators and near-replicators, with interesting patterns of behavior. Two of my favorites are "Qix!" and "Butterflies vs Centipedes" (both on three-state semitotalistic Von Neumann neighborhood automata): in Qix!, replicators compete with wick-stretchers, that eventually fill the grid with a Mondrian-like rectangular subdivision, while in "Butterflies vs Centipedes" the butterflies and centipedes refer to two different types of replicators that can both be seen at the same time in different regions of the grid.

The list of accepted papers and abstracts from COCOON 2012 is online.

Quite a few of them are about graph drawing and geometric graphs:

• Geometric RAC simultaneous drawings of graphs, by Evmorfia Argyriou, Michael Bekos, Michael Kaufmann and Antonios Symvonis
• Monotone paths in planar convex subdivisions, by Adrian Dumitrescu, Günter Rote and Csaba Toth
• Simultaneous embeddings with vertices mapping to pre-specified points, by Taylor Gordon
• Multilevel drawings of clustered graphs, by Fabrizio Frati
• Outerplanar graph drawings with few slopes, by Kolja Knauer, Piotr Micek and Bartosz Walczak
• Fáry's theorem for 1-planar graphs, by Seok-Hee Hong, Peter Eades, Giuseppe Liotta and S Poon
• Unexplored Steiner ratios in geometric networks, by Lilach Chaitman-Yerushalmi and Paz Carmi

Every positive integer has a unique representation using a form of base-2 place-value notation (that is, the digits represent 1's, 2's, 4's, 8's, etc just as in binary notation) but where the digits are 1 and 2 rather than 0 and 1:

1
2
11
12
21
22
111
112
121
122
211
...

These same digit strings in the same ordering can also be interpreted as the ternary numbers that don't have any 0 digits. The successor to a number is computed by finding the lowest-order non-two digit, incrementing it, and resetting all the lower-order 2's back to 1's. This differs from ternary, where the successor would reset all the lower-order 2's to 0's.

It's also easy to add these numbers directly, by the standard right-to-left method with carries. Each carry is 0, 1, or 2; in each digit, we compute the sum of the two given digits and the previous carry, write down 1 if the sum is even and 2 if it is odd, and carry half the remaining amount.

ETA: Via OEIS I find "A number system without a zero" (Foster, Math. Mag. 1947) which does the same sort of thing in decimal.

The poster for Graph Drawing 2012 (in September in Redmond, Washington) is out, and it looks like they're using a Lombardi Spirograph drawing of the Nauru graph as a central design element.

The submission deadline is June 8, less than two months away, so there's still time to come up with new graph drawing ideas and write them up for the conference. The conference web site has more information.

Come on, Google, you can do better than this. Put the "you might like" entries under the stream, instead of under the trending topics. That way, you can reduce the useful part of the UI to an even tinier fraction of the screen, and make the web browsing experience match the smartphone experience even more closely.



ETA: For a lot more on this, see #whitespace. In other news, Google+ is now trying to be twitter as well as trying to be facebook.

The kids (and their parents) are still not too old to have some fun decorating eggs...

The list of accepted papers (with abstracts) to the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012) is now public.

(Via +Jukka Suomela and +SWAT 2012)

I've been having some fun lately making drawings of some famous configurations of points and lines (in most cases with equal numbers of points per line and equal numbers of lines per point). You can go read the Wikipedia article if you want detailed explanations, but here are just the pictures.

( Read more... )

Probably I knew this already long since and forgot, but I recently rediscovered the fact that the 2012 SIAM Conference on Discrete Mathematics is using one of my illustrations as its logo.



( Read more... )

At the end of the 18th century and the beginning of the 19th, combinatorics flourished in German mathematics research, under the leadership of Carl Hindenburg. Later opinion has not been kind:

"ill-advised and purposeless modification" — Sir Thomas Muir 1906

"of limited scope and restricted application" — Encyclopaedia Brittanica 1910

"mired in the mathematical trivia by which the School itself was plagued" — Manning 1975

"The faults of his [Euler's] time found their culmination in the Combinatorial School in Germany, which has now passed into oblivion" — Cajori 1991

"thousands of pages filled with esoteric symbolism that must have impressed many nonmathematicians" — Knuth 2006

Knuth goes on to call Heinrich August Rothe "Hindenberg's best student", and says that his work is "not completely trivial", but cites as evidence only an algorithm for finding the successor and predecessor of a morse code sequence in lexicographic order.

Here are some Rothe's other contributions, from just one of his publications:

• The first definition of the inverse of a permutation
• A proof that the number of inversions of a permutation (the concept that Muir called "ill-advised and purposeless") is the same as for its inverse
• A proof that the determinant of a matrix is the same as for its transpose
• A diagram (the Rothe diagram) still used for visualization of permutations and inversions
• The first definition of a self-inverse permutation
• A simple recurrence formula for the number of self-inverse permutations

Not completely trivial?!

Yes, these results are easy nowadays, but in part that's because we learn about permutations from our beginning years of college, if not earlier. And where did what we learn about come from?

The kids below (except for the two younger boys in front) have all known each other since they were babies. It's difficult to believe they're already getting ready to graduate from high school and scatter to the four winds to go to college.

Suppose you are given as input a sequence of moves in a game of Go; that is, just the positions at which each player moves in each turn. You want to verify in real time that this is a correct game sequence (no moves on top of existing stones or suicidal moves), recognize when a capture has been made, and identify the captured pieces. How quickly can you do this?

( Read more... )

If you've spent any time on Wikipedia you've probably noticed its red links, links on certain words and phrases that don't actually go to another Wikipedia article. They're supposed to flag topics where Wikipedia should have an article but doesn't, and encourage people to start editing a new article on the topic. And often they do work that way. But they also tend to accumulate, especially on lists, and once they start doing that they tend to include many words and phrases on topics that aren't ready to be made into articles.

So anyway, for the last few weeks (in my copious spare time) I've been clearing out the red from List of people by Erdős number. It was never intended to be comprehensive; that's for the Erdős number project or maybe for the collaboration distance calculator built into MathSciNet. Rather, it's just supposed to list the subset of people who both have (or should have) Wikipedia articles and have a small Erdős number. The #3 section of the list has been clear of red for a long time, and now the #2 is. Most of what I did was to remove names, but along the way I found quite a few people who (it seemed to me) should so clearly have articles that I made new ones. They are:

Baruch Awerbuch, Robert G. Bland, Hans Bodlaender, Derek Corneil, Danny Dolev, Rod Downey, Amos Fiat, Benedict Freedman, Nancy Freedman, Uriel Frisch, László Fuchs, Curtis Greene, John P. Hayes, David Jerison, Lila Kari, Anna Karlin, Jon Lee, Darrell Long, Heikki Mannila, Paul G. Mezey, Cris Moore, Bernard Moret, George Nemhauser, Nathan Netanyahu, Noam Nisan, Alfred van der Poorten, John E. Savage, Boris M. Schein, Norman Schofield, Eli Shamir, Mike Steel, Ileana Streinu, Subhash Suri, Stevo Todorčević, Dorothea Wagner, Stan Wagon, Tandy Warnow, Dominic Welsh, Moti Yung, and William S. Zwicker.

(There are one or two in there that I didn't make but expanded someone else's recently created one. And at least one of the names above is not actually on the Erdős number list.)

You might notice that they're not all the same length or level of detail. That has very little to do with how important I think these people are, and very much to do with how easy I found it to write about them. Also, the fact that I removed a name doesn't imply that I think that person hasn't met the Wikipedia inclusion criteria for articles on academics: there were quite a few other names that I removed from the list for whom I would support the creation of an article, but wasn't ready to do it myself.