График смен

В теории граф сдвига $Gn для, k$ графов $n,k\in \mathbb {N} ,\ n>2k>0$ граф, вершины которого соответствуют упорядоченному $k$ -кортежи $a=(a_{1},a_{2},\dotsc ,a_{k})$ с $1\leq a_{1}<a_{2}<\cdots <a_{k}\leq n$ и где две вершины $a,b$ смежны тогда и только тогда, когда $a_{i}=b_{i+1}$ или $a_{i+1}=b_{i}$ для всех $1\leq i\leq k-1$ . Графики сдвига не содержат треугольников и для фиксированных $k$ их хроматическое число стремится к бесконечности с $n$ . ^[1] Естественно расширить график сдвига $G_{n,k}$ с ориентацией $a\to b$ если $a_{i+1}=b_{i}$ для всех $1\leq i\leq k-1$ . Позволять ${\overrightarrow {G}}_{n,k}$ — результирующий граф направленного сдвига.Обратите внимание, что ${\overrightarrow {G}}_{n,2}$ — ориентированный линейный граф транзитивного турнира, соответствующий тождественной перестановке. Более того, ${\overrightarrow {G}}_{n,k+1}$ представляет собой направленный линейный график ${\overrightarrow {G}}_{n,k}$ для всех $k\geq 2$ .

Дополнительные факты о графиках смен

Нечетные циклы $G_{n,k}$ иметь длину как минимум $2k+1$ , в частности $G_{n,2}$ треугольник свободен.
Для фиксированного $k\geq 2$ асимптотическое поведение хроматического числа $G_{n,k}$ дается $\chi (G_{n,k})=(1+o(1))\log \log \cdots \log n$ где повторяется функция логарифма ${\displaystyle k-1}$ раз. ^[1]
Дальнейшие связи с хроматической теорией графов и орграфов были установлены в. ^[2]
Графики сдвига, в частности $G_{n,3}$ также играют центральную роль в контексте размерности интервальных порядков. ^[3]

Представление графиков смен

График смен $G_{n,2}$ это линейный график полного графа $K_{n}$ следующим образом: Рассмотрим числа из $1$ к $n$ упорядочены на линии и рисуют отрезки линий между каждой парой чисел. Каждый сегмент линии соответствует $2$ -кортеж из его первого и последнего числа, которые в точности являются вершинами $G_{n,2}$ . Два таких отрезка соединяются, если начальная точка одного отрезка является конечной точкой другого.

Примечание. Это кажется ложным, поскольку $\{1,2\}$ и $\{1,3\}$ будет несмежным. Кто-то должен это проверить.

Ссылки

^ Jump up to: ^а ^б Эрдеш, П .; Хайнал, А. (1968), «О хроматическом числе бесконечных графов», Теория графов (Proc. Colloq., Тихань, 1966) (PDF) , Нью-Йорк: Academic Press, стр. 83–98, MR 0263693
^ Симони, Габор; Тардос, Габор (2011). «О направленном локальном хроматическом числе, графах сдвига и графах типа Борсука». Журнал теории графов . 66 : 65–82. arXiv : 0906.2897 . дои : 10.1002/jgt.20494 . S2CID 14215886 .
^ Фюреди, З. ; Хайнал, П.; Рёдль, В .; Троттер, WT (1991). «Интервальные порядки и графики сдвигов». Множества, графики и числа . 60 . Учеб. Коллок. Математика. Соц. Янош Боляи: 297–313.

[infinite_graphs-1] Jump up to: ^а ^б Эрдеш, П .; Хайнал, А. (1968), «О хроматическом числе бесконечных графов», Теория графов (Proc. Colloq., Тихань, 1966) (PDF) , Нью-Йорк: Academic Press, стр. 83–98, MR 0263693

[2] Симони, Габор; Тардос, Габор (2011). «О направленном локальном хроматическом числе, графах сдвига и графах типа Борсука». Журнал теории графов . 66 : 65–82. arXiv : 0906.2897 . дои : 10.1002/jgt.20494 . S2CID 14215886 .

[interval_orders-3] Фюреди, З. ; Хайнал, П.; Рёдль, В .; Троттер, WT (1991). «Интервальные порядки и графики сдвигов». Множества, графики и числа . 60 . Учеб. Коллок. Математика. Соц. Янош Боляи: 297–313.

[1]

[2]

[3]