On tiling the integers with 4-sets of the same gap sequence

Partitioning a set into similar, if not, identical, parts is a fundamental research topic in combinatorics. The question of partitioning the integers in various ways has been considered throughout history. Given a set $\{x_1,\dots ,x_n\}$ of integers where $x_1<?<x_n$, let the gap sequence of this set be the unordered multiset $\{d_1,\dots ,d_{n?1}\}=\{x_{i+1}?x_i:i\in \{1,\dots ,n?1\}\}$. This paper addresses the following question, which was explicitly asked by Nakamigawa: can the set of integers be partitioned into sets with the same gap sequence? The question is known to be true for any set where the gap sequence has length at most two. This paper provides evidence that the question is true when the gap sequence has length three. Namely, we prove that given positive integers $p$ and $q$, there is a positive integer $r_0$ such that for all $r\ge r_0$, the set of integers can be partitioned into 4-sets with gap sequence $p,q$, $r$.     

Sequences of binary irreducible polynomials

In this paper we construct an infinite sequence of binary irreducible polynomials starting from any irreducible polynomial $f_0\in F_2\left[x\right]$. If $f_0$ is of degree $n=2^l?m$, where $m$ is odd and $l$ is a nonnegative integer, after an initial finite sequence of polynomials $f_0,f_1,\dots ,f_s$, with $s\le l+3$, the degree of $f_{i+1}$ is twice the degree of $f_i$ for any $i\ge s$.     

The expansion of a chord diagram and the Tutte polynomial

A chord diagram is a set of chords of a circle such that no pair of chords has a common endvertex. A chord diagram $E$ is called nonintersecting if $E$ contains no crossing. For a chord diagram $E$ having a crossing $S=\{x_1{x}_3,x_2{x}_4\}$, the expansion of $E$ with respect to $S$ is to replace $E$ with $E_1=(E?S)\cup \{x_2{x}_3,x_4{x}_1\}$ or $E_2=(E?S)\cup \{x_1{x}_2,x_3{x}_4\}$. For a chord diagram $E$, let $f\left(E\right)$ be the chord expansion number of $E$, which is defined as the cardinality of the multiset of all nonintersecting chord diagrams generated from $E$ with a finite sequence of expansions.In this paper, it is shown that the chord expansion number $f\left(E\right)$ equals the value of the Tutte polynomial at the point $(2,?1)$ for the interlace graph $G_E$ corresponding to $E$. The chord expansion number of a complete multipartite chord diagram is also studied. An extended abstract of the paper was published (Nakamigawa and Sakuma, 2017) [13].     

Maximum average degree and relaxed coloring

We say a graph is $(d,d,\dots ,d,0,\dots ,0)$-colorable with $a$ of $d$’s and $b$ of $0$’s if $V\left(G\right)$ may be partitioned into $b$ independent sets $O_1,O_2,\dots ,O_b$ and $a$ sets $D_1,D_2,\dots ,D_a$ whose induced graphs have maximum degree at most $d$. The maximum average degree, $mad\left(G\right)$, of a graph $G$ is the maximum average degree over all subgraphs of $G$. In this note, for nonnegative integers $a,b$, we show that if $mad\left(G\right)<\frac{4}{3}a+b$, then $G$ is $(1_1,1_2,\dots ,1_a,0_1,\dots ,0_b)$-colorable.     

On the sum of distinct primes or squares of primes

In 1965 Erd?s introduced $f_2(s)$: $f_2(s)$ is the smallest integer such that every $l>f_2(s)$ is the sum of s distinct primes or squares of primes where a prime and its square are not both used. We prove that for all sufficiently large s, $f_2(s)?p_2+p_3+?+p_{s+1}+3106$, and the set of s with the equality has the density 1.