ExtSpGraphLim · Extremal Sparse Graphs and Graph Limits

Extremal Sparse Graphs and Graph Limits

The project Extremal Sparse Graphs and Graph Limits (ExtSpGraphLim - REP-747430-1) focused on understandings of large networks through quantitative measures. The problems studied in this project are in the intersection of mathematics, statistical physics and computer science. The general problem of the area is to give an approximation of a certain quantity of a network based on (partial) information about the network (the mathematical terminology for a network is graph). The information that we get might be the whole graph, but in real life application it is more likely that we only get some local statistics of the graph. For instance, we may only get the degree distribution of the network, where the degree of a node is simply the number of its neighbors in the network. So it might occur that we are only given the information that 40% of the nodes have 3 neighbours. 30% of the nodes have 4 neighbours and another 30% of the nodes have 5 neighbours. Our task is to give meaningful approximation of a pre-described quantity of the network based on such a limited information. It might also occur that we can discover the network from some random vertices in some depth: for instance, we can go from links to links in the world wide web from some random websites to get more accurate (but still statistical) information about the network. Sometimes the graph (network) is not finite, but an explicitly given infinite graph, for instance the infinite grid might be our network. This scenario is particularly common in statistical physics. All these questions have a complelety precise scientific counterpart. For instance, giving an efficient approximation algorithm for a graph parameter given the whole graph is probably one of the most classical problem in computer science. The mathematical language of graph limit theory can handle local statistics and infinite graphs. When the information about the graphs is only reduced to degree distribution of the network, then the questions naturally land in the area of extremal graph theory, because the best approximation we can do is to give the minimum and maximum value of the quantity beside the constraints. The importance of understanding large networks cannot be exaggerated as they surround us everywhere, let it be the internet, the network of people (facebook) or the neural network of a brain. Our focus was to develop tools to investiagte the above mentioned problems from a mathematical point of view, and not to study particular networks. Shortly, our goal was to improve on the already existent ideas, let it be the zero-free region of graph polynomials, the understanding of a statistical physical heuristics called Bethe approximation or advancing tools like the use of graph covers. These questions also lead to pure mathematical questions like Sidorenko's conjecture.

Data: CORDIS, © European Union