Может ли класс наследственных графов содержать почти все, но не все, n-вершинные графы?

10

Пусть наследственный класс графов. (Наследственный = замкнуто относительно взятия индуцированных подграфов.) Пусть обозначит множество -vertex графов в . Допустим, что содержит почти все графы, если доля всех вершинных графов, попадающих в приближается к 1 при . $Q$ $Q_n$ $n$ $Q$ $Q$ $n$ $Q_n$ $n\rightarrow\infty$

Вопрос: Возможно ли, что наследственный граф класса содержит почти все графы, но для каждого найдется хотя бы один граф, которого нет в ? $Q$ $n$ $Q_n$

graph-theory Андрас Фараго
источник

10

Ответ будет нет - при фиксированном пусть быть число вершин в наименьшем графе не в . Теперь рассмотрим гораздо больше, чем . Для случайного графа на вершинах вероятность того, что первые вершин индуцируют зависит только от . Разбиение набора вершин на непересекающихся множеств размера и рассмотрение вероятности того, что ни один из множеств не равен показывает, что вероятность нахождения в стремится к $Q$ $t$ $H$ $Q$ $n$ $t$ $n$ $t$ $H$ $t$ $n/t$ $t$ $H$ $Q$ $0$ при $n$ увеличивается.

Даниелло
источник

5

Это еще более убедительно доказывает, что любой нетривиальный наследственный класс содержит долю всех графов, сокращающуюся до

. Путем разбиения

на множество края непересекающихся

«s и используя тот же аргумент , что должно быть возможно усилить это в нечто большее , как

.

\exp - c n

$\exp -cn$

K_{n}

$K_n$

K_{t}

$K_t$

\exp - c n^{2}

$\exp -cn^2$

Дэвид Эппштейн

@ Андрас Фараго: Отказ от ответа также может быть напрямую выведен из известных результатов гипотезы Эрдоса-Хайнала [ en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Hajnal_conjecture] . Полученная оценка не так хороша (кажется, что вы получаете только долю

.

\exp (- \exp (c \sqrt{\log n}))

$\exp(-\exp(c \sqrt{\log n}))$

Луи Эсперет

1

@ Дэвид Эппштейн: Я думаю, что

- это именно то, что вы получаете, рекурсивно применяя (

раз) следующий классический результат. Если существует проективная плоскость порядка

то множество ребер

можно разбить на

непересекающихся по ребрам копий

.

\exp - c n^{2}

$\exp -cn^2$

\log \log n

$\log \log n$

q

$q$

K_{q^{2}}

$K_{q^2}$

q (q + 1)

$q(q+1)$

K_{q}

$K_q$

Луи Эсперет,

10

Чтобы добавить ответ Даниэля, точная плотность наследственных классов была тщательно исследована в комбинаторике. Для класса структур немеченый срез является множеством классов изоморфизмов структур в , имеющих вершин. (Немеченная) скорость из класса в структурах , Обозначим класс графов . Вопрос в том, будет ли $C$ $C_n$ $C$ $n$ $C$ $|C_n|$ $G$ $\lim_{n\to \infty} |Q_n|/|G_n| = 1$ для любого наследственного класса графов . $Q$

Поскольку предел всегда равен 0 для наследственного , фундаментальный вопрос заключается в том, как функция сам себя ведет. Пусть обозначает число целочисленных разбиений , где $Q$ $|Q_n|$ $p(n)$ $p(n) = 2^{\Theta(\sqrt{n})}$ $|Q_n|$ $|Q_n| = \Omega(p(n))$

Йожеф Балог, Бела Боллобас, Майкл Сакс и Вера Т. Сос, Немаркированная скорость свойства наследственного графа , Журнал комбинаторной теории, Серия B, 99 9–19, 2009. doi: 10.1016 / j.jctb.2008.03.004 ( препринт )

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

Может ли класс наследственных графов содержать почти все, но не все, n-вершинные графы?

Ответы: