10 December 2013 @ 01:51 pm
The list of new ACM fellows is out. This year's batch includes two of my UCI colleagues (Rina Dechter and Padhraic Smyth), another former UCI colleague (Mark Ackerman), and theoretical computer scientists and algorithm researchers Mihir Bellare, Sampath K. Kannan, Jon Kleinberg, Madhav V. Marathe, Satish Rao, David P. Williamson, Moti Yung, and David Zuckerman. Congratulations, all!
Tags: ,

08 December 2013 @ 04:07 pm
My sister-in-law and nephew with their dog,
and my daughter with a small guitar.

07 December 2013 @ 07:55 pm

Like most universities, UCI has a requirement that doctoral students get someone outside their own school to serve on their committees (only for us it's the candidacy committee instead of as most other places the thesis committee). Anyway, last week I found myself on the committee of a student in mechanical engineering, whose research project involves developing software to analyze the motion of mechanical linkages formed by systems of linked rigid bodies. In the class of systems he was interested in, the rigid bodies (links) lie in a plane, although they may cross each other. Pairs of links are connected at joints that restrict their relative motion to be a rotation, and (if one of the links is fixed in place) the whole system should have only one degree of freedom. A pair of scissors gives a familiar example with two links and one joint. Apparently car trunk lids are usually connected to the car body using four-bar linkages – at least, mine appears to be – and one of the other engineers at the exam said this was because a simple hinge would cause the lid to bump into the rear window of the car. Here are a couple of more complicated examples, with eight links:

)

22 November 2013 @ 11:16 pm

Find a planar graph all of whose faces (including the outer face) are all quadrilaterals. Possible choices include the square, the cube, K2,n, etc. (All such graphs are bipartite, a fact that will be useful below.) Turn it into a maximal planar graph by adding a new vertex inside each face, connected to all the vertices of the face. For instance, doing this to a cube produces a tetrakis cube, whose graph I've written about previously here. So for short, let's call the result of this construction a "tetrakis graph".

)

11 November 2013 @ 07:55 pm
It's been six years, but we went back to Joshua Tree again for the holiday weekend. Since the place we usually camp (Indian Cove) has no actual Joshua trees, we took a swing through the main part of the park afterwards to see them.

Something I find fascinating about Joshua trees (besides the fact that like tree ferns they're not trees at all) is the way they embody mathematical binary trees so naturally: they go straight for a while, then they bifurcate, then straight a while again, etc. I think I've heard that they tend towards being complete binary trees, because the branches are all likely to bifurcate at the same time, but that was obviously not true of all the trees I saw. It's a phenomenon that's easier to see in the smaller trees that have only branched a few times, rather than the big tangled ones. I tried to capture some of that in my photos, but I don't think I really succeeded.

The rest of the gallery.

09 November 2013 @ 02:08 pm
I've been working lately on the Wikipedia line graph article, and am only a few [citation needed]s away from clearing all its cleanup tags. In doing so, I ran across a neat result in structural graph theory by Frédéric Maffray, describing the graphs in which the only odd simple cycles are triangles.

These graphs had previously been known as the ones whose line graphs are perfect (and are therefore called "line perfect graphs"), but neither of those descriptions is really satisfactory mathematically, because they say what the graphs are not (they don't have long odd cycles) or what some derived objects do, rather than anything about the graphs themselves. And they're not satisfactory from my point of view as an algorithm designer because they don't tell you how to recognize these graphs efficiently.

Instead, what Maffray showed is that these graphs are exactly the graphs for which each biconnected component is one of three possibilities. It can be bipartite, the complete graph K4, or a book of one or more triangles sharing a common edge (K1,1,n).

How did Maffray do it?

)

08 November 2013 @ 09:26 am
Whenever I try to access dmtcs.org lately (the web site of open-access journal Discrete Mathematics & Theoretical Computer Science) I get (not from the front page but from the one it redirects you to) a scripting error, "Parse error: syntax error, unexpected $end in /global/web-serveurs/dmtcs/htdocs/ojs-2.2.4/cache/fc-journalSettings-1.php on line 166". It doesn't seem to depend on which browser I use. And because the web site is broken, I don't know who to contact to let them know their site has a problem. Does anyone know what's going on there? I haven't published in that journal myself, but I have referred to papers from there, so I want to be sure they continue to exist. The scientific literature is supposed to be permanent. This looks like just a temporary glitch but it's worrisome that it's been this way for at least several days. (It's also worrisome that, going by the numbers of papers listed in MathSciNet, they seem to be slowing down in their publication rate.) Update Nov 12: After the end of the French holiday weekend, the problem has been fixed and the site is back up again. 26 October 2013 @ 07:07 pm Some cleanups I've been making to the Wikipedia article on Bell numbers (and the new related article Bell triangle) have led me to play with the mathematics of rhyme schemes. ) 17 October 2013 @ 08:50 am arXiv now does MathJax! That means that when uploading new papers, you should leave the math dollar-sign delimiters in your abstracts rather than stripping them out. There doesn't seem to be a clean way to fix old abstracts without uploading a new version of your paper. Google is now turning what it knows about your online activity into product endorsements, in which it puts your face on ads that it shows to other people! But you can stop it. Here's how. Twice recently I've rounded up what I pay for something in cash so that the change I get is in larger bills (example: paying$12 on a bill of nearly $7 so that I get$5 and change back) and had the cashier, in total bewilderment, try to hand me back my extra ones as if I was crazy and didn't know how to count. I realize they haven't been able to do arithmetic in their heads for a while, but they could still punch numbers into their machines. I think this new bafflement with how change works must be caused by the fact that so few people use cash any more. But it's tempting to blame their unfamiliarity with the 5-adic number system (in which 12 is closer than 10 to 7).

16 October 2013 @ 10:28 pm
My co-authors and I have another paper on superpatterns up on the arXiv, "Small Superpatterns for Dominance Drawing", arXiv:1310.3770. It's a follow-up to our Graph Drawing paper, which used superpatterns for 213-avoiding permutations to improve the size of universal point sets for straight-line planar drawing. This one instead considers a different drawing style, dominance drawing, which led us to the problem of finding small superpatterns for 321-avoiding permutations.

If you shuffle a deck of cards (just once, using a single riffle) then the permutation you get will be 321-avoiding. (It will also avoid some other patterns as well.) 213-avoiding and 321-avoiding permutations are very similar to each other in many ways; for instance, there are the same number of them (the Catalan numbers). However, their behavior with respect to superpatterns is not so similar, and we were able to find significantly smaller superpatterns in this case, with size proportional to n3/2 instead of n2.

This will be appearing at ANALCO, which unlike previous years is concurrent with SODA instead of prior to it. So if you're going to SODA anyway, check out the program; you might find some interesting side talks.

07 October 2013 @ 10:32 am
My new OEIS sequence for the weekend: A227937. It begins 1, 0, 1, 3, 10, 25, 105, 385... and counts the number of partitions of a set of n items into subsets that must have either two or three elements per subset.

A polynomial recurrence relation is not hard to derive from the fact that the nth element must either be in a set of two (of which there are n–1 choices) or a set of three ((n–1)(n–2)/2 choices). From this recurrence, it follows that once three consecutive values in the sequence have the same divisor, so will all subsequent values. So, it tends to pick up prime factors as it goes, causing later values in the sequence to be highly divisible. For instance,

a(102) = 512 78 115 134 173 193 233 292 312 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 3229 134593 292152888047 72472250580547

In fact, all prime powers not of the form 2k or 3k each divide all but finitely many values in the sequence. I don't see how to derive this from the recurrence easily, but here's a direct proof: The number of partitions for n is equal to the sum, for pairs (a,b) such that 2a+3b=n, of partitions of n into sets of size 2a and 3b, multiplied by the numbers of partitions of 2a into pairs and 3b into triples. The number of partitions of 2a into pairs is a double factorial (eventually divisible by all odd numbers) and the number of partitions of 3a into triples is a multinomial that is eventually divisible by all numbers prime to 6. So for each term in the sum, at least one of its three factors is divisible by large prime powers, and it follows that the same is true for the whole sum.

I'll leave to others the task of filling in OEIS with the counts of partitions into sets of other restricted sizes, but I think there must be quite a few other interesting sequences in that vein.

30 September 2013 @ 05:34 pm
The call for papers for the 40th International Workshop on Graph-Theoretic Concepts in Computer Science is now online; submissions are due March 1. The actual conference will be in late June, at a chateau near Orléans, France.

For those who don't know, WG is centered on the topic of graph algorithms, and (more than many other algorithms conferences) welcomes research involving special classes of graphs. Despite the name I think it's more of a symposium than a workshop: that is, it consists of presentations of selected papers, which are collected in a proceedings, rather than having working groups, more informal talks about in-progress research, and no proceedings. It's somewhat but not highly selective: for instance, in 2009, the acceptance rate was around 40%. It's held annually, usually in central Europe. I'd go a lot more often if it weren't so far away from me.

28 September 2013 @ 12:39 pm
This summer, Bordeaux has had a big public art exhibit of pieces by Jaume Plensa in many of its public squares. Here's one of them, "House of Knowledge" (a giant hollow human figure made of letters) from the inside.

27 September 2013 @ 11:38 pm

I was just in Bordeaux, France, for the 21st International Symposium on Graph Drawing. Some highlights:

)

ETA: See also André Schulz's report from the same conference.

16 September 2013 @ 10:18 pm

14 September 2013 @ 03:34 pm
Johns Hopkins violates academic freedom of faculty blogger, backs off when called on it. I knew there was a reason I kept this thing off-site...

Nationality-based blacklisting from academic publishing. Via Gowers. Given that I apparently live in a rogue surveillance state that tortures people, conducts undeclared cyberwar against the French, etc., this sort of collective punishment for government misbehavior troubles me. I suppose it's better than bombing them, though.

And, to make up for all that seriousness:

PingFS: keeping your data in the cloud by juggling raindrops.

You know how I recently posted that attaching labels to the things they label by curves or slanted lines would be better than axis-parallel polylines? This isn't what I meant. And many more bad ideas in information visualization, via MF.

Hexadecimal metric system. Complete with a new method of writing hexadecimal numbers, using a system of syllables for digits in which the consonant of each syllable tells you the digit value (in the obvious ordering q, b, p, v, f, z, s, d, t, j, c, g, k, y, x, w, h) and the vowel tells you what power of 16 it should be multiplied by.

12 September 2013 @ 02:39 pm
This is a snub cube, radially projected onto its circumscribing sphere and then stereographically projected onto the plane. It's not quite a Lombardi drawing, because the angles of the quadrilateral faces are wider than the angles of the triangles. But I think it sets a good balance between optimizing the angular resolution around each vertex and preserving the property of the snub cube that, within each face, all the vertex angles are equal.

02 September 2013 @ 12:23 am
This Wednesday's deadline for the final proceedings version of papers for Graph Drawing 2013 must be drawing near: tonight's update to arXiv.org includes seven new preprints on graph drawing. They are:

)

01 September 2013 @ 03:01 pm

The ceiling function rounds numbers up to a not-smaller integer; it is denoted by surrounding its argument by the \lceil and \rceil symbols in LaTeX, &lceil; and &rceil; in html, or ⌈ and ⌉ in unicode. They look sort of like the top halves of square brackets. By analogy to the shape of these symbols, let's call a curve formed from two rays with a common apex, one vertically downwards and the other horizontal in either direction, a ceiling. Geometrically, ceilings behave a lot like lines, and with care this analogy can be made precise.

)

28 August 2013 @ 10:49 pm
Another of my Graph Drawing papers, "Fixed parameter tractability of crossing minimization of almost-trees" (with Michael Bannister and Joe Simons) went up on the arXiv as arXiv:1308.5741 yesterday.

Although it's mostly a technical paper about algorithms, it has a non-technical point as well: in many application areas of graph theory and graph visualization, the graphs have only a few more edges than vertices, meaning that they tend to have large tree-like parts and only a few cycles. It seems like a good idea to take advantage of this structure when visualizing these graphs, and in some of these applications the division between the tree-like and cyclic parts is important and should stand out in the visualization.

The image below is a case in point. We redrew it from a graph in a paper by Potterat et al (reference 24 of the paper), describing the self-reported sexual contacts among a set of people treated in an AIDS outbreak. According to our references, the cyclic parts of this sort of graph (the central circle) correspond to the growth phase of an outbreak, and the tree-like parts (the outer rings) correspond to its decline phase.

The only tricky part about generating a drawing like this is ordering the vertices in the central circle, in order to minimize its crossings, and that's what the technical parts of the paper (or at least the 1-page parts of it) are about.