Для ответа на этот вопрос сначала нужно разобраться, что понимается под случайным графом и какие свойства называются асимптотическими. Если начинать совсем издалека, то можно вспомнить, что графом называется пара множеств (V, E), где V - множество вершин, а E - множество пар (v, u), где v и u - некоторые объекты из V. Такое определение хоть и является достаточно общим и формальным, на деле не всегда оказывается понятным. Чаще всего граф представляют как множество точек на плоскости (вершины), где некоторые пары точек соединены линиями (ребрами).
Тем не менее, это лишь одна из многих интерпретаций графа. Кроме того, существует большое множество других, более сложных моделей, которые в том или ином роде являются частными случаями или обобщениями классической модели и заслуживают отдельного изучения (ориентированные графы, гипер-графы, регулярные графы, дистанционные графы и тд).
Что касается свойств графов, то их бесчисленное множество. По сути, любая характеристика, которую вы сможете придумать, тоже будет являться свойством графа. Из самых известных можно вспомнить свойство связности (это когда из любой вершины, двигаясь только по ребрам, можно добраться в любую другую вершину), гамильтоновости (это когда в графе есть замкнутый путь, проходящий через каждую вершину ровно один раз)
, число независимости графа (это размер наибольшего подмножества вершин, такого, что никакие две из них не соединены ребром), кликовое число графа (размер наибольшего подмножества вершин, такого, что любые две из них соединены ребром) и конечно же хроматическое число графа (минимальное число цветов, в которые можно раскрасить вершины графа так, чтобы концы любого ребра имели разные цвета)
. Каждому из этих свойств посвящено множество работ и все они имеют огромное количество полезных следствий и приложений. Некотрые из них изучены уже достаточно хорошо и в современной комбинаторике чаще рассматриваются их обобщения на более сложные модели, про другие же наоборот известно относительно мало, несмотря на то, что их изучением занимались многие выдающиеся ученые. Все эти свойства очень полезны при изучении дргуих характеристик графов или дргуих, гораздо более сложных структур.
Теперь о случайных графах. Желание добавить частицу теории вероятностей в графы является вполне естественным, поскольку большинство процессов, которые происходят в реальной жизни, в той или иной степени случайны. Соответственно и модель, описывающая эти процессы, должна учитывать это свойство нашего мира. Как и раньше, можно придумать много определений "случайного графа", и все они при этом будут правильными, однако самые известные модели были преложен учеными П. Эрдешем и А. Реньи (почитать про них можно, например, тут: https://mipt.ru/upload/30d/Pages_130-140_from_Trud-8-14-arphcxl1tgs.pdf). Коротко опишу одну из этих моделей: фиксируется некоторое число p между нулем и единицей, берется полный граф на n вершинах (это значит, что в нем проведены ребра между любыми двумя вершинами), а затем каждое ребро удаляется из графа с вероятностью p. Получившаяся в итоге случайная величина, принимающая значения на множестве всех возможных графов на n вершинах, и называется случайным графом. Такая модель имеет уже гораздо дольше общего с реальным миром. Например, если наш граф описывает транспортную сеть некоторого города, то случайное отсутствие каких-то ребер может быть обусловленно, например, тем, что любая дорога может быть с некоторой вероятностью забита пробкой, закрыта на ремонт или перекрыта из-за того, что кое кто едет с работы домой. Соответственно, теперь мы можем изучать свойства случайных графов. Выглядит это так: мы берем полный граф на n вершинах, удаляем с вероятностью p каждое ребро и смотрим, какими свойствами обладает получившийся граф и с какой вероятностью. Например, может так получиться, что мы удалили вообще все ребра из нашего графа (например, если мы возьмем p = 1). Тогда получившийся граф будет несвязным (потому что у него вообще не будет ребер, а значит мы не сможем дойти ни из какой вершины ни в какую другую). Аналогично, может оказаться, что мы вообще не удалили ребер из графа (p = 0), и такой граф будет связным.
Так можно исследовать и другие свойства и их вероятность в зависимости от разных значений p.
Наконец, мы добрались до асимптотических свойств. Как правило, рассуждать о свойствах какого-то конкретного случайного графа при фиксированном количестве вершин не имеет смысла (слишком частный случай). Тогда рассматривают вероятность различных свойств при условии, что число вершин стремится к бесконечности. Для каждого фиксированно n вероятность того или иного свойства есть некоторое фиксированное число (просто считаем вероятностную меру всех графов, обладающих этим свойством). Устремив n к бесконечности получаем последовательность чисел (вероятностей данного свойства при разных n), а значит можем говорить о пределе этой последовательности. Соответственно, говорим, что случайный граф асимптотически почти наверно обладает некоторым свойством, если последовательность вероятностей этого свойства для разных n стремится к единице. Чаще всего ученых интересует, при каких значениях p случайный граф обладает каким-то свойством, а при каких - нет. Такой подход вполне оправдан с точки зрения прикладных задач. В нашем примере с дорогами в городе, нам не нужно исследовать конкретный граф, характеризующий данный город, а достаточно просто сказать, что если число вершин достаточно большое (а вершинами тут могут быть, напрмиер, перекрестки) и вероятность для каждой дороги быть перекрытой больше какого-то числа P, то с большой вероятностью граф несвязный, а значит найдутся такие два перекрестка, что мы не сможем из одного добраться до другого. Подобные задачи исследования асимптотических свойств относятся к предельной теории графов, которая является важным разделом экстремальной комбинаторики и позволяет решать другие задачи из этой области.
На сегодняшний день достаточно неплохо изучены многие асимптотические свойства случайных графов, как более известные (например связность или гамильтоновость), так и менее известные (напрмиер распределение древесных компонент в случайных графах). Например, про все ту же связность известно, что если p > C*ln(n)/n, где C > 1 - некоторая константа, то случайный граф с таким p асимптотически почти наверно будет связным. Аналогично, если p < C*ln(n)/n, где C < 1 - некоторая константа, то граф будет несвязным (на самом деле, есть даже более точный результат, но у него более сложная формулировка). В качестве примера могу предложить вот эту статью: https://arxiv.org/pdf/1901.07139v8.pdf. В ней достаточно подробно описаны все известные на сегодняшний день результаты относительно гамильтоновости случайного графа.
Что касается распределения ребер в случайном графе, то вопрос неоднозначный. Зависит от того, какую именно модель вы рассматриваете и какие значения параметров (в нашем случае - число p) берете. По сути, все вышеперечисленные свойства и отвечают на вопрос о том, как распределены ребра. Существуют, конечно, и более фундаментальные характеристики графа, которые, возможно, лучше отвечают на этот вопрос. Например, в некоторых научных статьях можно встретить термин "(k, a)-expander". По определению, это граф, такой, что любое его подмножество вершин размер ане больше k "выпускает" из себя ребер не меньше, чем его размер умноженный на a. Это свойство можно интерпретировать как показатель того, что ребра в графе распределены достаточно "равномерно", то есть в нем нет маленьких подмножеств вершин, содержащих внутри себя много ребер (относительно своего размера). Это свойство является скорее вспомогательным и используется при исследовании других, более понятных свойств (напрмиер, длинне наибольшего пути в случайном графе или гамильтоновости случайного графа). Тем не менее, оно дает некоторое фундаментальное представление о распределении ребер. Подробнее про другие свойства и модели случайных графов можно почитать, например, тут: https://arxiv.org/pdf/math/0503745.pdf
Начала теории изложены, спрашивающему есть от чего оттолкнуться