Негізгі тәртіптегі матроид - Base-orderable matroid

Математикада а базалық тәртіптегі матроид Бұл матроид қатысты келесі қосымша қасиетке ие матроид негіздері.[1]

Кез-келген екі негіз үшін және бар а мүмкін болатын алмасу биекция, биекция ретінде анықталды бастап дейін , әрқайсысы үшін , екеуі де және негіздер болып табылады.

Меншікті Бруальди мен Скримгер енгізген.[2][3] A қатты негізді матроид келесі мықты қасиетке ие:

Кез-келген екі негіз үшін және , бар айырбастың күшті биекциясы, биекция ретінде анықталды бастап дейін , әрқайсысы үшін , екеуі де және негіздер болып табылады.

Мәнмәтіндік сипат

Реттіліктің негізі функцияға екі талап қояды :

  1. Бұл биекция болуы керек;
  2. Әрқайсысы үшін , екеуі де және негіздер болуы керек.

Осы қасиеттердің әрқайсысын қанағаттандыру оңай:

  1. Берілген матроидтың барлық негіздері бірдей бірдей болады, сондықтан да бар n! олардың арасындағы биекциялар (қайда n негіздердің жалпы өлшемі болып табылады). Бірақ осы биекциялардың біреуі 2 қасиетін қанағаттандыратынына кепілдік берілмейді.
  2. Барлық негіздер және матроид қанағаттандырады симметриялық негіз алмасу қасиеті, бұл әрқайсысы үшін , кейбіреулері бар , екеуі де және негіздер болып табылады. Алайда, f функциясының биекция болатынына кепілдік берілмейді - мүмкін бірнеше болуы мүмкін сәйкес келеді .

Матроидтар, олар негізделмейді

Кейбір матроидтер негізге тапсырыс бермейді. Көрнекті мысал болып табылады графикалық матроид графикте Қ4яғни, негізі ұзын ағаштар болып табылатын матроид клика 4 төбесінде.[1] Шыңдарын белгілеңіз Қ4 1,2,3,4-ке, ал оның шеттері 12,13,14,23,24,34-ке. Негіздер:

  • {12,13,14}, {12,13,24}, {12,13,34}; {12,14,23}, {12,14,34}; {12,23,24}, {12,23,34}; {12,24,34};
  • {13,14,23}, {13,14,24}; {13,23,24}, {13,23,34}; {13,24,34};
  • {14,23,24}, {14,23,34}; {14,24,34}.

Екі негізді қарастырайық A = {12,23,34} және B = {13,14,24}, және функциясы бар делік f айырбас қасиетін қанағаттандыру (жоғарыдағы 2-мүлік). Содан кейін:

  • f(12) 14-ке тең болуы керек: ол 24-ке тең бола алмайды, өйткені A {12} + {24} = {23,24,34}, бұл негіз емес; ол 13 болуы мүмкін емес, өйткені B {13} + {12} = {12,14,24}, бұл негіз емес.
  • f(34) 14-ке тең болуы керек: ол 24-ке тең бола алмайды, өйткені B {24} + {34} = {13,14,34}, бұл негіз емес; ол 13 болуы мүмкін емес, өйткені A {34} + {13} = {12,13,23} ол негіз емес.

Содан кейін f биекция емес - ол екі элементті бейнелейді A сол элементіне B.

Матроидтар бар, олар базалық тәртіпке ие, бірақ қатты негізделмейді.[4][1]

Матроидтар, олар негізделеді

Әрқайсысы matroid бөлімі тапсырыс бойынша негізделеді. Әрқайсысы көлденең матроид қатты негізделеді.[2]

Қасиеттері

Негізді реттелетін матроидтарда мүмкін болатын алмасу биекциясы тек базалар арасында ғана емес, сонымен бірге бірдей кардиналды кез келген екі тәуелсіз жиындар арасында, яғни кез-келген екі тәуелсіз жиындарда болады. және осындай .

Мұны жиындар мөлшері мен базистің мөлшері арасындағы айырмашылыққа индукция арқылы дәлелдеуге болады (матроидтың барлық негіздерінің өлшемдері бірдей болатынын еске түсірейік). Егер айырмашылық 0-ге тең болса, онда жиынтықтар іс жүзінде негіз болып табылады, ал қасиет базалық реттелетін матроидтардың анықтамасынан шығады. Әйтпесе, матроидтың ұлғайту қасиеті бойынша біз ұлғайта аламыз тәуелсіз жиынтыққа және ұлғайту тәуелсіз жиынтыққа . Содан кейін, индукция жорамалы бойынша мүмкін болатын айырбас биекциясы бар арасында және . Егер , содан кейін дейін және бұл мүмкін болатын айырбас биігі. Әйтпесе, және , сондықтан орнату арқылы өзгертуге болады: . Содан кейін, өзгертілген функцияны шектеу және бұл мүмкін болатын айырбас биігі.

Толықтығы

Негізгі реттелетін матроидтар класы болып табылады толық. Бұл дегеніміз, ол кәмелетке толмағандардың, дуалдардың, тікелей қосындылардың, қысқартулардың және индукциялардың операциялары кезінде бағытталған графиктермен жабылады.[1]:2 Ол сондай-ақ шектеу, біріктіру және кесу кезінде жабылады.[5]:410

Дәл осындай жағдай қатты реттелетін матроидтар класына қатысты.

Пайдаланылған әдебиеттер

  1. ^ а б c г. «Қатаң тәртіптілік үшін шеттетілген кәмелетке толмағандардың отбасы». Сызықтық алгебра және оның қолданылуы. 488: 396–429. 2016-01-01. arXiv:1507.05521. дои:10.1016 / j.laa.2015.09.055. ISSN  0024-3795. Түйіндеме (PDF).
  2. ^ а б Бруальди, Ричард А .; Скримгер, Эдвард Б. (1968-11-01). «Айырбастау жүйелері, сәйкестіктер және трансверстер». Комбинаторлық теория журналы. 5 (3): 244–257. дои:10.1016 / S0021-9800 (68) 80071-7. ISSN  0021-9800.
  3. ^ Бруальди, Ричард А. (1969-08-01). «Тәуелділік құрылымдарындағы негіздер туралы түсініктемелер». Австралия математикалық қоғамының хабаршысы. 1 (2): 161–167. дои:10.1017 / S000497270004140X. ISSN  1755-1633.
  4. ^ А.В. Инглтон. «Базалық емес матроидтар». Британдық Бесінші Комбинаторлық Конференция материалдары (Унив. Абердин, Абердин, 1975), 355–359 беттер. Конгрессус Нумерантиум, № XV, Утилитас Математикасы, Виннипег, Адам., 1976.
  5. ^ Оксли, Джеймс Г. (2006), Матроид теориясы, Оксфордтың математика бойынша магистратура мәтіндері, 3, Oxford University Press, ISBN  9780199202508.