Nelson-Erdős-Hadwiger problem

Nelson-Erdős-Hadwiger-problemet  är ett problem med kombinatorisk geometri , som ursprungligen ställdes som ett problem med färgning eller kromatiskt antal av euklidiska rymden .

Från och med 2022 är uppgiften fortfarande öppen .

Förklaring av problemet

Nelson-Erdős-Hadwiger-problemet väcker frågan om det minsta antalet färger där ett n -dimensionellt euklidiskt utrymme kan färgas på ett sådant sätt att det inte finns några punkter av samma färg som är på ett avstånd av 1 från varandra Detta tal kallas det kromatiska talet för det n -dimensionella euklidiska rummet.

Samma problem är vettigt för ett godtyckligt metriskt utrymme . I det allmänna fallet, låt vara  ett metriskt utrymme och . Vilket är det minsta antalet färger som kan målas på ett sådant sätt att det inte kan finnas ett fast avstånd mellan punkter med samma färg ? Eller vad är det kromatiska numret för det metriska rummet med avseende på det förbjudna avståndet ?

Enligt de Bruijn-Erdős sats räcker det att lösa problemet för alla finita delmängder av punkter.

Vissa resultat

Små dimensioner

Det är uppenbart att det kromatiska antalet endimensionella rymd är lika med två, men svaret är inte känt ens för ett plan. Det är lätt att bevisa att det krävs minst 4 och högst 7 färger för att färga ett plan, men det gick inte att flytta vidare förrän 2018. Samtidigt föreslogs att svaret kan bero på valet av mängdlärans axiom [1] [2] . 2018 visade Aubrey de Gray att 4 färger inte räcker [3] .

Asymptotik

Låt vara  Hölder -metriken . Den övre gränsen [4] är bevisad :

,

och den nedre gränsen [5] är bevisad :

För vissa specifika värden är uppskattningarna nedan något förstärkta. [6] Således är det fastställt att det kromatiska numret av ett n-dimensionellt utrymme växer asymptotiskt exponentiellt, medan för Borsuk-problemet har de övre och nedre gränserna olika tillväxthastigheter.

Historik

I början av 1940 - talet regisserades den av Hugo Hadwiger och Pal Erdős , oberoende av dem, ungefär samtidigt, den gjordes också av Eduard Nelson och John Isbell .

1961 publicerades det berömda arbetet av Hadwiger om olösta matematiska problem , varefter kromatiska tal började studeras aktivt.

År 1976 föreslog M. Benda och M. Perles att betrakta det i det mest allmänna sammanhanget av metriska utrymmen.

Under 2018 fick Aubrey de Gray en enhetsdistansgraf med 1581 hörn, som inte kan färgas med 4 färger. Den matematiska gemenskapen har förbättrat di Grays resultat, från och med 2021 har den minsta kända grafen som inte kan målas i 4 färger 509 hörn [7] .

Efter Aubrey de Grays bevis kan svaret på Nelson-Erdős-Hadwiger-problemet bara vara 5, 6 eller 7.

Variationer och generaliseringar

Anteckningar

  1. ↑ Shelah, Saharon & Soifer, Alexander (2003), Axiom of choice and chromatic number of the plane , 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 > . Hämtad 29 april 2013. Arkiverad 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. Matematiker saknade fyra färger för att färga planet . N+1 (10 april 2018). Hämtad 10 april 2018. Arkiverad från originalet 10 april 2018.
  4. ↑ Larman DG, Rogers CA Realiseringen av avstånd inom mängder i Euklidiska rymden// Mathematika. - 1972. -19. - C. 1-24.
  5. ↑ Frankl P., Wilson RM Skärningssatser med geometriska konsekvenser// Combinatorica. - 1981. - 1. - C. 357-368.
  6. ↑ A. M. Raigorodsky, "Around the Borsuk Hypothesis" . Hämtad 24 maj 2013. Arkiverad från originalet 14 december 2014.
  7. ↑ Hadwiger-Nelson problem - Polymath Wiki . Hämtad 24 mars 2021. Arkiverad från originalet 12 april 2021.

Litteratur