Pruned discrete random samples

Let $X_i,i\in \mathbb{N}$, be independent and identically distributed random variables with values in ${\mathbb{N}}_0$. We transform (‘prune’) the sequence $\{X_1,\dots ,X_n\},n\in \mathbb{N}$, of discrete random samples into a sequence $\{0,1,2,\dots ,Y_n\},n\in \mathbb{N}$, of contiguous random sets by replacing $X_{n+1}$ with $Y_n+1$ if $X_{n+1}>Y_n$. We consider the asymptotic behaviour of $Y_n$ as $n\to \infty$. Applications include path growth in digital search trees and the number of tables in Pitmanʼs Chinese restaurant process if the latter is conditioned on its limit value.     

On the longest common increasing binary subsequence

Let $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ be two independent sequences of iid Bernoulli random variables with parameter 1/2. Let ${\mathit{LCI}}_n$ be the length of the longest increasing sequence which is a subsequence of both finite sequences $X_1,\dots ,X_n$ and $Y_1,\dots ,Y_n$. We prove that, as n goes to infinity, $n^{?1/2}({\mathit{LCI}}_n?n/2)$ converges in law to a Brownian functional that we identify. To cite this article: C. Houdré et al., C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

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

A note on conservative galaxies,Skolem systems,cyclic cycle decompositions,and Heffter arrays

The conservative number of a graph $G$ is the minimum positive integer $M$, such that $G$ admits an orientation and a labeling of its edges by distinct integers in $\{1,2,\dots ,M\}$, such that at each vertex of degree at least three, the sum of the labels on the in-coming edges is equal to the sum of the labels on the out-going edges. A graph is conservative if $M=\left|E\left(G\right)\right|$. It is worth noting that determining whether certain biregular graphs are conservative is equivalent to find integer Heffter arrays.In this work we show that the conservative number of a galaxy (a disjoint union of stars) of size $M$ is $M$ for $M\equiv 0$, $3(mod4)$, and $M+1$ otherwise. Consequently, given positive integers $m_1$, $m_2$, …, $m_n$ with $m_i\ge 3$ for $1\le i\le n$, we construct a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of infinitely many circulant graphs, generalizing a result of Bryant, Gavlas and Ling (2003). In particular, it allows us to construct a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of the complete graph $K_{2M+1}$, where $M={\sum }_{i=1}^n{m}_i$. Also, we prove necessary and sufficient conditions for the existence of a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of $K_{2M+2}?F$, where $F$ is a 1-factor. Furthermore, we give a sufficient condition for a subset of ${\mathbb{Z}}_v?\left\{0\right\}$ to be sequenceable.     

Sequences of dilations and translations in function spaces

Let $f\in L^1[0,1]$ be a mean zero function and let $f_n$, $n=1,2,\dots$, be the dyadic dilations and translations of f. We investigate conditions on f, under which the linear operator $T_f$ defined by $T_f{h}_n=f_n$, $n=1,2,\dots$, where $h_n$, $n=1,2,\dots$, are mean zero Haar functions, can be continuously extended to the closed linear span $[h_n]$ in a certain function space X. Among other results we prove that $T_f$ is bounded in every symmetric space with nontrivial Boyd indices whenever $f\in BM{O}_d$ and f has “good” Haar spectral properties. In the special case of so-called Haar chaoses the above results can be essentially refined and sharpened. In particular, we find necessary and sufficient conditions, under which the operator $T_f$, generated by a Haar chaos f of order 1, is continuously invertible in $L^p$ for all $1<p<\infty$.     

Proof of a conjecture on monomial graphs

Let e be a positive integer, p be an odd prime, $q=p^e$, and ${\mathbb{F}}_q$ be the finite field of q elements. Let $f,g\in {\mathbb{F}}_q[X,Y]$. The graph $G_q(f,g)$ is a bipartite graph with vertex partitions $P={\mathbb{F}}_q^3$ and $L={\mathbb{F}}_q^3$, and edges defined as follows: a vertex $(p)=(p_1,p_2,p_3)\in P$ is adjacent to a vertex $[l]=[l_1,l_2,l_3]\in L$ if and only if $p_2+l_2=f(p_1,l_1)$ and $p_3+l_3=g(p_1,l_1)$. If $f=XY$ and $g=X{Y}^2$, the graph $G_q(XY,X{Y}^2)$ contains no cycles of length less than eight and is edge-transitive. Motivated by certain questions in extremal graph theory and finite geometry, people search for examples of graphs $G_q(f,g)$ containing no cycles of length less than eight and not isomorphic to the graph $G_q(XY,X{Y}^2)$, even without requiring them to be edge-transitive. So far, no such graphs $G_q(f,g)$ have been found. It was conjectured that if both f and g are monomials, then no such graphs exist. In this paper we prove the conjecture.     

Pointwise estimates for first passage times of perpetuity sequences

We consider first passage times ${\tau }_u=inf\{n:Y_n>u\}$ for the perpetuity sequence

$Y_n=B_1+A_1{B}_2+?+(A_1\dots A_{n?1})B_n,$

where $(A_n,B_n)$ are i.i.d. random variables with values in ${\mathbb{R}}^{+}\times \mathbb{R}$. Recently, a number of limit theorems related to ${\tau }_u$ were proved including the law of large numbers, the central limit theorem and large deviations theorems (see Buraczewski et al., in press). We obtain a precise asymptotics of the sequence $\mathbb{P}[{\tau }_u=logu∕\rho ]$, $\rho >0$, $u\to \infty$ which considerably improves the previous results of Buraczewski et al. (in press). There, probabilities $\mathbb{P}[{\tau }_u\in I_u]$ were identified, for some large intervals $I_u$ around $k_u$, with lengths growing at least as $loglogu$. Remarkable analogies and differences to random walks (Buraczewski and Ma?lanka, in press; Lalley, 1984) are discussed.     

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.