Packing analogue of -radius sequences

详细信息    查看全文

• 作者：Zbigniew Lonc<sup>asup><sup> ; sup><sup>zblonc@mini.pw.edu.pl" class="auth_mail" title="E-mail the corresponding authorsup> ; Mirosław Truszczyński<sup>bsup><sup> ; sup><sup>mirek@cs.uky.edu" class="auth_mail" title="E-mail the corresponding authorsup>
• 刊名：European Journal of Combinatorics
• 出版年：2016
• 出版时间：October 2016
• 年：2016
• 卷：57
• 期：Complete
• 页码：57-70
• 全文大小：418 K

文摘

Let <span id="mmlsi1" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si1.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=1e6227abaf358996ae54ab98f58ffbbb" title="Click to view the MathML source">kspan><span class="mathContainer hidden"><span class="mathCode">scroll">kspan>span>span> be a positive integer. A sequence <span id="mmlsi3" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si3.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=de3a2a1fa97af36a0e06e15e46e99398" title="Click to view the MathML source">s<sub>1sub>,s<sub>2sub>,…,s<sub>msub>span><span class="mathContainer hidden"><span class="mathCode">scroll">sub>s1sub>,sub>s2sub>,…,sub>smsub>span>span>span> over an <span id="mmlsi4" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si4.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=154071badf340ab9089c0eee55da54d5" title="Click to view the MathML source">nspan><span class="mathContainer hidden"><span class="mathCode">scroll">nspan>span>span>-element <span id="mmlsi5" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si5.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=50343e1219052bd4c5cdf12d185067ce" title="Click to view the MathML source">Aspan><span class="mathContainer hidden"><span class="mathCode">scroll">Aspan>span>span> alphabet is a packing  <span id="mmlsi1" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si1.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=1e6227abaf358996ae54ab98f58ffbbb" title="Click to view the MathML source">kspan><span class="mathContainer hidden"><span class="mathCode">scroll">kspan>span>span>-radius sequence  , if for all pairs of indices <span id="mmlsi7" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si7.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=ade580d12482c737dba0f59254eb7c5b" title="Click to view the MathML source">(i,j)span><span class="mathContainer hidden"><span class="mathCode">scroll">(i,j)span>span>span>, such that <span id="mmlsi8" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si8.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=a8799435e45f35cf9b3ccab4f4c975c1" title="Click to view the MathML source">1≤i<j≤mspan><span class="mathContainer hidden"><span class="mathCode">scroll">1≤i<j≤mspan>span>span> and <span id="mmlsi9" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si9.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=27292dafc7cac7921a8b504eaa5c1f04" title="Click to view the MathML source">j&minus;i≤kspan><span class="mathContainer hidden"><span class="mathCode">scroll">j&minus;i≤kspan>span>span>, the sets <span id="mmlsi10" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si10.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=14dd50401ed229dc00859064d01d5c84" title="Click to view the MathML source">{s<sub>isub>,s<sub>jsub>}span><span class="mathContainer hidden"><span class="mathCode">scroll">{sub>sisub>,sub>sjsub>}span>span>span> are pairwise different <span id="mmlsi11" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si11.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=1959b84aa585f2bca3dde120f856d5b0" title="Click to view the MathML source">2span><span class="mathContainer hidden"><span class="mathCode">scroll">2span>span>span>-element subsets of <span id="mmlsi5" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si5.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=50343e1219052bd4c5cdf12d185067ce" title="Click to view the MathML source">Aspan><span class="mathContainer hidden"><span class="mathCode">scroll">Aspan>span>span>. Let <span id="mmlsi13" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si13.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=1cc020038412efed175a6c7f7cbfd736" title="Click to view the MathML source">g<sub>ksub>(n)span><span class="mathContainer hidden"><span class="mathCode">scroll">sub>gksub>(n)span>span>span> denote the length of a longest <span id="mmlsi1" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si1.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=1e6227abaf358996ae54ab98f58ffbbb" title="Click to view the MathML source">kspan><span class="mathContainer hidden"><span class="mathCode">scroll">kspan>span>span>-radius sequence over <span id="mmlsi5" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si5.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=50343e1219052bd4c5cdf12d185067ce" title="Click to view the MathML source">Aspan><span class="mathContainer hidden"><span class="mathCode">scroll">Aspan>span>span>. We give a construction demonstrating that for every <span id="mmlsi16" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si16.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=c7548b87a6a545e246719d1562d91366" title="Click to view the MathML source">k=⌊cn<sup>αsup>⌋span><span class="mathContainer hidden"><span class="mathCode">scroll">k=⌊csup>nαsup>⌋span>span>span>, where <span id="mmlsi17" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si17.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=5d3e528acdda79ed5281ba6363311246" title="Click to view the MathML source">cspan><span class="mathContainer hidden"><span class="mathCode">scroll">cspan>span>span> and <span id="mmlsi18" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si18.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=4eb7e9caf679c33bc51b2a9d15c0ff99" title="Click to view the MathML source">αspan><span class="mathContainer hidden"><span class="mathCode">scroll">αspan>span>span> are fixed reals such that <span id="mmlsi19" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si19.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=9e87bcf4fd9232111b181392172644c9" title="Click to view the MathML source">c>0span><span class="mathContainer hidden"><span class="mathCode">scroll">c>0span>span>span> and <span id="mmlsi20" class="mathmlsrc">source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si20.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=df2e1021f9daf578abbae5351d7a166e">ss="imgLazyJSB inlineImage" height="21" width="72" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0195669816300063-si20.gif">script>style="vertical-align:bottom" width="72" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0195669816300063-si20.gif">script><span class="mathContainer hidden"><span class="mathCode">scroll">0≤α<12span>span>span>, <span id="mmlsi21" class="mathmlsrc">source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si21.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=2f09c655c963bcc71db5a6b216626628">ss="imgLazyJSB inlineImage" height="24" width="142" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0195669816300063-si21.gif">script>style="vertical-align:bottom" width="142" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0195669816300063-si21.gif">script><span class="mathContainer hidden"><span class="mathCode">scroll">sub>gksub>(n)=sup>n2sup>2k(1&minus;o(1))span>span>span>. For a constant <span id="mmlsi1" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si1.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=1e6227abaf358996ae54ab98f58ffbbb" title="Click to view the MathML source">kspan><span class="mathContainer hidden"><span class="mathCode">scroll">kspan>span>span> we show that <span id="mmlsi23" class="mathmlsrc">source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si23.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=239a5d070062a76567df0ee4c05b08c9">ss="imgLazyJSB inlineImage" height="24" width="151" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0195669816300063-si23.gif">script>style="vertical-align:bottom" width="151" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0195669816300063-si23.gif">script><span class="mathContainer hidden"><span class="mathCode">scroll">sub>gksub>(n)=sup>n2sup>2k&minus;O(sup>n1.525sup>)span>span>span>. Moreover, we prove an upper bound for <span id="mmlsi13" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si13.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=1cc020038412efed175a6c7f7cbfd736" title="Click to view the MathML source">g<sub>ksub>(n)span><span class="mathContainer hidden"><span class="mathCode">scroll">sub>gksub>(n)span>span>span> that allows us to show that <span id="mmlsi25" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si25.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=1d51d4673da94cc357067c1c9c51b934" title="Click to view the MathML source">g<sub>ksub>(n)=n(1+o(1))span><span class="mathContainer hidden"><span class="mathCode">scroll">sub>gksub>(n)=n(1+o(1))span>span>span> for every <span id="mmlsi16" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si16.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=c7548b87a6a545e246719d1562d91366" title="Click to view the MathML source">k=⌊cn<sup>αsup>⌋span><span class="mathContainer hidden"><span class="mathCode">scroll">k=⌊csup>nαsup>⌋span>span>span>, where <span id="mmlsi19" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si19.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=9e87bcf4fd9232111b181392172644c9" title="Click to view the MathML source">c>0span><span class="mathContainer hidden"><span class="mathCode">scroll">c>0span>span>span> and <span id="mmlsi28" class="mathmlsrc">source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300063&_mathId=si28.gif&_user=111111111&_pii=S0195669816300063&_rdoc=1&_issn=01956698&md5=37dd6520eb4b35123c357111ab94e44e">ss="imgLazyJSB inlineImage" height="21" width="71" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0195669816300063-si28.gif">script>style="vertical-align:bottom" width="71" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0195669816300063-si28.gif">script><span class="mathContainer hidden"><span class="mathCode">scroll">12<α<1span>span>span>.