УДК 519.14+512.542 |
А. А. Махнев, Д. В. Падучих |
Об автоморфизмах графа Ашбахера, 125–134. |
Если регулярный граф валентности $k$ диаметра $d$ имеет $v$ вершин, то выполняется неравенство, доказанное Муром (см. [1]): $v\leqslant 1+k+k(k-1)+\dots+k(k-1)^{d-1}.$ Графы, для которых это нестрогое неравенство превращается в равенство, называются графами Мура. Графы Мура имеют нечетный обхват, равный $2d+1$. Простейший пример графа Мура доставляет $(2d+1)$-угольник. Дамерелл доказал, что граф Мура валентности $k\geqslant 3$ имеет диаметр 2. В этом случае $v=k^2+1$, граф сильно регулярен с $\lambda=0$ и $\mu=1$, а валентность $k$ равна 3 (граф Петерсена), 7 (граф Хоффмана – Синглтона) или 57. Первые два графа являются графами ранга 3. Существование графа Мура валентности $k=57$ неизвестно, но Ашбахер доказал, что граф Мура с $k=57$ не является графом ранга 3. Граф Мура с $k=57$ назовем графом Ашбахера. Камерон доказал, что граф Ашбахера не может быть вершинно транзитивным. Здесь рассматриваются подграфы неподвижных точек автоморфизмов графов Мура и группы автоморфизмов гипотетического графа Ашбахера в случае, когда эта группа содержит инволюцию. |
Ключевые слова: граф Мура, граф Ашбахера, автоморфизм, инволюция. |
Адреса авторов: Махнев Александр Алексеевич, Россия, 620219, г. Екатеринбург, ул. С. Ковалевской, 16, Институт математики и механики УрО РАН. e-mail: makhnev@imm.uran.ru |
УДК 512.54 |
Н. Я. Медведев |
Частичные порядки на группах Длаба, 135–157. |
Для любой подгруппы $H$ ранга 1 мультипликативной группы положительных действительных чисел дается полное описание максимальных частичных порядков и минимальных изолированных частичных порядков групп Длаба $D_{H}({\bf I})$, $D_{H*}({\bf I})$, $D_{*H}({\bf I})$, ${\bar{D}}_{H}({\bf I})$ единичного интервала ${\bf I}=[0,1]$ и $D_{H}$, $D_{H*}$ расширенной действительной прямой ${{\bf \bar{R}}}$. Более точно, 1) любая группа, изоморфно вложимая в одну из вышеперечисленных групп Длаба, не имеет нетривиальных минимальных частичных порядков; 2) группы $D_{H}({\bf I})$ и $D_{H}$ имеют 4 максимальных частичных порядка и 4 нетривиальных минимальных изолированных частичных порядка; 3) группы $D_{H*}({\bf I})$, $D_{*H}({\bf I})$ и $D_{H*}$ имеют 10 максимальных частичных порядков и 8 нетривиальных минимальных изолированных частичных порядков; 4) группа ${\bar{D}}_{H}({\bf I})$ имеет 16 нетривиальных минимальных изолированных частичных порядков и 40 максимальных частичных порядков. |
Ключевые слова: частичный порядок, группа Длаба. |
Адрес автора: Медведев Николай Яковлевич, Россия, 656010, г. Барнаул, ул. Горно-Алтайская, д. 21, кв. 100. Тел. (дом.): (3852) 77-70-21. e-mail: medvedev@math.dcn-asu.ru |
УДК 512.57:512.565.7 |
А. Г. Пинус |
Внутренние гомоморфизмы и позитивно-условные термы, 158–173. |
Находятся критерий для того, чтобы две конечные или равномерно локально конечные алгебры конечной сигнатуры были позитивно-условно рационально эквивалентны (в терминах полугрупп внутренних гомоморфизмов этих алгебр), и критерий для того, чтобы две конечные алгебры были сильно схожи (в терминах обогащенных полугрупп внутренних гомоморфизмов этих алгебр). |
Ключевые слова: конечные алгебры, равномерно локально конечная алгебра, позитивно-условно рационально эквивалентные алгебры, сильно схожие алгебры. |
Адрес автора: Пинус Александр Георгиевич, Россия, 630099, г. Новосибирск, ул. Революции, д. 10, кв. 15. e-mail: algebra@nstu.nsk.su |
УДК 510.53+510.67+512.563 |
С. Ю. Подзоров |
Рекурсивные однородные булевы алгебры, 174–191. |
А. С. Морозов описал типы изоморфизма счетных однородных булевых алгебр. Им же был решен вопрос о разрешимости этих алгебр: счетная однородная булева алгебра имеет разрешимое представление тогда и только тогда, когда множество, характеризующее тип изоморфизма этой алгебры, лежит в классе $\Pi^0_2$ арифметической иерархии. Вопрос о характеризации однородных булевых алгебр, имеющих рекурсивное представление, оставался открытым. Дается частичный ответ на этот вопрос: находятся точная верхняя и точная нижняя оценки множества, характеризующего тип изоморфизма такой алгебры, в терминах иерархии Фейнера. |
Ключевые слова: рекурсивные однородные булевы алгебры, арифметическая иерархия, гиперарифметическая иерархия. |
Адрес автора: Подзоров Сергей Юрьевич, Россия, 630090, г. Новосибирск, ул. Пирогова, д. 20/1, к. 304-3. e-mail: podz@math.nsc.ru |
УДК 512.54 |
В. А. Романьков |
О тестовых элементах свободных разрешимых групп ранга 2, 192–201. |
Доказывается, что свободная разрешимая группа ранга 2 ступени 3 содержит тестовые элементы. Тем самым решается проблема Файна – Шпильрайна 14.88 из "Коуровской тетради". |
Ключевые слова: свободная разрешимая группа, тестовый элемент. |
Адрес автора: Романьков Виталий Анатольевич, Россия, 644077, г. Омск, пр. Мира, д. 55-В, кв. 27. |
УДК 512.56/.57:510.57 |
А. П. Семигродских |
О замкнутых классах финально периодических функций, 202–217. |
Вводится понятие рекурсивно замкнутого класса и дается описание рекурсивно замкнутых классов, порожденных константами. Данные классы входят в некоторое частично упорядоченное множество, "пронизывающее" решетку всех замкнутых по суперпозиции классов, состоящих из примитивно рекурсивных функций. При описании рекурсивно замкнутых классов, порожденных константами, вводится понятие финально периодической функции, обобщающее понятие периодической функции. Основным результатом является теорема о том, что рекурсивно замкнутый класс, порожденный множеством из $n$ констант, совпадает с классом всех принимающих значения из этого множества финально периодических функций, периоды которых делят натуральные степени числа $n!$. В качестве следствия получается описание рекурсивно замкнутых классов, порожденных бесконечными множествами констант. В частности, оказывается, что рекурсивно замкнутый класс, порожденный всеми константами, совпадает с классом всех финально периодических функций. |
Ключевые слова: финально периодическая функция, рекурсивно замкнутый класс. |
Адрес автора: Семигродских Александр Павлович, Россия, 620061, г. Екатеринбург, ул. Главная, 26-8. Тел.: (3432) 26-74-43, e-mail: Alexander.Semigrodskikh@usu.ru |
УДК 510.642+512.57 |
Д. Е. Тишковский |
Алгебраические эквиваленты некоторых свойств суперинтуиционистских предикатных логик, 218–242. |
аходятся алгебраические эквиваленты для свойства Бета, проективного свойства Бета, интерполяционного свойства, дизъюнктивного свойства и экзистенциального свойства суперинтуиционистских логик 1-го порядка. |
Ключевые слова: суперинтуиционистская предикатная логика, свойство Бета, проективное свойство Бета, интерполяционное свойство, дизъюнктивное свойство, экзистенциальное свойство. |
Адрес автора: Тишковский Дмитрий Евгеньевич, Россия, 630090, г. Новосибирск, пр. Ак. Коптюга, 4, Институт математики СО РАН. e-mail: tishkov@math.nsc.ru |