Crossing patterns of semi-algebraic sets

详细信息	查看全文 | 推荐本文 |

• 作者：Noga Alon ; Já ; nos Pach ; Rom Pinchasi ; Radoš ; Radoič ; ić ; and Micha Sharir
• 关键词：Crossing patterns ; Borsuk– ; Ulam theorem ; Real algebraic geometry ; Range searching ; Ramsey theory
• 刊名：Journal of Combinatorial Theory ; Series A
• 出版年：2005
• 期刊代码：72_00973165
• 类别：mt
• 出版时间：2005
• 卷：111
• 期：2
• 页码：310-326
• 文件大小：274 K

摘要

We prove that, for every family me="mml1">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml1&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=bb357231591f1c042f4d2c113bc8def0">mg src="http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4FN2N71-1-1/0?wchp=dGLbVtb-zSkWb" alt="Click to view the MathML source" align="absbottom" border="0" height=12 width=18> of n semi-algebraic sets in me="mml2">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml2&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=62950e2ac526e9ce395256f09676d308">mg src="http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4FN2N71-1-9/0?wchp=dGLbVtb-zSkWb" alt="Click to view the MathML source" align="absbottom" border="0" height=17 width=19> of constant description complexity, there exist a positive constant me="mml3">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml3&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=2ff7b0015ec465a1fb8e233128097d11" title="Click to view the MathML source">mg src="http://www.sciencedirect.com/scidirimg/entities/25b.gif" alt="var epsilon" border=0> that depends on the maximum complexity of the elements of me="mml4">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml4&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=42c8ca74bfadd9d51eb94d0437cadbd3">mg src="http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4FN2N71-1-C/0?wchp=dGLbVtb-zSkWb" alt="Click to view the MathML source" align="absbottom" border="0" height=12 width=18>, and two subfamilies me="mml5">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml5&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=62eca07d14c89106ea93314990591093">mg src="http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4FN2N71-1-D/0?wchp=dGLbVtb-zSkWb" alt="Click to view the MathML source" align="absbottom" border="0" height=15 width=99> with at least me="mml6">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml6&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=c2e277627362a830172052423afcf397" title="Click to view the MathML source">mg src="http://www.sciencedirect.com/scidirimg/entities/25b.gif" alt="var epsilon" border=0>n elements each, such that either every element of me="mml7">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml7&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=b07c1c1cf8885a2f5c771fc97e98308c">mg src="http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4FN2N71-1-G/0?wchp=dGLbVtb-zSkWb" alt="Click to view the MathML source" align="absbottom" border="0" height=14 width=25> intersects all elements of me="mml8">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml8&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=9c290ab1efef3fbeb51f31605c8f22bd">mg src="http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4FN2N71-1-H/0?wchp=dGLbVtb-zSkWb" alt="Click to view the MathML source" align="absbottom" border="0" height=14 width=26> or no element of me="mml9">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml9&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=16df4c6174e9863a147fdfbd2f71bb5a">mg src="http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4FN2N71-1-J/0?wchp=dGLbVtb-zSkWb" alt="Click to view the MathML source" align="absbottom" border="0" height=14 width=25> intersects any element of me="mml10">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml10&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=c0ac9cb8c67110f49dfdcc1a16ae1644">mg src="http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4FN2N71-1-2/0?wchp=dGLbVtb-zSkWb" alt="Click to view the MathML source" align="absbottom" border="0" height=14 width=26>. This implies the existence of another constant me="mml11">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml11&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=ac86c25996c353d86576b77b2b33a06c" title="Click to view the MathML source">δ such that me="mml12">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml12&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=ec57e5ed326b0b3f15e4adc4c5d94787">mg src="http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4FN2N71-1-4/0?wchp=dGLbVtb-zSkWb" alt="Click to view the MathML source" align="absbottom" border="0" height=12 width=18> has a subset me="mml13">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml13&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=b8776a2465a9823215782166419a0427">mg src="http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4FN2N71-1-5/0?wchp=dGLbVtb-zSkWb" alt="Click to view the MathML source" align="absbottom" border="0" height=16 width=63> with me="mml14">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml14&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=fae5508823bbdf4ec6b839bf4eeee6c4" title="Click to view the MathML source">n^δ elements, so that either every pair of elements of me="mml15">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml15&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=bc07496947b92264376d2ed404ec34ca">mg src="http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4FN2N71-1-7/0?wchp=dGLbVtb-zSkWb" alt="Click to view the MathML source" align="absbottom" border="0" height=14 width=23> intersect each other or the elements of me="mml16">method=retrieve&_udi=B6WHS-4FN2N71-1&_mathId=mml16&_user=10&_cdi=6858&_rdoc=12&_handle=V-WA-A-W-AE-MsSAYZA-UUA-U-AABZWYCVYW-AABBYZZWYW-CADVEEVCW-AE-U&_acct=C000050221&_version=1&_userid=10&md5=56b797fb8fd120e56b75c4a3b19c6c1d">mg src="http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4FN2N71-1-8/0?wchp=dGLbVtb-zSkWb" alt="Click to view the MathML source" align="absbottom" border="0" height=14 width=23> are pairwise disjoint. The same results hold when the intersection relation is replaced by any other semi-algebraic relation. We apply these results to settle several problems in discrete geometry and in Ramsey theory.