О $(p,q)$-свойстве графов и гиперграфов

В этом докладе будет рассказано о раскраске геометрических графов и гиперграфов, обладающих $(p,q)$-свойством.
Понятие $(p,q)$-свойства первоначально было введено Хадвигером и Дебруннером для семейства вынуклых тел в $\mathbb R^d$ в связи с обобщением теоремы Хелли.
Пусть $G=(V,E)$ это гиперграф, а $p$, $q$ целые числа такие, что $p\geqslant q\geqslant 1$. Будем говорить, что $G$ имеет $(p,q)$-свойство, если $|V|\geqslant p$, а каждое подмножество $V'\subseteq V$ с $|V|\geqslant p$ содержит независимое подмножество из $q$ элементов.
Следующая теорема это основной новый результат этого доклада.
Теорема. Пусть числа $r$, $p$, $q$, $p\geqslant q\geqslant r$ натуральные и $d=p-q$.
Если $p<r(d+1)$, то для всех $N$ существует $r$-граф $G$, имеющий $(p,q)$-свойство такой, что $\chi(G)>N$.
Если $p\geqslant r(d+1)$, то для любого $r$-графа $G$, имеющего $(p,q)$-свойство выполняются неравенства
$$ \left\lceil\frac{d}{r-1}\right\rceil+1 \le \chi(G) \leqslant\left\lceil \frac {d}{r-1} \right\rceil + 2. $$