Проблемы в латинских квадратах

В математике теория латинских квадратов является активной областью исследований со многими открытыми проблемами . Как и в других областях математики, подобные проблемы часто обсуждаются на профессиональных конференциях и собраниях. Поставленные здесь проблемы проявлялись, например, на конференциях Loops (Прага) и Milehigh (Денвер) .

Открытые проблемы

Границы максимального числа трансверсалей в латинском квадрате

Трансверсаль набор в латинском квадрате порядка n — это S из n ячеек , такой, что каждая строка и каждый столбец содержит ровно одну ячейку S , и такой, что символы в S образуют {1, ..., n }. Пусть T ( n ) — максимальное число трансверсалей в латинском квадрате порядка n . Оцените T ( n ).

Предложение: Ян Уэнлесс на Loops '03, Прага, 2003 г.
Комментарии: Уэнлесс, Маккей и МакЛеод имеют границы вида c ^н < Т ( п ) < d ^н n !, где c > 1 и d составляет около 0,6. Гипотеза Ривина, Варди и Циммермана (Ривин и др., 1994) гласит, что вы можете разместить как минимум exp( c n log n ) ферзей на неатакующих позициях на тороидальной шахматной доске (при некоторой константе c ). Если это правда, это будет означать, что T ( n ) > exp( c n log n ). вопрос — оценка числа трансверсалей в таблицах Кэли циклических групп нечетного Связанный с этим порядка . Другими словами, сколько ортоморфизмов имеют эти группы ?

Минимальное число трансверсалей латинского квадрата также является открытой проблемой. Х. Дж. Райзер предположил (Oberwolfach, 1967), что каждый латинский квадрат нечетного порядка имеет один квадрат. С этим тесно связана гипотеза, приписываемая Ришару Бруальди, о том, что каждый латинский квадрат порядка n имеет частичную трансверсаль порядка не менее n - 1.

Характеристика латинских подквадратов в таблицах умножения петель Муфанг

Опишите, как возникают все латинские подквадраты в таблице умножения петель Муфанг .

Предложение: Алеш Драпал на выставке Loops '03, Прага, 2003 г.
Комментарии: Хорошо известно, что каждый латинский подквадрат в таблице умножения группы G имеет вид aH x Hb , где H — подгруппа группы G , а a , b — элементы G. группы

Самые плотные частичные латинские квадраты со свойством Блэкберна

Частичный латинский квадрат обладает свойством Блэкберна , если всякий раз, когда ячейки ( i , j ) и ( k , l ) заняты одним и тем же символом, противоположные углы ( i , l ) и ( k , j ) пусты. Какова максимально достижимая плотность заполненных ячеек в частичном латинском квадрате со свойством Блэкберна? В частности, существует ли константа c > 0 такая, что мы всегда можем заполнить хотя бы c n ² клетки?

Предложение: Ян Уэнлесс на Loops '03, Прага, 2003 г.
Комментарии: В опубликованной статье Уэнлесс показал, что если c существует, то c < 0,463. Он также построил семейство частичных латинских квадратов со свойством Блэкберна и асимптотической плотностью не менее exp(- d (log n ) ^1/2) для константы d > 0.

Наибольшая степень двойки, делящая количество латинских квадратов

Позволять $L_{n}$ — количество латинских квадратов порядка n . Какое самое большое целое число $p(n)$ такой, что $2^{p(n)}$ делит $L_{n}$ ? Делает $p(n)$ растут квадратично по n ?

Предложение: Ян Уэнлесс на Loops '03, Прага, 2003 г.
Комментарии: Конечно, $L_{n}=n!(n-1)!R_{n}$ где $R_{n}$ — количество приведенных латинских квадратов порядка n . Это немедленно дает линейное число факторов, равное 2. Однако вот простые факторизации $R_{n}$ для n = 2,...,11:

2	3	4	5	6	7	8	9	10	11
1	1	2 ²	2 ³7	2 ⁶37 ²	2 ¹⁰35*1103	2 ¹⁷31361291	2 ²¹3 ²5231*3824477	2 ²⁸3 ²53137*547135293937	2 ³⁵3 ⁴528012206499*62368028479

Из этой таблицы следует, что степень двойки растет сверхлинейно. Лучшим текущим результатом является то, что

R_{n}

всегда делится на f !, где f составляет около n /2. См. (Маккей и Уэнлесс, 2003). Два автора заметили подозрительно высокую степень двойки (не имея возможности пролить на нее много света): (Alter, 1975), (Mullen, 1978).

См. также

Ссылки

Альтер, Рональд (1975), «Сколько здесь латинских квадратов?», Amer. Математика. Ежемесячно , 82 (6), Математическая ассоциация Америки: 632–634, doi : 10.2307/2319697 , JSTOR 2319697 .
Маккей, Брендан; Ванлесс, Ян (2005), «О количестве латинских квадратов», Ann. Гребень. , 9 (3): 335–344, doi : 10.1007/s00026-005-0261-7 , S2CID 7289396 .
Маллен, Гарри (1978), «Сколько существует сокращенных латинских квадратов ij?», Amer. Математика. Monthly , 85 (9), Математическая ассоциация Америки: 751–752, doi : 10.2307/2321684 , JSTOR 2321684 .
Ривин, Игорь; Варди, Илан; Циммерман, Пол (1994), «Проблема n ферзей», Amer. Математика. Ежемесячно , 101 (7), Математическая ассоциация Америки: 629–639, doi : 10.2307/2974691 , JSTOR 2974691 .

Внешние ссылки