М.Е. Жуковский "Свойства первого порядка случайного графа Эрдеша-Реньи" (Внимание! Семинар

http://www.google.com/calendar/event?eid=YmVwN3RrOW9rNWtnNXZiMjNvZjR2aHJmMnMgN2xyM2VjN2NvN3NwdnRwanQxaXE5ZmFvbjRAZw

http://www.google.com/calendar/feeds/7lr3ec7co7spvtpjt1iq9faon4%40group.calendar.google.com/public/basic/bep7tk9ok5kg5vb23of4vhrf2s

When: Tue Nov 24, 2015 6:30pm to 8pm  MSK

Event Status: confirmed
Event Description: Говорят, что случайный граф Эрдеша-Реньи подчиняется k-закону нуля или единицы, если для любого свойства, записанного с помощью формулы первого порядка, кванторная глубина которой не превосходит числа k, вероятность им обладать стремится либо к нулю, либо к единице. В 1988 году Дж. Спенсер и С. Шела доказали, что случайный граф Эрдеша-Реньи подчиняется k-закону нуля или единицы, если вероятность ребра является степенной функцией от количества вершин графа, где показатель степени – отрицательное иррациональное число. Мы нашли различные диапазоны рациональных значений показателя степени в вероятности ребра случайного графа, при которых он подчиняется k-закону нуля или единицы. Эффект отсутствия закона нуля или единицы, в частности, вызван тем, что для некоторых простых свойств первого порядка (например, экзистенциальных) существует пороговая вероятность, которая как раз равна степени числа вершин с соответствующим рациональным показателем. Под пороговой вероятностью свойства подразумевается такая функция от числа вершин, что при вероятности проведения ребра, асимптотически меньшей этой функции, вероятность выполнения свойства стремится к нулю, а при большей – к единице (или наоборот). Разумеется, пороговых вероятностей может быть более одной для одного свойства. Множество рациональных показателей степени в вероятностях проведения ребра, которые являются пороговыми вероятностями, называется спектром рассматриваемого свойства. В 1990 году Дж. Спенсер доказал, что существуют свойства первого порядка с бесконечным спектром. Спектром числа k мы называем объединение спектров всех свойств, выразимых формулами первого порядка, кванторные глубины которых не превосходятk. Дж. Спенсер доказал, что при достаточно больших k число 1/3 является предельной точкой в спектре числа k. Мы оценили минимальный и максимальный элементы спектров, а также минимальное значение k, при котором спектр бесконечен.