Iskanje po repozitoriju

Opis: We consider the following question by Balister, Győri and Schelp: given 2^{n-1} nonzero vectors in F_2^n with zero sum, is it always possible to partition the elements of F_2^n into pairs such that the difference between the two elements of the i-th pair is equal to the i-th given vector for every i? An analogous question in F_p, which is a case of the so-called "seating couples" problem, has been resolved by Preissmann and Mischler in 2009. In this paper, we prove the conjecture in F_2^n in the case when the number of distinct values among the given difference vectors is at most n-2log(n)-1, and also in the case when at least a fraction 1/2+ε of the given vectors are equal (for all ε>0 and n sufficiently large based on ε).
Ključne besede: binary vector spaces, seating couples, prescribed differences, perfect matching, functional batch code, graph colourings
Objavljeno v RUP: 21.12.2025; Ogledov: 292; Prenosov: 0
Celotno besedilo (467,06 KB)

Ključne besede: popolna koda, učinkovita dominacija, grafi z učinkovito dominantno množico, polinomski algoritmi, hereditarni grafovski razredi, perfect code, efficient domination, efficiently dominatable graphs, polynomial time algorithms, hereditary graph classes
Objavljeno v RUP: 15.10.2015; Ogledov: 6137; Prenosov: 354
Povezava na celotno besedilo