Michael Schapira: Internet Routing, Distributed Computation, Game Dynamics and Mechanism Design I

This post is authored by Michael Schapira. (It is the first in a series of two posts.)

In this post, I’ll outline work on Internet routing and sketch important areas for future work, both on routing itself and, more broadly, on mechanism design, game theory and distributed computation.

The Internet comprises administrative domains known as Autonomous Systems (ASes), which vary in size, from large (multi)national networks to small networks servicing schools or small businesses. The task of establishing routes between ASes, called interdomain routing, is currently handled by the Border Gateway Protocol (BGP)—the core routing protocol of the Internet. BGP is one of the most critical pieces of the Internet’s infrastructure and can be regarded as the glue that holds the Internet together.

Over the past decade, routing with BGP has been studied from engineering, computational, game theoretic and economic perspectives. Combining algorithmic and economic considerations in the study of interdomain routing is natural, because the many separate domains that make up the Internet are independent economic agents that must jointly execute a distributed algorithm in order to route traffic. In addition, interdomain routing motivates exciting new questions in computer science, game theory, and economics.

A (Simplified) Model of Interdomain Routing

The following is a simplified model of interdomain routing, based on the seminal work of Thimothy Griffin and Gordon Wilfong, and on the game-theoretic model of Hagay Levin, Michael Schapira, and Aviv Zohar   Continue reading

Joe Malkevitch: Why Planar Graphs are so Exceptional

Not only do interesting questions arise by considering the special class of planar graphs but additional special issues arise when one considers a specific plane drawing of a planar graph. This is because when a graph is drawn in the plane it becomes possible to order or number, say for example, the edges at a particular vertex of the graph, in an organized consistent way.

One example of results which started from this reality for plane graphs is this paper of Grunbaum and Motzkin: B. Grünbaum and T. S. Motzkin , The number of hexagons and the simplicity of geodesics on certain polyhedra. Canad. J. Math. 15 (1963), pp. 744–751. In this paper the following is explored (along with results about what today are called fullerenes). Suppose one has a 3-valent plane graph. If one picks any edge and moves along that edge (in either direction), when one gets to a vertex one has the choice of going left or right and moving on to another edge. Suppose one goes left, and at the next vertex in one’s “traversal” one goes right, alternating left, and right. Grunbaum and Motzkin refer to this as left-right path, and they prove that for a plane 3-valent graph with each of its faces having a multiple of 3 for its number of sides, that these left-right paths (starting on any edge) always generate “simple circuits.”

I was able to extend this result in several directions. Continue reading

(Eran Nevo) The g-Conjecture III: Algebraic Shifting

This is the third in a series of posts by Eran Nevo on the g-conjecture. Eran’s first post was devoted to the combinatorics of the g-conjecture and was followed by a further post by me on the origin of the g-conjecture. Eran’s second post was about the commutative-algebra content of the conjecture. It described the Cohen-Macaulay property (which is largely understood and known to hold for simplicial spheres) and the Lefshetz property which is known for simplicial polytopes and is wide open for simplicial spheres.

The g-conjecture and algebraic shifting

Squeezed spheres

Back to the question from last time, Steinitz showed that

any simplicial 2-sphere is the boundary of a convex 3-polytope.

However, in higher dimension

there are many more simplicial spheres than simplicial polytopes,

on a fixed large number of vertices. Continue reading

Ehud Friedgut: Murphy’s Law of Breastfeeding Twins

This post is authored by Ehud Friedgut. Congratulations to Keren, Ehud and Michal for the birth of Shiri and Hillel!

Murphy’s law of breastfeeding twins, like all of Murphy’s laws, is supported by strong empirical evidence.

The twins’ feeding rhythm depends on your approach. If you decide to try and synchronize them in order to minimize your hassle and maximize your rest periods then twin A’s hunger will be governed by $sine(t)$ and twin B’s by $cosine(t)$.

If you decide to respect their natural rhythm in hope of falling into a fixed predictable pattern then twin A will follow $sine(t)$ and twin B $sine(\phi\times t)$, where $\phi$, the golden ratio, is the number hardest to approximate by rationals

(Eran Nevo) The g-Conjecture I

This post is authored by Eran Nevo. (It is the first in a series of five posts.)

Peter McMullen

The g-conjecture

What are the possible face numbers of triangulations of spheres?

There is only one zero-dimensional sphere and it consists of 2 points.

The one-dimensional triangulations of spheres are simple cycles, having $n$ vertices and $n$ edges, where $n\geq 3$.

The 2-spheres with $n$ vertices have $3n-6$ edges and $2n-4$ triangles, and $n$ can be any integer $\geq 4$. This follows from Euler formula.

For higher-dimensional spheres the number of vertices doesn’t determine all the face numbers, and for spheres of dimension $\geq 5$ a characterization of the possible face numbers is only conjectured! This problem has interesting relations to other mathematical fields, as we shall see. Continue reading

Michal Linial: Vive La Technology

Nebi Samuel

It was a long night after crossing the Atlantic. I got to the airport and indeed the big signs of ‘Welcome’ and “TAAM SHEL BAIT” (taste of home) had a special appeal. It was 3:30 in the morning when I took the Taxi. The driver was very talkative and wanted to know where I am coming from, are the stories that he had heard on America true. Specifically he wanted to know if I went to the Twins to see the city from the tallest buildings etc, etc.
I replied shortly: “Yes, New York is as everybody said”. For the Twins, I replied: “No, there is no elevator there anymore”… I tried to be polite but at the same time to keep our touristy discussion to a minimum.  The Taxi driver turned out to be quite sensitive to my poor situation and told me very proudly: “Please tell me where, and I will take you, I have a new GPS, just tell me the address and the GPS will show me the way”. Indeed, I shared with him the importance of the GPS technology and even told him that I may soon buy one for my own car. My address is Nave Sha’anan 18, I told him, and 2 minutes later, I was asleep, this time very confident that in 45 min I am at home and to my bed. The next thing I know is Continue reading

1:0 to Italy: Michal Linial

Coming back from Hinxton, the most exciting genome center in the world and the most boring place after 5pm… At 5:30, a shuttle bus takes all the ‘workers’ to the big city – to Cambridge. The shuttle bus dropped us in the middle of town and without noticing, I remained alone. I quickly looked around; actually, there was no one on the street… OK I decided, the evening is not lost yet, I will go to London…

I waited 5 minutes and a Taxi stopped next to me. To the train station” I said. My taxi driver started the ride and then slowed down, stopped for a minute next to an open bar looked extremely worried and after 2 minutes speeded up again. We moved another 100 meters and again, he slows down and stop for 2 minutes next to a TV screen in the next open bar. He looks bothered and mumbled to himself, I hate him, Continue reading