H2020Индивидуална стипендия2021–2023

LASTING · LArge STructures IN random Graphs

„Хоризонт 2020“ — Действия „Мария Склодовска-Кюри“

Период: 2021-07-01 → 2023-06-30
Финансиране от ЕС: 224 934 €
Участници: 1
Схема: MSCA-IF

Линиите свързват координатора с партньорите.

Накратко на български

Случайните графи изследват математически структури от върхове и връзки, като например броенето на конкретни подграфи в една мрежа. Тези изследвания помагат за разбирането на общите свойства на графите и се прилагат в алгоритмите, физиката и науките за живота.

Този кратък обзор е генериран от изкуствен интелект

Кратко обяснение, генерирано от езиков модел по текста на CORDIS. Оригиналът е по-долу.

Резултати накратко

LArge STructures IN random Graphs

The study of graphs started during the 18th century with the seminal paper of Euler on the Seven Bridges of Königsberg. A graph is a pure mathematical structure that is also used to model networks and processes. A graph consists of a set of vertices and a set of pairs of vertices, the edges, representing connections between the vertices. Random graphs' systematic study was launched in 1959 by Erdős and Rényi, and by Gilbert. Since then, random graphs have become one of the most central notions in combinatorics; they also have a tremendous amount of applications in different fields such as networks, algorithms, physics, life sciences, and more. A random graph is a graph sampled from a collection of graphs according to some probability distribution. Random graphs are known by their nice properties, and have become one of the most central notions in combinatorics. Besides being interesting on their own, they are also often used for understanding properties of general graphs, as in many cases, understanding their behaviour can shed light on the behaviour of graphs in general. Going back to the origins of combinatorics, it is an area of mathematics primarily concerned with counting. Counting subgraphs in (random) graphs is therefore a well studied problem: How many copies of a given graph does a (random) graph (typically) contain? Or more generally, for a family of graphs F, determine the (typical) behaviour of the total number of appearances of members of F in a (random) graph. In this project I focus on families of graphs with a large size variety, and their weighted version, all having a specific structure. Another well studied example is graph decomposition. The area of graph decomposition has a long history and can be traced back to the famous Kirkman’s schoolgirl problem from 1850. The goal in these types of problems is to split the graph into pieces all having a prescribed structure. This notion is strongly connected to edge colouring, where we identify each colour class with a subgraph of the decomposition. In the most basic form, the colouring problem asks for the minimum number of colours needed in order to split the edges of the graph into matchings (where a matching is a disjoint collection of edges).

Текст от CORDIS, на английски · Данни: CORDIS, © Европейски съюз

Цел на проекта

The study of random graphs lies in the interface between combinatorics, graph theory, and probability, and has a tremendous amount of applications in various fields such as networks, algorithms, physics, and life sciences. The aim of this project is to study large structures in random graphs, count their appearances and measure their strength.In the first set of problems we aim to count the number of subgraphs from specific families in random graphs, where the families contain both large and small members. We consider families such as cycles, matchings, trees, and independent sets. In combinatorics, these types of problems are usually studied for families of equal-size members. We will combine advanced probabilistic ideas to solve these problems for families containing graphs of all possible sizes. This has strong connections to ideas from statistical physics.In the second set of problems we investigate classical extremal graph theoretical problems in the context of random graphs. Roughly speaking, we start with a graph satisfying some property (either deterministically or typically), and we want to measure how many edges can be removed (either randomly or deterministically) until the property no longer holds. These types of problems are known as robustness, resilience, and Turan-type problems. Here we study these problems with respect to spanning structures.The experienced researcher has made several advances to these problems and to closely related problems. For example, she solved robustness and Turan-type problems for almost-spanning cycles (with Krivelevich and Mond), and she approximately solved the counting problem of directed Hamilton cycles (With Ferber and Long). The supervisor, Prof. Keevash, is a world leading expert on the absorption method, a key tool to approach extremal problems when considering large structures. A combination between these ideas with new probabilistic and statistical-physics tools, will be the key ingredient in this research.

Оригинален текст от CORDIS (на английски).

Участници

THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD · OxfordКоординаторОбединеното кралство