<p>Given positive integers <i>v</i>, <i>k</i>, <i>t</i> and <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\lambda \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>λ</mi> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(v \ge k \ge t\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo>≥</mo> <mi>k</mi> <mo>≥</mo> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation>, a packing design <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\textrm{PD}_{\lambda }(v,k,t)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>PD</mtext> <mi>λ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is a pair <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\((V,\mathcal{B})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>V</mi> <mo>,</mo> <mi mathvariant="script">B</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <i>V</i> is a <i>v</i>-set and <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\mathcal{B}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">B</mi> </math></EquationSource> </InlineEquation> is a collection of <i>k</i>-subsets of <i>V</i> such that each <i>t</i>-subset of <i>V</i> appears in at most <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\lambda \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>λ</mi> </math></EquationSource> </InlineEquation> elements of <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\mathcal{B}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">B</mi> </math></EquationSource> </InlineEquation>. When <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\lambda =1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>λ</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, a <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\textrm{PD}_1(v,k,t)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>PD</mtext> <mn>1</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is equivalent to a binary code with length <i>v</i>, minimum distance <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(2(k-t+1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mo stretchy="false">(</mo> <mi>k</mi> <mo>-</mo> <mi>t</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and constant weight <i>k</i>. The maximum size of a <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\textrm{PD}_{\lambda }(v,k,t)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>PD</mtext> <mi>λ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is called the packing number, denoted <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(\textrm{PDN}_{\lambda }(v,k,t)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>PDN</mtext> <mi>λ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. In this paper we consider packing designs with <i>k</i> large relative to <i>v</i>. We prove that for a positive integer <i>n</i>, <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\textrm{PDN}_{\lambda }(v,k,t) = n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>PDN</mtext> <mi>λ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> whenever <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(nk-(t-1)\left( {\begin{array}{c}n\\ \lambda +1\end{array}}\right) \le \lambda v &lt; (n+1)k-(t-1)\left( {\begin{array}{c}n+1\\ \lambda +1\end{array}}\right) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mi>k</mi> <mo>-</mo> <mrow> <mo stretchy="false">(</mo> <mi>t</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mfenced close=")" open="("> <mrow> <mtable> <mtr> <mtd> <mi>n</mi> </mtd> </mtr> <mtr> <mtd> <mrow> <mrow /> <mi>λ</mi> <mo>+</mo> <mn>1</mn> </mrow> </mtd> </mtr> </mtable> </mrow> </mfenced> <mo>≤</mo> <mi>λ</mi> <mi>v</mi> <mo>&lt;</mo> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mi>k</mi> <mo>-</mo> <mrow> <mo stretchy="false">(</mo> <mi>t</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mfenced close=")" open="("> <mrow> <mtable> <mtr> <mtd> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow> <mrow /> <mi>λ</mi> <mo>+</mo> <mn>1</mn> </mrow> </mtd> </mtr> </mtable> </mrow> </mfenced> </mrow> </math></EquationSource> </InlineEquation>. We also prove that if no point appears in more than three blocks, then the blocks of a <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(\textrm{PD}_2(v,k,2)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>PD</mtext> <mn>2</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> can be ordered so that no ordered pair occurs more than once. This produces a directed packing design and we show that the corresponding directed packing number is equal to <i>n</i> when <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(nk-\left( {\begin{array}{c}n\\ 3\end{array}}\right) \le 2v &lt; (n+1)k-\left( {\begin{array}{c}n+1\\ 3\end{array}}\right) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mi>k</mi> <mo>-</mo> <mfenced close=")" open="("> <mrow> <mtable> <mtr> <mtd> <mi>n</mi> </mtd> </mtr> <mtr> <mtd> <mrow> <mrow /> <mn>3</mn> </mrow> </mtd> </mtr> </mtable> </mrow> </mfenced> <mo>≤</mo> <mn>2</mn> <mi>v</mi> <mo>&lt;</mo> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mi>k</mi> <mo>-</mo> <mfenced close=")" open="("> <mrow> <mtable> <mtr> <mtd> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow> <mrow /> <mn>3</mn> </mrow> </mtd> </mtr> </mtable> </mrow> </mfenced> </mrow> </math></EquationSource> </InlineEquation>. Such directed packing designs yield <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\((k-t)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>-</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-deletion-correcting codes.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Packing designs with large block size

  • Andrea C. Burgess,
  • Peter Danziger,
  • Daniel Horsley,
  • Muhammad Tariq Javed

摘要

Given positive integers v, k, t and \(\lambda \) λ with \(v \ge k \ge t\) v k t , a packing design \(\textrm{PD}_{\lambda }(v,k,t)\) PD λ ( v , k , t ) is a pair \((V,\mathcal{B})\) ( V , B ) , where V is a v-set and \(\mathcal{B}\) B is a collection of k-subsets of V such that each t-subset of V appears in at most \(\lambda \) λ elements of \(\mathcal{B}\) B . When \(\lambda =1\) λ = 1 , a \(\textrm{PD}_1(v,k,t)\) PD 1 ( v , k , t ) is equivalent to a binary code with length v, minimum distance \(2(k-t+1)\) 2 ( k - t + 1 ) and constant weight k. The maximum size of a \(\textrm{PD}_{\lambda }(v,k,t)\) PD λ ( v , k , t ) is called the packing number, denoted \(\textrm{PDN}_{\lambda }(v,k,t)\) PDN λ ( v , k , t ) . In this paper we consider packing designs with k large relative to v. We prove that for a positive integer n, \(\textrm{PDN}_{\lambda }(v,k,t) = n\) PDN λ ( v , k , t ) = n whenever \(nk-(t-1)\left( {\begin{array}{c}n\\ \lambda +1\end{array}}\right) \le \lambda v < (n+1)k-(t-1)\left( {\begin{array}{c}n+1\\ \lambda +1\end{array}}\right) \) n k - ( t - 1 ) n λ + 1 λ v < ( n + 1 ) k - ( t - 1 ) n + 1 λ + 1 . We also prove that if no point appears in more than three blocks, then the blocks of a \(\textrm{PD}_2(v,k,2)\) PD 2 ( v , k , 2 ) can be ordered so that no ordered pair occurs more than once. This produces a directed packing design and we show that the corresponding directed packing number is equal to n when \(nk-\left( {\begin{array}{c}n\\ 3\end{array}}\right) \le 2v < (n+1)k-\left( {\begin{array}{c}n+1\\ 3\end{array}}\right) \) n k - n 3 2 v < ( n + 1 ) k - n + 1 3 . Such directed packing designs yield \((k-t)\) ( k - t ) -deletion-correcting codes.