<p>A <i>k</i>-<i>uniform tight cycle</i> is a <i>k</i>-graph with a cyclic ordering of its vertices such that its edges are precisely the sets of&#xa0;<i>k</i> consecutive vertices in that ordering. We show that, for each <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_173_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(k \ge 3\)</EquationSource> </InlineEquation>, the Ramsey number of the <i>k</i>-uniform tight cycle on <i>kn</i> vertices is <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_173_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="131" /> </InlineMediaObject> <EquationSource Format="TEX">\((1+o(1))(k+1)n\)</EquationSource> </InlineEquation>. This is an extension to all uniformities of previous results for <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_173_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(k = 3\)</EquationSource> </InlineEquation> by Haxell, Łuczak, Peng, Rödl, Ruciński, and Skokan and for <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_173_Article_IEq6.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(k = 4\)</EquationSource> </InlineEquation> by Lo and the author and confirms a special case of a conjecture by the former set of authors. Lehel’s conjecture, which was proved by Bessy and Thomassé, states that every red-blue edge-coloured complete graph contains a red cycle and a blue cycle that are vertex-disjoint and together cover all the vertices. We also prove an approximate version of this for <i>k</i>-uniform tight cycles. We show that, for every <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_173_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(k \ge 3\)</EquationSource> </InlineEquation>, every red-blue edge-coloured complete <i>k</i>-graph on <i>n</i> vertices contains a red tight cycle and a blue tight cycle that are vertex-disjoint and together cover <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_173_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="63" /> </InlineMediaObject> <EquationSource Format="TEX">\(n - o(n)\)</EquationSource> </InlineEquation> vertices.</p>

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

On k-uniform Tight Cycles: the Ramsey Number for \(C_{kn}^{(k)}\) and an Approximate Lehel’s Conjecture

  • Vincent Pfenninger

摘要

A k-uniform tight cycle is a k-graph with a cyclic ordering of its vertices such that its edges are precisely the sets of k consecutive vertices in that ordering. We show that, for each \(k \ge 3\) , the Ramsey number of the k-uniform tight cycle on kn vertices is \((1+o(1))(k+1)n\) . This is an extension to all uniformities of previous results for \(k = 3\) by Haxell, Łuczak, Peng, Rödl, Ruciński, and Skokan and for \(k = 4\) by Lo and the author and confirms a special case of a conjecture by the former set of authors. Lehel’s conjecture, which was proved by Bessy and Thomassé, states that every red-blue edge-coloured complete graph contains a red cycle and a blue cycle that are vertex-disjoint and together cover all the vertices. We also prove an approximate version of this for k-uniform tight cycles. We show that, for every \(k \ge 3\) , every red-blue edge-coloured complete k-graph on n vertices contains a red tight cycle and a blue tight cycle that are vertex-disjoint and together cover \(n - o(n)\) vertices.