Nelson-Erdős-Hadwiger problem

Nelson-Erdős-Hadwiger-problemet  er et problem med kombinatorisk geometri , oprindeligt stillet som et problem med farvning eller kromatisk antal af det euklidiske rum .

Fra 2022 er opgaven fortsat åben .

Udtalelse af problemet

Nelson-Erdős-Hadwiger-problemet rejser spørgsmålet om det mindste antal farver, hvor et n -dimensionelt euklidisk rum kan farves på en sådan måde, at der ikke er punkter af samme farve, der er i en afstand af 1 fra hinanden Dette tal kaldes det kromatiske tal for det n -dimensionelle euklidiske rum.

Det samme problem giver mening for et vilkårligt metrisk rum . I det generelle tilfælde, lad være  et metrisk mellemrum og . Hvad er det mindste antal farver , der kan males på en sådan måde, at der ikke kan være en fast afstand mellem punkter i samme farve ? Eller hvad er det kromatiske tal for det metriske rum i forhold til den forbudte afstand ?

Ifølge de Bruijn-Erdős sætning er det nok at løse problemet for alle endelige delmængder af punkter.

Nogle resultater

Små dimensioner

Det er indlysende, at det kromatiske antal af et-dimensionelt rum er lig med to, men svaret er ikke kendt selv for et fly. Det er nemt at bevise, at der kræves mindst 4 og højst 7 farver for at farve et fly, men det var først muligt at flytte længere frem i 2018. Samtidig blev det foreslået, at svaret kan afhænge af valget af mængdelærens aksiomer [1] [2] . I 2018 viste Aubrey de Gray , at 4 farver ikke er nok [3] .

Asymptotik

Lad være Hölder-  metrikken . Den øvre grænse [4] er bevist :

,

og den nedre grænse [5] er bevist :

For nogle specifikke værdier er estimaterne nedefra noget styrket. [6] Det er således fastslået, at det kromatiske tal for et n-dimensionelt rum vokser asymptotisk eksponentielt, mens for Borsuk-problemet har de øvre og nedre grænser forskellige væksthastigheder.

Historie

I begyndelsen af ​​1940'erne blev det instrueret af Hugo Hadwiger og Pal Erdős , uafhængigt af dem, omkring samme tid, det blev også lavet af Eduard Nelson og John Isbell .

I 1961 blev det berømte værk af Hadwiger offentliggjort om uløste matematiske problemer , hvorefter kromatiske tal begyndte at blive aktivt studeret.

I 1976 foreslog M. Benda og M. Perles at betragte det i den mest generelle kontekst af metriske rum.

I 2018 opnåede Aubrey de Gray en enhedsafstandsgraf med 1581 hjørner, som ikke kan farves med 4 farver. Det matematiske samfund har forbedret di Grays resultat, fra 2021 har den mindste kendte graf, der ikke kan males i 4 farver, 509 hjørner [7] .

Efter Aubrey de Grays bevis kan svaret på Nelson-Erdős-Hadwiger-problemet kun være 5, 6 eller 7.

Variationer og generaliseringer

Noter

  1. ↑ Shelah, Saharon & Soifer, Alexander (2003), Axiom of choice and chromatic number of the fly , Journal of Combinatorial Theory, Series A vol. 103 (2): 387–391, doi : 10.1016/S0097-3165(03) 00102-X , < http://www.uccs.edu/~faculty/asoifer/docs/AXIOMOFCHOICEinJCT.pdf > . Hentet 29. april 2013. Arkiveret 14. juni 2011 på Wayback Machine . 
  2. ↑ Soifer, Alexander (2008), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators , New York: Springer, ISBN 978-0-387-74640-1 
  3. ↑ Vladimir Korolev. Matematikere manglede fire farver til at farve flyet . N+1 (10. april 2018). Hentet 10. april 2018. Arkiveret fra originalen 10. april 2018.
  4. ↑ Larman DG, Rogers CA Realiseringen af ​​afstande inden for mængder i det euklidiske rum// Mathematika. - 1972. -19. - C. 1-24.
  5. ↑ Frankl P., Wilson RM Skæringssætninger med geometriske konsekvenser// Combinatorica. - 1981. - 1. - C. 357-368.
  6. ↑ A. M. Raigorodsky, "Omkring Borsuk-hypotesen" . Hentet 24. maj 2013. Arkiveret fra originalen 14. december 2014.
  7. ↑ Hadwiger-Nelson problem - Polymath Wiki . Hentet 24. marts 2021. Arkiveret fra originalen 12. april 2021.

Litteratur