<p>We prove that every partially ordered set on <i>n</i> elements contains <i>k</i> subsets <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(A_{1},A_{2},\dots ,A_{k}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>A</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>A</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>A</mi> <mi>k</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> such that either each of these subsets has size <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\Omega (n/k^{5})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">/</mo> <msup> <mi>k</mi> <mn>5</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and, for every <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(i&lt;j\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>&lt;</mo> <mi>j</mi> </mrow> </math></EquationSource> </InlineEquation>, every element in <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(A_{i}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>A</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> is less than or equal to every element in <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(A_{j}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>A</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation>, or each of these subsets has size <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\Omega (n/(k^{2}\log n))\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">/</mo> <mrow> <mo stretchy="false">(</mo> <msup> <mi>k</mi> <mn>2</mn> </msup> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and, for every <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(i \not = j\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>≠</mo> <mi>j</mi> </mrow> </math></EquationSource> </InlineEquation>, every element in <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(A_{i}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>A</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> is incomparable with every element in <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(A_{j}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>A</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(i\ne j\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>≠</mo> <mi>j</mi> </mrow> </math></EquationSource> </InlineEquation>. This answers a question of the first author from 2006. As a corollary, we prove for each positive integer <i>h</i> there is <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(C_h\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mi>h</mi> </msub> </math></EquationSource> </InlineEquation> such that for any <i>h</i> partial orders <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(&lt;_{1},&lt;_{2},\dots ,&lt;_{h}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mo>&lt;</mo> <mn>1</mn> </msub> <mo>,</mo> <msub> <mo>&lt;</mo> <mn>2</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mo>&lt;</mo> <mi>h</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> on a set of <i>n</i> elements, there exists <i>k</i> subsets <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(A_{1},A_{2},\dots ,A_{k}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>A</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>A</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>A</mi> <mi>k</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> each of size at least <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(n/(k\log n)^{C_{h}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo stretchy="false">/</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <msub> <mi>C</mi> <mi>h</mi> </msub> </msup> </mrow> </math></EquationSource> </InlineEquation> such that for each partial order <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(&lt;_{\ell }\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mo>&lt;</mo> <mi>ℓ</mi> </msub> </math></EquationSource> </InlineEquation>, either <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(a_{1}&lt;_{\ell }a_{2}&lt;_{\ell }\dots &lt;_{\ell }a_{k}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>a</mi> <mn>1</mn> </msub> <msub> <mo>&lt;</mo> <mi>ℓ</mi> </msub> <msub> <mi>a</mi> <mn>2</mn> </msub> <msub> <mo>&lt;</mo> <mi>ℓ</mi> </msub> <mo>⋯</mo> <msub> <mo>&lt;</mo> <mi>ℓ</mi> </msub> <msub> <mi>a</mi> <mi>k</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> for any tuple of elements <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\((a_1,a_2,\dots ,a_k) \in A_1\times A_2\times \dots \times A_k\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">(</mo> <msub> <mi>a</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>a</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>a</mi> <mi>k</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>∈</mo> <msub> <mi>A</mi> <mn>1</mn> </msub> <mo>×</mo> <msub> <mi>A</mi> <mn>2</mn> </msub> <mo>×</mo> <mo>⋯</mo> <mo>×</mo> <msub> <mi>A</mi> <mi>k</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, or <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(a_{1}&gt;_{\ell }a_{2}&gt;_{\ell }\dots &gt;_{\ell }a_{k}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>a</mi> <mn>1</mn> </msub> <msub> <mo>&gt;</mo> <mi>ℓ</mi> </msub> <msub> <mi>a</mi> <mn>2</mn> </msub> <msub> <mo>&gt;</mo> <mi>ℓ</mi> </msub> <mo>⋯</mo> <msub> <mo>&gt;</mo> <mi>ℓ</mi> </msub> <msub> <mi>a</mi> <mi>k</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> for any <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\((a_1,a_2,\dots ,a_k) \in A_1\times A_2\times \dots \times A_k\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">(</mo> <msub> <mi>a</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>a</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>a</mi> <mi>k</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>∈</mo> <msub> <mi>A</mi> <mn>1</mn> </msub> <mo>×</mo> <msub> <mi>A</mi> <mn>2</mn> </msub> <mo>×</mo> <mo>⋯</mo> <mo>×</mo> <msub> <mi>A</mi> <mi>k</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, or <InlineEquation ID="IEq20"> <EquationSource Format="TEX">\(a_i\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>a</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> is incomparable with <InlineEquation ID="IEq21"> <EquationSource Format="TEX">\(a_j\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>a</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation> for any <InlineEquation ID="IEq22"> <EquationSource Format="TEX">\(i\ne j\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>≠</mo> <mi>j</mi> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq23"> <EquationSource Format="TEX">\(a_i\in A_i\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>a</mi> <mi>i</mi> </msub> <mo>∈</mo> <msub> <mi>A</mi> <mi>i</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq24"> <EquationSource Format="TEX">\(a_j\in A_j\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>a</mi> <mi>j</mi> </msub> <mo>∈</mo> <msub> <mi>A</mi> <mi>j</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>. This improves on a 2009 result of Pach and the first author motivated by problems in discrete geometry.</p>

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

A Multipartite Analogue of Dilworth’s Theorem

  • Jacob Fox,
  • Huy Tuan Pham

摘要

We prove that every partially ordered set on n elements contains k subsets \(A_{1},A_{2},\dots ,A_{k}\) A 1 , A 2 , , A k such that either each of these subsets has size \(\Omega (n/k^{5})\) Ω ( n / k 5 ) and, for every \(i<j\) i < j , every element in \(A_{i}\) A i is less than or equal to every element in \(A_{j}\) A j , or each of these subsets has size \(\Omega (n/(k^{2}\log n))\) Ω ( n / ( k 2 log n ) ) and, for every \(i \not = j\) i j , every element in \(A_{i}\) A i is incomparable with every element in \(A_{j}\) A j for \(i\ne j\) i j . This answers a question of the first author from 2006. As a corollary, we prove for each positive integer h there is \(C_h\) C h such that for any h partial orders \(<_{1},<_{2},\dots ,<_{h}\) < 1 , < 2 , , < h on a set of n elements, there exists k subsets \(A_{1},A_{2},\dots ,A_{k}\) A 1 , A 2 , , A k each of size at least \(n/(k\log n)^{C_{h}}\) n / ( k log n ) C h such that for each partial order \(<_{\ell }\) < , either \(a_{1}<_{\ell }a_{2}<_{\ell }\dots <_{\ell }a_{k}\) a 1 < a 2 < < a k for any tuple of elements \((a_1,a_2,\dots ,a_k) \in A_1\times A_2\times \dots \times A_k\) ( a 1 , a 2 , , a k ) A 1 × A 2 × × A k , or \(a_{1}>_{\ell }a_{2}>_{\ell }\dots >_{\ell }a_{k}\) a 1 > a 2 > > a k for any \((a_1,a_2,\dots ,a_k) \in A_1\times A_2\times \dots \times A_k\) ( a 1 , a 2 , , a k ) A 1 × A 2 × × A k , or \(a_i\) a i is incomparable with \(a_j\) a j for any \(i\ne j\) i j , \(a_i\in A_i\) a i A i and \(a_j\in A_j\) a j A j . This improves on a 2009 result of Pach and the first author motivated by problems in discrete geometry.