- Точный ранг разреженных случайных графов (arXiv)
Автор: Маргалит Глазго, Мэттью Кван, Ашвин Сах, Мехтааб Сони.
Аннотация: Два знаковых результата в комбинаторной теории случайных матриц, полученные Комлошем и Костелло-Тао-Ву, показывают, что дискретные случайные матрицы и симметричные дискретные случайные матрицы обычно несингулярны. В частности, на языке теории графов, когда p — фиксированная константа, матрица двухсмежности случайного двудольного графа Эрдёша-Реньи G(n,n,p) и матрица смежности случайного графа Эрдёша-Реньи G(n ,p) оба неособы с высокой вероятностью. Однако очень разреженные случайные графы (т. е. где p может быстро убывать вместе с n) обычно являются сингулярными из-за наличия «локальных» зависимостей, таких как изолированные вершины и пары вершин степени 1 с одним и тем же соседом. В этой статье мы даем комбинаторное описание ранга разреженного случайного графа G(n,n,c/n) или G(n,c/n) в терминах таких локальных зависимостей для всех констант c≠e (и мы приводим некоторые доказательства того, что ситуация сильно отличается для с = е). Это дает практически полный ответ на вопрос, заданный Ву на Международном конгрессе математиков 2014 года. В качестве приложений нашей основной теоремы и ее доказательства мы также определяем асимптотическую вероятность сингулярности 2-ядра разреженного случайного графа, мы показываем, что ранг разреженного случайного графа чрезвычайно хорошо аппроксимируется его числом соответствия, и мы вывести центральную предельную теорему для ранга G(n,c/n)
2. Обнаружение локализованной геометрии в случайных графах без масштаба (arXiv)
Автор : Джанмарко Бет, Риккардо Михилан, Клара Стегеуис.
Аннотация: Мы рассматриваем проблему определения того, содержит ли степенной неоднородный случайный граф геометрическое сообщество, и формулируем ее как задачу проверки гипотез. Точнее, будем считать, что нам дана выборка из неизвестного распределения на пространстве графов на n вершинах. При нулевой гипотезе выборка происходит из неоднородного случайного графа с последовательностью степеней с тяжелым хвостом. Согласно альтернативной гипотезе, k=o(n) вершин заданы в пространстве и соединяются друг с другом в соответствии с правилом соединения геометрически неоднородного случайного графа. Остальные n−k вершин подчиняются правилу соединения неоднородного случайного графа. Мы предлагаем простой и эффективный тест, основанный на подсчете нормализованных треугольников, чтобы различать две гипотезы. Мы доказываем, что наш тест правильно определяет наличие сообщества с высокой вероятностью при n→∞ и с высокой вероятностью идентифицирует вершины сообщества большой степени.
