Разреженные случайные графы и статистика случайных матриц

Цзяоян Хуан (Университет Пенсильвании) https://simons.berkeley.edu/talks/jia... Совместный интенсив: Спектральная теория за пределами графов + псевдослучайность и многомерное разложение Экстремальные собственные значения графов представляют особый интерес в теоретической информатике и комбинаторике. В частности, спектральный зазор — разница между наибольшим и вторым по величине собственными значениями — измеряет свойства разложения графа. В этом докладе я начну с обзора собственных значений случайных d-регулярных графов и их связи с теорией случайных матриц. Затем я обсужу наши результаты по жесткости собственных значений и универсальности ребер для этих графов. Жесткость собственных значений утверждает, что с высокой вероятностью каждое собственное значение концентрируется вокруг своего классического положения, как предсказывает распределение Кестена-Маккея. Универсальность ребер утверждает, что второе по величине собственное значение и наименьшее собственное значение случайных d-регулярных графов сходятся к распределению Трейси-Видома из гауссова ортогонального ансамбля. Следовательно, приблизительно 69% d-регулярных графов являются графами Рамануджана. Наконец, я представлю упрощенную структуру для доказательства сходимости к статистике случайных матриц на основе микроскопической версии уравнений петель. Эти характеристики обеспечивают прямой путь к универсальности: достаточно проверить соответствующие приближенные уравнения петель для рассматриваемого ансамбля. Во многих моделях эти уравнения следуют из локальных законов и интегрирования по частям.