Az A. 784. feladat (2020. október)

A. 784. Legyenek $\displaystyle n$, $\displaystyle s$, $\displaystyle t$ pozitív egész számok és $\displaystyle 0<\lambda<1$. Adott egy $\displaystyle n$ csúccsal és legalább $\displaystyle \lambda n^2$ éllel rendelkező egyszerű gráf. Azt mondjuk, hogy az $\displaystyle (x_1,\ldots,x_s,y_1,\ldots y_t)$ egy jó beillesztés, ha az $\displaystyle x_i$ és $\displaystyle y_j$ betűk nem feltétlenül különböző csúcsokat jelölnek, és mindegyik $\displaystyle x_iy_j$ éle a gráfnak ($\displaystyle 1~\le i \le s$, $\displaystyle 1\le j\le t$). Bizonyítsuk be, hogy a jó beillesztések száma legalább $\displaystyle \lambda^{st}n^{s+t}$.

Javasolta: Williams Kada (Cambridge)

(7 pont)

A beküldési határidő 2020. november 10-én LEJÁRT.

Megoldási ötletek. Számozzuk a csúcsokat az $\displaystyle 1,2,\dots,n$ számokkal. Ha $\displaystyle x$ és $\displaystyle y$ csúcsa a $\displaystyle G$ gráfnak, akkor legyen $\displaystyle G(x,y)=1$, ha $\displaystyle xy$ él, és $\displaystyle G(x,y)=0$, ha $\displaystyle xy$ nem él. Feltéve, hogy $\displaystyle G$ éleinek száma legalább $\displaystyle \frac12\lambda n^2$, fennáll, hogy

$\displaystyle \sum_{x,y=1}^n G(x,y)\ge \lambda n^2.$

A jó beillesztések száma pedig:

$\displaystyle S=\sum_{x_1,\dots,x_s,y_1,\dots,y_t=1}^n \left[\prod_{i=1}^s \prod_{j=1}^t G(x_i,y_j)\right].$

(Ugyanis $\displaystyle (x_1,\dots,x_s,y_1,\dots,y_t)$ jó beillesztés akkor és csak akkor, ha $\displaystyle G(x_i,y_j)=1$ minden $\displaystyle i=1,\dots,s$ és $\displaystyle j=1,\dots,t$ esetén.)

Példaképpen tekintsük előbb az $\displaystyle s=t=2$ esetet (ami, jegyezzük meg, az elemi kombinatorikában cseresznyeszámolásként ismeretes):

$\displaystyle S=\sum_{x,x',y,y'=1}^n G(x,y)G(x',y)G(x,y')G(x',y').$

Adott $\displaystyle y,y'$ érték mellett legyen $\displaystyle G_{y,y'}(x)=G(x,y)G(x,y')$. Ekkor

$\displaystyle S=\sum_{y,y'=1}^n \sum_{x=1}^n \sum_{x'=1}^n G_{y,y'}(x)G_{y,y'}(x'),$

ami teljes négyzetként ismerhető fel:

$\displaystyle S=\sum_{y,y'=1}^n \left(\sum_{x=1}^n G_{y,y'}(x)\right)^2.$

Használjuk fel $\displaystyle t\in [0,\infty)$, $\displaystyle t\mapsto t^2$ konvexitását (tehát a Jensen-egyenlőtlenséget):

$\displaystyle \frac1{n^2}\sum_{y,y'=1}^n \left(\sum_{x=1}^n G_{y,y'}(x)\right)^2\ge \left(\frac1{n^2} \sum_{y,y'=1}^n \sum_{x=1}^n G_{y,y'}(x)\right)^2.$

A zárójelben szereplő összeggel járjunk el ugyanígy. Cseréljük fel a szummát és alkalmazzunk konvexitási becslést.

$\displaystyle \sum_{y,y'=1}^n \sum_{x=1}^n G_{y,y'}(x)=\sum_{x=1}^n \sum_{y,y'=1}^n G(x,y)G(x,y')=$

$\displaystyle =\sum_{x=1}^n \left(\sum_{y=1}^n G(x,y)\right)^2 \ge n\cdot \left(\frac1n \sum_{x=1}^n \sum_{y=1}^n G(x,y)\right)^2.$

Végtermékként az élszámot látjuk. Ez teszi lehetővé a kitűzött alsó becslést.

A feladatbeli általánosítás hasonlóképp bizonyítható. Az eltérés mindössze annyi, hogy $\displaystyle s$-edik, illetve $\displaystyle t$-edik hatványokat tudunk felismerni.

Statisztika:

1 dolgozat érkezett.
0 pontot kapott:	1 versenyző.

A KöMaL 2020. októberi matematika feladatai