Type: Article

A rainbow Ramsey analogue of Rado's theorem

De Loera, J. A.; La Haye, R. N.; Montejano, A.; Oliveros, D.; Roldán-Pensado, E.;

Abstract:

Rado's Theorem is a classic result in arithmetic Ramsey theory classifying which systems of linear equations are regular, meaning that no matter how the positive integers are colored using k?1 colors, there will always be a monochromatic solution to the system. This compact paper provides a rainbow Ramsey analogue of Rado's fundamental theorem, disproves two conjectures of V. Jungi?, J. Nešet?il and R. Radoi?i? [Integers 5 (2005), no. 2, A9, 13 pp.; MR2192087] and of J. Fox, M. Mahdian and Radoi?i? [Discrete Math. 308 (2008), no. 20, 4773–4778; MR2438181], and concludes with applications to graph theory and matrices associated to the Fibonacci numbers. Ehrhart quasi-polynomials and Ehrhart-MacDonald reciprocity feature in the main proof. Let k?1 be an integer and let X be a set. A k-coloring of X is a surjective map c:X?{1,2,…,k}. A vector with coordinates from X is called rainbow if every coordinate in the vector is colored by a different color. ? A rational entry matrix A is rainbow partition k-regular if, for every integer n and for every equinumerous k-coloring of the integers [1,kn], there exists a rainbow vector with entries from the integers [1,kn] contained in kerA. Such a vector corresponds to a rainbow solution to the system of linear equations determined by A. ? The matrix A is simply called rainbow regular if A is rainbow partition k-regular for all sufficiently large k. ? The matrix A is robustly rainbow regular if there is a constant C>0 such that, for every ?>0 and positive integer n, the following holds for all sufficiently large k: for every k-coloring of the integers [1,kn] having each color used at least (C??)nk? times, there is a rainbow vector with entries from [1,kn] contained in kerA. The main result of the authors is to show that the following four conditions are equivalent for an m×d rational entry matrix A. 1. A is rainbow regular. 2. A is robustly rainbow regular. 3. There exists at least one vector from kerA with positive integer entries and every submatrix of A obtained by deleting two columns has the same rank as A. 4. There exists at least one vector from kerA with positive integer entries and, for every pair of distinct indices (i,j), there exists a pair of vectors x=(x1,…,xd) and y=(y1,…,yd) in kerA with xiyj?xjyi.