И снова задача о клике!

Запостила уже задачу на форуме Math Help Plfnet
http://mathhelpplanet.com/viewtopic.php?f=62&t=72879

Ну, там вряд ли будут решать. Так, на всякий случай запостила.
Дальше подробно расскажу, как я получила граф, который уже сидит на Яндекс.Диске
https://yadi.sk/d/ZIddJfJEzueXKg
Это маленький текстовый файл.
Граф у меня хороший :)
он имеет 1088 вершин и 345 рёбер.

Требуется найти клику максимального размера.
Предполагается, что это будет клика размера 6.
А вдруг найдётся клика размера 7.
Это будет опровержение моей гипотезы, которая записана в статье OEIS https://oeis.org/A328873
Цитирую

Conjecture: a(9) = 6. Natalia Makarova, Dec 24 2020

Добавлю, что задача о клике описана в Википедии
https://ru.wikipedia.org/wiki/Задача_о_клике
а также в английской Википедии
https://en.wikipedia.org/wiki/Clique_problem
Известен алгоритм поиска клики максимального размера. Даже и программа, кажется, написана кем-то.

Что такое мой граф?
Это множество ортогональных ДЛК, которые представляют собой вершины графа.
ДЛК связаны отношением ортогональности; если два ДЛК образуют ортогональную пару (то есть ортогональны друг другу), они соединяются ребром графа.

Граф представляет собой не что иное как таблицу ортогональности ДЛК данного множества.
Покажу начало таблицы ортогональности

2:  1
3:  1 2
4:  1 2 3
5:  1 2 3 4
6:  1 2 3 4 5
9:  2
214:  4 155 174
269:  120
272:  120
311:  246
317:  5
318:  5
319:  5
320:  5
342:  9 155
. . . . . 

Например. запись
6: 1 2 3 4 5
означает, что ДЛК №6 ортогонален ДЛК №№ 1, 2, 3, 4, 5.
Значит, вершина 6 соединена с вершинами 1, 2, 3, 4, 5.
Все ДЛК №№ 1, 2, 3, 4, 5 тоже взаимно ортогональны.
Очевидно, что это первая клика размера 6.
Есть ли другие клики размера 6?
А главный вопрос: есть ли клика размера 7?

Теперь расскажу, как я получила множество ДЛК, представленное в графе.
Взяла известную группу MODLS 9-го порядка, состоящую из 6 взаимно ортогональных ДЛК, вот она

0 1 2 3 4 5 6 7 8
3 4 5 6 7 8 0 1 2
6 7 8 0 1 2 3 4 5
7 8 6 1 2 0 4 5 3
1 2 0 4 5 3 7 8 6
4 5 3 7 8 6 1 2 0
5 3 4 8 6 7 2 0 1
8 6 7 2 0 1 5 3 4
2 0 1 5 3 4 8 6 7

0 1 2 3 4 5 6 7 8
4 5 3 7 8 6 1 2 0
8 6 7 2 0 1 5 3 4
1 2 0 4 5 3 7 8 6
5 3 4 8 6 7 2 0 1
6 7 8 0 1 2 3 4 5
2 0 1 5 3 4 8 6 7
3 4 5 6 7 8 0 1 2
7 8 6 1 2 0 4 5 3

0 1 2 3 4 5 6 7 8
5 3 4 8 6 7 2 0 1
7 8 6 1 2 0 4 5 3
4 5 3 7 8 6 1 2 0
6 7 8 0 1 2 3 4 5
2 0 1 5 3 4 8 6 7
8 6 7 2 0 1 5 3 4
1 2 0 4 5 3 7 8 6
3 4 5 6 7 8 0 1 2

0 1 2 3 4 5 6 7 8
6 7 8 0 1 2 3 4 5
3 4 5 6 7 8 0 1 2
5 3 4 8 6 7 2 0 1
2 0 1 5 3 4 8 6 7
8 6 7 2 0 1 5 3 4
7 8 6 1 2 0 4 5 3
4 5 3 7 8 6 1 2 0
1 2 0 4 5 3 7 8 6

0 1 2 3 4 5 6 7 8
7 8 6 1 2 0 4 5 3
5 3 4 8 6 7 2 0 1
8 6 7 2 0 1 5 3 4
3 4 5 6 7 8 0 1 2
1 2 0 4 5 3 7 8 6
4 5 3 7 8 6 1 2 0
2 0 1 5 3 4 8 6 7
6 7 8 0 1 2 3 4 5

0 1 2 3 4 5 6 7 8
8 6 7 2 0 1 5 3 4
4 5 3 7 8 6 1 2 0
2 0 1 5 3 4 8 6 7
7 8 6 1 2 0 4 5 3
3 4 5 6 7 8 0 1 2
1 2 0 4 5 3 7 8 6
6 7 8 0 1 2 3 4 5
5 3 4 8 6 7 2 0 1

и нашла максимальное расширение этой группы.
Ну, если не ошиблась, конечно.
Получила группу из 1088 ОДЛК, включая 6 исходных ДЛК.
Первые 6 исходных ДЛК расположены в начале списка ДЛК. Вот они и образуют первую клику размера 6, о которой я уже сказала выше.

Теперь найдите, пожалуйста, другие клики максимального размера в данном графе.
Ну, клики размера 6, если они ещё есть, не столь интересны.
Понятно, что интересна клика размера 7.
Но такой клики, согласно моей гипотезе, не существует.
Опровергнем гипотезу?

С ходу нашла клику размера 4, визуальным просмотром таблицы ортогональности
198, 489, 535, 922
Ну, это мало интересно.

Вообще-то, надо замесить эксперимент покруче.
Только пироги печь всё равно никто не будет :)

В BOINC-проектах найден полный набор КФ ОДЛК 9-го порядка.
Находим все ОДЛК к этим КФ, нормализуем их, выбрасываем дубликаты.
Вот вам и множество ОДЛК, в котором надо искать клику максимального размера.
Но эта задача вряд ли решабельна на одном ПК.

Так что, ни доказать, ни опровергнуть мою гипотезу пока не получается.
А я уверена в том, что она верная!
Моё доказательство на основе анализа всех полных систем MOLS 9-го порядка не отменяется!

У нас БД КФ ОДЛК 9-го порядка в данный момент содержит 59997 КФ ОДЛК.
В полной БД 75 тысяч с хвостиком КФ ОДЛК.
Сейчас покажу, сколько ОДЛК имеют все КФ нашей БД.

Вот хвост выходного файла программы Белышева ortogon_u

. . . . . . . . 
[DLK(4):272592]
0 8 7 6 3 2 5 4 1
4 1 5 8 6 3 7 0 2
7 6 2 5 8 0 3 1 4
8 7 4 3 0 6 1 2 5
6 5 1 2 4 8 0 3 7
2 3 0 7 1 5 4 8 6
1 4 8 0 2 7 6 5 3
3 2 6 1 5 4 8 7 0
5 0 3 4 7 1 2 6 8

[DLK(2):272596]
0 8 7 6 3 2 5 4 1
4 1 5 8 6 3 7 0 2
7 6 2 5 8 0 3 1 4
8 7 4 3 1 6 0 2 5
3 5 0 2 4 8 1 6 7
2 3 1 7 0 5 4 8 6
1 4 8 0 2 7 6 5 3
6 2 3 1 5 4 8 7 0
5 0 6 4 7 1 2 3 8

[DLK(4):272598]
0 8 7 6 3 2 5 4 1
4 1 5 8 6 3 7 0 2
7 6 2 5 8 0 3 1 4
8 7 4 3 1 6 0 2 5
6 5 0 2 4 8 1 3 7
2 3 1 7 0 5 4 8 6
1 4 8 0 2 7 6 5 3
3 2 6 1 5 4 8 7 0
5 0 3 4 7 1 2 6 8

272598 ортогональных диагональных соквадратов! Не хило.
Конечно, после нормализации часть квадратов удалится. Однако всё равно очень много.
Да к ним нужно ещё добавить все исходные КФ.

О-о-о!
На форуме Math Help Planet пришёл ответ

Программа SageMath говорит, что [1, 2, 3, 4, 5, 6] — единственная клика размера 6, а клик бóльшего размера нет.

http://mathhelpplanet.com/viewtopic.php?p=409566#p409566

Ну, решение ожидаемое, так и должно быть.
Осталось замесить эксперимент покруче :)

Да, программа указана. Где её можно раздобыть?
И как ею пользоваться?

На форуме Math Help Planet дали ссылку на программу, а также на Введение (на русском языке).

Ссылка на программу SageMath
https://www.sagemath.org

Ссылка на Введение
https://doc.sagemath.org/html/ru/tutorial/index.html

Установщик программы скачала, но ещё не устанавливала.
Введение чуть-чуть посмотрела, одним глазком :)

Господа!
Пожалуйста, попробуйте тоже эту программу, кто ещё не пользуется ею.
Это должно быть интересно и полезно.
Заодно мне поможете, если у меня что-то не пойдёт.
Я скачала самую последнюю версию (от 5 января т. г.).
Вот сейчас у меня программы закончат работать, попробую установить.

Ой, как интересно!
Во Ведении вычитала про этот режим
http://sagecell.sagemath.org
Там написано, что для работы в этом режиме можно и не устанавливать программу SageMath.
Я попробовала сейчас. Вот что у меня получилось



Это максимальная клика размера 6 в моём графе.
Просто задала её вручную (первые шесть вершин графа, которые и образуют эту клику).
Даже картинку программа нарисовала :) Ай-да молодец!

Господа!
Актуальный, животрепещущий вопрос!
Как в этом режиме запустить программку из файла?
Или как взять граф, записанный в текстовый файл?

На форуме Math Help Planet форумчанин дал код программки для моей задачи.
Вот этот код надо записать в текстовый файл, а потом запустить программу Sage из этого файла.
В PARI/GP, например, так делается.

Подключила второй уровень. Получила граф, в котором больше 18 тысяч вершин.
Пока ввожу их вручную, по тысяче.
Ввела уже 13 тысяч вершин.
Программа выдаёт какую-то ошибку, но клики вычисляет :)
Вот нашла клики размера 5, пять штук

[[2795, 12289, 3797, 7668, 8418],
[2924, 10300, 12771, 4228, 7611],
[10355, 12293, 990, 4702, 7728],
[11080, 12271, 992, 7741, 9559],
[11614, 12281, 4157, 7974, 8935]]

Отлично!
Программа работает замечательно! Несколько секунд и все клики найдены.
Интересно, возьмёт ли программа все 18 с хвостиком вершин?
На очереди максимальная клика размера 6.
Клику размера 7 я не ожидаю, её не может быть согласно моей гипотезе.

Тему на форуме Math Help Planet смотрите, я там тоже пишу
http://mathhelpplanet.com/viewtopic.php?f=62&t=72879

Добавила ещё тысячу вершин, нашлись следующие клики размера 5

[[927, 10678, 4619, 7906, 13447],
 [1045, 4432, 7107, 10204, 13934],
 [2795, 12289, 3797, 7668, 8418],
 [2924, 10300, 12771, 4228, 7611],
 [4394, 7424, 8632, 9992, 13655],
 [5206, 10774, 2174, 4605, 13717],
 [5206, 10799, 2169, 4596, 13717],
 [5546, 10852, 2146, 9498, 13797],
 [5589, 10852, 2133, 9512, 13785],
 [5601, 10859, 2133, 9502, 13785],
 [5782, 2065, 4544, 9069, 13930],
 [10355, 12293, 990, 4702, 7728],
 [11080, 12271, 992, 7741, 9559],
 [11614, 12281, 4157, 7974, 8935]]

Максимальной клики размера 6 пока нет.
Должна быть!

Ещё добавила тысячу вершин, нашлись опять только клики размера 5, но их теперь больше

[[927, 10678, 4619, 7906, 13447],
 [952, 4187, 5089, 9516, 14287],
 [1045, 4432, 7107, 10204, 13934],
 [1280, 7153, 9397, 10154, 14064],
 [1280, 7171, 9397, 10145, 14071],
 [1303, 7133, 9403, 10154, 14008],
 [1303, 7171, 9415, 10122, 14008],
 [1355, 7133, 9403, 10145, 14071],
 [1355, 7153, 9415, 10122, 14064],
 [1430, 6534, 11662, 8409, 14954],
 [1670, 6226, 4652, 10211, 14771],
 [1708, 3347, 10679, 7397, 14372],
 [2561, 5838, 4139, 8754, 14311],
 [2561, 5856, 4125, 8754, 14320],
 [2795, 12289, 3797, 7668, 8418],
 [2924, 10300, 4228, 7611, 12771],
 [4394, 7424, 8632, 9992, 13655],
 [5206, 10774, 2174, 4605, 13717],
 [5206, 10799, 2169, 4596, 13717],
 [5546, 10852, 2146, 9498, 13797],
 [5589, 10852, 2133, 9512, 13785],
 [5601, 10859, 2133, 9502, 13785],
 [5782, 2065, 4544, 9069, 13930],
 [5838, 2543, 4130, 8811, 14300],
 [5856, 2543, 4130, 8784, 14320],
 [6012, 11604, 4078, 9023, 14977],
 [6034, 11604, 4078, 8994, 14940],
 [6422, 2330, 3428, 8597, 14424],
 [6422, 2334, 3390, 8613, 14442],
 [6470, 2334, 3390, 8583, 14460],
 [6778, 10504, 2387, 8623, 14319],
 [10355, 12293, 990, 4702, 7728],
 [10584, 4651, 7299, 8625, 14696],
 [11080, 12271, 992, 7741, 9559],
 [11614, 12281, 4157, 7974, 8935]]

Фантастика! Уже введено 15 тысяч вершин, которые соединены N рёбрами.
Программа пока работает, правда, выдаёт какие-то ошибки.
Может быть, работает некорректно, но клики выдаёт!
Возможно, и не все выдаёт из-за ошибок.

Введено 16 тысяч вершин!
Появились клики размера 6

[[2330, 3428, 6422, 8597, 14424, 15625],
 [2334, 3390, 6422, 8613, 14442, 15625],
 [2334, 3390, 6470, 8583, 14460, 15611],
 [2561, 5838, 4139, 8754, 14311, 15405],
 [2561, 5856, 4125, 8754, 14320, 15380],
 [2924, 10300, 4228, 7611, 12771, 15255],
 [5206, 10774, 2174, 4605, 13717, 15868],
 [5206, 10799, 2169, 4596, 13717, 15857],
 [5838, 2543, 4130, 8811, 14300, 15405],
 [5856, 2543, 4130, 8784, 14320, 15355],
 [10504, 2387, 6778, 8623, 14319, 15266],
 [11614, 4157, 7974, 8935, 12281, 15906]]

Супер!
Ну, клику 7 я не ожидаю, её не может быть согласно моей гипотезе.
Однако осталось ввести 2 тысячи с хвостиком вершин.
Можно для чистоты эксперимента попробовать добить до конца этот граф.
Не лопнет ли программа? :)

PS. Да, вот оно расширение. Разумеется, расширение возможно.
И в расширении несколько клик размера 6 найдено.
И это ещё не предел! Можно перейти на следующий уровень расширения.
Получится огромное множество ОДЛК.
И в этом множестве тоже поискать клику размера 7.
Только напрасный труд! Нет такой клики для ОДЛК 9-го порядка.

Введено 17000 вершин!
Найдены следующие клики размера 6

[[952, 4187, 5089, 9516, 14287, 16206],
 [1045, 4432, 7107, 10204, 13934, 16086],
 [1670, 4652, 6226, 10211, 14771, 16514],
 [2330, 3428, 6422, 8597, 14424, 15625],
 [2334, 3390, 6422, 8613, 14442, 15625],
 [2334, 3390, 6470, 8583, 14460, 15611],
 [2561, 5838, 4139, 8754, 14311, 15405],
 [2561, 5856, 4125, 8754, 14320, 15380],
 [2924, 10300, 4228, 7611, 12771, 15255],
 [4157, 7974, 8935, 11614, 12281, 15906],
 [5206, 10774, 2174, 4605, 13717, 15868],
 [5206, 10799, 2169, 4596, 13717, 15857],
 [5782, 2065, 4544, 9069, 13930, 16205],
 [5838, 2543, 4130, 8811, 14300, 15405],
 [5856, 2543, 4130, 8784, 14320, 15355],
 [10504, 2387, 6778, 8623, 14319, 15266],
 [10679, 1708, 3347, 7397, 14372, 16183],
 [11080, 992, 7741, 9559, 12271, 16188]]

Осталось чуть-чуть.

Всё! Затолкала все вершины - 18291 штук. И программа не лопнула :)
Найдены следующие клики размера 6

[[927, 4619, 7906, 10678, 13447, 17465],
 [952, 4187, 5089, 9516, 14287, 16206],
 [992, 7741, 9559, 11080, 12271, 16188],
 [1045, 4432, 7107, 10204, 13934, 16086],
 [1202, 3988, 6119, 11640, 15067, 18175],
 [1280, 7153, 9397, 10154, 14064, 17316],
 [1280, 7171, 9397, 10145, 14071, 17292],
 [1303, 7133, 9403, 10154, 14008, 17316],
 [1303, 7171, 9415, 10122, 14008, 17292],
 [1355, 7133, 9403, 10145, 14071, 17244],
 [1355, 7153, 9415, 10122, 14064, 17244],
 [1430, 6534, 8409, 11662, 14954, 18139],
 [1670, 4652, 6226, 10211, 14771, 16514],
 [1708, 3347, 7397, 10679, 14372, 16183],
 [2065, 4544, 5782, 9069, 13930, 16205],
 [2133, 5589, 9512, 10852, 13785, 17109],
 [2133, 5601, 9502, 10859, 13785, 17108],
 [2146, 5546, 9498, 10852, 13797, 17109],
 [2330, 3428, 6422, 8597, 14424, 15625],
 [2334, 3390, 6422, 8613, 14442, 15625],
 [2334, 3390, 6470, 8583, 14460, 15611],
 [2543, 4130, 5838, 8811, 14300, 15405],
 [2543, 4130, 5856, 8784, 14320, 15355],
 [2561, 4125, 5856, 8754, 14320, 15380],
 [2561, 4139, 5838, 8754, 14311, 15405],
 [2795, 3797, 7668, 8418, 12289, 17198],
 [3328, 7005, 8526, 11295, 15118, 17061],
 [3674, 6661, 8531, 11388, 15051, 18039],
 [3674, 6677, 8518, 11388, 15062, 18026],
 [3686, 6632, 8531, 11404, 15047, 18039],
 [3686, 6677, 8510, 11431, 15047, 18026],
 [3716, 6632, 8518, 11404, 15062, 17997],
 [3716, 6661, 8510, 11431, 15051, 17997],
 [4078, 6012, 9023, 11604, 14977, 17864],
 [4078, 6034, 8994, 11604, 14940, 17866],
 [4157, 7974, 8935, 11614, 12281, 15906],
 [4394, 7424, 8632, 9992, 13655, 17499],
 [4651, 7299, 8625, 10584, 14696, 17421],
 [5206, 2169, 4596, 10799, 13717, 15857],
 [5206, 2174, 4605, 10774, 13717, 15868],
 [10300, 2924, 4228, 7611, 12771, 15255],
 [10355, 990, 4702, 7728, 12293, 17160],
 [10367, 3257, 7656, 8912, 15162, 17546],
 [10504, 2387, 6778, 8623, 14319, 15266]]

Их стало больше.
Клики размера 7 в данном расширении группы MODLS 9-го порядка нет
(если, конечно, программа всё правильно посчитала).
Это ещё раз подтверждает мою гипотезу.

Ну, я думаю, не пройдёт и года, как господин Ватутин найдёт группу MODLS порядка 9, состоящую из 7 взаимно ортогональных ДЛК.
Я такую группу больше искать не буду, потому что уверна, что такая группа не существует.

А как хорошо я с программой SageMath познакомилась. Классная программа!
У меня ещё задачка была о клике для ОДЛК 8-го порядка. Только форум проекта ОДЛК сейчас недоступен, и данные о задаче взять негде.

Нашла у себя в компьютере граф, который делала для ОДЛК 8-го порядка.
Я его выкладывала в теме на форуме проекта ОДЛК (можно на Яндекс.Диске и ссылку взять).
В графе 5034 вершины.
Граф, понятно, представлен таблицей ортогональности заданного множества ОДЛК, состоящего из 5034 квадратов.

Сейчас ввела этот граф в программу SageMath, вот "хвостик" видно

. . . . . . 
5032: [762,1453,3028],
5033: [757],
5034: [714,1433,1453,1481,1499,1537,1609,1634,1807,1874,
1925,2016,2082,2191,2247,2874,2998,3028,3118,3349,
3466,3549,3679,3745,3755,3923,3953,4057,4088],}
sage: g = Graph(d)
sage: g.cliques_maximum()

Программа мгновенно выдала единственную (!) клику размера 6

[761, 1455, 2082, 3068, 4010, 4996]

что и требовалось доказать.

Я искала эту клику вручную (визуально), и нашла её.
Но не была уверена в том, что других клик размера 6 нет.
Теперь это подтверждено программой.

Проект ОДЛК вернулся!
Дублирую сообщение о клике, о которой сказано в предыдущем посте

А вот и первая шестёрка, от показанной выше пятёрки произошла, добавилась вершина 4996

761: 1455 2082 3068 4010 4996

761
0 2 5 7 6 4 3 1
3 1 6 4 5 7 0 2
7 5 2 0 1 3 4 6
4 6 1 3 2 0 7 5
2 0 7 5 4 6 1 3
1 3 4 6 7 5 2 0
5 7 0 2 3 1 6 4
6 4 3 1 0 2 5 7

1455
0 1 2 3 4 5 6 7
2 3 0 1 6 7 4 5
5 4 7 6 1 0 3 2
7 6 5 4 3 2 1 0
6 7 4 5 2 3 0 1
4 5 6 7 0 1 2 3
3 2 1 0 7 6 5 4
1 0 3 2 5 4 7 6

2082
0 1 2 3 4 5 6 7
3 2 1 0 7 6 5 4
7 6 5 4 3 2 1 0
4 5 6 7 0 1 2 3
2 3 0 1 6 7 4 5
1 0 3 2 5 4 7 6
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1

3068
0 1 2 3 4 5 6 7
4 5 6 7 0 1 2 3
6 7 4 5 2 3 0 1
2 3 0 1 6 7 4 5
7 6 5 4 3 2 1 0
3 2 1 0 7 6 5 4
1 0 3 2 5 4 7 6
5 4 7 6 1 0 3 2

4010
0 1 2 3 4 5 6 7
5 4 7 6 1 0 3 2
4 5 6 7 0 1 2 3
1 0 3 2 5 4 7 6
3 2 1 0 7 6 5 4
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0
2 3 0 1 6 7 4 5

4996
0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0
1 0 3 2 5 4 7 6
6 7 4 5 2 3 0 1
5 4 7 6 1 0 3 2
2 3 0 1 6 7 4 5
4 5 6 7 0 1 2 3
3 2 1 0 7 6 5 4

Проверила взаимную ортогональность утилитой Harry White

2:  1
3:  1 2
4:  1 2 3
5:  1 2 3 4
6:  1 2 3 4 5

Всё правильно.

Остался последний вопрос: есть ли ещё клики размера 6???

Да! Она та же самая, что найдена программой SageMath!
Как быстро её можно было найти, а я визуально искала долго.

И на главный вопрос ответ программа дала: есть только одна клика размера 6 в этом графе.