r-aa (r_aa) wrote,
r-aa
r_aa

Category:

Поиск циркулярных предрамсеевских графов


В этом посте я хочу привести некоторые красно-синие реберные раскраски полных графов, связанные с числами Рамсея.

Напомню:
Число Рамсея R(r, b) - это наименьшее натуральное число n такое, что при любой красно-синей реберной раскраске полного графа порядка n, в нем найдется красная клика порядка r, либо синяя клика порядка b.

Рассмотрим числа Рамсея для 3 ≤ r ≤ 5, 3 ≤ b ≤ 5. Известно, что R(3, 3) = 6, R(3, 4) = 9, R(3, 5) = 14, R(4, 4) = 18, R(4, 5) = 25, 43 ≤ R(5, 5) ≤ 49.

Меня интересуют полные графы порядка меньше R(r, b) с красно-синей реберной раскраской, которые не содержат ни красных клик порядка r, ни синих клик порядка b. Если порядок такого графа равен R(r, b) - 1, то я называю этот граф предрамсеевским.

Интересно существование предрамсеевских графов в классе циркулярных графов (точнее циркулярными являются графы, содержащие только красные и только синии ребра рассматриваемого графа), так как такие графы обладают определенной простотой, симметрией и наглядностью.

В результате перебора всех циркулярных графов для чисел R(3, 3), R(3, 4), R(3, 5), R(4, 4), R(4, 5) в этом классе оказался предрамсеевский граф. Ниже они приведены:


Предрамсеевский циркулярный граф для R(3, 3):

Предрамсеевский циркулярный граф для R(3, 4):

Предрамсеевский циркулярный граф для R(3, 5):

Предрамсеевский циркулярный граф для R(4, 4):

Предрамсеевский циркулярный граф для R(4, 5):

А вот с R(5, 5) вышла неудача - циркулярного предрамсеевского графа для него не существует. Нашелся только полный граф порядка 41 без красных 5-клик и синих 5-клик:

В заключение приведу график количества раскрасок полных графов без красных r-клик и синих b-клик в зависимости от порядка графа для чисел Рамсея R(3, 3), R(3, 4), R(3, 5), R(4, 4), R(4, 5), R(5, 5). Количество раскрасок приведено без учета изоморфизма.


P.S.
А предрамсеевский граф для R(5, 5) придется искать в другом классе графов...
Tags: математика, теория графов, числа Рамсея
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments