The Spectral Lower Bound to Edge Expansion

In which we dwell at great length on the “easy” part of Cheeger’s inequality.

The edge expansion of a graph , defined as

is a measure of how “well connected” is a graph. A graph has edge expansion at least if and only if, in order to disconnect a set of vertices from the rest of the graph, one must remove at least edges. In other words, the removal of edges from a graph of edge expansion must leave a connected component of size , where is the number of vertices.

As readers of in theory know, graphs of large edge expansion (expander graphs) have many applications, and in this post we are going to return to the question of how one certifies that a given graph has large edge expansion.

For simplicity, we shall only talk about regular graphs. In a previous post we mentioned that if is the adjacency matrix of a graph, there are numbers (the eigenvalues of ), not necessarily distinct, and an orthonormal basis of , such that for all

And if the graph is -regular, then , , and for all we have . Finally, the numbers and the vectors are computable in polynomial time. (This is all the linear algebra we will need.)

Given this setup, we have the lower bound

That is, the difference between largest and second largest eigenvalue gives a lower bound to the edge expansion of the graph.

Although (1) is very easy to prove, it is a remarkable result, in the sense that it gives a polynomial-time computable certificate of a “coNP” statement, namely, that for all cuts, at least a certain number of edges cross the cut. Since computing edge expansion is NP-complete, the inequality cannot always be tight. Eventually shall compare it with other methods to lower bound the edge expansion, and see that they are all special cases of the same general approach. To begin with, in this post we shall show that is an efficiently computable relaxation of the edge expansion problem. (Or, rather, of the closely related sparsest cut problem.)

Cheeger’s Inequality and Other Approximations of Edge Expansion

Cheegers inequality relates the expansion of a graph to its eigenvalue gap.

There are at least three contexts where this result arises and is important:

People’s Fries

By electing an anti-intellectual conservative as president, France has mended its relations with the US, but a new crisis is brewing.

While disabled athlete Jin Jing was carried the torch during the Paris leg of the Olympic torch relay, wheeled on her wheelchair, several protesters ran around her, and one tried to snatch the torch.

The guys in blue tracksuits are nowhere to be seen, so this must have happened before Jin Jing’s torch was lighted, probably on her way to the relay.

The incident, unheard of in the West, has incited anti-French sentiment in China, and there are grassroots calls for a boycott of Carrefour (a French chain of drugstores and supermarkets with many branches in China) and of French products.

More generally, there has been broad outrage at the coverage of the riots and crackdown in Tibet by Western media. In this CNN interview, for example

one sees images of Tibetan protesters being taken away by uniformed officials, with a clear implication that those are images of the crackdown in Tibet. The uniformed officials, however, look less Chinese than I do, and the images are either from Nepal or India.

The very popular “anti-cnn” website has a number of such occurrences where images from Nepal and India are shown as from Tibet.

While the incompetence of Western media is no news to those who read them regularly, it takes an ominous tone in China, where media distortions are a state policy. An otherwise sane friend of mine has posted on his Facebook page (ostensibly, unironically), this article that argues how the protests along the torch relay were the result of a CIA conspiracy.

In lighter news, the Chinese government demanded an apology from CNN after commentator Jack Cafferty called the Chinese “goons and thugs.”

They “apologized” by explaining that the remark did not apply to all Chinese people, but only to the government. The Chinese government has not accepted the apology.

An elegant proof marred by an unfortunate haircut

One year ago, Vijay Vazirani proposed to add videos to conference submissions. Apparently Elsevier’s Journal of Number Theory is going to implement a similar process, except that videos will be sent only after the review process. (This is a crucial difference, and I favor this more conservative approach.)

Socialists in the Senate: USA 1 – Italy 0

What has happened in Italy is still too painful to talk about, but consider this: the Honorable Bernie Sanders, the junior Senator from Vermont, is a Socialist. Because of the bad timing of the elections, quirks of the new electoral law, the ever-present suicidal tendencies of the Left everywhere, and the way the new “Partito Democratico” was founded, there is now no Leftist party in the Italian Senate, for the first time since the Republic exists. The most progressive party is this new left-center-right party whose members range from moderates to Catholic conservatives (read: religious nuts), and which has the American Democratic Party as a model.

It was even worse in the race for Mayor of Rome, which was, to translate to the American setting, one between a more openly Fascist version of Giuliani and a less progressive version of Huckabee.

And I predict that soon the Chinese will be able to say, sure CCTV is a lying state-controlled propaganda machine, but have you seen RAI?

Too much of a good thing

The San Francisco International Film Festival starts in less than two weeks, and the program includes 104 movies, described in a 146-page program guide.

If any of you Bay Area readers has already done the work of studying the program and picking good movies, please do leave your recommendations in the comment thread. (I am writing notes on PCP for my class, I haven’t done my taxes yet, there is a long-overdue post on Cheeger’s inequality coming, and the energy to read through 104 movie reviews is lacking.)

It Works Every Time

Mayor Newsom pwned the protesters with the oldest trick in the book, the bait-and-switch. The Olympic torch relay was scheduled to start near the stadium, and go along the Embarcadero (the Eastern waterfront) until Fisherman’s Wharf; police barriers were set along the route, and thousands of people, including countless would-be protesters, converged there.

But, after a lightening ceremony at the stadium, the flame was then taken to a bus and rushed to Van Ness, whence it was uneventfully relayed along a secret alternate route that took it North to the Marina (the Northern waterfront), and near the Golden Gate bridge, while all the protesters were stuck along the Embarcadero.

Now the flame is back to San Francisco airport, and going to Buenos Aires. Or isn’t it?

One World, One Protest

The Olympic flame is following me around. It arrived in Beijing last Monday, as I was leaving town, and by way of Kazakhstan, Turkey, Russia, London and Paris it will reach San Francisco in two days.

A small contingent of Uighur people protested in Istanbul along the route of the relay, calling for the independence of Xinjiang, the majority-Muslim province of China known for its delicious lamb dishes.

But all hell broke loose in London, with protests (mostly about Tibet and about the Sudan) along the entire length of the relay. Reportedly, one protester charged at the torch-bearer with a fire extinguisher, but missed, dousing the police escort with foam instead. The general idea of the torch relay is that the flame, lit in Greece, should be alight for the whole time of the relay, and until the opening ceremony in Beijing in August. Thus a set of ten lanterns lighted with the “original Greek fire” travel along the relay route, so that if the torch goes out, it can be relighted with original Greek fire. The flame(s) travel with 12 Chinese security guards, who also run along the relay route. If, like me, you thought that men in tracksuits and fanny packs could not possibly look menacing, you were wrong.

In Paris, the torch went off, and had to be relighted, at least five times. Finally, for a good part of the relay, the torch moved in a bus. Notice the French police escorting the bus on rollerblades.

With due respect, nobody does street theater and political protests like San Franciscans, so I wonder what’s going to happen on Wednesday.

As a warm-up, today three activists climbed the suspension cables of the Golden Gate bridge, and unfurled two banners, one reading “One World, One Dream,” the motto of the 2008 Olympics, and another reading “Free Tibet 08.”

Tomorrow, there will be all-day events at Civic Center, which will include a march back and forth the Chinese consulate, which is on Laguna and Geary, quite far from the Civic Center (this won’t be good for traffic in the city). Some of the events will feature noted Tibetan Buddhist Richard Gere.

And here (via Boing Boing) is information on what’s planned for Wednesday. (Wear your Tibetan clothes!)