Scholarlink

<p>In the combinatorial context, one of the key problems in sequence reconstruction is to determine the largest intersection of two metric balls of radius <i>r</i>, where the distance between their centers is at least <i>d</i>. In this paper, the sequence reconstruction problem over permutations on <i>n</i> elements distorted by <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="200_2025_695_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(\ell _{\infty }\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>ℓ</mi> <mi>∞</mi> </msub> </math></EquationSource> </InlineEquation>-errors is presented. In this model, we study its properties and find the exact value of the largest intersection of its two metric balls for any <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="200_2025_695_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="108" /> </InlineMediaObject> <EquationSource Format="TEX">\(2r\ge n+d-1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>r</mi> <mo>≥</mo> <mi>n</mi> <mo>+</mo> <mi>d</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, or <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="200_2025_695_Article_IEq5.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">\(d=1,2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="200_2025_695_Article_IEq6.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(r=1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. Moreover, in the case of at most <i>r</i> <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="200_2025_695_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(\ell _{\infty }\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>ℓ</mi> <mi>∞</mi> </msub> </math></EquationSource> </InlineEquation>-errors and sufficiently large <i>n</i>, we obtain an asymptotic solution of the sequence reconstruction problem over permutations distorted by <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="200_2025_695_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(\ell _{\infty }\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>ℓ</mi> <mi>∞</mi> </msub> </math></EquationSource> </InlineEquation>-errors.</p>

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

Reconstruction of permutations distorted by single ℓ∞-errors

  • 期刊论文

  • 发表日期：

    2025年7月16日

查看全文
  • Xiang Wang

摘要

In the combinatorial context, one of the key problems in sequence reconstruction is to determine the largest intersection of two metric balls of radius r, where the distance between their centers is at least d. In this paper, the sequence reconstruction problem over permutations on n elements distorted by \(\ell _{\infty }\) ℓ ∞ -errors is presented. In this model, we study its properties and find the exact value of the largest intersection of its two metric balls for any \(2r\ge n+d-1\) 2 r ≥ n + d - 1 , or \(d=1,2\) d = 1 , 2 and \(r=1\) r = 1 . Moreover, in the case of at most r \(\ell _{\infty }\) ℓ ∞ -errors and sufficiently large n, we obtain an asymptotic solution of the sequence reconstruction problem over permutations distorted by \(\ell _{\infty }\) ℓ ∞ -errors.