Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

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 k\gen.

(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

 
{\bf a}_i^t {\bf b}_i + {\bf b}_i^t {\bf a}_i \,.

A G teljes gráf szomszédsági mátrixa pedig


A = \left(\matrix
%>
{
0 & 1 & 1 & \ldots & 1 \cr
1 & 0 & 1 & \ldots & 1 \cr
1 & 1 & 0 & \ldots & 1 \cr
\vdots & \vdots & \vdots & \ddots & \vdots \cr
1 & 1 & 1 & \ldots & 0 \cr
}\right).

Ezekkel a jelölésekkel a (b) feltételt a következő alakban is írhatjuk:


\sum_{i=1}^k ({\bf a}_i^t {\bf b}_i + {\bf b}_i^t {\bf a}_i) = A.

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


2n = rk(A)
\le \sum_{i=1}^k \big( rk({\bf a}_i^t {\bf b}_i) + rk({\bf b}_i^t {\bf a}_i) \big) 
= 2k,

tehát k\gen.


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