О некоторых свойствах случайных дистанционных графов специального вида
Автор: Ярмухаметов Андрей Ринатович
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Случайные графы
Статья в выпуске: 1 (13) т.4, 2012 года.
Бесплатный доступ
В настоящей работе рассматриваются случайные подграфы полного дистан- ционного графа, у которого вершины - векторы x ¡ {0, 1}n с условием ǁxǁ=√n/2, а ребра - пары векторов, отстоящих друг от друга на расстояние √n/2. Ранее была известна пороговая вероятность для свойства связности таких случайных графов, а также пороговая вероятность для возникновения гигантской компоненты в них. Мы доказываем теперь, что, как и в классической модели Эрдеша-Реньи, фазовый переход от связности к ее отсутствию совпадает с переходом от связности к наличию изолированных вершин. Также мы формулируем результат о предельной вероятности связности в предположении, что вероятность ребра находится "внутри" фазового перехода.
Случайный граф, связность, изолированная вершина, гигантская компонента, дистанционный граф, пороговая вероятность
Короткий адрес: https://sciup.org/142186200
IDR: 142186200
Список литературы О некоторых свойствах случайных дистанционных графов специального вида
- Алон Н., Спенсер Дж. Вероятностный метод.-М.: Бином, 2007.
- Erdos P., Renyi A. On random graphs 1//Publ. Math.-1959.-Debrecen 6.-P. 290-297.
- Erdos P., Renyi A. On the evolution of random graphs//Publ. Math. Inst. Hungar. Acad. Sci.-1960.-V 5.-P. 17-61.
- Erdos P., Renyi A. On the strength of connectedness of a random graph//Acta Math. Acad. Sci. Hungar.-1961.-V. 12.-P. 261-267.
- Bollobas B. Random Graphs.-New York: Academic Press., 2001.
- Райгородский А.М. Линейно-алгебраический метод в комбинаторике.-М.: МЦНМО, 2007.
- Райгородский А.М. Проблема Борсука и хроматические числа некоторых метрических пространств//УМН. -2001.-Т. 56, вып. 1 (337).-С. 107-146.
- Ярмухаметов А. Р. О связности случайных дистанционных графов специального вида//Чебышевский сборник.-2009.-Т. X, вып. 1 (29).-С. 95-108.
- Ярмухаметов А. Р. Древесные компоненты в случайных дистанционных графах специального вида//Современная математика и ее приложения. -2011. -Т. XX. -С. 98-110.
- Ярмухаметов А. Р. Гигантская компонента в случайных дистанционных графах специального вида//Математические заметки, в печати.
