Rotas grundgissning
I linjär algebra och matroidteori är Rotas grundgissning en obevisad gissning angående omarrangemang av baser , uppkallad efter Gian-Carlo Rota . Den anger att om X antingen är ett vektorrum med dimension n eller mer allmänt en matroid av rang n , med n disjunkta baser B i , så är det möjligt att arrangera elementen i dessa baser till en n × n matris i en sådan sätt att raderna i matrisen är exakt de givna baserna och matrisens kolumner är också baser. Det vill säga, det borde vara möjligt att hitta en andra uppsättning av n disjunkta baser Bi Ci , som var och en består av ett element från var och en av baserna .
Exempel
Rotas grundförmodan har en enkel formulering för punkter i det euklidiska planet : den anger att, givet tre trianglar med distinkta hörn, med varje triangel färgad med en av tre färger, måste det vara möjligt att omgruppera de nio triangelhörnen till tre "regnbågar" trianglar som har en vertex av varje färg. Trianglarna måste alla vara icke-degenererade, vilket innebär att de inte har alla tre hörn på en linje.
För att se detta som en instans av basförmodan kan man använda antingen linjärt oberoende av vektorerna ( i en tredimensionell reell vektorrymd (där ( ) är de kartesiska koordinaterna för triangelns hörn) eller på motsvarande sätt kan man använda en matroid av rang tre där en uppsättning S punkter är oberoende om antingen | S | ≤ 2 eller S bildar de tre hörnen i en icke-degenererad triangel. För denna linjära algebra och denna matroid är baserna exakt de icke-degenererade trianglarna. Med tanke på de tre inmatningstrianglarna och de tre regnbågstrianglarna är det möjligt att ordna de nio hörnen till en 3 × 3 matris där varje rad innehåller hörnen på en av enfärgstrianglarna och varje kolumn innehåller hörnen på en av regnbågstrianglar.
Analogt, för punkter i tredimensionell euklidisk rymd, anger gissningen att de sexton hörnen av fyra icke-degenererade tetraedrar med fyra olika färger kan omgrupperas till fyra regnbåstetraedrar.
Delvis resultat
Redovisningen av Rotas grundförmodan publicerades först av Huang & Rota (1994) och krediterade den (utan citat) till Rota 1989. Grundförmodan har bevisats för beläggningsmatroider (för alla n ) och för fallet n ≤ 3 ( för alla typer av matroid). För godtyckliga matroider är det möjligt att arrangera baselementen i en matris vars första Ω( √ n ) kolumner är baser. Grundantagandet för linjära algebror över fält med karakteristisk noll och för jämna värden på n skulle följa från en annan gissning om latinska kvadrater av Alon och Tarsi. Baserat på denna implikation är gissningarna känd för att vara sanna för linjära algebror över de reella talen för oändligt många värden på n .
Relaterade problem
I samband med Tverbergs teorem antog Bárány & Larman (1992) att för varje uppsättning r ( d + 1) punkter i d - dimensionell euklidisk rymd , färgad med d + 1 färger på ett sådant sätt att det finns r punkter av varje färg finns det ett sätt att dela upp punkterna i regnbågsförenklingar (uppsättningar av d + 1 poäng med en punkt av varje färg) på ett sådant sätt att de konvexa skroven i dessa uppsättningar har en icke-tom skärningspunkt. Till exempel anger det tvådimensionella fallet (bevisat av Bárány och Larman) med r = 3 att det för varje uppsättning av nio punkter i planet, färgade med tre färger och tre punkter av varje färg, är möjligt att dela upp punkterna i tre korsande regnbågstrianglar, ett uttalande som liknar Rotas grundförmodan som säger att det är möjligt att dela upp punkterna i tre icke-degenererade regnbågstrianglar. Bárány och Larmans gissningar tillåter att en kolinjär trippel av punkter betraktas som en regnbågstriangel, medan Rotas grundförmodan inte tillåter detta; å andra sidan kräver Rotas grundförmodan inte att trianglarna har en gemensam skärningspunkt. Betydande framsteg när det gäller gissningarna om Bárány och Larman gjordes av Blagojević, Matschke & Ziegler (2009) .
Se även
- Rotas gissning , en annorlunda gissning av Rota om linjär algebra och matroider
externa länkar
- Rotas grundförmodan , Open Problem Garden.