Problem A. 784. (October 2020)
A. 784. Let \(\displaystyle n\), \(\displaystyle s\), \(\displaystyle t\) be positive integers and \(\displaystyle 0<\lambda<1\). A simple graph on \(\displaystyle n\) vertices with at least \(\displaystyle \lambda n^2\) edges is given. We say that \(\displaystyle (x_1,\ldots,x_s,y_1,\ldots y_t)\) is agood insertion, if letters \(\displaystyle x_i\) and \(\displaystyle y_j\) denote not necessarily distinct vertices and every \(\displaystyle x_iy_j\) is an edge of the graph (\(\displaystyle 1~\le i \le s\), \(\displaystyle 1\le j\le t\)). Prove that the number of good insertions is at least \(\displaystyle \lambda^{st}n^{s+t}\).
Submitted by Kada Williams, Cambridge
(7 pont)
Deadline expired on November 10, 2020.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
1 student sent a solution. 0 point: 1 student.
Problems in Mathematics of KöMaL, October 2020