#	Pagina
attuale pagina	/open-h2020/projects/194538/results.html

Report

Teaser, summary, work performed and final results

Periodic Reporting for period 1 - LaDIST (Large Discrete Structures)

Teaser

Summary

The project aims at studying and developing methods to analyze and approximate large graphs and other discrete structures. Such techniques are of importance in computer science where very large networks appear and input structures are often enormous in many applications. Another area where the project results are applied is inside mathematics where the developed techniques are used to make progress on specific open problems.

Work performed

In the initial period of the project, we particularly focused on studying the structure and properties of large dense networks and their analytic representations (graphons). Our most important results concern graphons that are finitely forcible, i.e., they can be specified by finitely many density constraints. We proved universality of such graphons and used this result to disprove a conjecture of Lovasz on finitely forcible solutions of problems in extremal graph theory. We also provided results on the existence of specific substructures in graphons, generalizing several results from combinatorial optimization, and applied graph limit techniques to several specific problems in extremal combinatorics. Finally, we explored algorithmic applications of techniques studied in the framework of this project, which resulted, e.g., in improving the approximation ratio for the Traveling Salesperson Problem in the cubic graphs.

Final results

The project has already gone well beyond the start of the art. The particular highlight is proving the universality of finitely forcible graphons - this led to a counterexample to a conjecture of Lovasz on finite forcibility of optimal solutions of extremal graph theory problems (which was the second most often cited problem in the theory of graph limits). In the further stages of the project, the insights obtained in the initial period of the project will assist with developing techniques to better represent large networks/graphs.