|
СЕМИНАРЫ |
Семинар Лаборатории Чебышёва «Теория вероятностей»
|
|||
|
Случайные, псевдослучайные и универсальные графы Федор Петровab a Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН b Санкт-Петербургский государственный университет |
|||
Аннотация: Рассмотрим граф на конечном или счетном множестве, в котором любые две вершины соединяются или не соединяются ребром с вероятностью 1/2 (независимо от остальных пар). Эти графы почти наверное (для счетных графов) или с вероятностью, стремящейся к 1, (для больших конечных графов) обладают рядом комбинаторных и спектральных свойств, многие из которых можно принять за определение «квазислучайности» графа. Мы обсудим эквивалентность разных свойств квазислучайности конечных графов с большим числом вершин, а также выясним, что все счетные случайные графы изоморфны с вероятностью 1 и могут быть аксиоматически свойством универсальности. |