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

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 topology of valuation-theoretic representations of integrally closed domains

Let F be a field. For each nonempty subset X of the Zariski–Riemann space of valuation rings of F, let $A(X)={?}_{V\in X}V$ and $J(X)={?}_{V\in X}{\mathfrak{M}}_V$, where ${\mathfrak{M}}_V$ denotes the maximal ideal of V. We examine connections between topological features of X and the algebraic structure of the ring $A(X)$. We show that if $J(X)\ne 0$ and $A(X)$ is a completely integrally closed local ring that is not a valuation ring of F, then there is a space Y of valuation rings of F that is perfect in the patch topology such that $A(X)=A(Y)$. If any countable subset of points is removed from Y, then the resulting set remains a representation of $A(X)$. Additionally, if F is a countable field, the set Y can be chosen homeomorphic to the Cantor set. We apply these results to study properties of the ring $A(X)$ with specific focus on topological conditions that guarantee $A(X)$ is a Prüfer domain, a feature that is reflected in the Zariski–Riemann space when viewed as a locally ringed space. We also classify the rings $A(X)$ where X has finitely many patch limit points, thus giving a topological generalization of the class of Krull domains, one that includes interesting Prüfer domains. To illustrate the latter, we show how an intersection of valuation rings arising naturally in the study of local quadratic transformations of a regular local ring can be described using these techniques.     

On functors preserving skeletal maps and skeletally generated compacta

A map $f:X\to Y$ between topological spaces is skeletal if the preimage $f^{?1}(A)$ of each nowhere dense subset $A?Y$ is nowhere dense in X. We prove that a normal functor $F:\mathbf{Comp}\to \mathbf{Comp}$ is skeletal (which means that F preserves skeletal epimorphisms) if and only if for any open surjective map $f:X\to Y$ between metrizable zero-dimensional compacta with two-element non-degeneracy set $N^f=\{x\in X:|f^{?1}(f(x))|>1\}$ the map $Ff:FX\to FY$ is skeletal. This characterization implies that each open normal functor is skeletal. The converse is not true even for normal functors of finite degree. The other main result of the paper says that each normal functor $F:\mathbf{Comp}\to \mathbf{Comp}$ preserves the class of skeletally generated compacta. This contrasts with the known ??epin?s result saying that a normal functor is open if and only if it preserves the class of openly generated compacta.     

On degree sum conditions for 2-factors with a prescribed number of cycles

For a vertex subset $X$ of a graph $G$, let ${\Delta }_t\left(X\right)$ be the maximum value of the degree sums of the subsets of $X$ of size $t$. In this paper, we prove the following result: Let $k,m$ be positive integers, and let $G$ be an $m$-connected graph of order $n\ge 5k?2$. If ${\Delta }_2\left(X\right)\ge n$ for every independent set $X$ of size $?m∕k?+1$ in $G$, then $G$ has a 2-factor with exactly $k$ cycles. This is a common extension of the results obtained by Brandt et al. (1997) and Yamashita (2008), respectively.     

Equivariant Nielsen root theory for G-maps

Let X be a compact Hausdorff space, Y be a connected topological manifold, $f:X\to Y$ be a map between closed manifolds and $a\in Y$. The vanishing of the Nielsen root number $N(f;a)$ implies that f is homotopic to a root free map h, i.e., $h～f$ and $h^{?1}(a)=?$. In this paper, we prove an equivariant analog of this result for G-maps between G-spaces where G is a finite group.