Movember

Did you know that 1 in 6 men will get Prostate Cancer? If you are a man with a butt, or know a man with a butt, you should take notice that this is the month of MOvember, in which mustachioed gentlemen aim to “change the face of men’s health” by growing moustaches to promote awareness.

If you want to donate to the cause, visit http://ca.movember.com/mospace/423838. Incidentally, also let me know if you want to hire me to drive your truck.

Bound to Be a Good Time

I got my (draft) thesis printed and bound this week on Waterloo’s “espresso” book printer. It was fast, convenient, and cost about $10/copy (it turns out to be 60% the cost of printing it the normal spiral-bound way at the print shop). The only drawback I found is that there are still some bugs in the printing process: several fraction lines didn’t show up in the printing. Here’s a youtube of the printer in action.

Update: now with bacon

Comics Are Relevant

Evidence #1: “History’s Chumps” by Dinosaur Comics, after recent at-length discussions of chumpism. (Click for full size)

Evidence #2: “Backup Face” by Toothpaste For Dinner, which was posted the very night I almost lost my non-backed-up laptop in a bar, with my nearly-complete thesis on it.

There is a comic called “PhD Comics” which is not relevant, somehow, ever! So in their place I am going to give “Banana Dogs” by Superpoop which, while also not relevant, is awesome.

Better Know A Theorem: Polyhedral Union

Lausanne

This week I been at the EPF Lausanne, Switzerland. It has been a good opportunity to practice my French; there is not as much English spoken here as in the more touristic parts of the country. Nonetheless this is a good place to come if you are a tourist: it is nearby the beautiful lake Geneva, home to lots of awesome castles and old buildings, and good food and wine is plentiful. For some reason a main dish I see on a lot of menus is cold roast beef with tartar sauce, usually $25 (Swiss francs ~ Canadian dollars) — as of yet I don’t understand this.

In news that is not directly related, I was recently reading papers on a technique called disjunctive programming going back to the 1970s. The main tool can be interpreted as a very cute result having to do with the fundamentals of LPs that I will depict below. It has to do with taking the convex union of two polyhedra. It’s very simple but seems relatively unknown (or at least, I have seen it buried deep in papers but never in courses where it would fit well).

Polyhedron P1

A linear program in two dimensions can be thought of as a polygon (dots connected by straight lines), pictured as “P1″ at the left. There are several “linear constraints” which are all of the format

“2.1 * x + 1.8 * y ≥ 6.7″

and this particular constraint is the line pictured with the vector (arrowhead)

Polyhedron P2

coming out of it. This constraint says that only points to the right of that line are feasible for this constraint; P1 here has 4 other constraints corresponding to its four other sides, and the feasible region is the pentagon. At the right is a second polyhedron which I will call P2, which is similarly defined by four linear constraints.

Intersection of P1 and P2

Now can we get a collection of constraints which expresses the intersection of these two polyhedra? In this case it is easy: simply take all the constraints of P1, and throw in all the constraints of P2, then the feasible region of the resulting system is exactly the intersection of P1 and P2. The intersection polyhedron is pictured in black on the left-hand side. (In this example, there are 9 constraints, but the intersection polyhedron has only 7 sides, since two of the these constraints become redundant.)

Convex Hull of Union of P1 and P2

Whenever you do something with an intersection in mathematics, it is natural to ask if you can do the same thing with a union. That is to say, can we get a linear program to express the set of all points which lie in either P1 or P2 or both? Immediately we can see there is a problem with this, since linear programs can only express convex regions, and the union may not be convex. But it turns out there is an easy way to express the convex hull of the union of P1 and P2, i.e. the smallest convex set containing both P1 and P2 (pictured on the right-hand side).

To fully explain, we will need some symbols. Let z be a vector containing all the variables of the linear program, suppose P1 is represented by the linear system A₁z ≥ b₁ and P2 is represented by the linear system A₂z ≥ b₂. Essentially by definition, the convex hull of the two convex shapes P1 and P2 is equal to

The problem is that this program in variables is not linear, e.g. since we are multiplying with . But the slightly tricky & nice part is that if you rescale the variables, you get the following linear formulation for the same set:

Good times with linear programs! This type of method leads to something called “lift-and-project” in the literature which amounts to automatically strengthening a linear program in such a way that is becomes “closer” to having no fractional vertices.

10 Euros of Guilty Pleasure

I am now in Copenhagen where I gave a talk at the European Symposium on Algorithms. This conference has been excellent and I got to see a laser show last night at Tivoli, a very old amusement park. On the way here I had a very long stopover in Brussels, where as it turns out, I was able to attend the last day of the Belgian Beer Fest! Photos below feature:

• Two of the three beers I got: Waterloo Dark (not the one made in Waterloo, ON) and Cuvée des Trolls
• Fries with Bearnaise and Andalouse sauces (both extremely tasty)
• A church – the fry shop is at the bottom right

Cuvée des Trolls

Selling Out To The Man

I am in Chicago this week for the International Symposium on Mathematical Programming. I have found that the chain restaurants (which I am defining as 3 locations or more) here are pretty awesome:

• Wow Bao chinese buns
• Corner Bakery breakfast joint
• Argo Tea cafe
• Heaven on Seven soul food (the food was just OK but they have a billion hot sauces)

whereas the non-chain restaurants are batting only about 50%

• Fox & Obel gourmet supermarket was great and cheap for lunch
• some overpriced Italian restaurant
• tasty crawfish boil & green tomatoes at Lagniappe’s
• horribly awful overpriced Caesar salad on the “miracle mile” street

It is sort of sad since it means that the more fun strategy of “go randomly walk around until you find some awesome hole-in-the-wall” doesn’t seem to work that well downtown.

The conference itself is very large (several hundred presentations) but relaxed since the talks are 30 minutes, longer than most others I have been to before. I gave a presentation which went well, it was on pretty specialized technical material but helpful advice to make it non-technical seemed to pay off. It has been nice to just focus on research this week, I believe the last such week for me was a long time ago!

Survivor: Granville Island

Last week I went with a friend to Vancouver and took a day walk to Granville Island, located about a 40 second sea-bus ride from downtown. The island has a number of fanciful shops including a large market, where a few fruits that I have never seen before (and mostly never heard of) caught my eye. After consulting with the purveyor to see which ones I would be able to eat without any preparation, I bought the three things pictured at the right:

• salak (snake fruit)
• kalamansi
• sweet tamarind

Snake fruit

The snakefruit came with the dire warning “you probably don’t want to smell that, just go right ahead and eat it.” It tasted like lychee, mostly, but firmer with a silky texture (overall, like a slightly unripe peach).

Lately, trying to get some cables and memory to work, I have been annoyed that USB comes in three sizes (normal:mini:micro) and SD memory is the same. I would say that the ratio of limes:key limes:kalamansi basically fits the same pattern. I squeezed it into my water & it was very tasty.

Sweet tamarind

The tamarind was something whose name comes up a lot in foreign cooking, e.g. pad thai, but this one’s different, “a carefully cultivated sweet variety with little to no tartness grown specifically to be eaten as a fresh fruit” according to wikipedia. It has a lot of inedible parts, all very different: the thin hard outer shell (like a peanut shell), a brambly part that connects it all together, husks that contain each individual seed, and the seeds themselves. The edible part is a jam-like substance that is mushed up with the brambly part and around the husks. It tasted like the inside of a fig newton but a million times better, definitely worth the effort to get around the inedible parts.

Granville Island had a bunch of other cool stuff including a brewery, a very small amount of this stuff is in the pictures below.

Berries @ Granville Market

Fruits @ Granville Market

Siegel’s “possibly the best bagel in the world”

Vegetable Market Stand

Day of Global Solidarity with Iran

Over the past 6 weeks I have been following the post-election events in Iran. It has been very additctive for me to follow the story of the alleged vote-rigging, attempts to quash protests, and crazy political stuff going on. As a nerd I have been compelled by the fact that the use of electronic media by both sides has been unlike anything seen before: demonstrators use Facebook and Twitter to get out information, while the regime is said to be using technology akin to electronic wire-tapping in order to track down dissidents. But the suffering is real and very serious there, many dissidents have been killed or imprisoned and the regime continues to attack protestors.

Today is a global day of protest for the human and civil rights that the regime has taken away from its citizens. If you want to find out more about these events, or about what’s been going on in general, check out the NIAC Blog or the Huffington Post. The article “How Geeks (and Non-Geeks) Can Help Iranians Online” is a good read. Some places that are looking for financial contributions are counter-censorship projects like Tor, and reporting venues like Tehran Bureau who is looking to hire a translator. Mention the issue to friends if you think it is important!

Better Know A Theorem: Regular Graph-Subgraphs

My work on linear programs led me to read up on colouring arguments and eventually to post some remarks on the arXiv wherein I gave a proof ot the following. (See “graph” and “regular” on Wikipedia. A “spanning subgraph” is what you get when you delete some edges, but keep all the vertices.)

For every pair of integers 0<=m<=k, every 2k-regular graph contains a 2m-regular spanning subgraph, and every (2k-1)-regular graph contains a spanning subgraph all of whose degrees are in {2m-1, 2m}.

This has a natural generalization which I did not know how to prove, but seemed like it might be true:

(*) For every integer 0<m<=k, every k-regular graph contains a spanning subgraph all of whose degrees are in {m-1, m}.

How would one possibly prove such a thing? After thinking about it a few times, I opened up my electronic copy of the bible of combinatorial optimization and found this was proved by László Lovász in 1970, again by Bill Tutte in 1978, and again by Carsten Thomassen in 1981.

Thomassen is well-known for giving elegant proofs of hard theorems by making them even harder and then using induction. What I mean by this is that, to prove some statement T with no obvious inductive proof, you make some other stronger statement U such that U implies T, and such that U does have an easy inductive proof. I saw proofs of his that exibited this strategy when learning graph theory (the 5-list-colorability of planar graphs, explained here and here) and again at a recent conference in Montreal.

In this case the strengthened version of (*) is

(**) For every integer 0<m<=k, every graph all of whose degrees are in {k-1, k} contains a spanning subgraph all of whose degrees are in {m-1, m}.

Note that compared to (*), we have relaxed the restriction on the input graph, since a k-regular graph meets the hypothesis of (**). In fact it suffices to prove the following special case of (**):

(***) For every integer 0<k, every graph all of whose degrees are in {k-1, k} contains a spanning subgraph all of whose degrees are in {k-2, k-1}.

To see that (***) implies (**), note that we can repeatedly apply (***) to an input graph with degrees in {d-1, d} to get one with degrees in {d-2, d-1}, then one in {d-3, d-2}, etc. And (***) has a proof that is reasonably straightforward: first note that we can repeatedly delete any edge joining two vertices of degree k, and then we use Hall’s Theorem which is something most undergraduates in discrete math learn here at Waterloo.

Good times with induction!

The Internets

Today, on a news blog that is covering a lot of up-to-date information from Iran, I found an article on how internet bandwidth has been changing since the elections. Here is the picture:

I get antsy if my internet access is down for two hours (since this prevents me from downloading an album or two) so it is an understatement to say that it is a shitty move on behalf of the ruling regime to throttle usage in this way. The same article mentions

Iran has significant commercial and technological relationships with the rest of the world. In other words, the government cannot turn off the Internet without impacting business and perhaps generating further social unrest. In all, this represents a delicate balance for the Iranian government and a test case for the Internet to impact democratic change.

Who knew 0s and 1s were so important?