Kovács Benedek: Páronként diszjunkt vektorpárok keresése F_2^n-ben előírt különbségsorozattal

Kutatásomban Balister, Győri és Schelp 2008-as sejtését vizsgálom, mely a Coloring Vertices and Edges of a Path by Nonempty Subsets of a Set c. cikkükben található. Eszerint ha a kételemű test feletti N=2ⁿ elemű vektortérben adottak d₁,d₂,...,dₘ nemnulla különbségvektorok, ahol m=½N-1, akkor léteznek csupa különböző x₁,x₂,...,xₘ és y₁,y₂,...,yₘ vektorok úgy, hogy minden i-re xᵢ-yᵢ=dᵢ. Egyszerű mohó algoritmussal a feladat megoldható m=¼N-re, és Zsigri Bálinttal közös nyári kutatásunkban egy továbbfejlesztett módszer használatával sikerült ezt megjavítanunk m=7/26N-re. Célom az őszi félévben további haladás elérése a sejtés irányában, például a módszerünkön való lehetséges javítások keresésével.

Az őszi félévben beláttam az alábbi állítást, mely Balister, Győri és Schelp 2008-as sejtéséhez kapcsolódik: ha az F_2^n vektortérben adottak a d_1, d_2, ..., d_M nemnulla elemek, ahol M<5/18 * 2^n, akkor ki lehet választani a vektortérben csupa különböző a_1, a_2, ..., a_M és b_1, b_2, ..., b_M vektorokat úgy, hogy minden i-re a_i-b_i=d_i legyen. A korábbi, Zsigri Bálinttal közös kutatásunkkal elért 7/26 * 2^n-es eredményt egy rekurzív gondolatmenet használatával sikerült megjavítanom. A tavaszi félévben a kutatásom célja az eredményen való további javítások elérése.