Páronként diszjunkt vektorpárok keresése F_{2^n}-ben előírt különbségsorozattal Fizika, Földtudományok és Matematika

35 OTDK, Fizika, Földtudományok és Matematika Szekció, Kombinatorika és gráfelmélet Tagozat.

Páronként diszjunkt vektorpárok keresése F_{2^n}-ben előírt különbségsorozattal

Helyezés: 2

Hallgató: Kovács Benedek
Szak: Matematikus, Képzés típusa: msc, Intézmény: Eötvös Loránd Tudományegyetem, Kar: Természettudományi Kar

Témavazető: Csikvári Péter - egyetemi docens, Eötvös Loránd Tudományegyetem Természettudományi Kar

Legyenek adottak a d₁, d₂, ..., d_M nemnulla vektorok a kételemű test feletti N=2ⁿ elemű vektortérben. A célunk az, hogy találjunk csupa különböző a₁, a₂, ..., a_M, b₁, b₂, ..., b_M vektorokat úgy, hogy minden i-re a_i-b_i=d_i legyen. Mi az a lehető legnagyobb M érték, melyre ilyen vektorok mindig találhatók? Balister, Győri és Schelp 2008-as sejtése szerint a feladat M=1/2*N-2 esetén mindig megoldható. (Ez a sejtés a Coloring Vertices and Edges of a Path by Nonempty Subsets of a Set című cikkükben található.) Jelen kutatásom célja, hogy minél nagyobb M értékekre belássam a feladat megoldhatóságát. Ez remélhetőleg olyan módszereket tud eredményezni, melyek ennek a sejtésnek a bizonyítását segíthetik.

Egyszerű mohó algoritmussal a feladat megoldható M<=1/4*N-re: ekkor ha az {a₁,b₁}, {a₂,b₂}, ..., {a_M,b_M} párokat sorban egymás után, tetszőlegesen választjuk, sosem akadhatunk el. A cikkben részletesen leírok egy továbbfejlesztett módszert, mellyel sikerült ezt az eredményt megjavítanom M<=5/18*N-re.