1 of 13
Downloaded 10 times
Recommended
Maksim Zhukovskii – Zero-one k-laws for G(n,n−α)
Maksim Zhukovskii – Zero-one k-laws for G(n,n−α)YandexWe study asymptotical behavior of the probabilities of first-order properties for Erdős-Rényi random graphs G(n,p(n)) with p(n)=n-α, α ∈ (0,1). The following zero-one law was proved in 1988 by S. Shelah and J.H. Spencer [1]: if α is irrational then for any first-order property L either the random graph satisfies the property L asymptotically almost surely or it doesn't satisfy (in such cases the random graph is said to obey zero-one law. When α ∈ (0,1) is rational the zero-one law for these graphs doesn't hold.
Let k be a positive integer. Denote by Lk the class of the first-order properties of graphs defined by formulae with quantifier depth bounded by the number k (the sentences are of a finite length). Let us say that the random graph obeys zero-one k-law, if for any first-order property L ∈ Lk either the random graph satisfies the property L almost surely or it doesn't satisfy. Since 2010 we prove several zero-one $k$-laws for rational α from Ik=(0, 1/(k-2)] ∪ [1-1/(2k-1), 1). For some points from Ik we disprove the law. In particular, for α ∈ (0, 1/(k-2)) ∪ (1-1/2k-2, 1) zero-one k-law holds. If α ∈ {1/(k-2), 1-1/(2k-2)}, then zero-one law does not hold (in such cases we call the number α k-critical).
We also disprove the law for some α ∈ [2/(k-1), k/(k+1)]. From our results it follows that zero-one 3-law holds for any α ∈ (0,1). Therefore, there are no 3-critical points in (0,1). Zero-one 4-law holds when α ∈ (0,1/2) ∪ (13/14,1). Numbers 1/2 and 13/14 are 4-critical. Moreover, we know some rational 4-critical and not 4-critical numbers in [7/8,13/14). The number 2/3 is 4-critical. Recently we obtain new results concerning zero-one 4-laws for the neighborhood of the number 2/3.
References
[1] S. Shelah, J.H. Spencer, Zero-one laws for sparse random graphs, J. Amer. Math. Soc.
1: 97–115, 1988.
YouScan - мониторинг социальных медиа - функции
YouScan - мониторинг социальных медиа - функцииAlexey OrapПрезентация функций системы YouScan для мониторинга социальных медиа
Основы теории графов 11: гамильтоновы циклы
Основы теории графов 11: гамильтоновы циклыAlex DainiakДоказываем достаточные условия существования в графе гамильтоновых циклов: условия Эрдёша—Хватала, Асратяна—Хачатряна, Хватала. Доказываем необходимые условия существования гамильтонова цикла в планарном графе (теорема Гринберга).
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Основы теории графов 10: экстремальная теория графов
Основы теории графов 10: экстремальная теория графовAlex DainiakДоказываем теорему Турана, а затем теорему Эрдёша—Стоуна—Симоновица(Шимоновича) о связи хроматического числа подграфа с максимальным числом рёбер в графе, его не содержащего.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Основы теории графов 09: раскраски планарных графов, совершенные графы
Основы теории графов 09: раскраски планарных графов, совершенные графыAlex DainiakРассматриваем раскраски планарных графов и другие темы, связанные с раскрасками. Доказываем теорему Томассена о том, что списочное хроматическое число любого планарного графа не превышает пяти. Доказываем теорему Эрдёша о том, что существуют графы с большим хроматическим числом и одновременно большим обхватом.
Рассматриваем совершенные графы и доказываем слабую гипотезу Бержа.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Основы теории графов 08: раскраски и списочные раскраски
Основы теории графов 08: раскраски и списочные раскраскиAlex DainiakВводим понятие списочной раскраски. Демонстрируем различие между обчным и списочным хроматическим числом. Доказываем теоремы Брукса и Визинга. Доказываем теорему Алона об оценки списочного хроматического числа через минимальную степень вершин. Доказываем верхнюю оценку на списочное хроматическое число через обычное.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Основы теории графов 07: сепараторы в планарных графах
Основы теории графов 07: сепараторы в планарных графахAlex DainiakДоказываем теорему Липтона—Тарджена о существовании хороших разделяющих множеств (сепараторов) в планарных графах.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Основы теории графов 06: триангуляции и трёхсвязные планарные графы
Основы теории графов 06: триангуляции и трёхсвязные планарные графыAlex DainiakВводим понятие триангуляций. Доказываем, что триангуляции трёхсвязны. Доказываем критерий Татта о том, когда множество образует границу грани в трёхсвязном планарном графе. Доказываем теорему Вагнера—Фари о том, что у любого планарного графа существует укладка, в которой рёбра — отрезки прямых линий.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Основы теории графов 05: критерии планарности графов
Основы теории графов 05: критерии планарности графовAlex DainiakВводим определение укладки, планарных графов, доказываем критерии планарности Вагнера и Понтрягина—Куратовского.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Основы теории графов 04: метрики на деревьях
Основы теории графов 04: метрики на деревьяхAlex DainiakДоказываем теорему Зарецкого о существовании дерева с заданными расстояниями между вершинами.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Основы теории графов 03: связность
Основы теории графов 03: связностьAlex DainiakОбсуждаем два определения k-связности. Доказываем теорему Менгера об их эквавалентности (через теорему Форда—Фалкерсона). Доказываем теоремы о построении 2-связных и 3-связных графов. Вводим деревья блоков и точек сочленения. Доказываем теорему Мадера о существовании k-связного подграфа.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Основы теории графов 01: напоминание определений, теорема Форда—Фалкерсона
Основы теории графов 01: напоминание определений, теорема Форда—ФалкерсонаAlex DainiakВспоминаем определения изоморфизма, связности, соседства и т.п. Доказываем (напоминаем) теорему Форда—Фалкерсона, из которой на следующей лекции выведем теорему Менгера.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Основы теории графов 02: факторизация графов (разложение на простые подграфы)
Основы теории графов 02: факторизация графов (разложение на простые подграфы)Alex DainiakДоказываем теоремы о разложении полных графов на полные двудольные: Грэхема—Поллака и Анселя. Доказываем теорему Татта о критерии существования совершенного паросочетания в произвольном графе.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Конспект лекций по теории кодирования
Конспект лекций по теории кодированияAlex DainiakСобранные в один файл конспекты лекций по теории кодов, исправляющих ошибки. Лекции читаются на факультете ФИВТ МФТИ.
Последняя версия этого файла всегда доступна на www.dainiak.com
Графовая модель канала связи. Шенноновская ёмкость
Графовая модель канала связи. Шенноновская ёмкостьAlex DainiakГрафовая модель канала. Шенноновское произведение графов, шенноновская ёмкость. Теорема о верхней оценке шенноновской ёмкости.
Приложения теории кодирования
Приложения теории кодированияAlex DainiakПриложения кодов, исправляющих ошибки. Рандомизированный протокол в коммуникационной сложности. Криптосхема МакЭлиса. Однородные (псевдослучайные) множества на основе кодов, их приложения к дерандомизации задачи выполнимости и к задаче разделения секрета.
Циклические коды БЧХ, Хемминга. Восстановление синхронизации
Циклические коды БЧХ, Хемминга. Восстановление синхронизацииAlex DainiakКоды БЧХ.
Задача восстановления синхронизации. Восстановление синхронизации для смежных классов циклических кодов.
Циклическое представление кодов Хемминга. Совершенные коды. Коды Голея. Теорема Васильева.
Циклические коды. Граница БЧХ
Циклические коды. Граница БЧХAlex DainiakЦиклические коды. Проверочный и порождающий многочлены, критерий существования кода с заданным порождающим многочленом. Вид порождающей и проверочной матриц. Систематическое кодирование.
Граница Боуза—Чоудхури—Хоквингема.
Коды на основе многочленов и алгоритмы их декодирования
Коды на основе многочленов и алгоритмы их декодированияAlex DainiakКоды Рида—Соломона. Алгоритм декодирования Берлекэмпа—Велча.
Коды Рида—Маллера: кодовое расстояние, алгоритм мажоритарного декодирования.
Варианты обобщений конструкции Рида—Маллера. Лемма Липтона—ДеМилло—Шварца—Зиппеля. Понятие об алгеброгеометрических кодах.
Задача о ближайшем кодовом слове. Коды Галлагера—Сипсера—Шпильмана
Задача о ближайшем кодовом слове. Коды Галлагера—Сипсера—ШпильманаAlex DainiakСложность задачи декодирования линейных кодов: задача NCP (задачи о ближайшем кодовом слове).
Графы-расширители. Вероятностное доказательство существования расширителей. Коды на основе двудольных графов. Кодовое расстояние кодов на основе расширителей. Алгоритм декодирования Сипсера—Шпильмана.
Линейные коды
Линейные кодыAlex DainiakЛинейные коды. Определения. Порождающая и проверочная матрицы. Связь кодового расстояния с проверочной матрицей. Граница Варшамова—Гилберта. Систематическое кодирование. Декодирование по синдрому. Коды Хемминга.
Остаточный код. Граница Грайсмера—Соломона—Штиффлера.
Границы Плоткина и Элайеса—Бассалыго
Границы Плоткина и Элайеса—БассалыгоAlex DainiakГраница Плоткина.
Вложение метрических пространств. Лемма о числе векторов в евклидовом пространстве. Граница Элайеса—Бассалыго.
Коды, исправляющие ошибки. Простейшие границы. Коды Варшамова—Тененгольца.
Коды, исправляющие ошибки. Простейшие границы. Коды Варшамова—Тененгольца.Alex DainiakЗадача исправления и обнаружения ошибок. Геометрическая интерпретация. Типы ошибок. Метрики Хемминга и Левенштейна. Кодовое расстояние. Основные задачи теории кодов, исправляющих ошибки.
Коды Варшамова—Тененгольца, алгоритмы исправления одиночных ошибок выпадения и вставки символов.
Простейшие границы для параметров кодов, исправляющих ошибки замещения: границы сферической упаковки, Синглтона.
Алфавитное кодирование. Коды с минимальной избыточностью. Теорема Макмиллана.
Алфавитное кодирование. Коды с минимальной избыточностью. Теорема Макмиллана.Alex DainiakАлфавитное кодирование. Достаточные условия однозначности декодирования: равномерность, префиксность, суффиксность. Распознавание однозначности: критерий Маркова. Оценка длины неоднозначно декодируемого слова. Неравенство Крафта—Макмиллана; существование префиксного кода с заданным набором длин слов; следствие об универсальности префиксных кодов.
Коды с минимальной избыточностью: постановка задачи, теорема Хаффмана о редукции.
Коды Адамара. Каскадные коды Форни.
Коды Адамара. Каскадные коды Форни.Alex DainiakМатрицы Адамара. Конструкции Сильвестра и Пэли. Коды на основе матриц Адамара.
Каскадные коды. Коды Форни: конструкция и простой алгоритм декодирования.
Визуализация графов: left-right алгоритм распознавания планарности
Визуализация графов: left-right алгоритм распознавания планарностиAlex Dainiak
Визуализация графов: теорема Татта о барицентрической укладке
Визуализация графов: теорема Татта о барицентрической укладкеAlex Dainiak
More Related Content
More from Alex Dainiak (20)
Основы теории графов 05: критерии планарности графов
Основы теории графов 05: критерии планарности графовAlex DainiakВводим определение укладки, планарных графов, доказываем критерии планарности Вагнера и Понтрягина—Куратовского.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Основы теории графов 04: метрики на деревьях
Основы теории графов 04: метрики на деревьяхAlex DainiakДоказываем теорему Зарецкого о существовании дерева с заданными расстояниями между вершинами.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Основы теории графов 03: связность
Основы теории графов 03: связностьAlex DainiakОбсуждаем два определения k-связности. Доказываем теорему Менгера об их эквавалентности (через теорему Форда—Фалкерсона). Доказываем теоремы о построении 2-связных и 3-связных графов. Вводим деревья блоков и точек сочленения. Доказываем теорему Мадера о существовании k-связного подграфа.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Основы теории графов 01: напоминание определений, теорема Форда—Фалкерсона
Основы теории графов 01: напоминание определений, теорема Форда—ФалкерсонаAlex DainiakВспоминаем определения изоморфизма, связности, соседства и т.п. Доказываем (напоминаем) теорему Форда—Фалкерсона, из которой на следующей лекции выведем теорему Менгера.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Основы теории графов 02: факторизация графов (разложение на простые подграфы)
Основы теории графов 02: факторизация графов (разложение на простые подграфы)Alex DainiakДоказываем теоремы о разложении полных графов на полные двудольные: Грэхема—Поллака и Анселя. Доказываем теорему Татта о критерии существования совершенного паросочетания в произвольном графе.
[Слайды курса, прочитанного в МФТИ в 2013 году.]
Конспект лекций по теории кодирования
Конспект лекций по теории кодированияAlex DainiakСобранные в один файл конспекты лекций по теории кодов, исправляющих ошибки. Лекции читаются на факультете ФИВТ МФТИ.
Последняя версия этого файла всегда доступна на www.dainiak.com
Графовая модель канала связи. Шенноновская ёмкость
Графовая модель канала связи. Шенноновская ёмкостьAlex DainiakГрафовая модель канала. Шенноновское произведение графов, шенноновская ёмкость. Теорема о верхней оценке шенноновской ёмкости.
Приложения теории кодирования
Приложения теории кодированияAlex DainiakПриложения кодов, исправляющих ошибки. Рандомизированный протокол в коммуникационной сложности. Криптосхема МакЭлиса. Однородные (псевдослучайные) множества на основе кодов, их приложения к дерандомизации задачи выполнимости и к задаче разделения секрета.
Циклические коды БЧХ, Хемминга. Восстановление синхронизации
Циклические коды БЧХ, Хемминга. Восстановление синхронизацииAlex DainiakКоды БЧХ.
Задача восстановления синхронизации. Восстановление синхронизации для смежных классов циклических кодов.
Циклическое представление кодов Хемминга. Совершенные коды. Коды Голея. Теорема Васильева.
Циклические коды. Граница БЧХ
Циклические коды. Граница БЧХAlex DainiakЦиклические коды. Проверочный и порождающий многочлены, критерий существования кода с заданным порождающим многочленом. Вид порождающей и проверочной матриц. Систематическое кодирование.
Граница Боуза—Чоудхури—Хоквингема.
Коды на основе многочленов и алгоритмы их декодирования
Коды на основе многочленов и алгоритмы их декодированияAlex DainiakКоды Рида—Соломона. Алгоритм декодирования Берлекэмпа—Велча.
Коды Рида—Маллера: кодовое расстояние, алгоритм мажоритарного декодирования.
Варианты обобщений конструкции Рида—Маллера. Лемма Липтона—ДеМилло—Шварца—Зиппеля. Понятие об алгеброгеометрических кодах.
Задача о ближайшем кодовом слове. Коды Галлагера—Сипсера—Шпильмана
Задача о ближайшем кодовом слове. Коды Галлагера—Сипсера—ШпильманаAlex DainiakСложность задачи декодирования линейных кодов: задача NCP (задачи о ближайшем кодовом слове).
Графы-расширители. Вероятностное доказательство существования расширителей. Коды на основе двудольных графов. Кодовое расстояние кодов на основе расширителей. Алгоритм декодирования Сипсера—Шпильмана.
Линейные коды
Линейные кодыAlex DainiakЛинейные коды. Определения. Порождающая и проверочная матрицы. Связь кодового расстояния с проверочной матрицей. Граница Варшамова—Гилберта. Систематическое кодирование. Декодирование по синдрому. Коды Хемминга.
Остаточный код. Граница Грайсмера—Соломона—Штиффлера.
Границы Плоткина и Элайеса—Бассалыго
Границы Плоткина и Элайеса—БассалыгоAlex DainiakГраница Плоткина.
Вложение метрических пространств. Лемма о числе векторов в евклидовом пространстве. Граница Элайеса—Бассалыго.
Коды, исправляющие ошибки. Простейшие границы. Коды Варшамова—Тененгольца.
Коды, исправляющие ошибки. Простейшие границы. Коды Варшамова—Тененгольца.Alex DainiakЗадача исправления и обнаружения ошибок. Геометрическая интерпретация. Типы ошибок. Метрики Хемминга и Левенштейна. Кодовое расстояние. Основные задачи теории кодов, исправляющих ошибки.
Коды Варшамова—Тененгольца, алгоритмы исправления одиночных ошибок выпадения и вставки символов.
Простейшие границы для параметров кодов, исправляющих ошибки замещения: границы сферической упаковки, Синглтона.
Алфавитное кодирование. Коды с минимальной избыточностью. Теорема Макмиллана.
Алфавитное кодирование. Коды с минимальной избыточностью. Теорема Макмиллана.Alex DainiakАлфавитное кодирование. Достаточные условия однозначности декодирования: равномерность, префиксность, суффиксность. Распознавание однозначности: критерий Маркова. Оценка длины неоднозначно декодируемого слова. Неравенство Крафта—Макмиллана; существование префиксного кода с заданным набором длин слов; следствие об универсальности префиксных кодов.
Коды с минимальной избыточностью: постановка задачи, теорема Хаффмана о редукции.
Коды Адамара. Каскадные коды Форни.
Коды Адамара. Каскадные коды Форни.Alex DainiakМатрицы Адамара. Конструкции Сильвестра и Пэли. Коды на основе матриц Адамара.
Каскадные коды. Коды Форни: конструкция и простой алгоритм декодирования.
Визуализация графов: left-right алгоритм распознавания планарности
Визуализация графов: left-right алгоритм распознавания планарностиAlex Dainiak
Визуализация графов: теорема Татта о барицентрической укладке
Визуализация графов: теорема Татта о барицентрической укладкеAlex Dainiak
Основы теории графов 05: критерии планарности графов
Основы теории графов 05: критерии планарности графовAlex Dainiak
Основы теории графов 04: метрики на деревьях
Основы теории графов 04: метрики на деревьяхAlex Dainiak
Основы теории графов 01: напоминание определений, теорема Форда—Фалкерсона
Основы теории графов 01: напоминание определений, теорема Форда—ФалкерсонаAlex Dainiak
Основы теории графов 02: факторизация графов (разложение на простые подграфы)
Основы теории графов 02: факторизация графов (разложение на простые подграфы)Alex Dainiak
Графовая модель канала связи. Шенноновская ёмкость
Графовая модель канала связи. Шенноновская ёмкостьAlex Dainiak
Циклические коды БЧХ, Хемминга. Восстановление синхронизации
Циклические коды БЧХ, Хемминга. Восстановление синхронизацииAlex Dainiak
Коды на основе многочленов и алгоритмы их декодирования
Коды на основе многочленов и алгоритмы их декодированияAlex Dainiak
Задача о ближайшем кодовом слове. Коды Галлагера—Сипсера—Шпильмана
Задача о ближайшем кодовом слове. Коды Галлагера—Сипсера—ШпильманаAlex Dainiak
Коды, исправляющие ошибки. Простейшие границы. Коды Варшамова—Тененгольца.
Коды, исправляющие ошибки. Простейшие границы. Коды Варшамова—Тененгольца.Alex Dainiak
Алфавитное кодирование. Коды с минимальной избыточностью. Теорема Макмиллана.
Алфавитное кодирование. Коды с минимальной избыточностью. Теорема Макмиллана.Alex Dainiak
Визуализация графов: left-right алгоритм распознавания планарности
Визуализация графов: left-right алгоритм распознавания планарностиAlex Dainiak
Визуализация графов: теорема Татта о барицентрической укладке
Визуализация графов: теорема Татта о барицентрической укладкеAlex Dainiak
Визуализация графов: укладки деревьев
- 1. Визуализация графов Computer Science клуб, март 2014 Александр Дайняк, ФИВТ МФТИ www.dainiak.com
- 2. Правила укладки корневых деревьев
- 4. h-v-укладка и еѐ смещение
- 5. Склейка h-v-дерева из поддеревьев
- 12. Немного матана…