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