Группы автоморфизмов ассоциативных схем тема диссертации и автореферата по ВАК РФ 01.01.06, доктор физико-математических наук Пономаренко, Илья Николаевич

• Пономаренко, Илья Николаевич
• доктор физико-математических наук
• 2005

Оглавление диссертации доктор физико-математических наук Пономаренко, Илья Николаевич

Введение

1 Общая теория

1.1 Схемы отношений.

1.2 Алгебры смежности.

1.3 Группы перестановок.

1.4 Алгоритмы.

2 2-замыкания групп перестановок

2.1 Прямые суммы и тензорные произведения.

2.2 Сплетения групп и сплетения схем

2.3 Эксионенцирование схемы с группой перестановок.

2.4 Нахождение 2-замыканий в классах разрешимых групп.

3 Каноническая форма в классе всех схем

3.1 Линейные инварианты схем и групп.

3.2 Теорема Жордана и группы перестановок.

3.3 Канонические формы и канонические пометки

3.4 Основной алгоритм.

4 Теорема Бернсайда-Шура и её обобщение

4.1 Кольца Шура и схемы Кэли.

4.2 Кольца Шура над коммутативными кольцами.

4.3 Теорема о разделяющей подгруппе.

4.4 Доказательства теорем 4.11 и 4.8.

5 Канонические формы циркулянтных схем

5.1 Квазинормальные и сингулярные схемы.

5.2 Структура циркулянтных схем.

5.3 Циклическая база разрешимой группы.

5.4 Распознавание циркулянтных схем

5.5 Проверка изоморфизма циркулянтных графов

6 Теорема Биркгофа для схем и групп

6.1 Комбинаторная компактность.

6.2 Примеры компактных схем, групп и графов.

6.3 Алгоритм проверки изоморфизма компактных схем

6.4 Лесовидные схемы и алгебраические леса

Введение диссертации (часть автореферата) на тему «Группы автоморфизмов ассоциативных схем»

В своей известной монографии "Геометрическая алгебра"М.Артин на стр.79 пишет: "В современной математике исследование симметрии данной математической структуры приводит, как правило, к наиболее значительным результатам". Поскольку значительная часть математических структур может быть определена в терминах отношений (различной арности), естественно изучать группы автоморфизмов семейств отношений. Такой подход впервые возникает у Галуа, который фактически определяет группу уравнения, как группу автоморфизмов семейства отношений на множестве его корней. По сути тот же подход используется и в работе Шура [71], в которой он обобщает теорему Бернсайда о примитивных группах перестановок с регулярной циклической подгруппой посредством изучения бинарных отношений, инвариантных относительно последней. Алгебраическим аналогом возникающих при этом комбинаторных структур и являются кольца, известные теперь как кольца Шура. Систематическое использование этого подхода было начато Виландтом в [79] и привело к появлению метода инвариантных отношений, сутыо которого и является изучение произвольных групп, как групп автоморфизмов подходящих семейств отношений. Уже в случае бинарных отношений этот метод позволил получить характеризацию некоторых групп ранга 3 [48] и построить ряд спорадических простых групп таких, например, как группа Хигмана-Симса.

Общая теория семейств бинарных отношений, наследующих свойства бинарных инвариантных отношений групп перестановок, была заложена в работе Хигмана [49] и, независимо, в работе Вейсфейлера и Лемана [4] (см. ниже). Такие семейства были названы когерентными конфигурациями, более современное название которых - ассоциативные схемы или просто схемы - связано с появлением монографий [1, 29, 81]. Среди наиболее впечатляющих применений теории схем отметим отметим классическую теорему Бабаи, дающую асимптотически точную оценку максимального порядка примитивной группы перестановок, не являющейся дважды транзитивной [21].

Одной из наиболее важных задач математики является нахождение полного множества инвариантов изоморфизма объектов заданной категории. В случае конечных объектов такое множество всегда может быть выбрано конечным и потому естественная проблема состоит в поиске наименьшего количества инвариантов. С алгоритмической точки зрения проблема изоморфизма заключается в оценке сложности наиболее эффективного алгоритма, проверяющего изоморфизм двух заданных объектов. Известно, что проблема изоморфизма конечных алгебраических структур сводится к проблеме изоморфизма конечных графов, являющейся одной из наиболее известных нерешённых проблем теории сложности вычислений [11, 22, 24]. Именно эта проблема привела Вейсфейлера и Лемана к открытию клеточных алгебр, которые есть ни что иное как алгебры смежности схем отношений [4]. Связав с каждым графом клеточную алгебру, порождённую его матрицей смежности, они фактически показали, что проблема изоморфизма графов полиномиально эквивалентна проблеме нахождения группы автоморфизмов схем отношений [77]. Эти идеи в дальнейшем были развиты в ряде работ [14, 67, 27, 35, 36].

Основной целью диссертации является исследование групп автоморфизмов ассоциативных схем как с сугубо теоретической, так и с алгоритмической точек зрения. Ключевым моментом здесь служит соответствие Галуа между множеством всех схем С на конечном множестве V и множеством всех подгрупп Г симметрической группы

Sym(K), задаваемое отображениями

С Aut(C), Г^1пу(Г), (1) где Aut(C) - группа автоморфизмов схемы С и Inv(r) - схема орбит группы Г относительно её индуцированного действия на V2. Замкнутыми объектами в этом соответствии являются шуровы схемы и 2-замкнутые группы. Следует отметить, что соответствие (1), не являясь взаимно-однозначным, становится таковым при некоторых условиях. Важный пример такой ситуации возникает для классов схем и групп, для которых справедлив аналог теоремы Биркгофа о дважды стохастических матрицах; мы развиваем соответствующую теорию в главе б. Правая часть соответствия (1) легла в основу метода Шура, применяемого к схемам, группа автоморфизмов которых содержит регулярную подгруппу. Накладывая на такие схемы условие инвариантности относительно автоморфизмов этой подгруппы, удаётся существенно обобщить известную теорему Бернсайда-Шура о группах перестановок (глава 4).

С вычислительной точки зрения можно легко найти схему группы эффективным алгоритмом, в то время как нахождение группы автоморфизмов - трудная задача, полиномиально эквивалентная проблеме изоморфизма графов. Эта задача упрощается, если известна некоторая априорная информация о группе автоморфизмов или её можно получить изучая структуру соответствующей схемы. В первом случае примером является долгое время остававшаяся нерешённой проблема нахождения эффективного алгоритма построения группы автоморфизмов циркулянтной схемы (у такой схемы группа автоморфизмов содержит регулярную циклическую подгруппу). Мы полностью решаем эту проблему в главе 5 значительно развивая теорию таких схем, построенную в последнее время [52, 9]. Во втором случае, используя известную теорему Жордана о линейных группах, мы доказываем, что группа автоморфизмов произвольной однородной схемы содержит разрешимую подгруппу, индекс которой ограничен некоторой функцией, зависящей от инвариантов линейных представлений алгебры смежности этой схемы. Это позволяет построить алгоритм для нахождения канонической формы и группы автоморфизмов в классе всех схем, работающий полиномиальное время, когда упомянутые инварианты растут медленно в сравнении со степенью схемы (глава 3).

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

Список литературы диссертационного исследования доктор физико-математических наук Пономаренко, Илья Николаевич, 2005 год

1. Э. Баниаи, Т. Ито, Алгебраическая комбинаторика. Схемы отношений, М.: Мир, 1987.

2. Г. Биркгоф, Теория решёток, М.: Наука, 1984.

3. Г. Вейль, Классические группы. Их инварианты и представления, М.: ИЛ, 1947.

4. Б. Ю. Вейсфейлер, А. А. Леман, Приведение графа к каноническому виду и воз-никаюшая при этом алгебра, НТИ, сер. 2, 1968, 9, 12—16.

5. С. Евдокимов, Шуровостъ и отделимость ассоциативных схем, Диссертация на соискание степени д.ф.м.н., 2005, Санкт-Петербург.

6. С. Евдокимов, И. Пономаренко, Транзитивные группы перестановок с представлениями ограниченной степени, Записки научных семинаров ПОМИ, 223 (1995), 108-119.

7. С. Евдокимов, И. Пономаренко, О примитивных клеточных алгебрах, Записки научных семинаров ПОМИ, 256 (1999), 38-68.

8. С. Евдокимов, И. Пономаренко, Об одном семействе колец Шура над конечной циклической группой, Алгебра и анализ, 13 (2001), 3, 139-154.

9. С. Евдокимов, И. Пономаренко, Характеризация циклотомических схем и нормальные кольца Шура над циклической группой, Алгебра и анализ, 14 (2002), 2, 11-55.

10. С. Евдокимов, И. Пономаренко, Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время, Алгебра и анализ, 15 (2003), 6, 1-34.

11. В. Н. Земляченко, Н. М. Корнеенко, Р. И. Тышкевич, Проблема изоморфизма графов, Теория сложности вычислений, I. Записки научных семинаров ЛОМИ, 118 (1982), 83-158.

12. К. Кэртис, И. Райнер, Теория представлений конечных групп и ассоциативных алгебр, М., 1969.

13. А. А. Леман, Об автоморфизмах некоторых классов графов, Автоматика и Телемеханика, 2 (1970), 75-82.

14. И. Пономаренко, Проблема изоморфизма для классов графов, Докл. АН СССР, 304 (1989), 3, 552-556.

15. И. Пономаренко, Об одной оценке порядка примитивных групп перестановок, Записки научных семинаров ПОМИ, 215 (1994), 256-263.

16. И. Пономаренко, Нахождение группы автоморфизмов циркулянтной ассоциативной схемы за полиномиальное время, Записки научных семинаров ПОМИ, 321 (2005), 251-267.

17. Д. А. Супруненко, Группы матриц, М.: Наука, 1972.

18. В. 3. Файнберг, Группы автоморфизмов деревьев, ДАН БССР, 13 (1969), 10651067.

19. А. V. Aho, J. Е. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms,• Addison-Wesley, 1974.

20. A. Astie, Vertex-symmetric tournaments of order n with the minimum number of arc orbits, in: M. Fiedler (Edr), Recent Advances in Graph Theory, Academia, Prague, 1975, 17-30.

21. L. Babai, On the order of uniprimitive permutation groups, Annals of Math., 113 (1981), 553-568.

22. L. Babai, Automorphism groups, isomorphism, reconstruction, in: Handbook of combinatorics. Volume 2, edited by R. L. Graham, M. Grotschel and L. Lovasz, (Elsevier Science) 1995, 1447-1541.

23. L. Babai, D. Yu. Grigoryev, D. M. Mount, Isomorphism of graphs with bounded eigenvalue multiplicity, Proc. 14th ACM STOC, 1982, 310-324.

24. L. Babai, W. Kantor, E. M. Luks, Computational complexity and the classification of finite simple groups, Proc. 24th Ann. Symp. Found. Comput. Sci, 1983, 162-171.

25. L. Babai, E. M. Luks, Canonical labeling of graphs, Proc. 15th ACM STOC, 1983, 171-183.

26. L. Babel, I. V. Chuvaeva, M. Klin, D. V. Pasechnik, Algebraic combinatorics in mathematical chemistry. Methods and Algorithm. II. Program implementation of the Weisfeiler-Leman algorithm,

27. L. Babel, I. Ponomarenko, G. Tinhofer, The Isomorphism Problem for Directed Path Graphs and for Rooted Directed Path Graphs, J. of Algorithms, 21 (1996), 542-564.

28. K. Booth, G. Lueker, A linear time algorithm for deciding interval graph isomorphism, J. of ACM, 26 (1979), 183-195.

29. A. E. Brouwer, A. M. Cohen, A. Neumaier, Distance-regular graphs, Springer, Berlin, 1989.

30. W. Burnside, Theory of Groups of Finite Order, 2nd ed. Cambridge: Cambridge Univ. Press, 1911.

31. P. J. Cameron, Homogeneous Cayley objects, Europ. J. Combinatorics, 21 (2000), 745-760.

32. A. Chan, C. D. Godsil, Symmetry and Eigenvectors, Graph symmetry (Montreal, PQ, 1996), 75-106, NATO Adv. Sci. Inst. Ser. С Math. Phys. Sci., 497, Kluvver Acad. Publ., Dordrecht, 1997.

33. D. G. Corneil, H. Lerch and L. Stewart, Complement Reducible Graphs, Discrete Appl. Math., 3 (1981), 163-185.

34. J. D. Dixon, B. Mortimer, Permutation groups, Graduate Texts in Mathematics, No. 163, Springer-Verlag New York, 1996.

35. S. Evdokimov, I. Ponomarenko, On the geometric graph isomorphism problem, Journal of Pure and Applied Algebra, 117 & 118, (1997), 253-276.

36. S. Evdokimov, I. Ponomarenko, Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks, Combinatorica, 19 (1999), 321-333.

37. S. Evdokimov, I. Ponomarenko, On highly closed cellular algebras and highly closed isomorphisms, Electronic J. of Combinatorics, 6 (1999), #R18.

38. S. Evdokimov, I. Ponomarenko, Two-closure of odd permutation group in polynomial time, Discrete Mathematics, 235/1-3, (2001), 221-232.

39. S. Evdokimov, I. Ponomarenko, A new look at the Burnside-Schur theorem, Bulletin of the London Mathematical Society, 37 (2005), 535-546.

40. S. Evdokimov, M. Karpinski, I. Ponomarenko, On a New High Dimensional Weisfei-ler-Leman Algorithm, J. of Algebraic Combinatorics, 10 (1999), 29-45.

41. S. Evdokimov, M. Karpinski, I. Ponomarenko, Compact cellular algebras and permutation groups, Discrete Mathematics, 197/198 (1999), 247-267. (This paper has been selected for Discrete Mathematics Editor's Choice, 1999)

42. S. Evdokimov, I. Ponomarenko, G. Tinhofer, Forestal algebras and algebraic forests (on a new class of weakly compact graphs), Discrete Mathematics, 225 (2000), 149172.

43. I. A. Faradzev, M. H. Klin, M. E. Muzychuk, Cellular rings and groups of automorphisms of graphs, in: I.A. Faradzev et al. (eds): Investigations in algebraic theory of combinatorial objects, Kluwer Acad. Publ., Dordrecht, 1994, 1-152.

44. C. D. Godsil, Compact Graphs and Equitable Partitions, Linear Algebra Appl., 255 (1997), 259-266.

45. R. W. Goldbach, H. L. Claasen, Cyclotomic schemes over finite rings, Indag. Math. (N.S.), 3 (1992), 301-312.

46. M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.

47. A. Hanaki, I. Miyamoto, Classification of primitive association schemes of order up to 22, Kyushu J. Math., 54 (2000), 81-86.

48. D. G. Higman, Characterization of families of rank 3 permutation groups by the subdegree I, II, Arch. Math., 21 (1970), 151-156; 353-361.

49. D. G. Higrnan, Coherent configurations 1., Rend. Mat. Sem. Padova, 44 (1970), 1-25.

50. I. M. Isaacs, Irreducible constituents of faithful induced characters, Proc. Amer. Math. Soc., 128 (2000), 3471-3474.

51. I. M. Isaacs, D. S. Passman, Groups with representations of bounded degree, Canad. J. Math., 16 (1964), 299-304.

52. К. H. Leung, S. H. Man, On Schur Rings over Cyclic Groups, II, J. of Algebra, 183 (1996), 273-285.

53. С. H. Li, On isomorphisms of finite Cayley graphs a survey, Discrete Mathematics, 256 (2002), 301-334.

54. С. H. Li, The finite primitive permutation groups containing an abelian regular subgroup, Proc. London Math. Soc., 87 (2003), 725-747.

55. A. Lubivv, Some NP-complete problems similar to graph isomorphism, SIAM J. Comput., 10 (1981), 11-21.

56. E. M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Сотр. Sys. Sci., 25 (1982), 42-65.

57. E. M. Luks, Permutation groups and polynomial-time computation, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 11 (1993), 139-175.

58. R. Mathon, A note on the graph isomorphism counting problem, Inform. Process. Lett., 8 (1979), 131-132.

59. B. R. McDonald, Finite rings with identity, Pure and Applied Mathematics, Vol. 28, Marcel Dekker Inc., New York, 1974.

60. M. E. Muzychuk , On the structure of basic sets of Schur rings over cyclic groups, J. of Algebra, 169 (1994), 655-678.

61. M. Muzychuk, On the isomorphism problem for cyclic combinatorial objects, Discrete Math., 197/198 (1999), 589-606.

62. M. Muzychuk, A solution of the isomorphism problem for circulant graphs, Proc. London Math. Soc., 88 (2004), 1-41.

63. M. Muzychuk, M. Klin, R. Poschel, The isomorphism problem for circulant graphs via Schur ring theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 56 (2001), 241-264.

64. M. E. Muzychuk, G. Tinhofer, Recognizing circulant graphs of prime order in polynomial time, Electronic J. of Combinatorics, 5 (1998), #R25.

65. M. E. Muzychuk, G. Tinhofer, Recognizing circulant graphs in polynomial time: An application of association schemes, Electronic J. of Combinatorics, 8, (2001), #R26.

66. P. P. Palfy, A polynomial bound for the orders of primitive solvable groups, J. of Algebra, 77 (1982), 127-137.

67. I. Ponomarenko, Polynomial-time algorithms for recognizing and isomorphism testing of cyclic tournaments, Acta Appl. Math., 29 (1992), 139-160.

68. I. Ponomarenko, Graph isomorphism problem and 2-closed permutation groups, Applicable Algebra in Engineering, Communication and Computing, 5 (1994), 9-22.

69. L. Pyber, How abelian is a finite group?, in: The Mathematics of Paul Erdos, Vol. I. (R. L. Graham et al. eds.), Algorithms and Combinatorics 13, Springer-Verlag, Berlin, 1997, 372-384.

70. H. Schreck and G. Tinhofer, A note on certain subpolytopes of the assignment polytope associated with circulant graphs, Linear Algebra Appl., Ill, (1988), 125-134.

71. I. Schur, Ziir Theorie der einfach transitiven Permutationgruppen, S.-B. Preus Akad. Wiss. Phys.-Math. Kl., (1933), 598-623.

72. A. Seress, The minimal base size of primitive solvable permutation groups, J. London Math. Soc., 53 (1996), 243-255.

73. A. Seress, Permutation group algorithms, Cambridge Tracts in Mathematics 152, Cambridge University Press, 2003.

74. G. Tinhofer, Graph isomorphism and theorems of Birkhoff type, Computing, 36, (1986), 285-300.

75. G. Tinhofer, Strong tree-cographs are Birkhoff graphs, Discrete Applied Math., 22, (1988/89), 275-288.

76. G. Tinhofer, A note on compact graphs, Discrete Applied Math., 30, (1991), 253-264.

77. B. Weisfeiler (editor), On construction and identification of graphs, Springer Lecture Notes, 558, 1976.

78. H. Wielandt, Finite permutation groups, Academic press, New York London, 1964.

79. H. Wielandt, Permutation groups through invariant relations and invariant functions, Lect. Notes Dept. Math. Ohio St. Univ., Columbus, 1969.

80. P.-H. Zieschang, Algebraic Approach to Association Schemes, Springer, Berlin к Heidelberg, 1996.

81. P.-H. Zieschang, Theory of Association Schemes, Springer Monographs in Mathematics, 2005.