3. 3. Probl´ ema (T): Tal´alhat´o-e minden L v´eges h´al´ohoz egy G v´eges csoport ´es annak H r´eszcsoportja u ´gy, hogy a [H, G] intervallum (azaz a G-beli, H-t tartalmaz´o r´eszcsoportok h´al´oja) L-lel izomorf legyen? Megjegyz´ es: A k´erd´es ekvivalens az univerz´alis algebra egyik legnevezetesebb probl´em´aj´aval: El˝oa´ll-e minden v´eges h´al´o v´eges algebra kongruenciah´al´ojak´ent? A csoportelm´eleti k´erd´est F. B¨orner nemr´egiben a k¨ovetkez˝o speci´alis esetek vizsg´alat´ara vezette vissza: (i) G majdnem egyszer˝ u, azaz l´etezik olyan S / G, hogy S egyszer˝ u ´es CG (S) = 1 (teh´at G r´esze S automorfizmuscsoportj´anak); (ii) G = HN , H ∩ N = 1, N / G, N = S1 × .. × Sk , ahol S1 , .., Sk p´aronk´ent izomorf egyszer˝ u csoportok, NH (S1 )-ben nincs Hnak nemtrivi´alis norm´aloszt´oja ´es S1 minden bels˝o automorfizmusa el˝oa´ll alkalmas NH (S1 )-beli elemmel val´o konjug´al´ask´ent. A (ii) eset kivizsg´al´asa ´ıg´eretesnek l´atszik. Kit˝ uz˝ o: P´alfy P´eter P´al
6. 6. Probl´ ema (T): Legyen G egy a h´aromdimenzi´os Euklideszi t´erben elhelyezked˝o g¨omb felsz´ıne. Legyenek tov´abb´a K1 , K2 , ..., Kn ´es F1 , F2 , ..., Fn G-n elhelyezked˝o p´aronk´ent diszjunkt k¨or¨ok. Mikor l´etezik f : G → IR3 ¨onmag´at mer˝olegesen metsz˝o immerzi´o, amelyre a kett˝osvonalak ´eppen az f (Ki ) = f (Fi ) g¨orb´ek? Megjegyz´ es: Az immerzi´o maxim´alis rang´ u (nem felt´etlen¨ ul bijekt´ıv) lek´epez´es. Egy immerzi´o ¨onmag´at mer˝olegesen metsz˝o, ha a k´ep ¨onmetsz´espontjaiban az ´erint˝os´ıkok mer˝olegesek (a feladat szempontj´ab´ol csak az sz´am´ıt, hogy nem esnek egybe). A 2n k¨or elhelyezked´ese le´ırhat´o a ter¨ uletek szomsz´eds´agi gr´afj´aval, ami sz¨ uks´egk´eppen fa. Ha megadjuk a f´at ´es a p´aros´ıt´ast, akkor ez (a probl´em´at tekintve) meghat´arozza a k¨or¨ok elhelyezked´es´et. Teh´at a k´erd´es az, hogy mely “p´aros´ıtott f´ahoz” tartoz´o elhelyez´esre van a fenti felt´eteleknek megfelel˝o immerzi´o. Kit˝ uz˝ o: Sz˝ ucs Andr´as
7. 7. Probl´ ema (T): Vegy¨ unk n pontot a s´ıkon. Tegy¨ uk fel, hogy a pontp´arok ´altal meghat´arozott ir´anyok sz´ama legfeljebb Cn, ahol C konstans. Bizony´ıtsuk be, hogy ha n el´eg nagy, akkor van a pontok k¨oz¨ ul legal´abb 6, ami rajta van egy k´ upszeleten. Megjegyz´ es: B´armely k´ upszeleten tudunk venni n pontot u ´gy, hogy a meghat´arozott ir´anyok sz´ama legfeljebb Cn; a k¨or¨on p´elda erre a szab´alyos n-sz¨og, ket parhuzamos egyenesen egy-egy sz´amtani, ket metsz˝o egyenesen egy-egy m´ertani sorozat, parabol´an ´es hiperbol´an megfelel˝o sz´amtani illetve m´ertani sorozat. Kit˝ uz˝ o: Elekes Gy¨orgy
10. 10. Probl´ ema (T): Igaz-e, hogy R minden r´eszgy˝ ur˝ uje 0 vagy 1 dimenzi´os? Megjegyz´ es: Pertti Mattila feladata. Ismert, hogy a dimenzi´o vagy 1, vagy 0 ´es 1/2 k¨oz´e esik. Kit˝ uz˝ o: Cs¨ornyei Marianna
13. 13. Probl´ ema (T,N): Legyen E ⊂ Rn pozit´ıv m´ert´ek˝ u. Igaz-e, hogy van n n olyan f : R → R Lipschitz lek´epez´es, amelyre f (E) az Rn egys´egg¨ombje? Megjegyz´ es: Laczkovich Mikl´os feladata. Az n = 1, 2 esetben bizony´ıtott, mas n-ekre nem ismert (m´ar 3-ra is nagyon ´erdekes lenne). Kit˝ uz˝ o: Cs¨ornyei Marianna
14. 14. Probl´ ema (T,?): Legyen A ⊂ R2 egy r´eszhalmaz, amelynek az 1-dimenzi´os m´ert´eke v´eges. Igaz-e, hogy A m.m. pontj´an kereszt¨ ul m.m. egyenes v´eges sok pontban metszi A-t? Megjegyz´ es: Pertti Mattila feladata, kapcsol´odik az 1.3 probl´em´ahoz. Kit˝ uz˝ o: Cs¨ornyei Marianna
15. 15.1 Probl´ ema (T): Igaz-e, hogy tetsz˝oleges r1 , r2 , . . . , rn sz´amokhoz, melyek n´egyzet¨osszege 1, tal´alhat´o pozit´ıv m´ert´ek˝ u ¨onhasonl´o halmaz a s´ıkon ezekkel az ¨onhasonl´os´agi ar´anyokkal? Azaz olyan pozit´ıv m´ert´ek˝ u kompakt A halmazt szeretn´enk, amely el˝o´all mint A1 , ..., An halmazok (nem felt´etlen¨ ul diszjunkt) uni´oja, ahol Ai egy ri -szeresre kicsiny´ıtett hasonl´o k´epe A-nak. 15.2 Probl´ ema (T): Mi a v´alasz a fenti k´erd´esre, ha csak soksz¨oglapokat enged¨ unk meg ¨onhasonl´o halmazk´ent? 15.3 Probl´ ema (T): Jelent-e ez megszor´ıt´ast, azaz igaz-e, hogy ha r1 , ..., rn hez van ¨onhasonl´o halmaz, akkor van soksz¨oglap is? Ha tov´abbi megszor´ıt´ask´ent csak konvex soksz¨ogeket enged¨ unk meg, akkor a v´alasz negat´ıv: Ulrich Betke egy publik´alatlan eredm´enye szerint egy ¨onhasonl´o konvex soksz¨ognek legfeljebb 5 cs´ ucsa van (tal´an 5 helyett 6-ra ez nem olyan neh´ez), ezt f¨olhaszn´alva bel´athat´o, hogy a sz´obaj¨ohet˝o (r1 , ..rn ) sz´am n-esek megsz´aml´alhat´o sok 4-dimenzi´os sima sokas´agon vannak, ´ıgy az n > 5 esetben van ”rossz” sz´am n-es. Kit˝ uz˝ o: Keleti Tam´as
16. 16. Probl´ ema (T,N): Igaz-e, hogy tetsz˝oleges 0-hoz tart´o d1 , d2 , . . . sorozathoz tal´alhat´o egy pozit´ıv m´ert´ek˝ u H ⊂ R halmaz, amely nem tartalmazza a sorozat egy affin k´ep´et? Megjegyz´ es: Erd˝os P´al feladata. Kit˝ uz˝ o: Cs¨ornyei Marianna
20. 20. Probl´ ema (T): Igaz-e, hogy Sn tranzit´ıv r´eszcsoportjainak rendjeib˝ol ´all´o halmaz elemsz´ama korl´atozhat´o egy n-ben polinom f¨ uggv´ennyel? Megjegyz´ es: Primit´ıv r´eszcsoportokra ismert. Kapcsol´ od´ o anyag: Pyber L., Assymptotic results for simple groups and some applications, DIMACS Series in Discrete Math and Theoretical Comp Sci 29 (1997) 309-327. Kit˝ uz˝ o: Pyber L´aszl´o
31. 31. Probl´ ema (T): Egy v´eges halmazon ´ertelmezett (tetsz˝oleges v´altoz´osz´am´ u) m˝ uveleteknek egy halmaz´at kl´onnak nevezz¨ uk, ha z´art az ¨osszetett f¨ uggv´eny k´epz´es´ere ´es tartalmazza az ¨osszes pin (x1 , .., xn ) = xi (1 ≤ i ≤ n, n = 1, 2, ..) projekci´ot. A trivi´alis kl´on csak a projekci´okb´ol ´all. Egy kl´on minim´alis, ha nemtrivi´alis, de az egyetlen val´odi r´eszkl´onja a trivi´alis kl´on. Meghat´arozand´ok a minim´alis kl´onok. Megjegyz´ es: H´aromelem˝ u alaphalmazra Cs´ak´any B´ela, n´egyelem˝ ure B. Szczepara ´es Waldhauser Tam´as oldotta meg a feladatot. Az ´altal´anos esetben csak r´eszeredm´enyek ismertek. Kit˝ uz˝ o: P´alfy P´eter P´al
47. 47. Probl´ ema (T,?): Igaz-e, hogy ha a [0, 1] intervallum lefedhet˝o α db Cantor-halmazzal, akkor a [0, 1]N Hilbert-kocka is lefedhet˝o ugyanennyi Cantor-halmazzal? Azaz: konzisztens-e, hogy a Hilbert-kock´ahoz t¨obb Cantor-halmaz kell? Megjegyz´ es: Michal Moratine feladata. Kit˝ uz˝ o: Cs¨ornyei Marianna
53. 53. Probl´ ema (T,N): Bizony´ıtsd be, hogy annak a val´osz´ın˝ us´ege, hogy k´et f¨ uggetlen, v´eletlen menekv˝o s´eta szorzata is menekv˝o, polinom´alisan cs¨okken a s´et´ak hossz´aval. Megjegyz´ es: Egy d dimenzi´os, n hossz´ u s´eta egy f¨ uggv´eny {0..n−1}-r˝ol Z d be u ´gy, a 0 k´epe az orig´o, ´es minden i-re f (i) ´es f (i + 1) t´avols´aga 1. A s´eta menekv˝o, hogyha ez a f¨ uggv´eny injekt´ıv; legyen pn annak a val´osz´ın˝ us´ege, hogy egy v´eletlen (egyenletes eloszl´as´ u) n hossz´ u s´eta menekv˝o. Bizony´ıtand´o, hogy van olyan αd , hogy pn+m (n + m)αd ≥ p(n)p(m). Kapcsol´ od´ o anyag: D. Randall, A. Sinclair: Testable algorithms for selfavoiding walks, http://www.cs.berkeley.edu/ sinclair/saws.ps Kit˝ uz˝ o: Vir´ag B´alint (
[email protected])
57. 57. Probl´ ema (T,N): Van-e 3-n´al kisebb Hausdorff dimenzi´os halmaz 3 R -ben, amely minden ir´anyban tartalmaz szakaszt? Megjegyz´ es: Pozit´ıv v´alasz azonnal c´afoln´a a harmonikus anal´ızis k´et legfontosabb sejt´es´et, valamint egy h´ıres parci´alis differenci´alegyenlet es egy h´ıres analitikus sz´amelm´elet sejt´est. Jelenleg annyi ismert, hogy egy ilyen halmaz legal´abb 2.5000000001 dimenzi´os. Kor´abban 2.5 volt a rekord. Kit˝ uz˝ o: Keleti Tam´as
64. Szita Legyen n adott, ´es legyen f (m) azon sz´amok √ sz´ama az [m + 1, m + n] intervallumban, amelyeknek van legal´abb egy ( n, n)-be es˝o pr´ımoszt´ojuk. 64.1 Probl´ ema (T,?): stanssal?
Igaz-e, hogy f (m) > cn pozit´ıv c abszol´ ut kon-
A p ≤ N , p ≡ 3 (mod 4) pr´ımek t¨ok´eletesen kiszit´alj´ak a 3 ≤ 4k − 1 ≤ N sz´amokat, vagyis egy kb. N/4 hossz´ u sz´amtani sorozatot. 64.2 Probl´ ema (T,?): Ki tudnak-e szit´alni egy cN hossz´ u sz´amtani sorozatot a p ≡ 1 (mod 4) pr´ımek? Kit˝ uz˝ o: Ruzsa Imre
