<p>In this paper, we develop a sequential Hamilton framework, which is of independent interest, settling the problem proposed by Gupta et al. (2023) when <i>k</i> = 3, and draw the general conclusion for any <i>k</i> ⩾ 3 as follows. A <i>k</i>-graph system <Emphasis Type="BoldItalic">H</Emphasis> = {<i>H</i><sub><i>i</i></sub>}<sub><i>i</i>∈[<i>m</i>]</sub> is a family of not necessarily distinct <i>k</i>-graphs on the same <i>n</i>-vertex set <i>V</i>; moreover, a <i>k</i>-graph <i>H</i> on <i>V</i> with <i>m</i> edges is transversal in <Emphasis Type="BoldItalic">H</Emphasis> if there is a bijection <i>φ</i>: <i>E</i>(<i>H</i>) → [<i>m</i>] such that <i>e</i> ∈ <i>E</i>(<i>H</i><sub><i>φ</i>(<i>e</i>)</sub>) for each <i>e</i> ∈ <i>E</i>(<i>H</i>). We show that given <i>γ</i> &gt; 0, <i>k</i> ⩾ 3, sufficiently large <i>n</i> and an <i>n</i>-vertex <i>k</i>-graph system <Emphasis Type="BoldItalic">H</Emphasis> = {<i>H</i><sub><i>i</i></sub>}<sub><i>i</i>∈[<i>n</i>]</sub>, if <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\delta_{k-2}(H_{i}) \geqslant (5/9+\gamma)\left({\matrix{n\cr2}}\right)\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msub> <mi>δ</mi> <mrow> <mi>k</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <mo stretchy="false">(</mo> <msub> <mi>H</mi> <mrow> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>⩾</mo> <mo stretchy="false">(</mo> <mn>5</mn> <mrow> <mo>/</mo> </mrow> <mn>9</mn> <mo>+</mo> <mi>γ</mi> <mo stretchy="false">)</mo> <mrow> <mo>(</mo> <mrow> <mtable> <mtr> <mtd> <mi>n</mi> </mtd> </mtr> <mtr> <mtd> <mn>2</mn> </mtd> </mtr> </mtable> </mrow> <mo>)</mo> </mrow> </math></EquationSource> </InlineEquation> for <i>i</i> ∈ [<i>n</i>], then there exists a tight Hamilton cycle which is transversal in <Emphasis Type="BoldItalic">H</Emphasis>. This result implies the conclusion in a single graph, which was proved by Lang and Sanhueza-Matamala (2022) and Polcyn et al. (2021) independently.</p>

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

Transversal Hamilton cycle in the hypergraph system

  • Yucong Tang,
  • Bin Wang,
  • Guanghui Wang,
  • Guiying Yan

摘要

In this paper, we develop a sequential Hamilton framework, which is of independent interest, settling the problem proposed by Gupta et al. (2023) when k = 3, and draw the general conclusion for any k ⩾ 3 as follows. A k-graph system H = {Hi}i∈[m] is a family of not necessarily distinct k-graphs on the same n-vertex set V; moreover, a k-graph H on V with m edges is transversal in H if there is a bijection φ: E(H) → [m] such that eE(Hφ(e)) for each eE(H). We show that given γ > 0, k ⩾ 3, sufficiently large n and an n-vertex k-graph system H = {Hi}i∈[n], if \(\delta_{k-2}(H_{i}) \geqslant (5/9+\gamma)\left({\matrix{n\cr2}}\right)\) δ k 2 ( H i ) ( 5 / 9 + γ ) ( n 2 ) for i ∈ [n], then there exists a tight Hamilton cycle which is transversal in H. This result implies the conclusion in a single graph, which was proved by Lang and Sanhueza-Matamala (2022) and Polcyn et al. (2021) independently.