RUS  ENG
Полная версия
ЖУРНАЛЫ // Algebra and Discrete Mathematics // Архив

Algebra Discrete Math., 2016, том 22, выпуск 1, страницы 1–10 (Mi adm571)

RESEARCH ARTICLE

On colouring integers avoiding $t$-AP distance-sets

Tanbir Ahmed

Laboratoire de Combinatoire et d'Informatique Mathématique, UQAM, Montréal, Canada

Аннотация: A $t$-AP is a sequence of the form $a,a+d,\ldots, a+(t-1)d$, where $a,d\in \mathbb{Z}$. Given a finite set $X$ and positive integers $d$, $t$, $a_1,a_2,\ldots,a_{t-1}$, define $\nu(X,d) = |\{(x,y):{x,y\in{X}},{y>x}, {y-x=d}\}|$, $(a_1,a_2,\ldots,a_{t-1};d) =$ a collection $X$ s.t. $\nu(X,d\cdot{i})\geq a_i$ for $1\leq i\leq t-1$.
In this paper, we investigate the structure of sets with bounded number of pairs with certain gaps. Let $(t-1,t-2,\ldots,1; d)$ be called a $t$-AP distance-set of size at least $t$. A $k$-colouring of integers $1,2,\ldots, n$ is a mapping $\{1,2,\ldots,n\}\rightarrow \{0,1,\ldots,k-1\}$ where $0,1,\ldots,k-1$ are colours. Let $ww(k,t)$ denote the smallest positive integer $n$ such that every $k$-colouring of $1,2,\ldots,n$ contains a monochromatic $t$-AP distance-set for some $d>0$. We conjecture that $ww(2,t)\geq t^2$ and prove the lower bound for most cases. We also generalize the notion of $ww(k,t)$ and prove several lower bounds.

Ключевые слова: distance sets, colouring integers, sets and sequences.

MSC: 05D10

Поступила в редакцию: 05.10.2015
Исправленный вариант: 15.01.2016

Язык публикации: английский



Реферативные базы данных:


© МИАН, 2024