Transversal (kombinatorik)

I matematik , särskilt i kombinatorik , med tanke på en familj av uppsättningar , här kallad en samling C , är en transversal (även kallad ett tvärsnitt ) en uppsättning som innehåller exakt ett element från varje medlem av samlingen. När uppsättningarna i samlingen är inbördes disjunkta, motsvarar varje element i transversalen exakt en medlem av C (uppsättningen den är medlem av). Om originaluppsättningarna inte är osammanhängande finns det två möjligheter för definitionen av en transversal:

En variant är att det finns en bijektion f från transversalen till C så att x är ett element av f ( x ) för varje x i transversalen. I det här fallet kallas transversalen också ett system av distinkta representanter (SDR).
Den andra, mindre vanligt förekommande, kräver inte en en-till-en-relation mellan elementen i transversalen och uppsättningarna av C . I denna situation är medlemmarna i representantsystemet inte nödvändigtvis åtskilda.

Inom datavetenskap är beräkning av transversaler användbart i flera applikationsdomäner, där inmatningsfamiljen av uppsättningar ofta beskrivs som en hypergraf .

Existens och antal

En grundläggande fråga i studiet av SDR är om ett SDR existerar eller inte. Halls äktenskapsteorem ger nödvändiga och tillräckliga förutsättningar för att en ändlig samling av mängder, några möjligen överlappande, ska ha en transversal. Villkoret är att för varje heltal k måste varje samling av k uppsättningar innehålla gemensamma minst k olika element.

Följande förfining av HJ Ryser ger lägre gränser för antalet sådana SDR.

Sats . Låt S ₁ , S ₂ , ..., S _m vara en samling av mängder så att $S_{i_{1}}\cup S_{i_{2 }}\cup \dots \cup S_{i_{k}}$ innehåller minst k element för k = 1,2,..., m och för alla k -kombinationer { $i_{1},i_{2},\ldots ,i_{k}$ } av heltalen 1,2,..., m och anta att var och en av dessa mängder innehåller minst t element. Om t ≤ m så har samlingen minst t ! SDR, och om t > m så har samlingen minst t ! / ( t - m )! SDR.

Förhållande till matchning och täckning

Man kan konstruera en tvådelad graf där hörnen på ena sidan är mängderna, hörnen på den andra sidan är elementen, och kanterna förbinder en mängd med elementen den innehåller. Då är en transversal (definierad som ett system av distinkta representanter) ekvivalent med en perfekt matchning i denna graf.

Man kan konstruera en hypergraf där hörnen är elementen och hyperkanterna är mängderna. Sedan är en transversal (definierad som ett system av inte-nödvändigtvis distinkta representanter) ett vertextäcke i en hypergraf .

Exempel

I gruppteorin , givet en undergrupp H i en grupp G , är en höger (respektive vänster) transversal en mängd som innehåller exakt ett element från varje höger (respektive vänster) coset av H . I detta fall är "uppsättningarna" (cosets) ömsesidigt disjunkta, dvs cosets bildar en uppdelning av gruppen.

Som ett speciellt fall av det föregående exemplet, givet en direkt produkt av grupperna $G=H\ gånger K$ , så är H en transversal för bisatserna av K .

I allmänhet, eftersom varje ekvivalensrelation på en godtycklig uppsättning ger upphov till en partition, resulterar valet av valfri representant från varje ekvivalensklass i en transversal.

En annan instans av en partitionsbaserad transversal uppstår när man betraktar ekvivalensrelationen känd som den (mängd-teoretiska) kärnan för en funktion , definierad för en funktion $f$ med domän X som partitionen för domänen $\operatörsnamn {ker} f:=\left\{\,\left\{\,y\in X \mid f(x)=f(y)\,\right\}\mid x\in X\,\right\}$ . som delar upp domänen av f i ekvivalensklasser så att alla element i en klass mappar via f till samma värde. Om f är injektiv, finns det bara en transversal av $\operatorname {ker} f$ . För ett inte nödvändigtvis injektivt f , inducerar fixering av ett tvärgående T för ${\displaystyle \operatorname {ker} f} en en-till-en-överensstämmelse mellan$ T och bilden av f , hädanefter betecknad med $\operatörsnamn {Im} f$ . Följaktligen är en funktion $g:(\operatörsnamn {Im} f)\to T$ väldefinierad av egenskapen att för alla z i $\operatorname {Im} f,g(z)=x$ där x är det unika elementet i T så att $f(x)=z$ ; vidare g utökas (inte nödvändigtvis på ett unikt sätt) så att det definieras på hela samdomänen för f genom att välja godtyckliga värden för g(z) när z är utanför bilden av f . Det är en enkel beräkning för att verifiera att g som definieras på detta sätt har egenskapen att ${\displaystyle f\circ g\circ f=f} ,$ vilket är beviset (när domänen och kodomänen för f är samma uppsättning) att den fullständiga transformationssemigruppen är en vanlig semigrupp . $g$ fungerar som en (inte nödvändigtvis unik) kvasi-invers för f ; inom semigruppteorin kallas detta helt enkelt en invers. Observera dock att för ett godtyckligt g med ovannämnda egenskap kanske den "dubbla" ekvationen ${\displaystyle g\circ f\circ g=g} inte håller.$ Men om vi betecknar med $h=g\circ f\circ g$ , så är f en kvasi-invers av h , dvs $h\circ f\cirkel h=h$ .

Vanliga transversaler

En vanlig transversal av samlingarna A och B (där $|A|=|B|=n$ ) är en uppsättning som är en transversal av både A och B . Samlingarna A och B har en gemensam tvärgående om och endast om, för alla $I,J\subset \{1,...,n\}$ ,

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

Generaliseringar

En partiell transversal är en uppsättning som innehåller högst ett element från varje medlem av samlingen, eller (i den striktare formen av konceptet) en uppsättning med en injektion från uppsättningen till C . Transversalerna av en finit samling C av finita mängder utgör grundmängderna för en matroid , den transversala matroiden av C. De oberoende uppsättningarna av den transversala matroiden är de partiella transversalerna av C .

En oberoende transversal (även kallad en regnbågsoberoende uppsättning eller oberoende system av representanter ) är en transversal som också är en oberoende uppsättning av en given graf. För att förklara skillnaden i bildliga termer, överväg en fakultet med m institutioner, där fakultetsdekanus vill konstruera en kommitté med m ledamöter, en ledamot per institution. En sådan kommitté är en tvärgående. Men anta nu att vissa fakultetsmedlemmar ogillar varandra och inte går med på att sitta i kommittén tillsammans. I detta fall måste kommittén vara en oberoende transversal, där den underliggande grafen beskriver "ogillar"-relationerna.

En annan generalisering av begreppet transversal skulle vara en uppsättning som bara har en icke-tom skärningspunkt med varje medlem av C . Ett exempel på det senare skulle vara en Bernstein-uppsättning , som definieras som en mängd som har en icke-tom skärningspunkt med varje uppsättning av C , men som inte innehåller någon uppsättning av C , där C är samlingen av alla perfekta uppsättningar av en topologisk polska utrymme . Som ett annat exempel, låt C bestå av alla linjerna i ett projektivt plan , då är en blockerande uppsättning i detta plan en uppsättning punkter som skär varje linje men som inte innehåller någon linje.

Kategoriteori

På kategoriteorispråket är en tvärgående övergång av en samling av ömsesidigt disjunkta uppsättningar en del av kvotkartan som induceras av samlingen .

Beräkningskomplexitet

Beräkningskomplexiteten för att beräkna alla transversaler av en ingångsfamilj av uppsättningar har studerats , särskilt inom ramen för uppräkningsalgoritmer .

Se även

Vidare läsning

Lawler, EL Kombinatorisk optimering: nätverk och matroider. 1976.
Mirsky, Leon (1971). Transversal Theory: En redogörelse för några aspekter av kombinatorisk matematik. Akademisk press. ISBN 0-12-498550-5 .