Sub-Ramsey Numbers for Matchings
- PDF / 362,356 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 58 Downloads / 194 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Sub-Ramsey Numbers for Matchings Fangfang Wu1,2 • Shenggui Zhang1,2 • Binlong Li1,2 Received: 14 September 2019 / Revised: 12 July 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract Given a graph G and a positive integer k, the sub-Ramsey number sr(G, k) is defined to be the minimum number m such that every Km whose edges are colored using every color at most k times contains a subgraph isomorphic to G all of whose edges have distinct colors. In this paper, we will concentrate on srðnK2 ; kÞ with nK2 denoting a matching of size n. We first give upper and lower bounds for srðnK2 ; kÞ and exact values of srðnK2 ; kÞ for some n and k. Afterwards, we show that srðnK2 ; kÞ ¼ 2n when n is sufficiently large and k\ n8 by applying the Local Lemma. Keywords Sub-Ramsey number Rainbow matchings Local lemma
1 Introduction All graphs considered in this paper are simple and finite. For terminology and notation not defined here, we refer the reader to [5]. Let G be a graph and k a positive integer. An edge-coloring of G is a mapping C : EðGÞ ! N, where N is the set of natural numbers. We call C k-bounded if each color appears at most k times. If k ¼ 1, i.e., all edges of G have distinct colors, then we say that G is rainbow. The sub-Ramsey number sr(G, k) is defined to be the minimum number m such that every k-bounded edge-coloring of Km contains a rainbow subgraph isomorphic to G. & Shenggui Zhang [email protected] Fangfang Wu [email protected] Binlong Li [email protected] 1
School of Mathematics and Statistics, Northwestern Polytechnical University, Xi’an 710129, Shaanxi, China
2
Xi’an-Budapest Joint Research Center for Combinatorics, Northwestern Polytechnical University, Xi’an 710129, Shaanxi, China
123
Graphs and Combinatorics
The study of sub-Ramsey theory dates back to 1975 when Fred Galvin posed the Advanced Problem 6034 in the American Mathematical Monthly [12]. The problem description is as follows: Suppose that the edges of the complete graph on n vertices are colored so that no color appears more than k times. (1) If n k þ 2, show that there is a rainbow triangle. (2) Show that this is not necessarily so if n ¼ k þ 1. Galvin [12] gave a solution to this problem. After that, some related generalizations began to emerge. In Ref. [3] the authors gave the definition of the sub-Ramsey number and proved that srðG; kÞ rðG; kÞ (the definition of r(G, k) will be given later), and hence each sr(G, k) is guaranteed to be finite. So far the sub-Ramsey number has been considered for several special graph classes-complete graphs, paths, cycles and stars. Denote by Kn , Pn and Cn the complete graph, path and cycle of n vertices respectively, and K1;n the star with n þ 1 vertices. For complete graphs, Alspach et al. [3] proved that kðn 1Þ þ 1 srðKn ; kÞ
nðn 1Þðn 2Þðk 1Þ þ 3 ; 4
where n 4 and k 2. After that Hell et al. [16] showed that cn3=2 srðKn ; kÞ ð2n 3Þðn 2Þðk 1Þ þ 3 for some constant c, whic
Data Loading...
