A new proof on the Ramsey number of matchings
share
For given simple graphs H_1,H_2,...,H_c, the Ramsey number r(H_1,H_2,...,H_c) is the smallest positive integer n such that every edge-colored K_n with c colors contains a subgraph isomorphic to H_i in color i for some i∈{1,2,...,c}. A critical graph of r(H_1,H_2,...,H_c) is an edge-colored complete graph on r(H_1,H_2,...,H_c)-1 vertices with c colors which contains no subgraph isomorphic to H_i in color i for any i∈{1,2,...,c}. For n_1≥ n_2≥...≥ n_c≥ 1, Cockayne and Lorimer (The Ramsey number for stripes, J. Austral. Math. Soc. 19 (1975) 252--256.) showed that r(n_1K_2,n_2K_2,...,n_cK_2)=n_1+1+ ∑_i=1^c(n_i-1), in which n_iK_2 is a matching of size n_i. In this paper, using Gallai-Edmonds Structure Theorem, we give a new proof on the value of r(n_1K_2,n_2K_2,...,n_cK_2) which also characterized all critical graphs.
READ FULL TEXT