Colorings with only rainbow arithmetic progressions

DOI10.1007/S10474-020-01076-9MaRDI QIDQ2220973zbMATH OpenOpenAlexFDO

Authors János Pach, István Tomon

Publication date 25 January 2021

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

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

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)

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.

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

Cites work

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

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)