Явные и вероятностные конструкции дистанционных графов с маленьким кликовым и большим хроматическим числами

Изучаются дистанционные графы с экспоненциально большим хроматическим числом, не содержащие $k$-клик, т. е. полных подграфов размера $k$. Явные конструкции графов строятся на основе векторов целочисленной решетки. Для большого класса графов получены точные оценки параметров, при выполнении которых эти графы не содержат $k$-клик. За счет этого улучшены оценки снизу максимума хроматических чисел графов описанного класса. Приведен новый вероятностный подход для построения дистанционных графов без $k$-клик, который дает лучшие оценки максимума хроматических чисел при больших $k$.
Библиография: 23 наименования.