“Physics works”

Online video lectures is the greatest thing to have happened for me in the last few months. There are a lot of them available through MIT OCW; Yale has released some; IITs have put up very good lectures on youtube; and so on. This is a great hub that points to a lot of them. I have some pointers here. Many of them can be downloaded as well.

It’s always a great thing when an expert explains things in a clear manner. It’s also much more convenient than reading up and understanding. And it takes much less effort. Someone like me gets to learn and/or revise things by going through them. If I have to study on my own, I would keep postponing it forever!

For example, I understood how simple Newtonian physics is, if presented well, like Prof. Ramamurti Shankar from Yale does; or how intriguing the things that we simply assume are, like I felt when a prof pondered over the question of ‘what are real numbers at all’, in a lecture from IIT. It is also amazing the extent to which people can go to ensure that what they are presenting is absolutely clear. To experience this amazement, one has to watch Prof. Walter Lewin teach physics. He doesn’t just teach physics, he makes physics happen. He brings all kind of stuff to his lectures. Balls, springs, ropes, what have you. In a particular lecture on springs, SHM etc., he first records the period of a 5m long pendulum that has a 15kg ball. Then to show that the period of a pendulum is independent of the mass, he places himself on the metal ball, and swings, keeping himself as horizontal as possible. Then he notes the time, rushes to the board to write it below the one for the ball alone. He then yells, “Physics works!”

More on Regularity Preservation

As sri rightly pointed out in the comments section of the previous post, clique insertion is just one way to extend an r-regular graph into a bigger r-regular graph. We should be able to extend the graph by inserting any (r – 2)-regular graph (provided the insertion is possible — refer sri’s comment). In fact, clique insertion is the minimal case: the smallest connected (r-2)-regular graph has r -1 nodes.

There are interesting questions here. Can we insert any (r – 2)-regular graph? What is the procedure to do so? Are there some (r – 2)-regular graphs that cannot be inserted?

Let’s use some notations for ease of reference. Let Ro be the r-regular graph we start with, Ri be the (r – 2)-regular graph we want to insert and Rn be the graph resultant of the insertion.

A simple but important thing to be noted here is that, pairs of nodes that are adjacent in Ri, cannot be inserted in a single edge of Ro because that will result in an overlapping edge (we don’t allow multiedges between nodes); adjacent nodes in Ri have to be inserted in different edges. Even for small values of r, this becomes pretty complicated to visualize. I tried to insertions for small graphs, and it was possible to do. But I don’t know if we can always avoid creating a multigraph.

But then in the above discussion we have assumed Ri to be a connected graph. What if Ri is disconnected? If Ri is disconnected we can easily prove that there is no bound on the size of Ri that can be inserted. The simplest way to show this is by saying that our Ri has an arbitrarily large number of (r – 2)-cliques as disconnected components (disconnected edges, disconnected cycles, disconnected cubic graphs etc.). Now, you can either imagine this as adding an arbitrary number of cliques (like in the previous post) or as adding one large disconnected graph.

Of course, cliques are just one way to insert. We can simply insert nodes and add edges between the new nodes in such a way that all the new nodes have a degree of r.

Note that the resulting graph Rn is, of course, a connected graph.

***

Now, since we are talking about p2p networks, what is more important is the minimum number of nodes and edges that we need to add when nodes join or leave. Or more generally, the minimum change in topology that is required. When a new node comes in, let’s say we need to accommodate it without disrupting symmetry; so we may need to add dummy nodes and edges. The thing is – in a p2p network, most of the time, unrelated nodes join or leave unrelated parts of the network. So, essentially, we are dealing with disconnected components.