Problem B. 5035. (May 2019)

B. 5035. The edges of a complete graph on $\displaystyle n\ge 8$ vertices are coloured in two colours. Prove that the number of cycles formed by four edges of the same colour is more than $\displaystyle \frac{{(n-5)}^4}{64}$.

Based on a problem proposed by M. Pálfy, Budapest

(6 pont)

Deadline expired on June 11, 2019.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Vegyük az $\displaystyle n$ csúcsú teljes gráf éleinek egy tetszőleges színezését a piros és kék színekkel. Ha $\displaystyle abcd$ egy piros (kék) kör, akkor erre úgy is gondolhatunk, hogy $\displaystyle a$ és $\displaystyle c$ csúcsokhoz tartozik két csúcs, $\displaystyle b$ és $\displaystyle d$, melyek mindegyike $\displaystyle a$-val és $\displaystyle c$-vel is piros (kék) színnel van összekötve. (Persze a szerepek szimmetrikusak: $\displaystyle a$ és $\displaystyle c$ szerepét $\displaystyle b$ és $\displaystyle d$ is játszhatja, ekkor $\displaystyle b$ és $\displaystyle d$ szerepét $\displaystyle a$ és $\displaystyle c$ veszi át.) Mindezek alapján érdemes a piros és kék cseresznyék számára alsó becslést adni. Egy cseresznye egy olyan három pontú gráf, ahol a három pont (mondjuk $\displaystyle a,b,c$) egyike ($\displaystyle b$) össze van kötve a másik kettővel ($\displaystyle a,c$), ekkor $\displaystyle b$-t nevezzük a cseresznye középső csúcsának, $\displaystyle a$ és $\displaystyle c$ pedig a szélső csúcsok. (Ha $\displaystyle a,b,c$ egy háromszöget alkot, akkor ez a három csúcs összesen három cseresznyét határoz meg: bármelyik csúcs lehet középső.) A cseresznyét pirosnak (kéknek) mondjuk, ha $\displaystyle ab,cb$ élek mindegyike piros (kék), ha a középső csúcs $\displaystyle b$.

Megjegyezzük, hogy 4 hosszú körrel kapcsolatos problémáknál gyakran érdemes a cseresznyéket vizsgálni, ilyen gráfelméleti eredményekről és azok számelméleti alkalmazásairól a KöMaL 2004. decemberi számában megjelent Körök és multiplikatív Sidon-sorozatok (http://db.komal.hu/KomalHU/cikk.phtml?id=201729) c. cikkben írtunk.

Legyen $\displaystyle b$ egy tetszőleges csúcs. Ha $\displaystyle b$-ből $\displaystyle k$ piros és $\displaystyle n-k-1$ kék indul ki, akkor összesen $\displaystyle \binom{k}{2}+\binom{n-k-1}{2}$ olyan piros és kék cseresznye van, aminek $\displaystyle b$ a középső csúcsa. Az $\displaystyle \binom{x}{2}=\frac{x(x-1)}{2}$ a függvényt az egész valós számegyenesre kiterjesztve használjuk majd. Az előbbi képlet $\displaystyle k\in \{0,1\}$ (illetve $\displaystyle k\in \{n-2,n-1\}$) mellett is helyes eredményt ad: ekkor a piros (illetve kék) cseresznyék száma 0.

Az $\displaystyle \binom{x}{2}=\frac{x(x-1)}{2}$ függvény konvex (hiszen egy felfelé álló parabola), így a Jensen-egyenlőtlenség alapján kapjuk a következő alsó becslést az olyan egyszínű cseresznyék számára, melyek középső csúcsa $\displaystyle b$:

$\displaystyle \binom{k}{2}+\binom{n-k-1}{2}\geq 2\binom{\frac{n-1}{2}}{2}=\frac{(n-1)(n-3)}{4}.$

Így a gráfban található piros és kék cseresznyék száma összesen legalább $\displaystyle \frac{n(n-1)(n-3)}{4}$, hiszen a középső csúcs $\displaystyle n$-féle lehet.

Most visszatérve fenti megfigyelésünkre, tekintsük az egyszínű cseresznyék szélső pontpárjait. Ha $\displaystyle a$ és $\displaystyle c$ két különböző csúcs, és $\displaystyle p$ (illetve $\displaystyle k$) az olyan piros (illetve kék) cseresznyék száma, melyek szélső pontjai $\displaystyle a$ és $\displaystyle c$, akkor az olyan piros (illetve kék) négy hosszú körök száma, melyek két szemköztes csúcsa $\displaystyle a$ és $\displaystyle c$ pontosan $\displaystyle \binom{p}{2}$ (illetve $\displaystyle \binom{k}{2}$). Ezek alapján, ha az $\displaystyle N:=\binom{n}{2}$ pontpárhoz (mint szélső csúcsokhoz) tartozó piros (illetve kék) cseresznyék száma $\displaystyle p_1,p_2,\dots,p_N$ (illetve $\displaystyle k_1,k_2,\dots,k_N$), akkor a gráfban található egyszínű négy hosszú körök száma:

$\displaystyle \frac{1}{2}\left(\sum\limits_{i=1}^N \binom{p_i}{2}+\sum\limits_{i=1}^N \binom{k_i}{2} \right),$

hiszen minden négy hosszú kört kétszer számolunk: kétféleképpen választható ki benne a szemköztes pontpár.

Ismét a Jensen-egyenlőtlenséget használva:

$\displaystyle \frac{1}{2}\left(\sum\limits_{i=1}^N \binom{p_i}{2}+\sum\limits_{i=1}^N \binom{k_i}{2} \right)\geq \frac{1}{2}\left(2N \binom{\frac{\sum p_i+\sum k_i}{2N}}{2} \right). $

$\displaystyle {(*)}$

Tudjuk, hogy a gráf egyszínű cseresznyéinek száma (ami éppen $\displaystyle \sum\limits_{i=1}^N p_i+\sum\limits_{i=1}^N k_i$) legalább $\displaystyle \frac{n(n-1)(n-3)}{4}$, ezért

$\displaystyle \frac{\sum p_i+\sum k_i}{2N}\geq \frac{\frac{n(n-1)(n-3)}{4}}{2N}=\frac{n-3}{4}.$

Az $\displaystyle \binom{x}{2}=\frac{x(x-1)}{2}$ függvény az $\displaystyle [1/2,\infty)$ intervallumon szigorúan monoton növekedő, ezért $\displaystyle n\geq 5$ esetén kapjuk, hogy

$\displaystyle \binom{\frac{\sum p_i+\sum k_i}{2N}}{2}\geq\binom{\frac{n-3}{4}}{2}=\frac{(n-3)(n-7)}{32}.$

Ezt $\displaystyle (*)$-gal egybevetve adódik, hogy a gráfban található egyszínű négy hosszú körök száma legalább

$\displaystyle \frac{1}{2}\cdot 2N\cdot \frac{(n-3)(n-7)}{32}=\frac{n(n-1)(n-3)(n-7)}{64}.$

Végül megmutatjuk, hogy $\displaystyle n(n-1)(n-3)(n-7)\geq (n-5)^4$, ha $\displaystyle n\geq 8$. Mivel $\displaystyle n(n-7)=n^2-7n=(n-5)^2+(3n-25)$ és $\displaystyle (n-1)(n-3)=n^2-4n+3=(n-5)^2+(6n-22)$, ezért $\displaystyle n\geq 8$ esetén

$$\begin{multline*}n(n-1)(n-3)(n-7)=[(n-5)^2+(3n-25)][(n-5)^2+(6n-22)]\geq\\ \geq[(n-5)^2-1][(n-5)^2+26]= (n-5)^4+25(n-5)^2-26>(n-5)^4.\end{multline*}$$

Ezzel a feladat állítását igazoltuk.

Statistics:

10 students sent a solution.

6 points: Füredi Erik Benjámin, Hegedűs Dániel, Várkonyi Zsombor, Weisz Máté.

3 points: 2 students.

0 point: 4 students.

Problems in Mathematics of KöMaL, May 2019

10 students sent a solution.
6 points:	Füredi Erik Benjámin, Hegedűs Dániel, Várkonyi Zsombor, Weisz Máté.
3 points:	2 students.
0 point:	4 students.

Already signed up?
New to KöMaL?