Erdős–Faber–Lovász gissning

Ett exempel på Erdős–Faber–Lovász-förmodan: en graf som bildas av fyra klick med fyra hörn vardera, varav två som helst skär varandra i en enda vertex, kan vara fyrfärgad.

Inom grafteorin är Erdős –Faber–Lovász-förmodan ett problem om graffärgning , uppkallad efter Paul Erdős , Vance Faber och László Lovász , som formulerade den 1972. Den säger:

Om k kompletta grafer , var och en med exakt k hörn, har egenskapen att varje par av kompletta grafer har högst en delad vertex, då kan föreningen av graferna färgas korrekt med k färger.

Ett bevis på gissningen för alla tillräckligt stora värden av k tillkännagavs 2021 av Dong Yeap Kang, Tom Kelly, Daniela Kühn , Abhishek Methuku och Deryk Osthus .

Likvärdiga formuleringar

Haddad & Tardif (2004) introducerade problemet med en berättelse om sittplatser i kommittéer: anta att det på en universitetsavdelning finns k kommittéer, var och en bestående av k fakultetsmedlemmar, och att alla kommittéer träffas i samma rum, vilket har k stolar. Antag också att högst en person tillhör skärningspunkten mellan två kommittéer. Är det möjligt att tilldela utskottsledamöterna ordföranden på ett sådant sätt att varje ledamot sitter på samma ordförande för alla de olika utskotten som han eller hon tillhör? I denna modell av problemet motsvarar fakultetsmedlemmarna grafens hörn, kommittéer motsvarar kompletta grafer och ordförandena motsvarar vertexfärger.

En linjär hypergraf (även känd som partiellt linjärt utrymme ) är en hypergraf med egenskapen att varannan hyperkant har högst en vertex gemensam. En hypergraf sägs vara enhetlig om alla dess hyperkanter har samma antal hörn som varandra. De n klicken av storlek n i Erdős–Faber–Lovász-förmodan kan tolkas som hyperkanterna av en n -uniform linjär hypergraf som har samma hörn som den underliggande grafen. I detta språk säger Erdős–Faber–Lovász gissningar att, givet varje n -uniform linjär hypergraf med n hyperkanter, kan man n -färga topparna så att varje hyperedge har en vertex av varje färg.

En enkel hypergraf är en hypergraf där högst en hyperkant förbinder vilket par av hörn som helst och det inte finns några hyperkanter av storlek högst en. I graffärgsformuleringen av Erdős–Faber–Lovász-förmodan är det säkert att ta bort hörn som tillhör en enskild klick, eftersom deras färgning inte ger några svårigheter; när detta är gjort, bildar hypergrafen som har en vertex för varje klick och en hyperedge för varje grafvertex en enkel hypergraf. Och hypergrafdualen av vertexfärgning är kantfärgning . Således är Erdős–Faber–Lovász-förmodan likvärdig med påståendet att varje enkel hypergraf med n hörn har kromatiskt index (kantfärgningsnummer) som mest n .

Grafen för Erdős-Faber-Lovász-förmodan kan representeras som en skärningsgraf av uppsättningar: mot varje hörn av grafen, motsvarar uppsättningen av klicken som innehåller den vertexen, och koppla ihop två valfria hörn med en kant närhelst deras motsvarande mängder har en icke-tom korsning. Med hjälp av denna beskrivning av grafen kan gissningen omformuleras enligt följande: om någon familj av mängder har n totala element, och vilka två uppsättningar som helst skär varandra i högst ett element, då kan skärningsgrafen för mängderna vara n -färgad.

Skärningsnumret för en graf G är det minsta antalet element i en familj av uppsättningar vars skärningsdiagram är G , eller motsvarande det minsta antalet hörn i en hypergraf vars linjediagram är G . Klein & Margraf (2003) definierar det linjära skärningsnumret för en graf på liknande sätt som det minsta antalet hörn i en linjär hypergraf vars linjegraf är G . Som de observerar är Erdős–Faber–Lovász-förmodan likvärdig med påståendet att det kromatiska talet för en graf som mest är lika med dess linjära skärningsnummer.

Haddad & Tardif (2004) presenterar en annan ännu likvärdig formulering, i termer av teorin om kloner .

Historia, delresultat och eventuella bevis

Paul Erdős , Vance Faber och László Lovász formulerade den ofarliga gissningen vid en fest i Boulder Colorado i september 1972. Dess svårighet insågs bara långsamt. Paul Erdős erbjöd ursprungligen 50 USD för att bevisa gissningen ja, och höjde senare belöningen till 500 USD. Faktum är Paul Erdős ansåg att detta var ett av hans tre mest favoritkombinatoriska problem.

Chiang & Lawler (1988) bevisade att det kromatiska antalet grafer i gissningarna är högst 3 k /2 − 2 , och Kahn (1992) förbättrade detta till k + o ( k ) .

År 2021, nästan 50 år efter att den ursprungliga gissningen angavs, löstes den för alla tillräckligt stora n .

Relaterade problem

Det är också av intresse att betrakta det kromatiska antalet grafer som bildas som föreningen av k klicker med k hörn vardera, utan att begränsa hur stora skärningspunkterna mellan par av klick kan vara. I det här fallet är det kromatiska talet för deras förening högst 1+ k √ k − 1 , och vissa grafer som bildas på detta sätt kräver så många färger.

En version av gissningen som använder det kromatiska bråktalet i stället för det kromatiska talet är känt för att vara sann. Det vill säga, om en graf G bildas som föreningen av k k -klickar som skär parvis i högst en vertex, så kan G vara k -färgad.

Inom ramen för kantfärgning av enkla hypergrafer, definierar Hindman (1981) ett tal L från en enkel hypergraf som antalet hypergrafiska hörn som hör till en hyperkant av tre eller flera hörn. Han visar att för varje fast värde på L räcker en finit beräkning för att verifiera att gissningen är sann för alla enkla hypergrafer med det värdet på L . Baserat på denna idé visar han att gissningen verkligen är sann för alla enkla hypergrafer med L ≤ 10 . I formuleringen av färgningsgrafer bildade av sammanslutningar av klick visar Hindmans resultat att gissningen är sann när som mest tio av klicken innehåller en vertex som tillhör tre eller flera klick. I synnerhet gäller det för n ≤ 10 .

Se även

Anteckningar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Erdős–Faber–Lovász_conjecture&oldid=1136215525 "