Anti-Ramsey number of matchings in hypergraphs
Anti-Ramsey number of matchings in hypergraphs
复制标题
DOI：
10.1016/j.disc.2013.06.015
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
Lale Özkahya;Michael Young
中科院分区：
文献类型：
--
作者：
Lale Özkahya;Michael Young
超图中的k匹配是k条边的集合，使得这些边中没有两条相交。在n个顶点上的完全s-均匀超图H中的k匹配的反拉姆齐数，记为ar (n, s, k)，是最小的整数c，使得在H的恰好c种颜色的边的任何着色中，都存在一个k匹配的边具有不同的颜色。Turán数字，用ex （n, s, k）表示，是在n个顶点上无k匹配的s-均匀超图的最大边数。对于k≥3，我们推测如果n>是k，则ar (n, s, k)= ex (n, s, k−1)+ 2。同样，如果n= k，则如果k< c，则ar (n, s, k)={ex (n, s, k−1)+ 2，如果k≥c，则ex (n, s, k−1)+ s+ 1，其中c s是依赖于s的常数。我们在k= 2, k= 3和足够大的n时证明了这一猜想，并给出了上界和下界。
A k-matching in a hypergraph is a set of k edges such that no two of these edges intersect. The anti-Ramsey number of a k-matching in a complete s-uniform hypergraph H on n vertices, denoted by ar (n, s, k), is the smallest integer c such that in any coloring of the edges of H with exactly c colors, there is a k-matching whose edges have distinct colors. The Turán number, denoted by ex (n, s, k), is the the maximum number of edges in an s-uniform hypergraph on n vertices with no k-matching. For k≥ 3, we conjecture that if n> s k, then ar (n, s, k)= ex (n, s, k− 1)+ 2. Also, if n= s k, then ar (n, s, k)={ex (n, s, k− 1)+ 2 if k< c s ex (n, s, k− 1)+ s+ 1 if k≥ c s, where c s is a constant dependent on s. We prove this conjecture for k= 2, k= 3, and sufficiently large n, as well as provide upper and lower bounds.