О несуществовании 3-представимости четырёхмерного куба

О несуществовании 3-представимости четырёхмерного куба

Пяткин А. В., Сафарова А. И.
Дискретный анализ и исследование операций, 33, 2, 97-114 (2026)
Скачать статью

УДК 519.17 
DOI: 10.33048/daio.2026.33.848

Аннотация:

Граф называется 3-представимым, если существует 3-униформное слово, буквами которого являются вершины графа, причём две вершины смежны тогда и только тогда, когда соответствующие буквы чередуются в слове. В работе представлено компьютерное доказательство того, что четырёхмерный куб не 3-представим. 

Ил. 1, библиогр. 11.

Литература:
  1. Kitaev S. V., Pyatkin A. V. On representable graphs // J. Autom. Lang. Comb. 2008. V. 13, No. 1. P. 45–54.
     
  2. Китаев С. В., Пяткин А. В. Графы, представимые в виде слов. Обзор результатов // Дискрет. анализ и исслед. операций. 2018. Т. 25, № 2. С. 19–53.
     
  3. Kitaev S. V., Lozin V. V. Words and graphs. Cham: Springer, 2015. 264 p.
     
  4. Bouchet A. Circle graph obstructions // J. Comb. Theory, Ser. B. 1994. V. 60, No. 1. P. 107–144.
     
  5. Kitaev S. V. On graphs with representation number 3 // J. Autom. Lang. Comb. 2013. V. 18, No. 2. P. 97–112.
     
  6. Alshammari N. S., Kitaev S. V., Pyatkin A. V. On the representation number of grid graphs and cylindric grid graphs. Ithaca, NY, 2025. 10 p. (e-Print Archive / Cornell Univ.; arXiv:2507.16469). DOI: 10.48550/arXiv.2507.16469.
     
  7. Dwary T., Mozhui K., Krishna K. V. Representation number of wordrepresentable split graphs. Ithaca, NY, 2025. 14 p. (e-Print Archive / Cornell Univ.; arXiv:2502.00872). DOI: 10.48550/arXiv.2502.00872.
     
  8. Broere B., Zantema H. The $k$-dimensional cube is $k$-representable // J. Autom. Lang. Comb. 2019. V. 24, No. 1. P. 3–12.
     
  9. Hefty Z., Horn P., Muir C., Owens A. Word-representable graphs: Orientations, posets, and bounds // Electron. J. Comb. 2024. V. 31, No. 4. Article ID P4.2. 26 p.
     
  10. Glen M., Kitaev S. V., Pyatkin A. V. On the representation number of a crown graph // Discrete Appl. Math. 2018. V. 244. P. 89–93.
     
  11. Hefty Z., Horn P., Muir C., Owens A. Word-representation numbers of graphs: Bottlenecks and bounds // J. Comb. Theory, Ser. A. 2026. V. 223. Article ID 106215. 25 p.

Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF–2026–0021). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Пяткин Артём Валерьевич
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: artem@math.nsc.ru 

Сафарова Алиса Исламовна
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: a.safarova1@g.nsu.ru 

Статья поступила 11 марта 2026 г.
После доработки — 10 апреля 2026 г.
Принята к публикации 22 апреля 2026 г.

Abstract:

A graph is 3-representable if there exists a 3-uniform word whose letters are the vertices of the graph, and two vertices are adjacent if and only if the corresponding letters alternate in the word. In this paper we provide a computer-aided proof of the fact that the 4-dimensional cube is not 3-representable. 

Illustr. 1, bibliogr. 11.

References:
  1. S. V. Kitaev and A. V. Pyatkin, On representable graphs, J. Autom. Lang. Comb. 13 (1), 45–54 (2008).
     
  2. S. V. Kitaev and A. V. Pyatkin, Word-representable graphs: A survey, Diskretn. Anal. Issled. Oper. 25 (2), 19–53 (2018) [Russian] [J. Appl. Ind. Math. 12 (2), 278–296 (2018)].
     
  3. S. V. Kitaev and V. V. Lozin, Words and Graphs (Springer, Cham, 2015).
     
  4. A. Bouchet, Circle graph obstructions, J. Comb. Theory, Ser. B, 60 (1), 107–144 (1994).
     
  5. S. V. Kitaev, On graphs with representation number 3, J. Autom. Lang. Comb. 18 (2), 97–112 (2013).
     
  6. N. S. Alshammari, S. V. Kitaev, and A. V. Pyatkin, On the representation number of grid graphs and cylindric grid graphs (Ithaca, NY, 2025) (e-Print Archive / Cornell Univ., arXiv:2507.16469), DOI: 10.48550/arXiv.2507.16469.
     
  7. T. Dwary, K. Mozhui, and K. V. Krishna, Representation number of word-representable split graphs (Ithaca, NY, 2025) (e-Print Archive / Cornell Univ., arXiv:2502.00872), DOI: 10.48550/arXiv.2502.00872.
     
  8. B. Broere and H. Zantema, The $k$-dimensional cube is $k$-representable, J. Autom. Lang. Comb. 24 (1), 3–12 (2019).
     
  9. Z. Hefty, P. Horn, C. Muir, and A. Owens, Word-representable graphs: Orientations, posets, and bounds, Electron. J. Comb. 31 (4), ID P4.2 (2024).
     
  10. M. Glen, S. V. Kitaev, and A. V. Pyatkin, On the representation number of a crown graph, Discrete Appl. Math. 244, 89–93 (2018).
     
  11. Z. Hefty, P. Horn, C. Muir, and A. Owens, Word-representation numbers of graphs: Bottlenecks and bounds, J. Comb. Theory, Ser. A, 223, ID 106215 (2026).