Hadwigerova domněnka (kombinatorická geometrie) - Hadwiger conjecture (combinatorial geometry) - Wikipedia

Trojúhelník může být zakryt třemi menšími kopiemi sebe sama; čtverec vyžaduje čtyři menší kopie

Nevyřešený problém v matematice: Může každý ${ displaystyle n}$-rozměrné konvexní tělo bude zakryto ${ displaystyle 2 ^ {n}}$ menší kopie sebe sama? (více nevyřešených úloh z matematiky)

v kombinatorická geometrie, Hadwigerův dohad uvádí, že jakýkoli konvexní tělo v n-dimenzionální Euklidovský prostor lze pokrýt 2ⁿ nebo méně menších těl homotetický s původním tělem, a to navíc, horní hranice 2ⁿ je nutné tehdy a jen tehdy, pokud je tělo a rovnoběžnostěn. Existuje také ekvivalentní formulace, pokud jde o počet reflektorů potřebných k osvětlení těla.

Hadwigerova domněnka je pojmenována po Hugo Hadwiger, který jej v roce 1957 zařadil na seznam nevyřešených problémů; to však bylo dříve studováno Levi (1955) a nezávisle, Gohberg a Markus (1960). Kromě toho existuje jiný Hadwigerův dohad vztahující se k zbarvení grafu —A v některých zdrojích se geometrický Hadwigerův dohad také nazývá Domněnka Levi – Hadwiger nebo Hadwiger – Levi pokrývající problém.

Domněnka zůstává nevyřešená ani ve třech rozměrech, ačkoli dvourozměrný případ byl vyřešen Levi (1955).

Formální prohlášení

Formálně je Hadwigerova domněnka: If K. je jakýkoli ohraničený konvexní sada v n-dimenzionální Euklidovský prostor Rⁿ, pak existuje sada 2ⁿ skaláry s_i a sada 2ⁿ překladové vektory proti_i takové, že všechny s_i leží v rozsahu 0 <s_i <1 a

${ displaystyle K subseteq bigcup _ {i = 1} ^ {2 ^ {n}} s_ {i} K + v_ {i}.}$

Horní mez je dále nutná, pokud K. je rovnoběžnostěn, v takovém případě všechny 2ⁿ skalárů lze zvolit tak, aby se rovnaly 1/2.

Alternativní formulace s osvětlením

Jak ukazuje Boltyansky, problém je ekvivalentní problému osvětlení: kolik reflektorů musí být umístěno mimo neprůhledné konvexní těleso, aby bylo možné zcela osvětlit jeho exteriér? Pro účely tohoto problému se těleso považuje za osvětlené pouze tehdy, pokud pro každý bod hranice tělesa existuje alespoň jeden světlomet, který je od tělesa oddělen všemi tečná roviny protínající tělo v tomto bodě; tedy i když tváře krychle mohou být osvětleny pouze dvěma reflektory, roviny tečné k jejím vrcholům a hranám způsobují, že k tomu, aby byla plně osvětlena, potřebuje mnohem více světel. U každého konvexního tělesa se ukázalo, že počet světlometů potřebných k úplnému osvětlení odpovídá počtu menších kopií tělesa, které jsou potřebné k jeho zakrytí.^[1]

Příklady

Jak je znázorněno na obrázku, trojúhelník může být zakryt třemi menšími kopiemi sebe sama a obecněji v jakékoli dimenzi a simplexní může být pokryta n + 1 jeho kopií, zmenšen faktorem n/(n + 1). Pokrytí čtverce menšími čtverci (s rovnoběžnými stranami originálu) však vyžaduje čtyři menší čtverce, protože každý může pokrýt pouze jeden ze čtyř rohů většího čtverce. Ve vyšších rozměrech krycí a hyperkrychle nebo obecněji rovnoběžnostěn u menších homotetických kopií stejného tvaru vyžaduje samostatnou kopii pro každou z vrcholy původní hyperkrychle nebo rovnoběžnostěnu; protože tyto tvary mají 2ⁿ vrcholy, 2ⁿ jsou nutné menší kopie. Toto číslo je také dostatečné: kostka nebo hranol může být kryta 2ⁿ kopie, zmenšené o faktor 1/2. Hadwigerova domněnka je, že nejhorším případem tohoto problému jsou rovnoběžnostěny a že jakékoli jiné konvexní tělo může být pokryto méně než 2ⁿ menší kopie sebe sama.^[1]

Známé výsledky

Dvojrozměrný případ byl vyřešen Levi (1955): každá dvourozměrná ohraničená konvexní množina může být pokryta čtyřmi menšími kopiemi sebe sama, přičemž čtvrtá kopie je nutná pouze v případě rovnoběžníků. Domněnka však zůstává otevřená ve vyšších dimenzích, s výjimkou některých zvláštních případů. Nejznámější asymptotická horní hranice počtu menších kopií potřebných k zakrytí daného těla je^[1]

${ displaystyle displaystyle 4 ^ {n} (5n ln n).}$

Pro malé ${ displaystyle n}$ horní hranice ${ displaystyle (n + 1) n ^ {n-1} - (n-1) (n-2) ^ {n-1}}$ zřízen Lassak (1988) je lepší než asymptotická. Ve třech rozměrech je známo, že vždy stačí 16 kopií, ale to je ještě daleko od domnělé hranice 8 kopií.^[1]

Je známo, že domněnka platí pro určité speciální třídy konvexních těles, včetně symetrických mnohostěnů a tělesa konstantní šířky ve třech rozměrech.^[1] Počet kopií potřebných k pokrytí všech zonotop je nanejvýš ${ displaystyle (3/4) 2 ^ {n}}$, zatímco pro tělesa s hladkým povrchem (tj. s jedinou tečnou rovinou na hraniční bod), maximálně ${ displaystyle n + 1}$ jsou zapotřebí menší kopie k zakrytí těla, jako Levi již prokázáno.^[1]

Viz také

• Borsukova domněnka na zakrytí konvexních těl sadami o menším průměru

Poznámky

Reference

• Boltjansky, V .; Gohberg, Izrael (1985), „11. Hadwigerova domněnka“, Výsledky a problémy v kombinatorické geometrii, Cambridge University Press, str. 44–46.
• Brass, Peter; Moser, William; Pach, János (2005), „3.3 Levi – Hadwiger Covering Problem and Illumination“, Výzkumné problémy v diskrétní geometrii, Springer-Verlag, str. 136–142.
• Gohberg, Izrael Ts.; Markus, Alexander S. (1960), „Určitý problém zakrytí konvexních množin homotetickými“, Izvestiya Moldavskogo Filiala Akademii Nauk SSSR (v Rusku), 10 (76): 87–90.
• Hadwiger, Hugo (1957), "Ungelöste Probleme Nr. 20", Elemente der Mathematik, 12: 121.
• Lassak, Marek (1988), „Pokrytí hranice konvexní sady dlaždic“, Proceedings of the American Mathematical Society, 104 (1): 269–272, doi:10.1090 / s0002-9939-1988-0958081-7, PAN  0958081.
• Levi, Friedrich Wilhelm (1955), „Überdeckung eines Eibereiches durch Parallelverschiebungen seines offenen Kerns“, Archiv der Mathematik, 6 (5): 369–370, doi:10.1007 / BF01900507.