Введение
В теории графов граф называется псевдослучайным, если он подчиняется определенным свойствам, которые подчиняются случайным графам с высокой вероятностью. Конкретного определения псевдослучайности графов нет, но существует много разумных характеристик псевдослучайности, которые можно рассмотреть. Псевдослучайные свойства впервые были официально рассмотрены Эндрю Томассоном в 1987 году. Он определил условие, называемое "смешанностью": граф, как говорят, смешан для реального и с если для каждого подмножества множества вершин , где число краев среди (эквивалентно, число краев в подграфе, индуцированных множеством вершин). Можно показать, что случайный график Эрдоша-Рени почти наверняка перепутан. Однако графики с менее равномерно распределенными краями, например, график на вершинах, состоящий из вершины полного графа и полностью независимых вершин, не перемешаны для любого небольшого , что делает перемешаность разумным количественным показателем для "случайных" свойств распределения краев графа.
for every subset of the vertex set , where is the number of edges among (equivalently, the number of edges in the subgraph induced by the vertex set ). It can be shown that the Erdős–Rényi random graph is almost surely jumbled. However, graphs with less uniformly distributed edges, for example a graph on vertices consisting of an vertex complete graph and completely independent vertices, are not jumbled for any small , making jumbledness a reasonable quantifier for "random like" properties of a graph's edge distribution.
Связь с местными условиями
Томассон показал, что условие "сброшенного" подразумевается более простым условием проверки, только в зависимости от кодеграду двух вершин, а не от каждого подмножества множества вершин графа. Позволяя быть числом общих соседей двух вершин и , Томассон показал, что, если дается график на вершинах с минимальной степенью , если для каждого и , то перемешано. Этот результат показывает, как алгоритмически проверить состояние путаницы в полиномиальном времени в количестве вершин, и может быть использован для показа псевдослучайности конкретных графиков.
Связь с регулярностью графа
Концепция графов, которые действуют как случайные графы, тесно связана с концепцией регулярности графов, используемой в лемме регулярности Шемереди. Для , пара множеств вершин называется регулярной, если для всех подмножеств , она утверждает, что где обозначает плотность краев между и : число краев между и делится на Это условие предполагает двухсторонний аналог условия несоответствия, и по сути утверждает, что краи между и ведут себя "случайным образом". Кроме того, Миклош Симоновиц и Вера Т. Сос в 1991 году показали, что граф удовлетворяет вышеуказанным условиям слабой псевдослучайности, используемым в теореме Чунга-Грэма-Уилсона, если и только если он обладает разделом Шемереди, где почти все плотности близки к плотности краев всего графа.
where denotes the edge density between and : the number of edges between and divided by This condition implies a bipartite analogue of the discrepancy condition, and essentially states that the edges between and behave in a "random like" fashion. In addition, it was shown by Miklós Simonovits and Vera T. Sós in 1991 that a graph satisfies the above weak pseudorandomness conditions used in the Chung–Graham–Wilson theorem if and only if it possesses a Szemerédi partition where nearly all densities are close to the edge density of the whole graph.
Аналоги теоремы Чжунга, Грэма и Уилсона
Теорема Чжунга Грэма Уилсона, в частности, подразумевает подсчет подграфов из расхождения, не следует для последовательностей графов с плотностью краев, приближающейся к , или, например, для обычного случая регулярных графов на вершинах, как следующие редкие аналоги расхождения и собственных граничащих условий обычно рассматриваются: Незначительное расхождение: для любых подмножек множества вершин , количество краев между и находится в пределах ограниченного собственного значения: Если собственные значения матрицы смежности , то, как правило, верно, что это собственное условие подразумевает соответствующее расхождение, но обратное условие не верно: несовместное соединение случайного большого регулярного графа и полного вершины графа имеет точно два собственных значения свойства, но, вероятно, удовлетворяет расхождению. Однако, как доказали Дэвид Конлон и Юфэй Чжао в 2017 году, небольшие варианты расхождения и условий собственных значений для регулярных графиков Кейли эквивалентны линейному масштабированию в одном направлении, это следует из леммы смешивания экспандеров, в то время как другое требует предположения, что график является графиком Кейли и использует неравенство Гротендика.
Sparse discrepancy: for any subsets of the vertex set , the number of edges between and is within of Sparse eigenvalue bounding: If are the eigenvalues of the adjacency matrix of , then
It is generally true that this eigenvalue condition implies the corresponding discrepancy condition, but the reverse is not true: the disjoint union of a random large regular graph and a vertex complete graph has two eigenvalues of exactly but is likely to satisfy the discrepancy property. However, as proven by David Conlon and Yufei Zhao in 2017, slight variants of the discrepancy and eigenvalue conditions for regular Cayley graphs are equivalent up to linear scaling in One direction of this follows from the expander mixing lemma, while the other requires the assumption that the graph is a Cayley graph and uses the Grothendieck inequality.
Связь с теоремой Грин-Тао
Псевдослучайные графики играют заметную роль в доказательстве теоремы Грин-Тао. Теорема доказана путем переноса теоремы Сземереди, утверждения о том, что набор положительных целых чисел с положительной естественной плотностью содержит произвольно длинные арифметические прогрессии, в разреженную настройку (поскольку простые числа имеют естественную плотность в целых числах). Переход к редким множествам требует, чтобы множества вели себя псевдослучайно, в том смысле, что соответствующие графики и гиперграфики имеют правильные плотности подграфов для некоторого фиксированного множества небольших (гипер) подграфов. Затем показано, что подходящее супермножество простых чисел, называемое псевдопростыми, в котором простые числа плотно, подчиняется этим условиям псевдослучайности, завершая доказательство.