Bounded in a Nutshell

I was playing around with some new ideas earlier this week; that's usually a sign that my research brain is swinging from asleep to awake and hollering. In this case, it was prompted by my having to proctor tests without any other diversion than a pen and a pad of paper. Anyhow, in my musings I came up with sort of a neat construction. Specifically, I figured out that every simple graph can be found as an induced subgraph of some Kneser graph.

What that means for those of you who don't do this stuff for a living: I work with graphs, which are configurations of dots and lines. That's not much of a definition, and so it admits quite a lot; any random, irregular collection of dots, with pairs either connected by a line or not, qualifies as a graph. An induced subgraph is what you get when you take a graph and only concentrate on a part of it: some collection of dots, and any lines only involving those dots. And a Kneser graph is a highly regular, symmetrical sort of structure.

And hence: any graph, any configuration of dots and lines – no matter how arbitrary it looks, no matter how irregular – can always be seen as a small part of something ordered and balanced. Contrariwise, highly structured configurations can, when looked at closely enough, be made up of the strangest things.

And I thought that was kind of cool.

This appeared in my mailbox tonight: not spam, so much as the template for spam.

Subject: Never-seen {SPUR_2} Take pleasure from

Dear user.

{SPUR_1} 

{SPUR_3}

 {SPUR_4}

 Find what you need: {SPUR_DOMAIN} 

 Come on in and get it all very cheap!

There's a lot about mass commercial e-mail that strikes me as essentially pointless – the mangling of language to get e-mails past spam filters, for instance, to the point of illegibility – but a spammer who can't even be bothered configuring their mass mailer? I'm almost prepared to believe at this point that the computers are doing this themselves, and that this is some AI's cry for help.

I am drunk on the power of networked library systems. While they won't quite deliver books to my door, the results are generally close enough.

So remember how last month I posted about iTunes 7? This post was presumably sucked in by a search-engine spider (as all blog posts ultimately are), and was thus found by a reporter for the Wall Street Journal. The reporter in question was apparently researching for a story on buying movies from the iTunes Store, and wanted to know more about the problem I mentioned in the last bullet-point of my post. So she interviewed me, and has apparently cited me in the piece. (I don't subscribe to the WSJ, so I can't really say for sure that this is the case.)

So there's a lesson worth remembering: the Internet forgets nothing and forgives nothing. If you write something on the web, eventually someone on the web will read it. That thing might get you interviewed, or it might get you fired.

(Secondary lesson: rig up some site stats that record search strings from referers. I'm kind of curious exactly how the reporter found the Nutshell now.)