Erdős-Faber-Lovasin hypoteesi

Erdős-Faber-Lovasin arvelu on graafin väritysongelma , joka on nimetty Pal Erdősin , Vance Faberin ja Laszlo Lovasin mukaan, jotka muotoilivat sen vuonna 1972 [1] . Hypoteesi sanoo:

Jos k täydellistä graafia , joissa jokaisessa on täsmälleen k kärkeä, on se ominaisuus, että millä tahansa täydellisten graafien parilla on enintään yksi yhteinen kärki, niin graafien liitto voidaan värjätä k  värillä.

Vuonna 2021 julkaistiin esipainos, jossa oli todiste suuren k :n olettamuksesta [2] .

Vastaavat formulaatiot

Addad ja Tardif [3] esittivät ongelman komitean luomisen historiassa – kuvitellaan, että yliopiston tiedekunnassa on k komiteaa, joissa kussakin on k jäsentä, ja kaikki komiteat jakavat saman huoneen k paikalla. Oletetaan, että kahdessa komiteassa on enintään yksi henkilö. Onko mahdollista antaa puheenjohtaja jokaiselle valiokunnan jäsenelle siten, että jokainen jäsen istuu samassa puheenjohtajassa kaikissa valiokunnissa? Tässä tehtävämallissa toimikunnan jäsenet vastaavat graafin kärkipisteitä, komiteat täyttävät graafit ja tuolit vastaavat värejä.

Lineaarinen hypergrafi (tunnetaan myös nimellä osittain lineaarinen avaruus ) on hypergraafi , jolla on ominaisuus, että kahdella hyperreunalla on enintään yksi kärki. Hypergrafin sanotaan olevan homogeeninen, jos sen kaikilla hyperreunoilla on sama määrä osapisteitä. Erdős–Faber–Lovas- oletuksessa n koon n klikkiä voidaan tulkita n -homogeenisen viivahypergrafin hyperreunuksiksi, joilla on samat kärjet kuin alla olevalla graafilla. Tällä kielellä Erdős-Faber-Lovasin oletus väittää, että jos mikä tahansa n -homogeeninen viivahypergrafi, jossa on n hyperreunaa, on mahdollista värittää kärjet n värillä siten, että jokaisessa hyperreunassa on yksi piste jokaista väriä [4] .

Yksinkertainen hypergrafi on hypergrafi, jossa korkeintaan yksi reuna yhdistää minkä tahansa pisteparin ja jossa ei ole yhden suuruisia hyperreunoja. Erdős-Faber-Lovas-oletuksen muotoilussa graafin värityksen kielellä voidaan helposti poistaa vain yhdelle klikkille kuuluvat kärjet, koska niiden väritys ei aiheuta vaikeuksia. Kun tämä on tehty, hypergrafi, jossa on klikejä kärkeinä ja graafin kärjet hyperreunaina, on yksinkertainen hypergraafi. Hypergraafin kaksoispistevärjäys on reunavärjäys . Siten Erdős-Faber-Lovas-oletus vastaa väitettä, että minkä tahansa yksinkertaisen hypergraafin, jossa on n kärkeä, kromaattinen indeksi (väritysvärien lukumäärä) ei ylitä n :ää [5] .

Erdős-Faber-Lovas-oletuksen graafi voidaan esittää joukkojen leikkauspisteiden graafina - graafin kukin huippu vastaa kärjen sisältävää klikkijoukkoa, ja mitkä tahansa kaksi kärkeä on yhdistetty reunalla, jos niitä vastaavilla joukoilla on ei-tyhjä risteys. Tämän graafin kuvauksen avulla hypoteesi voidaan esittää seuraavasti: jos tietyssä perheessä on yhteensä n alkiota ja missä tahansa kahdessa leikkauspisteen joukossa on enintään yksi alkio, näiden joukkojen leikkauskaavio voidaan värittää n värillä . [6] .

Graafin G leikkausnumero on yhtä suuri kuin niiden joukkojen perheen alkioiden minimimäärä, joiden leikkausgraafi osuu G :n kanssa , tai vastaavasti pienin määrä hypergrafipisteitä, joiden viivagraafi on sama kuin G . Klein ja Margraf [7] määrittävät samalla tavalla graafin lineaarisen leikkauspisteen määrän pisteiden minimimääräksi lineaarisessa hypergraafissa, jonka viivagraafi on sama kuin G . Kuten he huomauttavat, Erodes-Faber Lovas -oletus vastaa sanomista, että minkä tahansa graafin kromaattinen luku ei ylitä sen lineaarista leikkausnumeroa.

Haddad ja Tardif [3] antavat erilaisen, mutta silti vastaavan muotoilun klooniteorian kannalta .

Historia ja osatulokset

Pal Erdős , Vance Faber ja Laszlo Lovas muotoilivat olettamuksen vuonna 1972 [1] . Pal Erdős tarjosi aluksi 50 dollaria todistaakseen hypoteesin ja nosti myöhemmin palkkion 500 dollariin [1] [8] .

Chiang ja Lawler [9] osoittivat, että graafin kromaattinen luku arvelussa ei ylitä 3 k / 2 − 2 , ja Kahn [10] paransi tämän arvon k + o ( k ) .

Aiheeseen liittyvät tehtävät

On myös mielenkiintoista tarkastella niiden graafien kromaattista lukumäärää, jotka muodostuvat k klikin ja k pisteen yhdistämisestä kussakin ilman, että klikkiparien leikkauspisteen kokoa rajoitetaan. Tässä tapauksessa niiden liiton kromaattinen luku ei ylitä ja jotkin tällä tavalla muodostetut graafit vaativat täsmälleen tämän määrän värejä [11] [12] .

Arvauksen version, joka käyttää kromaattista murtolukua kromaattisen luvun sijaan, tiedetään olevan oikea. Eli jos graafi G muodostuu k k -klikkien liitosta, jotka leikkaavat pareittain enintään kahdessa kärjessä, graafi G voidaan värjätä k -väreillä [13] .

Yksinkertaisten hypergraafien reunavärjäyksen tapauksessa Hindman [6] määrittelee luvun L yksinkertaiselle hypergraafille niiden hypergrafipisteiden lukumääräksi, jotka kuuluvat hyperreunaan, jossa on vähintään kolme kärkeä. Hän osoitti, että minkä tahansa L :n kiinteän arvon kohdalla sen tarkistaminen, että olettamus on totta kaikille yksinkertaisille kaavioille, joissa on , vaatii rajallisen määrän laskentaa. Tämän ajatuksen perusteella hän osoitti, että olettamus on totta kaikille yksinkertaisille hypergrafeille, joissa on . Klikkien liiton muodostamien graafien värjäyksen muotoilussa Hindmanin tulos osoittaa, että olettamus on totta, jos korkeintaan kymmenen klikejä sisältää pisteitä, jotka kuuluvat kolmeen tai useampaan klikkiin. Tämä pätee erityisesti .

Katso myös

Muistiinpanot

  1. ↑ 1 2 3 Erdős, 1981 .
  2. ↑ Kelsey Houston-Edwards. Matemaatikot ratkaisevat Erdősin väritysoletuksen  . Quanta (5. huhtikuuta 2021). Haettu 5. huhtikuuta 2021. Arkistoitu alkuperäisestä 5. huhtikuuta 2021.
  3. ↑ 1 2 Haddad, Tardif, 2004 .
  4. ↑ Romero, Sánchez Arroyo, 2007 .
  5. ↑ Chiang, Lawler, 1988 . Hindman (( Hindman 1981 )) kuvaa vastaavaa ongelmaa joukkojärjestelmänä hypergraafien sijaan.
  6. ↑ 12 Hindman , 1981 .
  7. ↑ Klein, Margraf, 2003 .
  8. ↑ Chung, Graham, 1998 .
  9. ↑ Chiang, Lawler, 1988 .
  10. ↑ Kahn, 1992 .
  11. ↑ Erdős, 1991 .
  12. ↑ Horak, Tuza, 1990 .
  13. ↑ Kahn, Seymour, 1992 .

Kirjallisuus