Colorings with only rainbow arithmetic progressions

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

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

arithmetic progression induced matching rainbow

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

Abstract: If we want to color

1, 2, l d o t s, 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, l d o t s, n

of size at least

n - n^{a l p h a}

, 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

k g e 3

. 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.

Review text

In the paper it is proven that there exist \(\alpha, \beta < 1\) such that for every sufficiently large natural number \(n\), there is a set \(A\subset \{1,\dots,n\}\) with \(\vert A\vert \geq n- n^\alpha\) and a coloring of \(A\) with at most \(n^\beta\) colors, where every 3-term arithmetic progression in \(A\) is rainbow (i.e., their elements receive 3 distinct colors). This result is used to construct graphs with \(n\) vertices and \((1-o(1))\binom{n}{2}\) edges which can be partitioned into a small number of induced matchings. The first such constructions were found in \textit{N. Alon} et al. [J. Eur. Math. Soc. (JEMS) 15, No. 5, 1575--1596 (2013; Zbl 1278.05183)] as a corollary, a simple proof of main result the above paper is given.

Recommendations

Cites work

Cited in

(5)

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)