and my daughter with a small guitar.
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:( Read more...Collapse )
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".( Read more...Collapse )
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.
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?
( Read more...Collapse )
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.
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).
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.
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.
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.
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.
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, ⌈ and ⌉ 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.
( Read more...Collapse )
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.