Colorings with only rainbow arithmetic progressions

DOI10.1007/S10474-020-01076-9zbMATH Open1474.11037arXiv1912.07470OpenAlexW3044702813MaRDI QIDQ2220973FDOQ2220973

Authors: János Pach, István Tomon 

Publication date: 25 January 2021

Published in: Acta Mathematica Hungarica (Search for Journal in Brave)

Abstract: If we want to color $1,2,ldots,n$ with the property that all 3-term arithmetic progressions are rainbow (that is, their elements receive 3 distinct colors), then, obviously, we need to use at least $n/2$ colors. Surprisingly, much fewer colors suffice if we are allowed to leave a negligible proportion of integers uncolored. Specifically, we prove that there exist $$ such that for every $n$, there is a subset $A$ of $1,2,ldots,n$ of size at least $n-n^{alpha}$, the elements of which can be colored with $$ colors with the property that every 3-term arithmetic progression in $A$ is rainbow. Moreover, $$ can be chosen to be arbitrarily small. Our result can be easily extended to $k$-term arithmetic progressions for any $kge3$. As a corollary, we obtain the following result of Alon, Moitra, and Sudakov, which can be used to design efficient communication protocols over shared directional multi-channels. There exist $$ such that for every $n$, there is a graph with $n$ vertices and at least $$ edges, whose edge set can be partitioned into at most $$ induced matchings.

Full work available at URL: https://arxiv.org/abs/1912.07470

Recommendations

• On rainbow arithmetic progressions
• Integer colorings with no rainbow 3-term arithmetic progression
• scientific article; zbMATH DE number 2124068
• Integer colorings with no rainbow \(k\)-term arithmetic progression
• On the existence of rainbow 4-term arithmetic progressions

zbMATH Keywords

arithmetic progressioninduced matching rainbow

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Arithmetic progressions (11B25)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Title not available (Why is that?)
• Title not available (Why is that?)
• Testing subgraphs in directed graphs
• Monotonicity testing over general poset domains
• On sets of integers containing k elements in arithmetic progression
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Simple analysis of graph tests for linearity and PCP
• Title not available (Why is that?)
• Nearly complete graphs decomposable into large induced matchings and their applications
• On the uniform-traffic capacity of single-hop interconnections employing shared directional multichannels
• Testing subgraphs in large graphs
• Title not available (Why is that?)
• On graphs decomposable into induced matchings of linear sizes

Cited In (3)

• Schur numbers involving rainbow colorings
• Integer colorings with no rainbow 3-term arithmetic progression
• Arithmetic progressions, quasi progressions, and Gallai-Ramsey colorings

This page was built for publication: Colorings with only rainbow arithmetic progressions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220973)