<p>The <i>(weak) chromatic number</i> of a hypergraph <i>H</i>, denoted by <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\chi (H)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>χ</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, is the smallest number of colors required to color the vertices of <i>H</i> so that no hyperedge of <i>H</i> is monochromatic. For every <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(2\le k\le d+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mo>≤</mo> <mi>k</mi> <mo>≤</mo> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, denote by <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\chi _L(k,d)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <mi>L</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>,</mo> <mi>d</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> (resp. <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\chi _{PL}(k,d)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <mrow> <mi mathvariant="italic">PL</mi> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>,</mo> <mi>d</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>) the supremum <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\sup _H \chi (H)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mo movablelimits="true">sup</mo> <mi>H</mi> </msub> <mi>χ</mi> <mrow> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> where <i>H</i> runs over all finite <i>k</i>-uniform hypergraphs such that <i>H</i> forms the collection of maximal faces of a simplicial complex that is linearly (resp. PL) embeddable in <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\mathbb {R}^d\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>d</mi> </msup> </math></EquationSource> </InlineEquation>. Following the program by Heise, Panagiotou, Pikhurko and Taraz, we improve their results as follows: For <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(d \ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, we show that A. <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\chi _L(k,d)=\infty \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <mi>L</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>,</mo> <mi>d</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation> for all <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(2\le k\le d\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mo>≤</mo> <mi>k</mi> <mo>≤</mo> <mi>d</mi> </mrow> </math></EquationSource> </InlineEquation>, B. <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\chi _{PL}(d+1,d)=\infty \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <mrow> <mi mathvariant="italic">PL</mi> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>d</mi> <mo>+</mo> <mn>1</mn> <mo>,</mo> <mi>d</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation> and C. <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(\chi _L(d+1,d)\ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <mi>L</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>d</mi> <mo>+</mo> <mn>1</mn> <mo>,</mo> <mi>d</mi> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> for all odd <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(d\ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>. As an application, we extend the results by Lutz and Møller on the weak chromatic number of the <i>s</i>-dimensional faces in the triangulations of a fixed triangulable <i>d</i>-manifold <i>M</i>: D. <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(\chi _s(M)=\infty \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <mi>s</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>M</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(1\le s \le d\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mi>s</mi> <mo>≤</mo> <mi>d</mi> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

On Colorings of Hypergraphs Embeddable in \(\mathbb {R}^d\)

  • Seunghun Lee,
  • Eran Nevo

摘要

The (weak) chromatic number of a hypergraph H, denoted by \(\chi (H)\) χ ( H ) , is the smallest number of colors required to color the vertices of H so that no hyperedge of H is monochromatic. For every \(2\le k\le d+1\) 2 k d + 1 , denote by \(\chi _L(k,d)\) χ L ( k , d ) (resp. \(\chi _{PL}(k,d)\) χ PL ( k , d ) ) the supremum \(\sup _H \chi (H)\) sup H χ ( H ) where H runs over all finite k-uniform hypergraphs such that H forms the collection of maximal faces of a simplicial complex that is linearly (resp. PL) embeddable in \(\mathbb {R}^d\) R d . Following the program by Heise, Panagiotou, Pikhurko and Taraz, we improve their results as follows: For \(d \ge 3\) d 3 , we show that A. \(\chi _L(k,d)=\infty \) χ L ( k , d ) = for all \(2\le k\le d\) 2 k d , B. \(\chi _{PL}(d+1,d)=\infty \) χ PL ( d + 1 , d ) = and C. \(\chi _L(d+1,d)\ge 3\) χ L ( d + 1 , d ) 3 for all odd \(d\ge 3\) d 3 . As an application, we extend the results by Lutz and Møller on the weak chromatic number of the s-dimensional faces in the triangulations of a fixed triangulable d-manifold M: D. \(\chi _s(M)=\infty \) χ s ( M ) = for \(1\le s \le d\) 1 s d .