Problem A. 477. (March 2009)
A. 477. Let G be the complete graf with 2n vertices, and suppose that S1,...,Sk are subgraphs of G with the following properties:
(a) Every Si is a complete bipartite graph;
(b) Every edge of G is contained by an odd number of subgraphs Si.
Show that kn.
(5 pont)
Deadline expired on April 15, 2009.
Sorry, the solution is available only in Hungarian. Google translation
Megoldásvázlat. A feladatot lineáris algebrai eszközökkel oldjuk meg. A csúcsok különböző részhalmazait, illetve a G külöbnöző részgráfjait a kételemű test feletti 2n-dimenziós (oszlop)vektorokkal, illetve 2n×2n-es mátrixokkal fogjuk reprezentálni.
Az egyszerűség kedvéért legyenek G csúcsai az 1,2,...2n számok.
A csúcsok egy tetszőleges részhalmazának feleltessünk meg egy 2n hosszú vektort, amelynek elemei a 0 és 1 számok lehetnek; az i-edik koordináta akkor legyen 1, ha az i csúcs eleme az adott részhalmaznak.
A G részgráfjait reprezentáljuk 2n×2n-es mátrixokkal a következőképpen: a mátrix (i,j)-edik eleme legyen 1, ha az i és j össze van kötve, egyébként pedig 0. (Ezt a mátrixot a gráf szomszédsági vagy adjacencia-mátrixának is nevezik. Egyszerű gráfok esetén -- mint a feladatban is -- az adjacencia-mátrix mindig szimmetrikus, és a főátlóban csak 0-k állhatnak.)
Minden egyes i-re legyenek az Si csúcsosztályainak megfelelő vektorok ai és bi; ekkor Si szomszédsági mátrixa
A G teljes gráf szomszédsági mátrixa pedig
Ezekkel a jelölésekkel a (b) feltételt a következő alakban is írhatjuk:
Nevezzük tetszőleges M mátrix rangjának, és jelöljük rk(M)-mel, azt, hogy a mátrix oszlopai közül hány (GF2 fölött) lineárisan függetlent lehet kiválasztani.
Könnyen ellenőrizhető, hogy az A mátrix determinánsa 1, a rangja 2n. Ezért
tehát kn.
Statistics:
4 students sent a solution. 5 points: Nagy 235 János, Nagy 314 Dániel, Tomon István. 1 point: 1 student.
Problems in Mathematics of KöMaL, March 2009