A coding problem for pairs of subsets

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

A coding problem for pairs of subsets

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

A coding problem for pairs of subsets

Popis výsledku anglicky

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

Druh

C - Kapitola v odborné knize

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GPP201%2F12%2FP288" target="_blank" >GPP201/12/P288: Reprezentace grafů</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2014

Kód důvěrnosti údajů

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

Název knihy nebo sborníku

Geometry, Structure and Randomness in Combinatorics

ISBN

978-88-7642-524-0

Počet stran výsledku

11

Strana od-do

47-59

Počet stran knihy

160

Název nakladatele

Edizioni della Normale

Místo vydání

Pisa

Kód UT WoS kapitoly

—