Complete Kneser transversals

详细信息    查看全文

• 作者：J. Chappelon^a ; ^{jonathan.chappelon@umontpellier.fr" class="auth_mail" title="E-mail the corresponding author} ; L. Martí ; nez-Sandoval^b ; ^{leomtz@im.unam.mx" class="auth_mail" title="E-mail the corresponding author} ; L. Montejano^b ; ^{luis@math.unam.mx" class="auth_mail" title="E-mail the corresponding author} ; L.P. Montejano^a ; ^{lpmontejano@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; J.L. Ramí ; rez Alfonsí ; n^a ; ^{jorge.ramirez-alfonsin@umontpellier.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：52A35 ; 05C15 ; 52C40 ; 52B40 ; 52B99
• 刊名：Advances in Applied Mathematics
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：82
• 期：Complete
• 页码：83-101
• 全文大小：401 K

文摘

Let class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300604&_mathId=si1.gif&_user=111111111&_pii=S0196885816300604&_rdoc=1&_issn=01968858&md5=92c0cf2f49901eb0bfd2bea6d537aebb" title="Click to view the MathML source">k,d,λ⩾1class="mathContainer hidden">class="mathCode">$k,d,\lambda ⩾1$ be integers with class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300604&_mathId=si2.gif&_user=111111111&_pii=S0196885816300604&_rdoc=1&_issn=01968858&md5=3e57b826777a68d6d31af52a5daef9bd" title="Click to view the MathML source">d⩾λclass="mathContainer hidden">class="mathCode">$d⩾\lambda$. Let class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300604&_mathId=si3.gif&_user=111111111&_pii=S0196885816300604&_rdoc=1&_issn=01968858&md5=ce431fb952f126b9c482d717585b90e6" title="Click to view the MathML source">m(k,d,λ)class="mathContainer hidden">class="mathCode">$m(k,d,\lambda )$ be the maximum positive integer n such that every set of n   points (not necessarily in general position) in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300604&_mathId=si107.gif&_user=111111111&_pii=S0196885816300604&_rdoc=1&_issn=01968858&md5=7d4c8315dace50dcd0a3cb77fd3ee448" title="Click to view the MathML source">R^dclass="mathContainer hidden">class="mathCode">${\mathbb{R}}^d$ has the property that the convex hulls of all k  -sets have a common transversal class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300604&_mathId=si37.gif&_user=111111111&_pii=S0196885816300604&_rdoc=1&_issn=01968858&md5=c013fedb69ad73219b92034efa622bbd" title="Click to view the MathML source">(d−λ)class="mathContainer hidden">class="mathCode">$(d-\lambda )$-plane. It turns out that class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300604&_mathId=si3.gif&_user=111111111&_pii=S0196885816300604&_rdoc=1&_issn=01968858&md5=ce431fb952f126b9c482d717585b90e6" title="Click to view the MathML source">m(k,d,λ)class="mathContainer hidden">class="mathCode">$m(k,d,\lambda )$ is strongly connected with other interesting problems, for instance, the chromatic number of Kneser hypergraphs and a discrete version of Rado's centerpoint theorem. In the same spirit, we introduce a natural discrete version class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300604&_mathId=si6.gif&_user=111111111&_pii=S0196885816300604&_rdoc=1&_issn=01968858&md5=ed369363b081ed7fec36478a69566ee1" title="Click to view the MathML source">m^⁎class="mathContainer hidden">class="mathCode">$m^{⁎}$ of m by considering the existence of complete Kneser transversals  . We study the relation between them and give a number of lower and upper bounds of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300604&_mathId=si6.gif&_user=111111111&_pii=S0196885816300604&_rdoc=1&_issn=01968858&md5=ed369363b081ed7fec36478a69566ee1" title="Click to view the MathML source">m^⁎class="mathContainer hidden">class="mathCode">$m^{⁎}$ as well as the exact value in some cases. The main ingredient for the proofs are Radon's partition theorem as well as oriented matroids tools. By studying the alternating oriented matroid we obtain the asymptotic behavior of the function class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300604&_mathId=si6.gif&_user=111111111&_pii=S0196885816300604&_rdoc=1&_issn=01968858&md5=ed369363b081ed7fec36478a69566ee1" title="Click to view the MathML source">m^⁎class="mathContainer hidden">class="mathCode">$m^{⁎}$ for the family of cyclic polytopes.