Аннотация:
В докладе рассматриваются законы нуля или единицы для различных моделей случайных дистанционных графов. Говорят, что случайный граф подчиняется закону нуля или единицы, если для всякого свойства первого порядка вероятность того, что случайный граф обладает этим свойством, стремится к 0 или 1. В докладе даются условия, при которых случайный дистанционный граф подчиняется закону нуля или единицы, а также условия, при которых можно выделить подпоследовательность случайных дистанционных графов, подчиняющуюся закону нуля или единицы. Также рассматриваются законы нуля или единицы для формул с ограниченной кванторной глубиной и некоторые другие ослабленные варианты закона нуля или единицы.
|
