Let $C$ be a code of length $n$ over an alphabet of $q$ letters. A codeword $y$ is called a descendant of a set of $t$ codewords $\{x^1,\dots,x^t\}$ if $y_i \in \{x^1_i,\dots,x^t_i\}$ for all $i=1,\dots,n$. A code is said to have the Identifiable Parent Property of order $t$ if, for any word of length $n$ that is a descendant of at most $t$ codewords (parents), it is possible to identify at least one of them. Let $f_t(n,q)$ be the maximum possible cardinality of such a code. We prove that for any $t,n,q$, $(c_1(t)q)^{\frac{n}{s(t)}} < f_t(n,q) < c_2(t)q^{\lceil{\frac{n}{s(t)}}\rceil}$ where $s(t) = \lfloor(\frac{t}{2}+1)^2 \rfloor -1$ and $c_1(t),c_2(t)$ are some functions of $t$. We also show some bounds and constructions for $f_3(5,q)$, $f_3(6,q)$, and $f_t(n,q)$ when $n < s(t)$.

This note presents two results on real zeros of chromatic polynomials. The first result states that if $G$ is a graph containing a $q$-tree as a spanning subgraph, then the chromatic polynomial $P(G,\lambda)$ of $G$ has no non-integer zeros in the interval $(0,q)$. Sokal conjectured that for any graph $G$ and any real $\lambda>\Delta(G)$, $P(G,\lambda)>0$. Our second result confirms that it is true if $\Delta(G)\ge \lfloor n/3\rfloor -1$, where $n$ is the order of $G$.

Two infinite 0–1 sequences are called compatible when it is possible to cast out $0\,$s from both in such a way that they become complementary to each other. Answering a question of Peter Winkler, we show that if the two 0–1 sequences are random i.i.d. and independent from each other, with probability $p$ of $1\,$s, then if $p$ is sufficiently small they are compatible with positive probability. The question is equivalent to a certain dependent percolation with a power-law behaviour: the probability that the origin is blocked at distance $n$ but not closer decreases only polynomially fast and not, as usual, exponentially.

Let $G$ be a finite graph with maximum degree at most $d$. Then, for every partition of $V(G)$ into classes of size $3d-1$, there exists a proper colouring of $G$ with $3d-1$ colours in which each class receives all $3d-1$ colours.

Given a subset $S$ of an abelian group $G$ and an integer $k\geq 1$, the $k$-deck of $S$ is the function that assigns to every $T\subseteq G$ with at most $k$ elements the number of elements $g\in G$ with $g+T\subseteq S$. The reconstruction problem for an abelian group $G$ asks for the minimal value of $k$ such that every subset $S$ of $G$ is determined, up to translation, by its $k$-deck. This minimal value is the set-reconstruction number$r_{\rm set}(G)$ of $G$; the corresponding value for multisets is the reconstruction number$r(G)$.

Previous work had given bounds for the set-reconstruction number of cyclic groups: Alon, Caro, Krasikov and Roditty [1] showed that $r_{\rm set}({\mathbb{Z}}_n)<\log_2n$ and Radcliffe and Scott [15] that $r_{\rm set}({\mathbb{Z}}_n)<9\frac{\ln n}{\ln\ln n}$. We give a precise evaluation of $r(G)$ for all abelian groups $G$ and deduce that $r_{\rm set}({\mathbb{Z}}_n)\leq 6$.

Let $F\,{=}\,\{H_1,\ldots,H_k\}$ be a family of graphs. A graph $G$ is called totally$F$-decomposable if for every linear combination of the form $\alpha_1 e(H_1) \,{+}\,{\cdots}\,{+}\,\alpha_k e(H_k) \,{=}\, e(G)$ where each $\alpha_i$ is a nonnegative integer, there is a colouring of the edges of $G$ with $\alpha_1\,{+}\,{\cdots}\,{+}\,\alpha_k$ colours such that exactly $\alpha_i$ colour classes induce each a copy of $H_i$, for $i\,{=}\,1,\ldots,k$. We prove that if $F$ is any fixed nontrivial family of trees then $\log n/n$ is a sharp threshold function for the property that the random graph $G(n,p)$ is totally $F$-decomposable. In particular, if $H$ is a tree with more than one edge, then $\log n/n$ is a sharp threshold function for the property that $G(n,p)$ contains $\lfloor e(G)/e(H) \rfloor$ edge-disjoint copies of $H$.

A signing of a graph $G=(V,E)$ is a function $s:E \rightarrow \{-1,1\}$. A signing defines a graph $\widehat{G}$, called a {\em 2-lift of $G$}, with vertex set $V(G)\times\{-1,1\}$. The vertices $(u,x)$ and $(v,y)$ are adjacent iff $(u,v) \in E(G)$, and $x \cdot y = s(u,v)$. The corresponding signed adjacency matrix$A_{G,s}$ is a symmetric $\{-1,0,1\}$-matrix, with $(A_{G,s})_{u,v} = s(u,v)$ if $(u,v) \in E$, and $0$ otherwise.