Глобальные свойства наследственных классов?

15

Наследственный класс структур (например, графы) - это класс, замкнутый при индуцированных подструктурах или, что то же самое, замкнутый при удалении вершины.

Классы графов, которые исключают минор, имеют хорошие свойства, которые не зависят от конкретного исключенного минора. Мартин Грох показал, что для классов графов, исключая минор, существует полиномиальный алгоритм для изоморфизма, а логика с фиксированной точкой со счетом захватывает полиномиальное время для этих классов графов. (Grohe, Определенность с фиксированной точкой и полиномиальное время на графах с исключенными несовершеннолетними , LICS, 2010.) Их можно рассматривать как «глобальные» свойства.

Известны ли похожие «глобальные» свойства для наследственных классов (графов или более общих структур)?

Было бы хорошо, чтобы каждый ответ был сосредоточен только на одном конкретном свойстве.

Андраш Саламон
источник

Ответы:

13

Наследственные свойства очень «устойчивы» в следующем смысле.

Нога Алон и Асаф Шапира показали, что для любого наследственного свойства , если граф G нуждается в добавлении или удалении более чем ϵ n 2 ребер, чтобы удовлетворить P , то в G существует подграф с размером не более f P ( ε ) , которая не удовлетворяет P . Здесь функция f зависит только от свойства P (а не, например, от размера графа G ). Эрдос сделал такую ​​гипотезу только о свойстве k- окрашиваемости.пграммϵn2PGfP(ϵ)PfPGk

В самом деле, Алон и Шапир доказать следующее более сильный факт: данный , для любых е в ( 0 , 1 ) , есть N ( ε ) , ч ( ε ) и δ ( ε ) такое , что если граф G имеет , по меньшей мере , N вершин и нужно, чтобы по крайней мере ϵ n 2 ребер было добавлено / удалено, чтобы удовлетворить P , тогда для по крайней мере δ доли индуцированных подграфов на h вершинах индуцированный подграф нарушаетPϵ(0,1)N(ϵ)h(ϵ)δ(ϵ)GNϵn2Pδh . Таким образом, если ϵ и свойство P фиксированы, чтобы проверить, удовлетворяет ли входной граф P или ϵ- далеко от удовлетворения P , тогда нужно только запросить ребра случайного индуцированного подграфа постоянного размера из графа и проверьте, удовлетворяет ли это свойство или нет. Такой прибор всегда будет принимать графикиудовлетворяющие P и отвергнет графы epsi ; -far от удовлетворения его с постоянной вероятностью. Кроме того, любое свойство, которое в этом смысле проверяется в одностороннем порядке, является наследственным свойством! Смотрите статью Алона и Шапира для деталей.PϵPPϵPPε

Арнаб
источник
Два дня назад Czumaj провел приятную пленарную беседу ( springerlink.com/content/9rw586wx50656412 ) по тестированию собственности. Более подробную информацию можно найти в публикации Терри Тао ( terrytao.wordpress.com/2007/10/31/… ) или в опросе Голдрайха ( eccc.uni-trier.de/report/2010/082 ).
RJK
Тестируемость - это великое глобальное свойство. Спасибо за хорошее резюме.
Андрас Саламон
8

Возможно, это не совсем то, что вы имели в виду, но существуют известные ограничения на то, сколько графов на вершинах может быть в наследственном классе графов. Например, не существует наследственного класса графов, который бы имел от 2 Ω ( n ) до 2 o ( n log n ) графов на n вершинах.N2Ω(N)2о(NжурналN)N

Ссылка: Э. Шейнерман, Дж. Зито, О размерах наследственных классов графов, Журнал Комбинаторной Теории, Серия B

Трэвис Сервис
источник
Эти свойства, безусловно, соответствуют: я думаю, что количество, на которое вы ссылаетесь, называется «скоростью».
Андрас Саламон
8

Это связано с ответом Трэвиса. На самом деле, это можно считать более сильной версией.

Статья Bollob \ « как и Томасона показывает (Combinatorica, 2000) , что в Ерд \ Н {о} С.Р. \» Enyi случайные графы р некоторой фиксированной постоянной), каждое наследственное свойство может быть аппроксимирована то , что они назвать базовую собственность. Базовый почти означает графы, чьи наборы вершин являются объединениями r классов, s из которых охватывают клики, а r - s из которых охватывают независимые множества, но не совсем. Это приближение используется для характеристики размера наибольшего P- множества, а также P- хроматического числа G n ,граммN,ппрsр-sпп , где P некоторое фиксированное наследственное свойство. Еслирразрешено варьировать, поведение не является понятным.граммN,ппп

Для большей предыстории этой и связанной с ней работы есть обзор Bollob \ 'as (Proceedings of ICM 1998), который также дает заманчивую гипотезу в этом направлении, но для гиперграфов.

Я нахожу очень интересной глубокую связь между наследственными свойствами и леммой Регулярности Семёди, поскольку она использовалась здесь и в результатах Алона и Шапиры.

RJK
источник
Спасибо Росс Связь, которую вы выделяете между наследственными свойствами и леммой о регулярности, может дать некоторые интересные вопросы.
Андрас Саламон
7

Ответ Суреша о гипотезе AKR заставил меня задуматься о той же гипотезе для наследственных свойств. Я думаю (если я не сделал ошибку), я могу показать, что все нетривиальные наследственные свойства имеют (рандомизированную и детерминистическую) сложность дерева решений , которая устанавливает гипотезу AKR для таких свойств (с точностью до констант).Θ(N2)

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

Итак, это еще один пример глобального свойства всех наследственных свойств графа.

Робин Котари
источник
Мне было бы очень интересно прочитать черновик с вашими результатами.
Андрас Саламон
Я дам вам знать, когда найду время написать это. Я также достаточно уверен, что это должно следовать из некоторых известных нижних границ в этой области. К сожалению, я не знаю ни одного эксперта в этой области, которого я мог бы спросить.
Робин Котари
6

Ω(Nс)с>0

Дэвид Эппштейн
источник
2
Это потенциально очень интересный пример, но некоторые превосходные теоретики структурных графов, которых я знаю, считают это ложным!
RJK
4

Это «обратное» направление, но хорошо известная гипотеза Аандераа-Розенберга-Карпа применима к свойствам графа, которые монотонны вверх (т. Е. Если G удовлетворяет этому свойству, то любой граф на тех же узлах, у которого множество ребер содержит E (G) )).

Суреш Венкат
источник
4
Гипотеза AKR в равной степени применима к свойствам, которые являются монотонными в нисходящем направлении, потому что дополнение к восходящему-монотонному свойству является нисходящим-монотонным свойством, а сложность дерева решений для свойства и его дополнения одинакова. Однако понятие монотонности в гипотезе AKR относится к удалению ребер, в то время как вопрос OP касается монотонности по удалению вершин. Они определяют два разных класса свойств.
Робин Котари
2
Может быть интересно сделать новый вопрос для классов, закрытых по субструктуре.
Андрас Саламон