Database CF ODLS of order n

Message boards : Science : Database CF ODLS of order n
Message board moderation

To post messages, you must log in.

Previous · 1 · 2 · 3

AuthorMessage
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12851
Credit: 0
RAC: 0
Message 6782 - Posted: 8 Nov 2020, 7:36:19 UTC

Итак, начинаю всё сначала.
Дурная голова черепашке покоя не даёт :)

Берём 1105 КФ ОДЛК 8-го порядка (это полная БД) и находим к ним все ортогональные ДЛК программой Белышева ortogon_u.
Их нашлось 4545. Но! Среди них много одинаковых ДЛК.
Более того, если ДЛК нормализовать, ещё появляются одинаковые ДЛК.
Сразу нормализовала 4545 ДЛК и воспользовалась программой Белышева sos-operate, которая выдала все различные ДЛК.
Их оказалось 3929. Ну вот, теперь всё в порядке и дублей ДЛК нет.

Сейчас объединю эти ДЛК с исходными ДЛК, будет множество из 5034 ДЛК.
В этом множестве с помощью утилиты Harry White найду все ортогональные пары.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6782 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12851
Credit: 0
RAC: 0
Message 6783 - Posted: 8 Nov 2020, 7:43:42 UTC
Last modified: 8 Nov 2020, 7:46:47 UTC

Объединила и проверила полученные ОДЛК утилитой Harry White.
Вот какие квадратики мы имеем

Order? 8

Enter the name of the squares file: inp
.. writing type information to file inpTypeDetail_5.txt

Counts
------
      5034 diagonal Latin
        69 associative
        72 weakly pandiagonal
      2018 axial symmetric
       239 double axial symmetric
       465 center symmetric
      3929 nfr
      1105 natural \diagonal
       147 self-orthogonal

Сейчас найду все ортогональные пары, образуемые квадратами этого множества.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6783 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12851
Credit: 0
RAC: 0
Message 6784 - Posted: 8 Nov 2020, 7:52:06 UTC

Вот
Order? 8

Enter the name of the squares file: inp
..output file inpPairs_5.txt
..output file inpPairNos_5.txt
squares 5034 orthogonal pairs 5855

elapsed time 0:00:04

Теперь всего 5855 ортогональных пар (вместо прежних 16675).
Замечательно!

Итак. у нас новый граф... Толстой :)
В графе 5034 вершины и 5855 рёбер.
Требуется найти все клики максимального размера 6.

Красивая задача, господа!
Жаль, что нет желающих решить.

Да, надо выложить новый граф и новую таблицу ортогональных пар.
Займусь этим.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6784 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12851
Credit: 0
RAC: 0
Message 6785 - Posted: 8 Nov 2020, 13:05:47 UTC
Last modified: 8 Nov 2020, 13:16:20 UTC

Ой, увлеклась поиском клик в новом графе :)
По-прежнему ищу визуально.
Вот клики размера 3

761: 1455 2082
1433: 2062 3030
1453: 2095 2999
1463: 2046 2998
1478: 2043 3051
1481: 3028 3923
1647: 2495 2737

А вот две клики размера 4

761: 1455 2082 3068
1433: 2062 3030 3920

Пятёрка пока не попалась.
Очень интересно искать! Прекрасная головоломка.
Думаю, что шестёрок много не будет.

Конечно, в новом графе работать проще, потому что намного меньше вершин и рёбер.
Следует отметить, что в нашем графе максимальный размер клики равен 6.
В нём не может быть клики размера 7, потому что для ДЛК 8-го порядка максимальный размер группы MODLS равен 6.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6785 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12851
Credit: 0
RAC: 0
Message 6786 - Posted: 8 Nov 2020, 16:22:25 UTC
Last modified: 8 Nov 2020, 16:27:00 UTC

Дальше у меня поиск развивался так:

1453: 2095 3965
1453: 2095 2999 3965
1463: 2046 3968
1463: 2046 2998 3968
761: 1455 4010
761: 1455 2082 4010
761: 1455 2082 3068 4010
2056: 3060 4025
1436: 2061 4088
1436: 2061 3052 4088
1478: 2043 4093
1478: 2043 3051 4093

Закономерность превращения клики размера n в клику размера n+1 уже очень хорошо видна, точно по алгоритму, описанному выше.
Найдена клика размера 5.
Остался один шаг до шестёрки.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6786 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12851
Credit: 0
RAC: 0
Message 6787 - Posted: 8 Nov 2020, 16:33:13 UTC
Last modified: 8 Nov 2020, 16:44:44 UTC

Выложила граф (содержит 5034 ОДЛК 8-го порядка) и таблицу ортогональных пар на Яндекс.Диск
https://yadi.sk/d/FXSKw-Htv9bhYQ

Квадраты пронумерованы в порядке их расположения.
По номерам квадратов легко найти сами квадраты.

Сейчас я найду квадраты, входящие в клику размера 5 и покажу их.
Живые квадраты можно проверить - действительно ли они взаимно ортогональны.

Это клика размера 5
761: 1455 2082 3068 4010

Это соответствующие ОДЛК

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

Утилита Harry White выдаёт следующую таблицу ортогональных пар

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

Всё верно: квадраты взаимно ортогональны.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6787 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12851
Credit: 0
RAC: 0
Message 6788 - Posted: 9 Nov 2020, 6:26:15 UTC

А вот и первая шестёрка, от показанной выше пятёрки произошла, добавилась вершина 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???
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6788 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12851
Credit: 0
RAC: 0
Message 6793 - Posted: 9 Nov 2020, 10:02:32 UTC

Смотрите, как интересно формировалась клика размера 6; проверяется вершина 4996

761:1455 4996
761: 1455 2082 4996
761: 1455 2082 3068 4996
761: 1455 2082 3068 4010 4996

Нашла ещё три клики размера 5

1436: 2061 3052 4088 5012
1453: 2095 2999 3965 5031
1478: 2043 3051 4093 4995

А вот клика размера 6 больше не попалась. Вполне возможно, что пропустила, это же визуальная проверка.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6793 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12851
Credit: 0
RAC: 0
Message 6823 - Posted: 13 Nov 2020, 7:53:14 UTC

Поискала вторую клику размера 6 визуально, не нашла.
А может, её и нет? :)
Трудно искать чёрную кошку в тёмной комнате, особенно если её там нет.

Родилось ещё одно рацпредложение.
Мне кажется (хотя обосновать не могу), что одна из вершин клики размера 6 обязательно будет среди 1105 ОДЛК, которые есть полная БД ОДЛК 8-го порядка.
Найденная мной клика размера 6 подтверждает это.
Следовательно, можно составить все ортогональные пары во множестве ОДЛК, найденных к 1105 базовым квадратам, и в полученном графе искать клику размера 5.
Сейчас реализую это рацпредложение.
Множество ОДЛК к базовым квадратам содержит 4545 ДЛК, после нормализации осталось 3929 ДЛК.
Отлично. Сейчас составлю таблицу ортогональных пар для этой группы ОДЛК и буду искать клики размера 5.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6823 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12851
Credit: 0
RAC: 0
Message 6824 - Posted: 13 Nov 2020, 8:04:28 UTC

Утилита Harry White выдала
Order? 8

Enter the name of the squares file: inp1
..output file inp1Pairs_2.txt
..output file inp1PairNos_2.txt
squares 3929 orthogonal pairs 1310

Всего 1310 ортогональных пар. Вот какой маленький граф: 3929 вершин и 1310 рёбер.

Найдётся ли в этом графе клика размера 5?
Думаю, что должна найтись, если мои рассуждения верные.
При этом все вершины клики размера 5 должны иметь связь (отношение ортогональности) с одной и той же вершиной из 1105 базовых квадратов.
Тогда мы будем иметь искомую клику размера 6.

Ушла искать клику :)
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6824 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12851
Credit: 0
RAC: 0
Message 6825 - Posted: 13 Nov 2020, 13:33:13 UTC

Вот первая клика размера 5, найденная в новом графе
350: 977 1963 2905 3891


350
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

977
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

1963
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

2905
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

3891
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

Эта клика в точности соответствует клике размера 6, найденной в предыдущем графе, сравните с этой кликой, она показана здесь
https://boinc.progger.info/odlk/forum_thread.php?id=173&postid=6788

Однако... я нашла ещё одну клику размера 5 в урезанном графе
373: 938 1946 2988 3890

Сейчас проверю её.
Главное: найти вершину в базовых квадратах, с которой эта клика связана.
Есть ли такая вершина? Надеюсь, что есть.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6825 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12851
Credit: 0
RAC: 0
Message 6826 - Posted: 13 Nov 2020, 13:44:24 UTC
Last modified: 13 Nov 2020, 13:58:41 UTC

Пока не проверила, но заполз червь сомнения...
Эта клика размера 5 была найдена в предыдущем графе
1478: 2043 3051 4093 4995

Соответствие абсолютно точное; прибавьте 1105 к каждой вершине этой клики
373: 938 1946 2988 3890

и вы получите показанную выше клику.

Ну вот поэтому и червь сомнения заполз. Эта клика, скорее всего, не имеет связи ни с какой вершиной из 1105 базовых квадратов.
Но чтобы убедиться, сейчас проверю.

Всё, сомнений не осталось: нет такого базового квадрата из БД, который был бы ортогонален всем пяти вершинам этой клики размера 5.
Увы!

Итак, пока клика размера 6 у меня одна.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6826 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12851
Credit: 0
RAC: 0
Message 6886 - Posted: 24 Nov 2020, 18:20:01 UTC - in response to Message 6713.  
Last modified: 24 Nov 2020, 18:27:30 UTC

В OEIS есть последовательность
https://oeis.org/A330391
Цитирую
Number of main classes of diagonal Latin squares of order n with at least one orthogonal diagonal mate.
1, 0, 0, 1, 1, 0, 5, 1105

Можно пока сказать, что a(9)>53844.

PS. Уже найдено ещё несколько КФ ОДЛК, поэтому неравенство строгое.

В данный момент БД КФ ОДЛК порядка 9 содержит уже больше 56171 КФ ОДЛК.
Поэтому можем изменить нижнюю границу: a(9)>56171.
Предварительная БД, состоящая из 56171 КФ ОДЛК, опубликована здесь
https://yadi.sk/d/XC4QkgXx9pdsEQ

Мы продолжаем работать над составлением полной БД КФ ОДЛК порядка 9.
Подробности смотрите в теме
https://boinc.progger.info/odlk/forum_thread.php?id=44
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6886 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Previous · 1 · 2 · 3

Message boards : Science : Database CF ODLS of order n


©2024 (C) Progger