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

Ramsey Numbers for Multiple Copies of Hypergraphs

  • Gholam Reza Omidi,
  • Ghaffar Raeisi

摘要

For given k-uniform hypergraphs \({\mathcal {G}}\) G and \({\mathcal {H}}\) H , the Ramsey number \(R({\mathcal {G}},{\mathcal {H}})\) R ( G , H ) is the smallest positive integer N such that in every red-blue coloring of the edges of the complete k-uniform hypergraph on n vertices there is either a red copy of \({\mathcal {G}}\) G or a blue copy of \({\mathcal {H}}\) H . In this paper, results are given which permit the \(R(m{\mathcal {G}},n{\mathcal {H}})\) R ( m G , n H ) to be evaluated exactly when m or n is large and \({\mathcal {G}}\) G is a k-uniform hypergraph with the maximum independent set that intersects each edge in \(k-1\) k - 1 vertices and \({\mathcal {H}}\) H is a k-uniform hypergraph with a vertex so that the hypergraph induced by the edges containing this vertex is a star. There are several examples for such \({\mathcal {G}}\) G and \({\mathcal {H}}\) H , among them are any disjoint union of k-uniform hypergraphs involving loose paths, loose cycles, tight paths, tight cycles, stars, Kneser hypergraphs and complete k-uniform k-partite hypergraphs for \({\mathcal {G}}\) G and linear hypergraphs for \({\mathcal {H}}\) H . As an application, \(R(m{\mathcal {G}},n{\mathcal {H}})\) R ( m G , n H ) is determined when m or n is large and \({\mathcal {G}}\) G , \({\mathcal {H}}\) H are either loose paths, loose cycles, tight paths or stars. Moreover, for given k-uniform hypergraphs \({\mathcal {G}}\) G and \({\mathcal {H}}\) H and positive integers mn, some bounds are given for \(R(m{\mathcal {G}},n{\mathcal {H}})\) R ( m G , n H ) which enable us to compute \(R(m{\mathcal {G}},n{\mathcal {H}})\) R ( m G , n H ) when \(m\ge n\ge 1\) m n 1 and \({\mathcal {G}}, {\mathcal {H}}\) G , H are either 3-uniform loose path \({\mathcal {P}}_r^3\) P r 3 or loose cycle \({\mathcal {C}}_r^3\) C r 3 : We shall show that for every \(m\ge n\ge 1\) m n 1 and \(r\ge s\) r s , \(R(m{\mathcal {C}}_r^3,n{\mathcal {C}}_s^3)=2rm+\Big \lfloor \frac{s+1}{2}\Big \rfloor n-1,\) R ( m C r 3 , n C s 3 ) = 2 r m + s + 1 2 n - 1 , and \(R(m{\mathcal {P}}_r^3,n{\mathcal {P}}_s^3)=(2r+1)m+\Big \lfloor \frac{s+1}{2}\Big \rfloor n-1.\) R ( m P r 3 , n P s 3 ) = ( 2 r + 1 ) m + s + 1 2 n - 1 .