Az A. 934. feladat (2026. április)

A. 934. Jelölje \(\displaystyle \mathcal{T}\) a megszámlálható, irányítatlan fagráfok halmazát. A valós számok egy \(\displaystyle X\) részhalmazát baritonnak nevezzük, ha bármely nemüres részhalmazának van legkisebb eleme.

a) Igazoljuk, hogy minden bariton \(\displaystyle X\) esetén létezik olyan \(\displaystyle f\colon X\to \mathcal{T}\) függvény, amelyre bármely \(\displaystyle y\), \(\displaystyle z\in X\) esetén \(\displaystyle y\leq z\) akkor és csak akkor teljesül, ha \(\displaystyle f(y)\) izomorf \(\displaystyle f(z)\)-nek egy részgráfjával.

b) Igaz marad-e az előző állítás, ha még azt is megköveteljük, hogy minden \(\displaystyle x\in X\)-re \(\displaystyle f(x)\) minden csúcsának véges legyen a fokszáma?

Egy \(\displaystyle V\) csúcshalmazú gráf megszámlálható, ha létezik \(\displaystyle V\to \mathbb{N}\) injektív leképezés.

Javasolta: Németh Márton (Budapest)

(7 pont)

A beküldési határidő 2026. május 11-én LEJÁRT.

a) \(\displaystyle X\) megszámlálható: bármely \(\displaystyle x\in X\) esetén \(\displaystyle \{y\,|\, y>x\}\cap X\)-nek van legkisebb eleme, így kiválasztható olyan \(\displaystyle \varepsilon_x>0\), melyre \(\displaystyle (x,x+\varepsilon_x)\cap X=\emptyset\). Vagyis \(\displaystyle X\) minden eleméhez rendeltünk egy intervallumot, melyek páronként diszjunktak, így mivel minden intervallumban található racionális szám, \(\displaystyle X\) megszámlálható.

\(\displaystyle X\) továbbá jólrendezett a feltétel szerint, így valamely \(\displaystyle \alpha\) megszámlálható rendszámra \(\displaystyle X\cong \alpha\). Elegendő tehát olyan \(\displaystyle f:\alpha\to \mathcal{T}\) függvényt mutatni, melyre \(\displaystyle y,z\in \alpha\) esetén \(\displaystyle y\leq z\) akkor és csak akkor teljesül, ha \(\displaystyle f(y)\) izomorf \(\displaystyle f(z)\) egy részgráfjával. Először transzfinit rekurióval konstruálunk egy \(\displaystyle g:\alpha\to \mathcal{T}'\) segédfüggvényt, ahol \(\displaystyle \mathcal{T}'\) az irányított , megszámlálható fagráfok halmaza, mely hasonlóan eleget tesz a feltételnek.

Ha \(\displaystyle \alpha = 0\), \(\displaystyle g:\emptyset\to \mathcal{T}\) létezik. Ellenkező esetben (rákövetkező, és határrendszám esetén is) \(\displaystyle g(\alpha)\) legyen az az irányított fa, melynek van egy \(\displaystyle R\) gyökere, és \(\displaystyle R\)-ből irányított él megy az összes \(\displaystyle g(\gamma)\) fa gyökerébe (mindegyikből veszünk egy diszjunkt másolatot). Vegyük észre, hogy az összes így konstruált fára az élek egy kinevezett gyökértől elfelé mutatnak, illetve minden ilyen fa megszámlálható lesz, hiszen megszámlálható halmazok megszámlálható uniója megszámlálható.

Végül megmutatjuk, hogy az így konstruált \(\displaystyle g(\gamma)\) fák teljesítik a kívánt feltételt: ha \(\displaystyle y\leq z\), akkor könnyű látni, hogy \(\displaystyle g(y)\) megtalálható \(\displaystyle g(z)\)-ben. Legyen \(\displaystyle z<y\). Tegyük fel, hogy \(\displaystyle g(y)\) izomorf \(\displaystyle g(z)\) egy részgráfjával. Legyen \(\displaystyle R_0\) \(\displaystyle g(z)\) gyökere. Legyen \(\displaystyle R_1\) az a csúcs \(\displaystyle g(z)\)-ben, mely \(\displaystyle g(y)\) gyökerének a képe. Legyen \(\displaystyle R_2\) az a csúcs \(\displaystyle g(z)\)-ben, mely a \(\displaystyle g(y)\)-ban, mint részfában található \(\displaystyle g(z)\) gyökere, és így tovább. Világos, hogy \(\displaystyle R_0\), \(\displaystyle R_2\), \(\displaystyle R_4\), \(\displaystyle \ldots\), és néhány, a közöttük lévő úton haladó csúcs egy végtelen utat alkot \(\displaystyle g(z)\)-ben.

Ez azonban nem lehetséges, melyet indukcióval bizonyítunk: \(\displaystyle g(0)\)-ban nincs végtelen út. Tegyük fel, hogy \(\displaystyle \gamma<\alpha\) esetén \(\displaystyle g(\gamma)\)-ban nincs végtelen út, ekkor mivel egy végtelen útnak \(\displaystyle g(\alpha)\)-ban a gyökérből valamely \(\displaystyle g(\gamma)\) gyökerében kell folytatódnia, \(\displaystyle g(\alpha)\)-ban sincs végtelen út. Ezzel az állítást beláttuk.

Végül megkonstruáljuk az így kapott \(\displaystyle g\) függvény alapján \(\displaystyle f\)-et is: cseréljünk le minden irányított élt \(\displaystyle g(\alpha)\)-ban: az \(\displaystyle (u\to v)\) élt hagyjuk el, és helyette adjuk hozzá a fához az \(\displaystyle a,b,c\) csúcsokat, és húzzuk be az \(\displaystyle (u,a), (a,b), (b,v), (b,c)\) éleket. Világos, hogy a szükséges injekciók továbbá is léteznek.

Ezen kívül egy injekció a \(\displaystyle g(z)\) fa eredeti csúcsait \(\displaystyle f(z)\)-ben biztosan \(\displaystyle f(y)\) eredeti csúcsaira képezi, így a másik iránnyal is készen vagyunk.

b) Az állítás igaz marad. Mutatunk egy konstrukciót, mely a valós számok tetszőleges \(\displaystyle X\) részhalmazára működik, a csúcsok fokszáma véges marad, továbbá nem használ transzfinit rekurziót.

Először konstruáljunk egy \(\displaystyle M\) végtelen, szimmetrikus bináris keresőfát: a fa gyökere legyen \(\displaystyle \epsilon\), \(\displaystyle \epsilon\) gyerekei legyenek \(\displaystyle 0\) és \(\displaystyle 1\), továbbá bármely \(\displaystyle w\) csúcs gyerekei legyenek \(\displaystyle w0\) és \(\displaystyle w1\). Most konstruálunk egy \(\displaystyle h:V(M)\to \mathbb{Q}\) bijekciót, melyre \(\displaystyle h(w0) < h(w) < h(w1)\) bármely \(\displaystyle w\) csúcs esetén.

Legyen \(\displaystyle \mathbb{Q} = \{q_0, q_1, \ldots\}\) a racionális számok tetszőleges felsorolása. Az \(\displaystyle i\geq 0\)-edik lépésben keressünk egy \(\displaystyle w\) csúcsot, melyre \(\displaystyle |w| = i\), és \(\displaystyle h(w)\) értékét beállíthatjuk \(\displaystyle q_i\)-re, anélkül, hogy a korábban beállított értékekkel sértenénk a feltételt (ha \(\displaystyle q_i\) súlyt már kapott valamelyik korábbi csúcs, hagyjuk ki ezt a lépést). Végül a megmaradt \(\displaystyle \{w:|w|=i\}\) csúcsokat súlyozzuk tetszőlegesen.

Ezt mindig meg tudjuk tenni, hiszen bármely intervallum tartalmaz racionális számot.

Most megkonstruáljuk az \(\displaystyle f\) függvényt: vegyük egy tetszőleges \(\displaystyle x\) valós értéket. \(\displaystyle M\) minden olyan \(\displaystyle w\) csúcsához, melyre \(\displaystyle h(w)\leq x\), illesszünk egy levelet. Így megkapjuk az \(\displaystyle M_x\) fát. Végül \(\displaystyle M\) gyökeréhez illesszünk \(\displaystyle 5\) levelet. Így megkapjuk az \(\displaystyle M_x'\) fát. Legyen \(\displaystyle f(x) = M_x'\).

A konstrukció helyességének ellenőrzését az olvasóra bízzuk.

Statisztika:

8 dolgozat érkezett.
7 pontot kapott:	Aravin Peter, Áron Bence, Bodor Mátyás, Diaconescu Tashi, Kis Ágoston, Sami El-Hajjar.
6 pontot kapott:	Morvai Várkony Albert.
2 pontot kapott:	1 versenyző.

A KöMaL 2026. áprilisi matematika feladatai