<p>We say that a poset <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9693_Article_IEq1.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">\((Q,\le _{Q})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>Q</mi> <mo>,</mo> <msub> <mo>≤</mo> <mi>Q</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> contains an induced copy of a poset <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9693_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">\((P,\le _P)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <msub> <mo>≤</mo> <mi>P</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> if there is an injective function <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9693_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="83" /> </InlineMediaObject> <EquationSource Format="TEX">\(\phi :P\rightarrow Q\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϕ</mi> <mo>:</mo> <mi>P</mi> <mo stretchy="false">→</mo> <mi>Q</mi> </mrow> </math></EquationSource> </InlineEquation> such that for every two <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9693_Article_IEq4.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="147" /> </InlineMediaObject> <EquationSource Format="TEX">\(X,Y\in P,\;\; X\le _P Y\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>X</mi> <mo>,</mo> <mi>Y</mi> <mo>∈</mo> <mi>P</mi> <mo>,</mo> <mspace width="0.277778em" /> <mspace width="0.277778em" /> <mi>X</mi> <msub> <mo>≤</mo> <mi>P</mi> </msub> <mi>Y</mi> </mrow> </math></EquationSource> </InlineEquation> if and only if <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9693_Article_IEq5.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="109" /> </InlineMediaObject> <EquationSource Format="TEX">\(\phi (X)\le _Q \phi (Y)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϕ</mi> <mrow> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> </mrow> <msub> <mo>≤</mo> <mi>Q</mi> </msub> <mi>ϕ</mi> <mrow> <mo stretchy="false">(</mo> <mi>Y</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. We denote the Boolean lattice <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9693_Article_IEq6.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="57" /> </InlineMediaObject> <EquationSource Format="TEX">\((2^{[n]},\subseteq )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mrow> <mo stretchy="false">[</mo> <mi>n</mi> <mo stretchy="false">]</mo> </mrow> </msup> <mo>,</mo> <mo>⊆</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> by <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9693_Article_IEq7.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">\(Q_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation>. Given a fixed 2-coloring <i>c</i> of a poset <i>P</i>, the poset Erdős-Hajnal number of this colored poset is the smallest integer <i>N</i> such that every 2-coloring of the Boolean lattice <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9693_Article_IEq8.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="27" /> </InlineMediaObject> <EquationSource Format="TEX">\(Q_N\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>N</mi> </msub> </math></EquationSource> </InlineEquation> contains an induced copy of <i>P</i> colored as in <i>c</i>, or a monochromatic induced copy of <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9693_Article_IEq7.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">\(Q_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation>. We present bounds on the poset Erdős-Hajnal number of general colored posets, antichains, chains, and small Boolean lattices. Let the poset Ramsey number <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9693_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="76" /> </InlineMediaObject> <EquationSource Format="TEX">\(R(Q_n,Q_n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo stretchy="false">(</mo> <msub> <mi>Q</mi> <mi>n</mi> </msub> <mo>,</mo> <msub> <mi>Q</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> be the least <i>N</i> such that every 2-coloring of <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9693_Article_IEq8.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="27" /> </InlineMediaObject> <EquationSource Format="TEX">\(Q_N\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>N</mi> </msub> </math></EquationSource> </InlineEquation> contains a monochromatic induced copy of <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9693_Article_IEq7.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">\(Q_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation>. As a corollary, we show that <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9693_Article_IEq13.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="139" /> </InlineMediaObject> <EquationSource Format="TEX">\(R(Q_n,Q_n)&gt; 2.02n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo stretchy="false">(</mo> <msub> <mi>Q</mi> <mi>n</mi> </msub> <mo>,</mo> <msub> <mi>Q</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> <mo>&gt;</mo> <mn>2.02</mn> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>, improving on the best known lower bound <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9693_Article_IEq14.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="48" /> </InlineMediaObject> <EquationSource Format="TEX">\(2n+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> by Cox and Stolee (Order <b>35</b>(3), 557–579 2018).</p>

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

Erdős-Hajnal Problems for Posets

  • Christian Winter

摘要

We say that a poset \((Q,\le _{Q})\) ( Q , Q ) contains an induced copy of a poset \((P,\le _P)\) ( P , P ) if there is an injective function \(\phi :P\rightarrow Q\) ϕ : P Q such that for every two \(X,Y\in P,\;\; X\le _P Y\) X , Y P , X P Y if and only if \(\phi (X)\le _Q \phi (Y)\) ϕ ( X ) Q ϕ ( Y ) . We denote the Boolean lattice \((2^{[n]},\subseteq )\) ( 2 [ n ] , ) by \(Q_n\) Q n . Given a fixed 2-coloring c of a poset P, the poset Erdős-Hajnal number of this colored poset is the smallest integer N such that every 2-coloring of the Boolean lattice \(Q_N\) Q N contains an induced copy of P colored as in c, or a monochromatic induced copy of \(Q_n\) Q n . We present bounds on the poset Erdős-Hajnal number of general colored posets, antichains, chains, and small Boolean lattices. Let the poset Ramsey number \(R(Q_n,Q_n)\) R ( Q n , Q n ) be the least N such that every 2-coloring of \(Q_N\) Q N contains a monochromatic induced copy of \(Q_n\) Q n . As a corollary, we show that \(R(Q_n,Q_n)> 2.02n\) R ( Q n , Q n ) > 2.02 n , improving on the best known lower bound \(2n+1\) 2 n + 1 by Cox and Stolee (Order 35(3), 557–579 2018).