Linjediagram av en hypergraf

En linjegraf för en hypergraf  är en graf vars vertexuppsättning är hypergrafens hyperkantuppsättning och två hyperkanter ligger intill om de har en icke-tom skärningspunkt. Med andra ord är linjegrafen för en hypergraf skärningsgrafen för en familj av ändliga mängder. Konceptet är en generalisering av en linjegraf av en vanlig graf.

Frågor om linjediagram av hypergrafer är ofta generaliseringar av frågor om linjediagram av vanliga grafer. Till exempel, en hypergraf vars alla kanter är av storlek k kallas k-uniform' (en 2-uniform hypergraf är en vanlig graf). Inom hypergrafteorin är det ofta naturligt att kräva k -likformighet. Vilken vanlig graf som helst är ett linjediagram av någon hypergraf, men om vi fixar kantstorleken k (antalet punkter i uppsättningen som hör till kanten), är inte varje graf ett linjediagram av någon k - enhetlig graf. Huvuduppgiften är att beskriva linjediagram för varje .

En hypergraf kallas linjär om något par av hyperkanter har högst en vertex i skärningspunkten. Vilken graf som helst är en linjegraf, inte bara av någon hypergraf, utan också av någon linjär hypergraf [1] .

Linjediagram av k -uniforma hypergrafer,

Beinecke [2] beskrev linjegraferna för vanliga grafer genom att lista 9 förbjudna inducerade subgrafer (se posten om linjediagram ). Ingen beskrivning av förbjudna inducerade subgrafer är känd för linjegraferna för k-uniforma hypergrafer för någon , och Lovas [3] visade att det inte finns någon sådan beskrivning i form av en finit lista för k = 3.

Kraus [4] beskrev linjediagram av vanliga grafer i termer av klicktäckning ( Se linjediagram ). En global beskrivning av Kraus-typen för linjediagram av k -uniforma hypergrafer för alla ges av Berge [1] .

Linjediagram av k -uniforma linjehypergrafer för

En global beskrivning av Kraus-typen för linjediagram av k -uniforma linjehypergrafer för alla ges av Naik, Rao, Srikhande och Singhi [5] . Samtidigt fann de ett ändligt antal förbjudna inducerade subgrafer för linjära 3-uniforma hypergrafer med en minsta vertexgrad på minst 69. Metelsky och Tyshkevich [6] och Jakobson, Kezdi, Lekhel [7] förbättrade denna gräns till 19 , medan Skums, Suzdal och Tyszkiewicz [8] reducerade detta till 16. Metelsky och Tyszkiewicz [6] bevisade också att det för k > 3 inte finns någon sådan lista för linjära k -uniforma hypergrafer, oavsett vilken gradbegränsning som är pålagd.

Komplexiteten med att hitta en beskrivning av linjära k -uniforma hypergrafer är att det finns oändligt många förbjudna genererade subgrafer. För att ge ett exempel, för m > 0, ta en kedja med m diamantgrafer så att diamanterna delar andra ordningens hörn, och lägg till några hängande hörn, som visas i figuren, för att få en av familjerna med minimala förbjudna subgrafer [5 ] [9] .

Det finns ett antal intressanta beskrivningar för linjegraferna för linjära k -uniforma hypergrafer som ges av olika författare [10] , med förbehåll för begränsningar för den minsta graden av hörn eller den minsta graden av kanter. Den minsta kantgraden för att beskriva linjediagram av k -uniform linjehypergrafer för alla , vilket inte är mindre i Naik, Rao, Srikhandes och Sighis arbete [5] , reduceras till i verk av Jakobson, Kezdi, Lehel [7 ] och Zverovich [11] .

Komplexiteten i att känna igen linjediagram av linjära k -uniforma hypergrafer utan begränsningar på minsta grad (eller minsta grad av kanter) är okänd. För k = 3 och en lägsta grad på minst 19 är igenkänning möjlig i polynomtid [7] [6] ). Skums, Suzdal och Tyszkiewicz [8] sänkte minimigraden till 10.

Det finns många olösta problem och hypoteser i verk av Nike et al., Jacobson et al., Metelsky et al., och Zverovich.

Anteckningar

  1. ↑ 12 Berge , 1989 .
  2. ↑ Beineke, 1968 .
  3. ↑ Lovász, 1977 .
  4. ↑ Krausz, 1943 .
  5. ↑ 1 2 3 Naik, Rao, Shrikhande, Singhi, 1980 .
  6. ↑ 1 2 3 Metelsky och Tyshkevich, 1997 .
  7. ↑ 1 2 3 Jacobson, Kézdy, Lehel, 1997 .
  8. ↑ 1 2 Skums, Suzdal', Tyshkevich, 2009 .
  9. ↑ Naik, Rao, Shrikhande, Singhi, 1982 .
  10. ↑ Naik, Rao, Shrikhande, Singhi, 1980 ; Naik, Rao, Shrikhande, Singhi 1982 ; Jacobson, Kézdy, Lehel, 1997 ; Metelsky och Tyshkevich, 1997 ; Zverovich, 2004
  11. ↑ Zverovich, 2004 .

Litteratur