Лемма о регулярности для разреженных графов

25

Лемма о регулярности Семереди говорит, что каждый плотный граф может быть аппроксимирован как объединение многих двудольных графов расширителей. Точнее, существует большинство разбиений вершин на наборов, так что большинство пар множеств образуют двудольные расширители (количество множеств в разбиении и параметр расширения зависят от параметра аппроксимации):O ( 1 )О(1)О(1)

http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma

Существуют версии этой леммы для "хороших" разреженных графов, см., Например:

http://www.estatistica.br/~yoshi/MSs/FoCM/sparse.pdf

http://people.maths.ox.ac.uk/scott/Papers/sparseregularity.pdf

Что удивляет меня в этих формулировках, так это то, что они гарантируют, что большинство пар множеств в разбиении образуют двудольные экспандеры, и эти двудольные экспандеры могут быть пустыми. Таким образом, в общих разреженных графах вполне возможно, что все ребра между различными частями в разбиении вершин не принадлежат расширителю.

Интересно, есть ли формулировки, которые дают большинство ребер между частями от расширителя, или нет надежды на такую ​​формулировку.

Дана Мошковиц
источник
1
но разве не кажется интуитивным, что thm, который для плотных графов, ломается в некотором роде на разреженных? обратите внимание, что ссылка на википедию, на которую ссылаются, на самом деле ничего не говорит о графах расширителей, что говорит о том, что это может быть более поздняя интерпретация / формулировка ...
vzn 24.12.12
1
(1) Обычный термин для хороших пар поведения наборов - «правильные пары» (в Википедии «псевдослучайная» пара). Я заменил его «двудольными экспандерами», потому что считаю эту терминологию более естественной для меня. В любом случае предполагается, что если вы выберете достаточно большие подмножества с обеих сторон пары, количество ребер между подмножествами будет пропорционально количеству ребер в паре. (2) Конечно, то, что верно для плотных графов, может перестать быть верным для разреженных графов. Мой вопрос как раз о том, в какой степени свойства из плотного случая продолжают сохраняться в редком случае.
Дана Мошковиц

Ответы:

4

Ниже многословен ответ, но Т.Л., д - р в общем случае нет никакой надежды на такую формулировку, но и для многих конкретных классов разреженных графов, имеющих регулярность Леммы этой формулировки существует.

Для фона есть две популярные версии SRL. Это: для любого фиксированного и любого узлового графа можно разделить на запчасти так что ...ε>0Nгзнак равно(В,Е)Взнак равноВ0В1Вппзнак равноОε(1)

  • (Комбинаторное выражение) (1) и размеры любых отличаются не более чем на ( называется "исключительным множеством") и (2) всеми парами оставшихся частей, кроме удовлетворяют (здесь дает плотность между частями, то есть долю имеющихся ребер).|В0|εNВ1,...,Вп1В0εп2(Вя,ВJ)

    |d(S,T)-d(Вя,ВJ)|<ε для всех SВя,TВJ
    d(,)

  • (Аналитическое выражение) Letting мы имеем

    dяsс(Вя,ВJ)знак равноМаксимумSВя,TВJ|Вя||ВJ||d(Вя,ВJ)-d(S,T)|,
    Σя,Jзнак равно0пdяsс(Вя,ВJ)<εN2,

«Комбинаторная формулировка» (я только что придумал эти названия, они не являются стандартными) является оригинальной и, вероятно, более известной, тогда как «аналитическая формулировка» более современная и связана с ограничениями графа и т. Д. (Я думаю, что она была популяризирована здесь). На мой взгляд, аналитическая форма - это правильная формализация «графа, аппроксимированного объединением двудольных экспандеров», поскольку он дает контроль над общей «ошибкой» такого приближения, и не существует исключительного набора, в котором можно скрыть массу. Но на данный момент это просто косметика, потому что это простая, но важная лемма, что эти две фразы эквивалентны. Чтобы перейти от комбинаторного к аналитическому, просто объединение связывает вклад в несоответствие нерегулярных частей и исключительного множества. Чтобы перейти от аналитического к комбинаторному, просто переместите любую часть, которая вносит слишком большое расхождение в исключительный набор, и примените неравенство Маркова для контроля его массы.

Теперь для редкости регулярности. Цель редкой регулярности заменить в соответствующих неравенств с , где представляет собой долю всех возможных ребер представить в . Критически, с этим изменением, две фразы больше не эквивалентны. Скорее, аналитическая формулировка сильнее: она все еще подразумевает Combinatorial точно так же, как и раньше, но Combinatorial обычно не подразумевает Analytic, потому что (как и предполагалось в OP) можно потенциально скрыть большую плотность в исключительном наборе или между нерегулярным пары деталей. В самом деле, это разделение формально: графы нижней границы для плотного SRL (скажем, этотεεd(г)d(г)г) подразумевают, что аналитическое выражение не распространяется вообще на разреженные графы, но статья Скотта, связанная в ОП, показывает, что комбинаторное выражение фактически распространяется на все разреженные графы без условий.

Обследование, связанное в ОП, в основном говорит о SRL для «регулярных верхних» разреженных графов, что примерно означает, что на графике нет разрезов, которые более плотны, чем среднее значение более чем на постоянный коэффициент. Для этих конкретных графов комбинаторные и аналитические фразы эквивалентны, поскольку в исключительных частях не может быть скрыто слишком много дополнительной массы, поэтому их вклад в расхождение можно ограничить объединением, как в плотном случае. Таким образом, эти графы имеют интерпретацию «аппроксимируемую объединением двудольных экспандеров».

Наконец, я должен упомянуть, что есть много других гипотез в литературе, которые также подразумевают эквивалентность между этими фразами. Например, верхняя регулярность (определенная здесь ) является более общей, чем верхняя регулярность, и ее все же достаточно, чтобы подразумевать эквивалентность. Однако для этого класса графов и других я знаю только о связанных леммах слабой регулярности.Lп

GMB
источник
1
Кроме того, извинения за некромантию потока - это просто совпало с моим текущим освещенным обзором, и я подумал, что поделюсь тем, что нашел.
GMB