Vita:Graham-szám

Ez a szócikk témája miatt a matematikai műhely érdeklődési körébe tartozik.
Bátran kapcsolódj be a szerkesztésébe! Besorolatlan Ezt a szócikket még nem sorolták be a kidolgozottsági skálán. Nem értékelt Ezt a szócikket még nem értékelték a műhely fontossági skáláján. Értékelő szerkesztő: ismeretlen

épp most fordítom a Graham számát az angol definícióból, és nem tudom annak a jelentését kitalálni, hogy "that lies in a plane". Lehet hogy nincs túl fontos jelentése, ezért kihagytam a cikkből, mivel anélkül is van értelme a mondatnak.

valami olyasmi, ami egy síkban fekszik. Alensha 2005. június 4., 22:00 (CEST)

Ennek viszont nem sok értelmét látom, tekintve hogy a gráfot bárhogyan lehet ábrázolni (értsd 2-, 3-, akárhány dimenzióban), és így értelmét veszti az hogy egy síkban van egy gráfban 4 pont. Arra viszont most jöttem rá, hogy azért van ez az n-dimenziós hiperkocka, hogy egy 2ⁿ-csúcsú gráfot kapjunk, és így szerintem könnyebb kiszámolni és kezelni n legkisebb értékét, mintha csak egy k-csúcsú gráfot néznénk (tekintve, hogy milyen baromi nagy ez a szám).

De a gyakorlati hasznát még nem látom. Lacipac 2005. június 13., 13:25 (CEST)

Szerintem kérdezd Grahamtól, mert más nem hiszem, hogy meg tudja neked mondani. Vsz. még ő se. Gubb

A jelen helyzetben megfeledkezel arról, hogy itt nem izomorfiáról van szó. Ez a gráf egy hiperkocka, ami a térbe van ágyazva. Nincs szó arról, hogy kiteríthetnénk, vagy izomorf módon ábrázolhatnánk. Emiatt van értelme (valszeg) annak, hogy 4 pont egy síkba essen. Gubb 2005. június 13., 13:24 (CEST)

De azt mikor írták, hogy térbe van ágyazva? Ha nem lehetne egy csúcsot sem odébb mozgatni, akkor egy n-dimenziós gráfot kéne elképzelni, azt pedig, valljuk be, még Graham számára sem lenne könnyű feladat. A gráfoknak éppen az a lényege, hogy bárhogyan mozgathatjuk a csúcsait, ha az élek ugyanazokhoz a csúcsokhoz maradnak kötve, akkor az még ugyanaz (izomorf). Lacipac 2005. június 13., 13:33 (CEST)

Az n-dimenziós hiperkocka mindenképpen térbe van ágyazva. Graham pedig valószínűleg nem elképzeli, hanem mondjuk incidenciamátrixokkal dolgozik (lineáris algebra), számol (ez egy nagyon szokásos módszer többdimenziós térbeli gráfokra [is], és általában a kombinatorikában). Mellesleg van olyan matematikus, aki bevallottan el tud képzelni egy hétdimenziós egyenlet megoldáshalmazát a megfelelő térben, de nyolcdimenziós térben - szégyenkezve vallja - sajnos már kudarcot vall (ld. Staar: Matematikusok és teremtett világaik c. könyv). Ami a gráfizomorfiát illeti, az általad említett izomorf gráfosztályzás csak egy lehetőség. Vannak például - egy bizonyos értelemben - síkba nem rajzolható gráfok (ld. három ház, három kút-probléma). Szóval ne ítélj elhamarkodottan, nézz utánna részletesen, ha érdekel, de valszeg van értelme (ti. jelentése; mert hogy haszna van-e, az más kérdés a matekban). Gubb

Akkor a 'térbe ágyazás' fogalmát nem tudom :) . Amikor azt mondtam, hogy síkba lehet rajzolni, nem úgy értettem, hogy az élek nem fogják egymást metszeni (mivel nekem már a 4-dimenziós hiperkockában is megtaláltam a K₅-öt), hanem hogy le lehet vetíteni 2 dimenzióba (lásd http://en.wikipedia.org/wiki/Image:Hypercube_cubes.png). Lehet, hogy ugyanarra gondolok, mint te, csak matematikai tudásom hiányosságai miatt nem tudom olyan jól megfogalmazni, de én arra jutottam, hogy "a gráfban mindig van 4 pont, amely egy síkba esik és ugyanolyan a színük" (1280247 dimenzió esetén is 2-dimenziós síkról beszélve). Az igazad elismertem :) Lacipac 2005. június 13., 14:05 (CEST)

Consider an n-dimensional hypercube, and connect each pair of vertices to obtain a complete graph on 2ⁿ vertices. Then colour each of the edges of this graph using only the colours periwinkle and orange. What is the smallest value of n for which every possible such colouring must necessarily contain a single-coloured complete sub-graph with 4 vertices that lies in a plane?

Megjegyzés: a sík vajon valami hipersíkot jelent-e vagy kétdimenziós síkot? Vsz. az utóbbit. Gubb

Vegyünk egy n-dimenziós hiperkockát, és páronként kössük össze csúcsait (mindet minddel), úgy, hogy egy 2ⁿ csúcsú teljes gráfot kapjunk. Ezután színezzük ki az összes élt e gráfban két színnel (szilvalekvárzölddel és hipermangánlilával). Mekkora az n legkisebb értéke, ha minden lehetséges ilyen színezés olyan kell legyen, hogy tartalmaz egy egyszínű teljes részgráfot 4 egy síkban fekvő csúccsal? Gubb

anyááám, hogy vannak emberek, akik ilyesmit kitalálnak... :-D Alensha 2005. június 4., 22:29 (CEST)

Graham egy távközlési cégnél dolgozott matikusként (Belle labs? vagy At&At már nem tudom), elsődleges feladata a hálózatoptimalizálás. Hogy például van-e olyan telefonhálózat, ami a legkevesebb vezetékkel a legtöbb felhasználót éri el, meg ilyenek (csak a hasamra ütöttem és mondtam egy problémát, ennél mélyebb dolgokat csinált). Közben pogo-sticken ugrál össze-vissza, meg gumiszőnyegen (eredeti foglalkozása akrobata ugyanis). Meg pingpongozik Erdős Pállal. Irodalom: A prímember. E. P. kalandozásai a matematika végtelenjében vagy ilyesmi. Nagyon rossz könyv (majd rájössz , miért, ha elolvasod), és nagyon sok kritika is érte (például mert teljesen idiótának állítja be E. Pált - erről egy volt kollégája írt egy kritikát valahol a Ponticulus vagy melyik weblapon). Hol is tartottam? Ja a hálózatoptimalizálás. Na a hálózat egy gráf. És ha gráf, akkor mért ne lehetne kétszínű teljes gráf, aminek négy csúcsa egy síkban fexik.ˇHa meg már ilyen, akkor mért ne legyen rögtön n-dimenziós. Ha meg n-dimenziós, akkor miért ne legyen rögtön nemeuklideszi, nemarkhimédeszi, nemlineáris. Valahogy így jönnek ezek a dolgok. Gubb 2005. június 4., 22:36 (CEST)

" Újabban (2003-ban) azonban az Indianai Állami Egyetem munkatársa, Geoff Exoo kimutatta, hogy ennek a számnak legalább 11-nek kell lennie, és bizonyította is, hogy nagyobb annál. "

Ez az "azonban" mit állít ellentétbe egymással? Szerintem 11 alsó becslés n értékére, G pedig felső becslés n-re. Mi az ellentmondó ebben? (Javaslom húzzuk ki az azonbant.)Mozo 2005. november 11., 21:27 (CET)

Nyugodtan. Gubb ✍ 2005. november 11., 21:30 (CET)