Pagerank centrality

I was playing a few tricks on a few centrality measures on a few graphs. SO, thought of penning down a quick piece of notes on the notion of centrality (A quick introduction can be found here along with Wikipiedia page on centrality)

The number 143

I don’t Twitter a lot, in spite of having an account which I visit once in a while and tweet at an even low rate. To me, Tweets are too short and too soon; The 143 characters is something too low a number to post an opinion without multiple breaks. Thats just my take and clearly it is different from the large segment of the rest of the world population.

Anyway, I am still wondering what made the Twitter founders to decided on restricting the length to 143 characters. Yesterday, during a dinner party I hear some of them commenting on this. I didnt get the rationale fully, but it was apparently chosen based on some SMS research, using curtailed English words.

I did a few Google search, but nothing quite came with the explanation. The Wikipedia interestingly has a page for 143. Would you believe? As it turns out, 143 indeed has some very interesting properties.

143 is the sum of three consecutive primes (43 + 47 + 53), as well as the sum of seven consecutive primes (11 + 13 + 17 + 19 + 23 + 29 + 31). But this number is never the sum of an integer and its base 10 digits, making it a self number.

Every positive integer is the sum of at most 143 seventh powers (see Waring’s problem).

143 is the difference in the first exception to the pattern shown below:

3² + 4² = 5²

3³ + 4³ + 5³ = 6³

3⁴ + 4⁴ + 5⁴ + 6⁴ = 7⁴ − 143

Giant component, Erdos Renyi and staples

On a lighter note, here is a very interesting blog piece, bringing some sort of similarity to the giant component behaviour on a pile of staple pins. This is sort of a layman view of the Erdos Renyi explanation.

In one version of the Erdős-Rényi process, one start with a set of isolated vertices and then keep adding random edges one at a time;  More specifically, at each stage one choose two vertices at random from among all pairs that are not already connected, then draw an edge between them. It turns out there’s a dramatic change in the nature of the graph when the number of edges reaches . Below this threshold, the graph consists of many small, isolated components; above , the fragments coalesce into one giant component that includes almost all the vertices. “The Birth of the Giant Component” was later described in greater detail in an even bigger paper–it filled an entire issue of Random Structures and Algorithms (1993, 4:233–358)–by Svante Janson, Donald E. Knuth, Tomasz Luczak and Boris Pittel.

Ofcourse Joel Spencer has written a beautiful article on AMS commemurating the golden anniversity of the giant component.

Ulam’s game

An interesting and twisted version of the twenty question game came across recently. I saw it in the 2009 ISIT paper on the error correction under Feedback with list decoding, by Ofer Shayevitz.  The problem goes like this (I am going by the nice narration of Ofer with the famous Alice and Bob duo).

The game is being played by Alice and Bob. Alice selects one of possible objects, and Bob can ask   binary questions (where the answer can be either  yes or no only), in a quest to identify the object selected. If Alice is always truthful, then questions are obviously both necessary and sufficient. Now, suppose Alice is allowed to lie up to times. How many questions does Bob need to get the correct object? Alternatively, given questions, what is the maximal number of objects that Bob can separate? This version of the “twenty questions game” with lies is known as Ulam’s game.

LT codes decoding using Wiedemann algorithm

Glanced upon a paper from the 2009 ISIT, titled “LT Codes Decoding: Design and Analysis” by Feng Lu et al. The authors discusses LT decoding strategy which is Peeling decoder (conventional simple LT decoding) followed by an extension based on the well known Widemann algorithm solving a sparse homogeneous linear system. Here is a brief summary as I understood.

On packet erasure channels (internet being one close realization of a model of this kind, where, the TCP/IP suit, one can either gets packets correctly delivered or lost in the wild), Luby Transform (LT) codes forms an easy way to transfer information.  It is well known that, asymptotically (When the number of information symbols  (or packets)  and the number of packets received $r$ are large) near full recovery is made possible by simple peeling decoder which grows in complextity at . The claim is that, for   or so, with , on average  we can, with high probability, recover all of  information packets  by simple unwrapping of xor-ed packets. A more precise statement will read as: If from information packets, each coded packet constructed independently by xor operation (the number of packets taken for xor operation follows a distribution; Plain vanila version of LT codes uses Soliton distribution), then the content of the original information source can be recovered from any packets with probability by an average of symbol operations. However, when the number of input symbols is not large (say less, ) the overhead term is not small. It is not too surprising, since we need sufficiently large and to converge the performance in expectation.  One can think of solving the system of linear equations using Gaussian elimination and get the best figures, but the question mark stays on the complexity of this method over the cheaper peeling decoder complexity .

Conventional LT decoding based on Peeling decoding rule terminate, once the number of degree -1 packets (ripple as it is called in graph theory parlance) are void. One can hope to continue from there, by using Gaussian elimination and decode a a few more (if the graph matrix rank permits it). If the original graph is full rank, one can technically decode all of them.  Gauissian eliminatio being heavy, one hope to find an easy, preferably recursive method. Indeed there comes Wiedemann and that is what the authors use.  The authors propose what they call as full rank  decoding, which essentially is LT decoding, until there are no more degree one packets. From there, they borrow a packet and then uses Wiedemann algorithm which is somewhat light on computational complexity.

The larger aspect on whether this scheme do any better than conventional LT peeling decoder is the other question they answer. To achieve full recovery we need to have a full rank matrix. Now, the matrix being a sparse matrix defined over where is the number of received packets. The probability of the matrix having a full rank will directly help us to infer the decoding merits. This is an interesting piece since I had looked into the computation of the rank of a binary matrix and also the probability of a random matrix rank being equal to an arbitrary value. All this was done during the Modern Coding Theory doctoral course by Ruediger Urbanke at EPFL.  For binary random matrix, we can also setup a recursive formula and thereby a good inference on the probability of decoding can be arrived at.

Happy Birthday Martin Gardner

Martin Gardner‘s 95-th Birth day today. I dont think any other soul can claim to own the legacy of aspiring enthusiasm, among children and adults alike, on the subject of mathematics, in the most interesting and playful mode; Recreational mathematics transcended to newer heights thanks to Gardner’s amazing production of puzzles and games. A philosopher by education and a Navy man by profession, Gardner’s transition post World War II is something worth a story telling! I was (still remain so) a huge fan of Gardner ever since romping on to his old articles in the Scientific American volumes, which I greedily grabbed from NIT Calicut library. There was a time (in the pre internet and digital era) when I used to maintain a notebook of Martin Gardner puzzles, where I had handwritten the riddles and games. It is incredible to know that he is still active and steaming. Thank you Martin Gardner for spurring enthusiasm to many a generations. His “Colossal book of mathematics” is one of the worthy possessions in my library!

Many many happy returns of the day Martin. NY times has a nice page published on his birthday!

Sum of square roots of binomial coefficients

Today, during the evening chat, Emmanuel Abbe threw an interesting question: Whether the sum of square roots of consecutive binomial coefficients converge to some closed form! That is, . We tried a few known combinatorics tweak, but no meaningful solution arrived. We were also wondering whether this has some asymptotic limit, but that too did not yield anything. A quick check on Mathematica wasn’t helpful either. Now the question is: Does this sum yield some closed form expression.

While playing with this sum in Mathematica, I found that for the sum of squares of binomial coefficients, there is a nice simple closed form.

I was toying with a proof. It turns out that, the proof is extremely simple and is a one line tweak of the Vandermonde identity . Simply substitute and we have the results on table. The natural question then would be: Is there a generalization for for any . Ofcourse now for it is trivial.

Apparently, it turns out that, there is no closed form expression for a general (all) . There are some interesting divisibility properties of these sums. An interesting account of that is addressed by Neil Calkin (Factors of sums of powers of binomial coefficients).

At the moment, I get a feeling that sum of fractional powers of binomial coefficients is not trivial. May be there is no closed form. May be not!

Inclusion exclusion principle

A few years ago, during undergrad days, myself and  friend Ramani during our lazy 75 paise mini canteen tea outing, were discussing a small riddle. It was motivated from a real world experience from our computer center in NIT Calicut (REC Calicut). In REC those days, we students almost exclusively used rubber slippers (Yes, those Paraqon brand which used to cost 20 rupees or so), usually called by the name ‘chappels’. With that, we were not only comfortable while walking and running around, but we’re equally at ease playing cricket and badminton with the very same foot support; and many other things too, including jogging. Those thin hard rubber slippers used to last an year or more without giving much trouble, other than perhaps an occasional tearing of the rubber tie. In all, we were at peace with that.

But there was an issue, not exclusively for this brand, but for chappals in general (shoes were a luxury of sort in the campus;atleast it wasnt very common). Not for everyone though! If and only if you were fancied of visiting the computer center! Well, computer center wasn’t all that fanciful then, since we were provided with only graphics less Unix terminals (no colour monitors!). You might wonder, huh! what age am I talking about? Besides, Internet and Emails were only taking shape then. Chats and browsing were not quite there yet;Unless you felt a touch inferior to the computer wizkid around, that was not a compelling centre de visite. As, ‘would be‘ electronics and communication engineers we had that occasional inferiority complex!. Computer center was air conditioned and was strictly slippers free. We were expected to keep our valuable slippers outside (no clock room luxury! well that was not a necessity either) before entering to that cooler room, filled with monochromatic terminals. Since most of the chappals dropped outside were alike (in size and also sometimes color) there was a good chance that at the time return, we ended up with a different pair of slippers (Some folks found happy for themselves by a visit to the computer center, just for a pair change, often to an improved lot!).  Sometimes, we ended up having differently colored ones, say left foot white and right foot blue. That wasn’t a problem socially either, as long as you stayed within the campus. It was socially accepted within the walls!

Anyway, coming back to the riddle we were busy conjecturing on. We wanted to automate a clock room. The idea then would be to just deposit the chappals there at random. The clock room work automatically. Upon asking (at the time of return, say) it will select a pair at random and give it to you. Sorry, you cant have a choice. Just accept and hope for the best. We asked the questions:

1) What is the probability that everyone gets their own chappals

2) What is the probability that none of them get their submitted pairs

Assume number of  people (and hence pairs). We can assume that, a pair is a single entity (say both left and right slippers are tied and submitted as one) . This simplified the problem to people slipper scenario. A simplistic model assumeed that all people submit their slippers at the same time. We wanted to build that great randomized clocker machine! And we wanted that to work for any , which means, the algorithm had to be implementable and to work well in expectation!

We had thought and pondered about it for a while, then. In the end, we had found that the first one is easy, but the second one a little harder to generalize for beyond or something.  As busy undergrads, we left the problem after an hour of discussion, probably until we had finished sipping the tea. Aside, we were busy with many other extra curricular activities including a 3 hour daily cricket match at the lush green international hostel ground. The megadeth team, as we proudly grouped ourselves, the electronics and communication batch hardly missed those cricket matches. We were electronics engineers and had taken pride in ourselves by not really bothered to ask any fellow discrete math or combinatorics folks! That perhaps helped in some sense.  Ramani found management more interesting than those technical details of counting. I am sure he took the right career. Anyway…too much digressing already!

Now, it turns out that, the very same problem is akin to a well known problem in combinatorics. It is called the Hatcheck lady problem. It is fairly easy to solve it using the inclusion exclusion principle. The proof outline is shown below. As I type, memory fetches that discussion,  sitting leg-folded on the cement bench at the REC mini-canteen, perhaps an occasional cool breeze around too. 

The inclusion exclusion principle is the following:

                

                

The Hatchek lady problem can be stated with a similar story as the random clocker machine. (From Harris, Mossinghoff, Hirst’s book on Combinatorics and Graph Theory)

A lazy professor gives a quiz to a class of students, then collects the papers, shuffles them, and redistribute them randomly to the class for grading. The professor would prefer that no student receives his or her own paper to grade. What is the probability that this occurs? This indeed is an equivalent statement of the well known Hatcheck lady problem (I guess the exact name come from a hatcheck lady who collects hats and absentmindedly return them)

For Hatcheck lady problem, the probability .

When gets larger and larger it converges asymptotically to a constant!

N is a number: A Portrait of Paul Erdős

The popular documentary on this fascinating mathematical prodigy of 20th century is now available on you tube. Personally, while watching the video, the cam river and the row boat brought a touch of nostalgia! I have heard mountains of stories about Paul Erdős. This documentary is a must watch for not only mathematicians and mathematically curious guys (or guys like me who are just curious about mathematics, mathematicians and mathematical minds or for that matter about anything in this world!), but for everyone interested to know about such an extra ordinary mind of our times.  What a fascinating experience it would have been to listen to one of his lectures live. Now this youtube brought the gap down to finite length/time reality.

I have never seen Erdős. Now that he is no more warrants any thoughts anyway.  In a away I am lucky this semester to attend courses of another prolific mathematician of this era Janos Pach. Interestingly, Janos Pach is one of the few living mathematicians with Erdős number 1.  His lectures on Graph theory as well as the one on geometrical graph theory are truly fascinating. 

Anyway, if you have not seen the documentary yet, here is the link. It is a must watch. I bet, you wouldnt miss the time. On many occasions, the Cam river and its slow movement etches something in the backdrop of those days.  Didnt I like that place?

Concentration of the Chromatic Number

An interesting bound (problem from Rudi’s  Modern coding theory book) regarding the chromatic number of a random graph.  I first attempted it during the course.  Here is the problem statement:

C.5 (Concentration of the Chromatic Number – Spencer and Shamir). Consider a graph  on  vertices.  The chromatic number of a graph , denoted by , is the smallest number of colors needed to color all vertices so that no two vertices which are joined by an edge have the same color. Consider the standard ensemble of random graphs on vertices with parameter : to sample from this ensemble, pick  vertices and connect each of the Ž ordered pairs of vertices independently from all other connections with probability . Show that for this ensemble 

.

My solution is as folllows: (PDF typeset as single file is available here. Look for problem 3)

Let  is a random graph with vertices.  If is the probability that a given edge is in . The probability space be .  Let be a filter on the set of all such random graphs. We can define a Martingale as follows:

where

and is the Chromatic number of . Chromatic number changes at most by one , when the information about the new edge comes in. Clearly, satisfies the conditions for Azuma’s inequality.

is a Martingale, with ).  Let . Clearly 

Now we can use the Azuma’s inequality on to get,

.

Since , the result 

 

follows.

Rank of a random binary matrix

Here is an interesting riddle on random matrices.  

(Rank of Random Binary Matrix). Let  denote the number of binary matrices of dimension  and rank , so that by symmetry .  This is a repost of the solution that I have arrived at (certainly not the first!) and submitted as part of a homework (9) problem from the doctoral course  Modern coding theory (by Rudiger Urbanke) at  EPFL.  The sumbitted solution in PDF is available here.

Rank of a matrix is essentially the number of nonzero rows when the matrix is expressed in echelon form. So, we just need to compute the ways these matrices can be created with non zero rows. Since the elements of the matrix are binary (from ), we can simply do a counting.

It is trivial to compute for and . For  , only all zero matrix possible, and only one such matrix exist. Hence . For  , since  , no matrix exist, which means  . 

Now we consider .  How many ways? We have   non zero rows of the   matrix, which means all rows must be nonzero. Without loss of generality, for counting, we could assume that, the rows are ordered. The last row ( row can be be done in ,  since there anything other than all  vector (of size ) is allowed. On -th row, anything other than that of row  is allowed. There are  ways here. -th row can have anything except any linear combination of the rows  and . This is nothing but . Row then have  and so on. In all, Following the same procedure, we can have a total of  

 ways.  For , we can construct a rank  matrix of size  in any of the following ways:

1.  Take a rank matrix of size  and add an independent row.
2.  Take a rank  matrix of size  and add a dependent row.

For every  matrix, 

and hence,

ways. (Essentially avoid all possible linear combinations of existing rows).  Using the second (item 2 above) method, we can have  and 

 

different ways a rank matrix can be formed. Where,the first term () is when the all zero row is picked as the new row. In ways we can pick any one of the exisiting row as a dependent (new row). In general for  we can have combination of  existing rows  out of in  different ways to make a dependent (new) row.

So using (1) and (2) we get,

Putting everything together,