Obrovské podkúbické grafy a čísla, ktoré ich definujú

V poslednom videu od Numberphile sa Richard Elwes ponoril do fascinujúceho sveta teórie grafov a predstavil výzvu týkajúcu sa takzvaných podkúbických grafov. Ide o grafy, v ktorých každý uzol má najviac tri hrany. Video skúma, ako tieto grafy môžu "skrývať" iné grafy vo svojom usporiadaní a aké obrovské čísla vznikajú pri pokuse nájsť najdlhšie možné sekvencie týchto grafov. Výsledné čísla sú tak rozsiahle, že prekonávajú známe gigantické hodnoty ako Grahamovo číslo.

Kľúčové poznatky

• Podkúbický graf: Graf, v ktorom každý uzol má najviac tri hrany.
• Topologický minor: Jeden graf môže byť topologickým minorom iného, ak je možné z neho vytvoriť prvý pomocou operácií s hranami (mazanie alebo kontrakcia).
• Výzva SSCG: Nájsť najdlhšiu sekvenciu podkúbických jednoduchých grafov, kde n-tý graf má najviac n uzlov a žiadny predošlý graf sa v ňom nevyskytuje.
• Obrovské čísla: Najdlhšie známe sekvencie SSCG vedú k číslam, ktoré výrazne presahujú známe gigantické hodnoty ako Grahamovo číslo a tree(3).

Čo sú to podkúbické grafy?

Predstavte si sieť bodov (uzlov) spojených líniami (hrán). To je základná definícia grafu. Podkúbický graf je špeciálny typ grafu, kde každý uzol má najviac tri hrany prichádzajúce k nemu. Dôležité je, že dĺžka hrán alebo pozícia uzlov nemá v tomto kontexte žiadny význam – počítajú sa len samotné spojenia.

Hľadanie skrytých grafov: Koncept topologického minora

Richard Elwes predstavil fascinujúci koncept "skrývania" grafov. Jeden graf môže byť považovaný za topologický minor iného, ak je možné z neho vytvoriť prvý pomocou jednoduchých operácií – buď odstránením hrán alebo uzlov, alebo stiahnutím hrany (kontrakciou). To znamená, že jeden graf sa nachádza "vnútri" druhého v zmysle jeho štruktúry.

Výzva SSCG: Hľadanie najdlhších sekvencií

Hlavnou témou videa je výzva SSCG – hľadáme najdlhšiu možnú sekvenciu podkúbických jednoduchých grafov, kde n-tý graf v sekvencii má najviac n uzlov a žiadny predošlý graf sa v ňom nevyskytuje. Začínajúc jedným uzlom je možné vytvoriť len dva grafy: jeden uzol a potom prázdny graf (bez uzlov a hrán). Začínajúc dvoma uzlami, najdlhšia sekvencia obsahuje päť grafov.

Čísla, ktoré ohromujú: Prekračovanie Grahamovho čísla

Skutočne šokujúcim zistením je, že pri pokuse nájsť najdlhšie sekvencie SSCG začínajúc grafmi s troma uzlami, sa dostávame k číslam, ktoré sú obrovské. Tieto čísla výrazne presahujú známe gigantické hodnoty ako Grahamovo číslo a tree(3). Richard Elwes uviedol, že toto číslo je dokonca väčšie ako tree of tree(3), čo ilustruje jeho nepredstaviteľnú veľkosť.

Graf Minor Theorem: Matematický základ

Video sa dotýka aj dôležitého matematického konceptu – Graph Minor Theorem. Toto tvrdenie hovorí, že akákoľvek nekonečná množina konečných grafov obsahuje dvojicu, kde jeden je minorom druhého. V kontexte podkúbických grafov to znamená, že vždy nájdeme dva grafy v našej sekvencii, kde jeden "skrýva" druhý.

Záverečné úvahy a odporúčania

Video od Numberphile predstavuje fascinujúci pohľad do sveta teórie grafov a ukazuje, ako sa z jednoduchých konceptov môžu vynoriť obrovské matematické výzvy a čísla, ktoré prekonávajú naše bežné chápanie veľkosti. Ak vás zaujímajú gigantické čísla a komplexná matematika, toto video určite stojí za pozretie.

Zdroje:

• Richard Elwes na University of Leeds: https://eps.leeds.ac.uk/maths/staff/4018/dr-richard-elwes
• Kniha Richarda Elwesa: https://amzn.to/4fJIhHE

Približne 139 gCO₂ bolo uvoľnených do atmosféry a na chladenie sa spotrebovalo 0.70 l vody za účelom vygenerovania tohoto článku.