Transversaal (combinatoriek) - Transversal (combinatorics)

In de wiskunde , met name in de combinatoriek , is bij een familie van verzamelingen, hier een verzameling C genoemd , een transversaal (ook wel een doorsnede genoemd ) een verzameling die precies één element uit elk lid van de verzameling bevat. Wanneer de sets van de collectie onderling onsamenhangend zijn, komt elk element van de transversale overeen met precies één lid van C (de set waarvan het lid is). Als de originele sets niet onsamenhangend zijn, zijn er twee mogelijkheden voor de definitie van een transversaal:

• Een variatie is dat er een bijectie f is van de transversaal naar C zodat x een element is van f ( x ) voor elke x in de transversaal. In dit geval wordt de transversale ook wel een systeem van afzonderlijke vertegenwoordigers (SDR) genoemd.
• De andere, minder gebruikelijke, niet één-op-één relatie tussen de elementen van de transversale en de stellen vereist C . In deze situatie zijn de leden van het systeem van vertegenwoordigers niet noodzakelijk verschillend.

In de informatica zijn computertransversale gegevens nuttig in verschillende toepassingsdomeinen, waarbij de invoerfamilie van sets vaak wordt beschreven als een hypergraaf .

Bestaan ​​en aantal

Een fundamentele vraag bij de studie van SDR is of er al dan niet een SDR bestaat. Halls huwelijksstelling geeft noodzakelijke en voldoende voorwaarden voor een eindige verzameling verzamelingen, waarvan sommige mogelijk overlappen, om een ​​transversaal te hebben. Voorwaarde is dat, voor elk integer k , elke verzameling k sets ten minste k verschillende elementen gemeenschappelijk moet bevatten .

De volgende verfijning door HJ Ryser geeft lagere grenzen aan het aantal van dergelijke SDR's.

Stelling . Laat S ₁ , S ₂ , ..., S _m een verzameling verzamelingen zijn die tenminste k elementen bevat voor k = 1,2, ..., m en voor alle k -combinaties { } van de gehele getallen 1, 2, ..., m en stel dat elk van deze sets ten minste t elementen bevat. Als t ≤ m dan heeft de collectie tenminste t  ! SDR's, en als t > m dan heeft de collectie tenminste t  ! / ( t - m )! SDR's. ${\ displaystyle S_ {i_ {1}} \ cup S_ {i_ {2}} \ cup \ dots \ cup S_ {i_ {k}}}$${\ displaystyle i_ {1}, i_ {2}, \ ldots, i_ {k}}$

Relatie met matchen en bedekken

Men kan een bipartiete graaf construeren waarin de hoekpunten aan de ene kant de sets zijn, de hoekpunten aan de andere kant de elementen, en de randen een set verbinden met de elementen die het bevat. Een transversaal (gedefinieerd als een systeem van afzonderlijke vertegenwoordigers) is dan gelijk aan een perfecte afstemming in deze grafiek.

Men kan een hypergraaf construeren waarin de hoekpunten de elementen zijn en de hyperedges de verzamelingen. Vervolgens is een transversaal (gedefinieerd als een systeem van niet noodzakelijkerwijs verschillende vertegenwoordigers) een hoekpuntafdekking in een hypergraaf .

Voorbeelden

In de groepentheorie , gegeven een subgroep H van een groep G , is een rechter (respectievelijk linker) transversaal een verzameling die precies één element uit elke rechter (respectievelijk linker) nevenverzameling van H bevat . In dit geval zijn de "sets" (nevenklassen) onderling disjunct, dwz de nevenklassen vormen een partitie van de groep.

Als een bijzonder geval van het vorige voorbeeld, gegeven een direct product groepen dan H is een transversaal voor nevenklassen van K . ${\ displaystyle G = H \ maal K}$

In het algemeen, aangezien elke equivalentierelatie op een willekeurige set aanleiding geeft tot een partitie, resulteert het kiezen van een vertegenwoordiger uit elke equivalentieklasse in een transversaal.

Een ander geval van een partitie-gebaseerde transversale doet zich voor wanneer men de equivalentierelatie beschouwt die bekend staat als de (set-theoretische) kernel van een functie , gedefinieerd voor een functie met domein X als de partitie van het domein . die het domein van f verdeelt in equivalentieklassen zodat alle elementen in een klasse via f naar dezelfde waarde toewijzen . Als f injectief is, is er slechts één transversaal van . Voor een niet-noodzakelijk-injectieve f induceert het vastleggen van een transversale T van een één-op-één overeenkomst tussen T en het beeld van f , hierna aangeduid met . Derhalve een functie is goed gedefinieerd door de eigenschap dat voor alle z in waarbij x het unieke element T , zodat ; bovendien kan g worden uitgebreid (niet noodzakelijkerwijs op een unieke manier) zodat het wordt gedefinieerd op het hele codomein van f door willekeurige waarden te kiezen voor g (z) wanneer z buiten het beeld van f ligt . Het is een eenvoudige berekening om te verifiëren dat g aldus gedefinieerd de eigenschap heeft dat , wat het bewijs is (wanneer het domein en het codomein van f dezelfde set zijn) dat de volledige transformatie semigroep een reguliere semigroep is . fungeert als een (niet noodzakelijk unieke) quasi-inverse voor f ; binnen de semigroepentheorie wordt dit simpelweg een inverse genoemd. Merk echter op dat voor een willekeurige g met de bovengenoemde eigenschap de "dubbele" vergelijking mogelijk niet geldt. Als we echter aanduiden met , dan is f een quasi-inverse van h , dwz . ${\ displaystyle f}$ ${\ Displaystyle \ operatorname {ker} f: = \ left \ {\, \ left \ {\, y \ in X \ mid f (x) = f (y) \, \ right \} \ mid x \ in X \,\Rechtsaf\}}$${\ displaystyle \ operatornaam {ker} f}$${\ displaystyle \ operatornaam {ker} f}$${\ displaystyle \ operatorname {Im} f}$${\ displaystyle g: (\ operatorname {Im} f) \ naar T}$${\ displaystyle \ operatorname {Im} f, g (z) = x}$${\ displaystyle f (x) = z}$${\ displaystyle f \ circ g \ circ f = f}$${\ displaystyle g}$${\ displaystyle g \ circ f \ circ g = g}$${\ displaystyle h = g \ circ f \ circ g}$${\ displaystyle h \ circ f \ circ h = h}$

Gemeenschappelijke transversalen

Een gemeenschappelijke transversale van de verzamelingen A en B (waar ) is een cyclus die een transversale zowel A en B . De collecties A en B hebben een gemeenschappelijke transversale als en slechts als, voor alle , ${\ displaystyle | A | = | B | = n}$${\ displaystyle I, J \ subset \ {1, ..., n \}}$

${\ displaystyle | (\ bigcup _ {i \ in I} A_ {i}) \ cap (\ bigcup _ {j \ in J} B_ {j}) | \ geq | I | + | J | -n}$

Generalisaties

Een gedeeltelijke transversale is een reeks die hoogstens één element van elk lid van de verzameling, of (in engere vorm van het concept) een reeks met een injectie van de set C . De transversals van een eindige verzameling C van eindige verzamelingen vormen de basis stellen een matroïde de transversale matroïde van C . De onafhankelijke reeks van dwarse matroïde zijn de partiële transversals van C .

Een onafhankelijk transversaal (ook wel een regenboogonafhankelijke set of onafhankelijk systeem van vertegenwoordigers genoemd ) is een transversaal dat ook een onafhankelijke set van een bepaalde grafiek is. Om het verschil figuurlijk te verklaren, kun je denken aan een faculteit met m afdelingen, waar de faculteitsdecaan een commissie wil samenstellen van m leden, één lid per afdeling. Zo'n commissie is transversaal. Maar stel nu dat sommige faculteitsleden een hekel aan elkaar hebben en het niet eens zijn om samen in de commissie te zitten. In dit geval moet de commissie een onafhankelijke transversaal zijn, waarbij de onderliggende grafiek de "afkeer" -relaties beschrijft.

Een andere algemene toepassing van het concept van een transversaal zou een set die slechts een niet-lege kruispunt met elk lid van zijn C . Een voorbeeld van het laatste is een Bernstein-set , die wordt gedefinieerd als een set die een niet-lege kruising heeft met elke set C , maar geen set C bevat , waarbij C de verzameling is van alle perfecte sets van een topologisch Pools. ruimte . Als een ander voorbeeld, laat C bestaan ​​uit alle lijnen van een projectief vlak , dan is een blokkeringsset in dit vlak een set punten die elke lijn snijdt maar geen lijn bevat.

Categorie theorie

In de taal van de categorietheorie is een transversaal van een verzameling onderling onsamenhangende verzamelingen een deel van de quotiëntkaart die door de verzameling wordt geïnduceerd.

Computationele complexiteit

De computationele complexiteit van het berekenen van alle transversalen van een invoerfamilie van verzamelingen is bestudeerd, in het bijzonder in het kader van opsommingsalgoritmen .

Zie ook

• Axioma van keuze
• Permanent

Referenties

Verder lezen

• Lawler, EL Combinatorische optimalisatie: netwerken en matroïden. 1976.
• Mirsky, Leon (1971). Transversale theorie: een verslag van enkele aspecten van combinatorische wiskunde. Academische pers. ISBN   0-12-498550-5 .