Search

In its usual form, Freiman's 3k−4$3k-4$ theorem states that if A$A$ and B$B$ are subsets of Z${\mathbb {Z}}$ of size k$k$ with small sumset (of size close to 2k$2k$), then they are very close to arithmetic progressions. Our aim in this paper is to strengthen this by allowing only a bounded number of possible summands from one of the sets. We show that if A$A$ and B$B$ are subsets of Z${\mathbb {Z}}$ of size k$k$ such that for any four‐element subset X$X$ of B$B$ the sumset A+X$A+X$ has size not much more than 2k$2k$, then already this implies that A$A$ and B$B$ are very close to arithmetic progressions. [ABSTRACT FROM AUTHOR]

How many random transpositions (meaning that we swap given pairs of elements with given probabilities independently) are needed to ensure that each element of [n] is uniformly distributed--in the sense that the probability that i is mapped to j is 1/n for all i and j And what if we insist that each pair is uniformly distributed In this paper we show that the minimum for the first problem is about 1 2nlog2 n, with this being exact when n is a power of 2. For the second problem, we show that, rather surprisingly, the answer is not quadratic: O(nlog2 n) random transpositions suffice. We also show that if we ask only that the pair (1, 2) is uniformly distributed, then the answer is 2n 3. This proves a conjecture of Groenland, Johnston, Radcliffe, and Scott. [ABSTRACT FROM AUTHOR]

Our aim in this paper is to show that, for any k, there is a finite colouring of the set of rationals whose denominators contain only the first fc primes such that no infinite set has all of its finite sums and products monochromatic. We actually prove a 'uniform' form of this: there is a finite colouring of the rationals with the property that no infinite set whose denominators contain only finitely many primes has all of its finite sums and products monochromatic. We also give various other results, including a new short proof of the old result that there is a finite colouring of the naturals such that no infinite set has all of its pairwise sums and products monochromatic. [ABSTRACT FROM AUTHOR]

A factorisation x=u1u2⋯$x = u_1 u_2 \cdots$ of an infinite word x$x$ on alphabet X$X$ is called 'monochromatic', for a given colouring of the finite words X∗$X^*$ on alphabet X$X$, if each ui$u_i$ is the same colour. Wojcik and Zamboni proved that the word x$x$ is periodic if and only if for every finite colouring of X∗$X^*$ there is a monochromatic factorisation of x$x$. On the other hand, it follows from Ramsey's theorem that, for any word x$x$, for every finite colouring of X∗$X^*$ there is a suffix of x$x$ having a monochromatic factorisation. A factorisation x=u1u2⋯$x = u_1 u_2 \cdots$ is called 'super‐monochromatic' if each word uk1uk2⋯ukn$u_{k_1} u_{k_2} \cdots u_{k_n}$, where k1<⋯

In this paper we study the following geometric problem: given $2^n-1$ real numbers $x_A$ indexed by the nonempty subsets $A\subset \{1,\dots,n\}$, is it possible to construct a body $T\subset \mathbb{R}^n$ such that $x_A=|T_A|$, where $|T_A|$ is the $|A|$-dimensional volume of the projection of $T$ onto the subspace spanned by the axes in $A$? As it is more convenient to take logarithms, we denote by $\psi_n$ the set of all vectors $x$ for which there is a body $T$ such that $x_A=\log |T_A|$ for all $A$. Bollobás and Thomason showed that $\psi_n$ is contained in the polyhedral cone defined by the class of "uniform cover inequalities." Tan and Zeng conjectured that the convex hull $\operatorname{conv}(\psi_n)$ is equal to the cone given by the uniform cover inequalities. We prove that this conjecture is "nearly" right: the closed convex hull $\overline{\operatorname{conv}}(\psi_n)$ is equal to the cone given by the uniform cover inequalities. However, perhaps surprisingly, we also show that $\operatorname{conv}(\psi_n)$ is not closed for $n\ge 4$, thus disproving the conjecture. [ABSTRACT FROM AUTHOR]