Характеризация матроидов в терминах поверхностей | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/1

Характеризация матроидов в терминах поверхностей

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

A characterization of matroids in terms of surfaces.pdf Введение Впервые определение конечного матроида было дано в 1935 г. Х. Уитни [1]. В дальнейшем было предложено множество эквивалентных определений матроида. Например, в [2] приведены тринадцать различных эквивалентных определений матроида (не считая их вариантов). Достаточно полный обзор определений матроида содержится также в [3, 4]. Большая часть этих определений может быть отнесена к следующим двум группам. Первая группа определений. Матроид определяется как булева решётка 2U всех подмножеств конечного множества U с выделенным семейством подмножеств. К этой группе относится данное Уитни определение в терминах независимых множеств, где выделено непустое семейство A С 2U, обладающее следующими свойствами: - (A1) если A Е A, B С A, то B Е A (наследственность); - (A2) для любых A, B Е A, таких, что |B| = |A| + 1, существует элемент b Е B \ A, для которого A U {b} Е A (пополнение). Обозначается такой матроид обычно как M = (U, A). Множества семейства A называются независимыми, а все остальные подмножества U - зависимыми множествами матроида M. Максимальные по включению независимые множества матроида M называются базами, а минимальные по включению зависимые множества - циклами матроида M. Семейства всех баз и всех циклов матроида обозначаются B и C соответственно. Для любого множества X С U базой множества X С U называется любое его максимальное по включению независимое подмножество. Базы множества U являются базами матроида. Нетрудно показать, что в матроиде все базы любого множества имеют одинаковую мощность. Ранговой функцией матроида M = (U, A) называется отображение r : 2U ^ Z+, значением которой r(X) для множества X С U является мощность любой базы множества X. Ранг множества U называется рангом матроида. К первой группе относятся также хорошо известные определения матроида в терминах баз (выделено семейство B), циклов (выделено семейство C) и другие. Вторая группа определений. Матроид определяется как булева решетка 2U всех подмножеств конечного множества U с заданным на 2U отображением. Наиболее известными определениями второй группы являются определение в терминах ранговой функции и следующее определение в терминах оператора замыкания. Матроид - это пара M = (U, ф), где U - непустое конечное множество, ф - отображение булевой решётки 2U всех подмножеств множества U в себя, которое ставит в соответствие любому множеству X С U его замыкание X и обладает следующими свойствами: - (ф1) X С X для любого X С U (направленность); - (ф2) для любых X,Y С U если X С Y, то X С Y (монотонность); - (ф3) X = X для любого X С U (идемпотентность); - (ф4) для любых элементов u,v Е U и любого подмножества X С U если u Е X и u Е X U {v}, то v Е X U {и} (свойство замены). Матроид M = (U, ф) называется обыкновенным, если он, кроме того, обладает свойством (ф5): - (ф5) 0 = 0 и {и} = {и} для любого и Е U. Подмножество X С U называется замкнутым, если X = X. Замкнутые множества матроида M = (U, ф) называют его листами или поверхностями. Наряду с конечными матроидами изучают также матроиды общего вида, основное множество U в которых может быть бесконечным. Как правило, в таких матроидах накладывают некоторые ограничения на ранг. Например, матроид конечного ранга в терминах независимых множеств определяется как булева решётка 2U всех подмножеств произвольного (возможно, бесконечного) множества U с выделенным семейством AC 2U, обладающим свойствами (A1), (A2) и - (A3) существует такое число r Е N, что для любого A е A выполнено |A| ^ r (свойство конечности ранга). Заметим, что класс матроидов конечного ранга представляет собой объединение всех классов матроидов фиксированного ранга k по всем k Е N. В определении матроида конечного ранга в терминах оператора замыкания свойство конечности ранга выглядит следующим образом: - (

Ключевые слова

матроид, поверхность, ранг, комбинаторная геометрия, matroid, surface, rank, combinatorial geometry

Авторы

ФИООрганизацияДополнительноE-mail
Ильев Артем ВикторовичИнститут математики им. С. Л. Соболева СО РАНаспирантartyom_iljev@mail.ru
Ильев Виктор ПетровичИнститут математики им. С. Л. Соболева СО РАН; Омский государственный университетдоктор физико-математических наук, доцент, старший научный сотрудник; профессорiljev@mail.ru
Всего: 2

Ссылки

Whitney H. On the abstract properties of linear dependence // Amer. J. Math. 1935. V. 57. P. 509-533.
Brylawski T. Appendix of matroid cryptomorphisms // Theory of Matroids. Encyclopedia of Mathematics and its Applications 26 / ed. N. White. Cambridge: Cambridge University Press, 1986. P. 298-312.
Schrijver A. Combinatorial Optimization. V. B. Berlin, Heidelberg, N.Y.: Springer Verlag, 2003. 1881 p.
Welsh D. J. A. Matroid Theory. London, N.Y., San Francisco: Academic Press, 1976. 433 p.
Айгнер М. Комбинаторная теория. М.: Мир, 1982. 558с.
Рыбников К. А. Введение в комбинаторный анализ. М.: Изд-во МГУ, 1985. 308с.
Crapo H. H. and Rota G.-C. On the Foundations of Combinatorial Theory. II. Combinatorial Geometries. Cambridge, MA: MIT Press, 1970. 293 p.
VanLint J. H. and Wilson R. M. A Course in Combinatorics. N. Y.: Cambridge University Press, 2001. 602 p.
Gordon G. and McNulty J. Matroids: a Geometric Introduction. Cambridge: Cambridge University Press, 2012. 410 p.
Mason J. H. Matroids as the study of geometrical configurations // Higher Combinatorics / ed. M. Aigner. Dordrecht: Reidel Publishing Company, 1977. P. 133-176.
Bruhn H., Diestel R., Kriesell M., et al. Axioms for infinite matroids // Adv. Math. 2013. V. 239. P. 18-46.
Delucchi E. Combinatorial Geometries in Algebra and Topology. Habilitationsschrift. Universitat Bremen, 2011. 160 p.
Gelfand I. M., Goresky R. M., McPherson R. D., and Serganova V. Combinatorial geometries, convex polyhedra and Schubert cells // Adv. Math. 1987. V. 63. P. 301-316.
Oxley J. Matroid Theory. N. Y.: Oxford University Press, 1992. 532 p.
Pitsoulis L. S. Topics in Matroid Theory. N. Y.: Springer Verlag, 2014. 127 p.
Theory of Matroids. Encyclopedia of Mathematics and its Applications 26 / ed. N. White. Cambridge: Cambridge University Press, 1986. 316 p.
Combinatorial Geometries. Encyclopedia of Mathematics and its Applications 29 / ed. N. White. Cambridge: Cambridge University Press, 1987. 212 p.
Matroid Applications. Encyclopedia of Mathematics and its Applications 40 / ed. N. White. Cambridge: Cambridge University Press, 1992. 363 p.
Mac Lane S. Some interpretations of abstract linear dependence in terms of projective geometry // Amer. J. Math. 1936. V. 58. P. 236-240.
 Характеризация матроидов в терминах поверхностей | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/1

Характеризация матроидов в терминах поверхностей | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/1