Новые нижние границы для чисел Рамсея | ||
Написано 31-03-2016 в 15:56 | ||
|
||
Здесь представлены результаты проводимых мною поисков максимальных рамсеевых графов для чисел Рамсея вида R(3, n) при помощи эвристических алгоритмов. На текущий момент удалось получить 4 новых нижних оценки чисел Рамсея: R(3, 12) ≥ 53, R(3, 13) ≥ 60, R(3, 14) ≥ 67, R(3, 15) ≥ 74. Обзор достижений в этой области на январь 2014 г. можно посмотреть в Stanisław Radziszowski, Small Ramsey Numbers ( http://www.combinatorics.org/ojs/index.p...ew/DS1/pdf ). Неориентированный полный граф с рёбрами, раскрашенными в цвета 0 и 1, и с A вершинами служит доказазательством R(3, n) ≥ A+1, если в нём нет 3-х вершин, попарно связанных рёбрами цвета 1, и n вершин, попарно связанных рёбрами цвета 0. R(3, 12) Всего получено более 100 попарно неизоморфных R(3, 12; 52)-графов, некоторые из которых имеют нетривиальный автоморфизм. Матрица смежности одного из найденных R(3, 12; 52)-графов: 0000011001000010010000000000100100000001100100000100 0000001101000010110010000000010000100000000001000001 0000000001000000000000100010101000100011100010000010 0000001100001010000001010100000000100000010000000010 0000000001001000100000000010110001101000000011000000 1000000000000000001101000010000010110010010010000000 1101000000000001001100001010000000000010000010100000 0101000000000001000000000010100100000001000000101100 0000000000011001110100100000000110000100000000010000 1110100000010100000001000000000010010000011000000000 0000000000011010100101000100000100001000000000100010 0000000011100000001000010010000000100001000011000100 0001100010100000000010000001001000010001000100001000 0000000001000000100010000110010000100000000101011000 1101000000100000000000100010000011000100000000011000 0000001110000000000000000001001001111000010100000000 0100100010100100001000010000000000000000111000000100 1100000010000000000001010110000000001000000000101010 0000011000010000100000100000101100000000000000001011 0000011010100000000000010000110000000000001000001001 0100000000001100000000000000100101001000110010000100 0001010001100000010000101000000001000000100100010000 0010000010000010001001000101000000001000000001100100 0001000000010000110100000001001101010000000100000000 0000001000000000000001000000100110110001010000001100 0001000000100100010000100000101001010000000010000001 0010111100010110010000000000000000000000001000000001 0000000000001001000000110000110010000010001000010010 1010100100000000001110001101000000000100000000000000 0100100000000100000100000001000100000101110000000100 0010000000001001001000010100000010000100000001010100 1000000110100000001010011000010000000010001000000000 0000010011000010000000001001001000001000100100100000 0000100000000011000011010100000000000011000000100010 0111110000010101000000001000000000000000001000100000 0000010001001001000000011100000000000100100000000010 0000100000100001010010100000000010000101000000010000 0000000010000010000000000000111000011010001100100000 0010011000000000000000000001000101000100000001001101 1010000100011000000000001000010001001000001000000001 1010000000000000100011000000010010010000000001001001 0001010001000001100010001000010000000000000001100001 0000000001000000100100000011000100100101000011000000 1000000000001101000001010000000010000100000010000011 0010111000010000000010000100000000000000001100011000 0100100000010100000000100000001000000010111000000010 0000001100100000010000100000000011100100010000010000 0000000010000110000001000001001000001000000010100001 0000000100001110011100001000000000000010100010000000 1000000100010000100010101000011000000010000000000010 0011000000100000011000000001000001010000000101000100 0100000000000000001100000110000000000011110100010000 R(3, 13) Матрица смежности одного из найденных R(3, 13; 59)-графов: 00000000000000000001100001100000000100110100000100001000010 00100000000000000010010000010000011000010010001000100000011 01010101100000011000001010000000000010100000000000001000000 00100000000010100010000000010010010000001001010000000000011 00000010001000010000000000010000000001000000010100000010111 00100000000100000001000000000000100000010101000001110100100 00001000110100100000010010000010000100001001000010000000000 00100000001100100000000001101000000000000001000000110101000 00100010000001000010000101000100110000000010000000000000011 00000010000011000001001000001000110000010000100100001000000 00001001000001001010100000000011001000010000100000000000000 00000111000000001010000000010001000011000000010000001000010 00010000010000000000110000100001000101000110000010010000000 00000000111000000000010000110000000010001101000001100000000 00010011000000000101000000000000100000010110001001000000100 00101000000000000111010000000001010100000010000010000001000 00100000001100000000010000000000010100000010000110010010100 00000000000000110000000011101000000001000001000100001000001 01010000101100010000001000000000000000100000000100010010100 10000100010000110000000110000010001001000000000000000010001 10000000001010000000001010001000110010000001000001100000000 01000010000011011000000101000100100000100000000000000100000 00100000010000000010100000100100000000001100001000000100011 00000000100000000001010000110000000000011000101101001000000 00100010000000000101100000010001000000000000010000010101010 10000001100000000100010000010010000000001000110001000000100 10000001000011000100001100000010110000000000010000000000100 01011000000101000000000111000100100100000000000010000000000 00000001010000000100100000000110000100101100000000000000110 00000000100000000000011000011001001001010000000000110000000 00010010001000000001000001101000000010000010001000100001000 00000000001110010000000010000100000000001000001100000010101 00000100110000100000110000110000001000001000000000000011000 01010000110000011000100000100000000000100100000000000100000 01000000001000000001000000000100100000000101010111001000000 10000010000010011000000000011000000000000000110001000100001 00100000000101000000100000000010000000000000100100010110100 00001000000110000101000000000100000000101000001000000101000 10100000000000000010010000001000010001000010100011000000001 11000100011000100000000100000100000000000000010010000011000 00010010000001000000001101001001100001000010000000010000000 10000100000011100000001000001000011000000000100000000011000 01000000100010111000000000000010000000101001010000000100000 00010111000001000100100000000000001000000010101000000010000 00000000011000000000000101000000000110100101000000100000010 00011000000100000000000011100000001100010010001000100000000 01000000000000100000001100000011000001000001010010010000000 10001000010000001110000100000001001010000000000000100000000 00000010000010011000000000010000001000110000001000100100010 00000100000001100000100101000000001100100000000000000011010 01000101000001000000100000000110000000000000110110001000000 00000101000010001010000010000100000010001000001000001000001 10100000010100000100000100000000001000000000000000110110100 00000101000000000000011010000000010111000010000010001000000 00001000000000001011000000000001100010010101000001001000000 00000001000000010000000010000010100001010100000001000000101 00001100000000101010000001101001000010000000000000001001000 11011000100100000000001010001000000000000000100011000000000 01011000100000000101001000000001000100100000000000010001000 R(3, 14) Матрица смежности одного из найденных R(3, 14; 66)-графов: 000001001010000010100000000000001000001000000100000000000010010101 000111100000000000000100010001000110010000000000000000000000010010 000000100000001000000100000010000101101001000000000000001100010010 010000000100100000001000001010100001001000000000000110001000000001 010000010100110000010000000000100001001000000000000000001100001100 110000000000110000000010000100110001000000001000000000010001000000 011000000000000000100000100000001000000110000100000101010000000101 000010000000000000100100000000011000000001010100100101010001000000 100000000000001100000010011100000000010010000010000000011000000000 000110000010001001000000010000001000000011110000000000100001000000 100000000100000000000010000011110000100100001000000010010000000010 000000000000100000100000110010000000001001010000001000001100100010 000111000001001000000001000001000000110100000101100000000000000000 000011000000000000001001101010000100010000000000000110000000000001 001000001100100000100000100000010010000000001000001010000000100000 000000001000000001000001100010001100001001101000000000100100000000 100000000000000000000011100110010100010001001000000000010100000000 000000000100000100000000000000010000110100000000010011001010000010 100000110001001000001001000000000001100000000001010000100000001000 000010000000000000000010000000010000000001010100000000100011110001 000100000000010000100000000000001000000000001110000001010110010100 011000010000000000000010100000000000000110000001000000100010101000 000001001010000010010100000000000000001000100000111101000000000000 000000000000110110100000010000100010000000010000001000000001100010 000000100001011110000100000000100001100000000000000000000001010000 010000001101000000000001000000010000100100001101100010000000000000 000100001000010000000000000000010000100100010000010001000110001010 000001001000000010000000000000001000101100100000000010100000000010 001100000011010110000000000000000010000000000010010001000011000000 010000000010100000000000000000000001001001000010010001001110000000 000111000010000000000001100000000100010001000010010001000010000000 000001010010001011010000011000000000001010000010000000000000000100 100000110100000100001000000100000000010000000001011000001000100000 011000000000010110000000000000100000000110010101100000000001000000 010000000000001000000001000010000000001111000101100000001100000000 001111000000000000100000100001000000010110010000001000000000100000 001000000010100001100000111100000000000010000010001000000000100000 010000001000110011000000000000101001001000100000000000100001000000 101110000001000100000010000101010010010000000000000000010000000000 000000100010100001000100011100000111000000000010000000000000010000 000000101100000000000100000000010111100000001000000010000000010010 001000010101000110010000000001100010000000000000000000000000001100 000000000100000100000010000100000000010000000100000000001010111101 000000010101000000010001001000000101000000001010000010000000000100 000001000010001110001000010000000000000010010000000100001000001001 100000110000100000011000010000000110000000100000011000000000000010 000000001000000000001000000011110000100100010000000100000000001011 000000000000100000100100010000001110000000000000000101010000000111 000000010000100000000010010000000110000000000000000000100010111011 000000000000000001100010001011101000000000000100000000010000010101 000000000001001000000011000000001001100000000100000000000010011101 000100110000010000000010000000000000000000001011000000100110110000 000100000010011001000000010100000000000010010000000000000100001000 000000110000000001001010001011100000000000000001000000100000100000 000000000100000100110100000100000000010000000000100101011000000100 000001111010000010001000000000000000001000000001010000100000101000 001110001001000001000000000001001010000000101000000000100001000000 001010000001000110001000001001000010000000000000000110000001000001 100000000000000001011100001011100000000000100000101100000000000000 000001010100000000010001100010000100010000000000000000001100001100 000000000001001000010101000000001001100000100000100101010000000000 111000000000000000011000100000000000000110100000111100000000000000 000010000000000000100100001000000000000001101010101010010001000000 100010100000000000001000000000010000000001110001011000100001000000 011000000011000001000001001100000000000010000111100000000000000000 100100100000010000010000000000000000000000101011111000000100000000 R(3, 15) Матрица смежности одного из найденных R(3, 15; 73)-графов: 0000010001000000100000000000000010000010000001000000110000001111001000010 0011110000010000001000000000010001001100100000000010000000001000000001000 0100000000000010000000001000100000000010010001011000000011000010100000100 0100000001001000100000000000100000010010010010000000100010000000010100010 0100000100001100000100000000100100010010000010000000000010000001000000001 1100000010001000000000100000100100010000000110000000000110010000000000000 0000000000011000001000000000000011001000100001000000010100001001001000001 0000100010000000001001000000000010000000011100001101000000010010000000000 0000010100000110000100000101000000000010100000000000000000000001000000101 1001000000000010000000100100000000000000100100100000000101010000000000101 0000000000000000000000000000000010001001000010000100110000100000100011100 0100001000000000000001010100100000010011010000000000000011000100000000100 0001111000000000000001010100010000000101000000000010000000000100000001100 0000100010000000000000011000010001000100010100000000100000000000011100010 0010000011000000001000000010000101011001000010000010000000001000000010000 0000000000000000000000011001110011000010011000000000001001000000000010100 1001000000000000000000111000010101000100000000000000000101000000000000001 0000000000000000000000000001000000000000000110100100010000100010000001111 0100001100000010000010110000000000100000000000000000101000100100100000000 0000100010000000000000100000000010000000010101000000110000011100011000000 0000000000000000001001000001000010000000001010001000000100000001000111100 0000000100011000000010101000000000001000100001010000101000100000100000000 0000010001000000101101000000000000000010001000001101000000000011000000010 0000000000011101101000000000001000001000100001010000000000011000000000000 0010000000000101100001000100001000010001000000000010000000011100000000000 0000000011011000000000001000000100001000000011011000000000000010000000000 0000000000000010000000000001111010000000001100000000001000000010000000011 0000000010000001010010000010000000001101000000000001100010000000101000000 0011110000010001000000000010000000100000000000100100010000100000000001000 0100000000001101100000000010000000010000000010100100010010110000000000000 0000000000000000000000011010000001000110010000100100010001100000000000100 0000110000000010100000000100000000000000110000000000100000000000010100110 1000001100100001000110000010000000000100000000110010000010000000000000000 0100001000000111100000000000001000100000000000001000000000010110100000000 0000000000000000001000000000100001001110110000000010000011001000000000100 0001110000010010000000001000010000000100000001011000000000000010100001000 0100001000100010000001010101000000100000000100100000000000000100010000010 0100000000001100100000000001001010110000001010000000001000010000000010000 1011100010010001000000100000001000100000000100000000000100010000000001000 0000000000111010000000001001000000000000100101111000000000000000010000010 0100001011000000000001010000000100100001000010000000000000000110000000000 0011000100010101000100000000001100100000000000000000000100000001000001001 0000000100000001000010100010000000000100000001100000010010001100011000000 0000010101000100010100000010000000001011000000000000000000000001100010000 0001110000100010010010000100010000000100100000000001000001000000001000000 1010001000000000000101010100000000010001001000000111000000000000000100000 0000000001000000010000000000111010001001001000000000101000000000100010000 0010000000000000000001010100000010010001000000000000010100000101001000001 0010000100000000000010100100000001010001000000000010101000101000000000001 0000000100100000010000100000111000000000000001000000001000001100010000000 0100000000001010000000001000000010100000000001001000010100000001101000000 0000000100000000000000100001000000000000000011000000010000101100010011100 1001000000100100001101000001000100000000000000101000000101000000000000000 1000001000100000010100000000111000000000001000010011001000000000000000000 0000000000000001001001000010000000000100000000101100010110000001000100000 0000011001000000100010000000000000000010010000010010101000100010000000010 0011110000010000000000000001010010100000001000000000001000000000000011000 0010000001010001100000000000001000100000000010000000100000000000010101010 0000000000100000011001000000111000000000000000001001000100000001001100000 0000010101000000000100011000010001000110000000000000000000000001000100010 1100001000000010000100011000000000100000001000001101000000000000100100000 1000000000011000001100001000000001001000101000010101000000000000000100000 1010000100000000010000100110000001010000100000000000000100000000010110000 1000101010000000000010100000000000000000010100010010001000110000010000000 0010000000100000001001000001000001010000000100100010000000001000010000010 0001000000000100000100000000000100001001001000000101000001000011100000001 1000001000000100000100000001000000000000001010010010000000100000000011100 0001000000000100000010000000000100000000000001000000001001111110000000001 0000000000100011000010000000000000000100000100100001000010000010001000011 0100000000101000010010000000100000010010010000000001000011000000001000000 0010000011111001010010000000001100100000000000000001000000000000001000000 1001000000000100010000100010000100001001000000000000000101010000100010000 0000101011000000110000000010000000000000010000011000000000000000010110000 М. Колодяжный |