Expand, count

Mutual penetration of different areas of mathematics not only leads to remarkable new results — which fully manifested Margulis and Furstenberg — but also of great aesthetic and intellectual experience even when proved facts are well known. One of the earliest and most important theorems of mathematics — infinite series of Prime numbers 2,3,5,7… the Reader familiar with the basics of General topology, we recommend you to get acquainted with the proposed Furstenberg topological proof of this fact.

This proof of Furstenberg, then Harry (he was born in Germany in 1934, his family had to flee to America in 1939), was invented while a student at new York’s Yeshiva University. Deep religiosity and interest in Jewish theology he retains throughout life. To get acquainted with the views of Fürstenberg as regards the relationship of religion and science from a Preface he had written for the book “Divine action and natural selection”.

To explain the modern mathematics of the highest level, as a rule, very difficult. But in the case of works of the laureates of this year is possible at least to formulate something, not by appealing to knowledge that goes beyond in-depth school program. To this we turn next.

From the works of Grigory Margulis discuss the article “Explicit constructions of expanders” — the most cited, because it is directly tied to applications. It is a question about the design of the so-called graph-extenders. In order not to overload the text, we will not define those objects in their entirety, but will explain the essence.

Let d > 2 — given a natural number (in the example, Margulis d = 5), α > 0 is a fixed constant. Count-expander is arranged as follows: suppose that in social network there are N users, and each is friends with d other. The extension property is the following: if you take any group of k < N/2 users, they are friends together with at least α·k users outside of this group. This means that if one user learns a big secret and begins to tell him her friends, and they to their and so on, the secret is spreading with the speed of a geometric progression: if today know it k users, then tomorrow at least (1 + α)·k, and so until he learns at least half of the users. This happens very quickly: in logarithmic in N number of steps. The restriction N/2 does not matter: you can replace it with N/3 or 4N/5, the essence remains the same — home secede from N.

Almost all graphs satisfy the extension property. That is, if you take, for example, many network users and to acquaint them with each other haphazardly, so everybody had d ‘s friends, property expansion will occur with probability almost 1. It is not very difficult to install, thereby proving the existence of graphs expander. For completeness here is an example of a graph that does not have the extension property. Imagine sitting in a circle of N people, and everyone familiar with d/2 neighbors to the right and d/2 neighbors to the left. In this graph the dissemination of information is linear with speed.

Even despite the fact that real social cohesion is arranged not by chance, it still has the extension property. In the case of, for example, spread of infection, this fact is very unpleasant, but in other situations, it has considerable benefits, for example, this allows you to build a robust computer network, which will continue to operate even in the event of breakdowns.

Graphs are expanders have many applications historically, one of the first — the creation on their basis of codes to correct caused by information error.

As graphs are expanders help with data loss

For example, Alice has learned which of the 16 teams won the championship of on football and wants to transmit this information to Bob through a binary code (sequence of ones and zeros).

Simply 4 symbols (bits): sequence variants of length 4 from zeros and ones as times 16 (which one corresponds to which team, they agreed to the championship). But what if the channel is not reliable, and some characters could go wrong?

If Alice transmits 7 characters and no more than one of them may be transferred erroneously, it can still reach the goal. To do this, it will consider seven vertices of a three dimensional cube (all except the selected vertices A), and 16 possible results of the championship of will compare these coloring these 7 tops in black and white colors that each of the three faces containing the vertices Andeven number of black and white vertices. Check that these colorings exactly 16, and that any two of them differ in the color at least three vertices.

If now the coloring to match a sequence of seven zeros and ones, then Alice can transmit information about the champion, and Bob to decipher it, even if one of the bits is corrupted.

This is the simplest code, error-correcting (Hamming code). Using graphs-dilators are more advanced codes that correct many errors, and the clear design allow them to quickly decode.

Leave a Reply

Your email address will not be published.