A coding problem for pairs of subsets

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10286297" target="_blank" >RIV/00216208:11320/14:10286297 - isvavai.cz</a>
Result on the web
<a href="http://arxiv.org/pdf/1403.3847v2.pdf" target="_blank" >http://arxiv.org/pdf/1403.3847v2.pdf</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-88-7642-525-7_4" target="_blank" >10.1007/978-88-7642-525-7_4</a>

Result language
angličtina
Original language name
A coding problem for pairs of subsets
Original language description
Let X be an n-element finite set and k a positive an integer less than or equal to n/2. Suppose that {A1,A2} and {B1,B2} are pairs of disjoint k-element subsets of X (that is, |A1|=|A2|=|B1|=|B2|=k, the intersection of A1 and A2 is empty, and so is the intersection of B1 and B2). Define the distance of these pairs by d({A1,A2},{B1,B2}) to be the min{|A1-B1|+|A2-B2|,|A1-B2|+|A2-B1|}. This is the minimum number of elements of the union of A1and A2 that one has to move to obtain the other pair {B1,B2}. LetC(n,k,d) be the maximum size of a family of pairs of disjoint subsets, such that the distance of any two pairs is at least d. Here we establish a conjecture of Brightwell and Katona concerning an asymptotic formula for C(n,k,d) for k,d are fixed and n approaches infinity. Also, we find the exact value of C(n,k,d) in an infinite number of cases, by using special difference sets of integers. Finally, the questions discussed above are put into a more general context and a number of coding
Czech name
—
Czech description
—

Project
<a href="/en/project/GPP201%2F12%2FP288" target="_blank" >GPP201/12/P288: Graph representations</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)