D-intervall hypergraf
I grafteorin är en d -intervallhypergraf en sorts hypergraf som är konstruerad med hjälp av intervall av reella linjer . Parametern d är ett positivt heltal . Hörnen i en hypergraf med d -intervall är punkterna på d disjunkta linjer (det finns alltså oräkneligt många hörn) . Kanterna på grafen är d - tuplingar av intervall, ett intervall på varje reell linje .
Det enklaste fallet är d = 1 . Spetsmängden för en hypergraf med 1 intervall är uppsättningen av reella tal; varje kant i en sådan hypergraf är ett intervall av den verkliga linjen. Till exempel, uppsättningen { [−2, −1], [0, 5], [3, 7] } definierar en hypergraf med 1 intervall. Notera skillnaden från en intervallgraf : i en intervallgraf är hörnen intervallen (en ändlig mängd ) ; i en hypergraf med 1 intervall är hörnen alla punkter i den verkliga linjen (en oräknelig mängd ) .
Som ett annat exempel, i en hypergraf med 2 intervall, är vertexuppsättningen den disjunkta föreningen av två reella linjer, och varje kant är en förening av två intervall: en i linje #1 och en i linje #2.
Följande två begrepp definieras för d -intervallhypergrafer precis som för finita hypergrafer:
- En matchning är en uppsättning icke-korsande kanter, dvs en uppsättning icke-korsande d -intervall. Till exempel, i 1-intervallshypergrafen { [−2, −1], [0, 5], [3, 7] } är mängden { [−2, −1], [0, 5] } en matchning av storlek 2, men mängden { [0, 5], [3, 7] } är inte en matchning eftersom dess element skär varandra. Den största matchande storleken i H betecknas med ν ( H ) .
- En täckning eller en transversal är en uppsättning av hörn som skär varje kant, dvs en uppsättning punkter som skär varje d -intervall. Till exempel, i 1-intervallshypergrafen { [−2, −1], [0, 5], [3, 7] } är mängden {−1.5, 4} en täckning av storlek 2, men mängden { −1.5, 1} är inte en täckning eftersom den inte skär kanten [3, 7] . Den minsta tvärgående storleken i H betecknas med τ ( H ) .
ν ( H ) ≤ τ ( H ) är sant för varje hypergraf H.
Tibor Gallai bevisade att i en 1-intervallshypergraf är de lika: τ ( H ) = ν ( H ) . Detta är analogt med Kőnigs teorem för tvådelade grafer .
Gabor Tardos bevisade att i en 2-intervallshypergraf, τ ( H ) ≤ 2 ν ( H ) , och den är tät (dvs varje 2-intervallshypergraf med en matchning av storleken m kan täckas av 2 m punkter) .
Kaiser bevisade att i en d -intervall hypergraf, τ ( H ) ≤ d ( d – 1) ν ( H ) , och dessutom kan varje d -intervall hypergraf med en matchning av storleken m täckas av vid d ( d − 1) m punkter, ( d − 1) m punkter på varje linje.
Frick och Zerbib visade sig vara en färgstark (" regnbåge ") version av detta teorem.