November 5th, 2009

beartato phd

(no subject)

Some things that have gone wrong lately but are more or less acceptable:

My office is at a pretty steady temperature of 85 degrees now. I complained about this a week ago-ish when it hit 80 and, allegedly, gears are turning, and maybe eventually it will be fixed.

My bicycle's tires started to get a little low on air, and I thought, hey I'll by a cheap little pump and pump them up a bit, and promptly did everything wrong and let all the air out of my back tire. After escargonaut heroically helped me a lot over the phone, I still couldn't get any air to apparently get into the tire and I finally gave in and went back to the bike shop and they just air-compressored them back to normal shape.

The moral here is that when you are a Educated Person and fancy yourself an Adult at least and on a good day Generally Quite Clever, and it's just about the most painful thing in the world to have --- and not only to have, but to display in front of an entire store full of people who know what's what --- the sort of obliterating, flailing, not-even-a-rudimentarily-correct-mental-model ignorance (the sort that you can just hardly fathom any non-troglodyte human having when it is about your own favorite problem domain), it is actually a good idea to just suck it the fuck up, ask for help when you need to, and try to observe and by observation learn a couple of things if you can. Now I know, for instance, that there are two types of air valves, one common in low-pressure mountain bike tires, one in high-pressure road bike tires.
beartato phd

(no subject)

I do so love Lipton's blog. The linked entry mentions the graph reconstruction conjecture which is a beautiful little open problem in graph theory. In one sentence, it is:

A graph (on at least 3 vertices) is uniquely determined by the multiset of all possible vertex deletions of it.

Determined up to isomorphism, that is. A vertex deletion of a graph is the graph you get out of deleting some vertex and all the edges incident to it. You have to say at least 3 vertices because it's just not true for 2! There are only two graphs on 2 vertices, * * and *→*, which both have {*,*} as their multiset of vertex deletions.

There's a related (stronger) conjecture,

A graph (on at least 4 vertices) is uniquely determined by the set of all possible vertex deletions of it

And there you can see the 4 is necessary, because the multiset of vertex deletions of
* *→* is {* *, * *, *-*}, and that of *-*-* is {* *, *-*, *-*}, and these collapse to the same set if we ignore multiplicities, {* *, *-*}.

Here's a question I thought of:
Given n, what is the smallest pair of graphs G and H such that ||D(G) ∩ D(H)|| ≥ n, where D(G) is the set of vertex deletions of G?

I can't even think of graphs such that ||D(G) ∩ D(H)|| ≥ 3! I sort of expect they must exist, though. The thought of there being a constant upper bound on ||D(G) ∩ D(H)|| for all G and H seems absurd. I bet this could be refuted by playing with the output of Nauty, which contains tools for generating all nonisomorphic graphs over n vertices, and testing graph isomorphism.

---

Ah, thought of a pair over four vertices just by pencil-and-paper brute force.
   o--o
   |
o--o--o

   o--o
   |  |
o--o--o

both possess vertex deletions
o--o   o--o
|      |
o--o   o

   o
   |
o--o--o

and then each has one more that distinguishes them.

---

Another example that is smaller with respect to jointly how many distinct vertex deletions exist of of G (3) and H (4):

G           H
  o---o       o---o
 / \ / \     / \ / \
o---o---o   o---o   o


Maybe the right question to ask is how small you can get the distinct sets of vertex deletions of the pair
such that their intersection is at least n big. In this case (||D(G)||,||D(H)||) = (n,n+1) for ||D(G)∩D(H)||=n is as close as you can get without violating the second conjecture above (which violation would require (n,n)), and this does in fact obtain for n=1,2,3.