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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\Omega(n^c)$$c>0$

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