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

Egyéni Kutatómunka 1

2020/21 I. félév

Témavezető:
Csikvári Péter (ELTE TTK, Számítógéptudományi Tanszék)

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.