Coloration des graphes de reines

Until 2003 no chromatic numbers (${\chi }_n$) for the queen graphs were available for $n>9$ except where n is not a multiple of 2 or 3. In this research announcement we present an exact algorithm which provides coloring solutions for $n=12,14,15,16,18,20,21,22,24,26,28$ and 32 such as ${\chi }_n=n$. Then we prove that there exists an infinite number of values for n such that $n=2p$ or $n=3p$, and ${\chi }_n=n$. To cite this article: M. Vasquez, C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

Contacts et auto-contacts sans frottement

Let M be a submanifold of ${\mathbb{R}}^n$ ($n=2,3$) considered as the reference configuration of a hyperelastic solid. A topological constraint is imposed on the admissible deformations $\psi :M\to {\mathbb{R}}^n$ of the solid in order to satisfy a non penetration condition. We show that the associated minimization problem has at least one solution and, in the case $\dim (M)\ne 2$ or $n\ne 3$, provides a mathematical model of body that allows frictionless self-contact. A numerical application is presented. To cite this article: O. Pantz, C. R. Acad. Sci. Paris, Ser. I 341 (2005).     

Solutions with interior bubble and boundary layer for an elliptic Neumann problem with critical nonlinearity

We study positive solutions of the equation ${\mathrm{?}}^2\mathrm{\Delta }u?u+u^{\frac{n+2}{n?2}}=0$, where $n=3,4,5$ and $\mathrm{?}>0$ is small, with Neumann boundary condition in a unit ball B. We prove the existence of solutions with an interior bubble at the center and a boundary layer at the boundary ?B. To cite this article: J. Wei, S. Yan, C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

On the triplex substitution – combinatorial properties

If a substitution τ over a three-letter alphabet has a positively linear complexity, that is, $P_{\tau }(n)=C_{1}n+C_2$ ($n⩾1$) with $C_1,C_2⩾0$, there are only 4 possibilities: $P_{\tau }(n)=3$, $n+2$, $2n+1$ or 3n. The first three cases have been studied by many authors, but the case 3n remained unclear. This leads us to consider the triplex substitution $\sigma :a\mapsto ab$, $b\mapsto acb$, $c\mapsto acc$. Studying the factor structure of its fixed point, which is quite different from the other cases, we show that it is of complexity 3n. We remark that the triplex substitution is also a typical example of invertible substitution over a three-letter alphabet. To cite this article: B. Tan et al., C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

Krull dimension,overrings and semistar operations of an integral domain

In this paper, we will present new developments in the study of the links between the cardinality of the sets $O(R)$ of all overrings of R, $\mathit{SSF}c(R)$ of all semistar operations of finite character when finite to the Krull dimension of an integral domain R. In particular, we prove that if $|\mathit{SSF}c(R)|=n+\dim R$, then R has at most $n?1$ distinct maximal ideals. Moreover, R has exactly $n?1$ maximal ideals if and only if $n=3$. In this case R is a Prüfer domain with exactly two maximal ideals and Y-graph spectrum. We also give a complete characterizations for local domains R such that $|\mathit{SSF}c(R)|=3+\dim R$, and nonlocal domains R with $|\mathit{SSF}c(R)|=|O(R)|=n+\dim R$ for $n=4$, $n=5$, $n=6$ and $n=7$. Examples to illustrate the scopes and limits of the results are constructed.     

Some existence results for a Paneitz type problem via the theory of critical points at infinity

In this paper a fourth order equation involving critical growth is considered under the Navier boundary condition: ${\mathrm{\Delta }}^{2}u=K{u}^p$, $u>0$ in Ω, $u=\mathrm{\Delta }u=0$ on ∂Ω, where K is a positive function, Ω is a bounded smooth domain in ${\mathbb{R}}^n$, $n⩾5$ and $p+1=2n/(n-4)$, is the critical Sobolev exponent. We give some topological conditions on K to ensure the existence of solution. Our methods involve the study of the critical points at infinity and their contribution to the topology of the level sets of the associated Euler–Lagrange functional.     

Self-orthogonal decompositions of graphs into matchings

Given a simple graph H, a self-orthogonal decomposition (SOD) of H is a collection of subgraphs of H, all isomorphic to some graph G, such that every edge of H occurs in exactly two of the subgraphs and any two of the subgraphs share exactly one edge. Our concept of SOD is a natural generalization of the well-studied orthogonal double covers (ODC) of complete graphs. If for some given G there is an appropriate H, then our goal is to find one with as few vertices as possible. Special attention is paid to the case when G a matching with $n-1$ edges. We conjecture that $v(H)=2n-2$ is best possible if $n\ne 4$ is even and $v(H)=2n$ if n is odd. We present a construction which proves this conjecture for all but 4 of the possible residue classes of n modulo 18.     

Fractional parts of powers and Sturmian words

Let $b?2$ be an integer. In terms of combinatorics on words we describe all irrational numbers $\xi >0$ with the property that the fractional parts $\{\xi b^n\}$, $n?0$, all belong to a semi-open or an open interval of length $1/b$. The length of such an interval cannot be smaller, that is, for irrational ξ, the fractional parts $\{\xi b^n\}$, $n?0$, cannot all belong to an interval of length smaller than $1/b$. To cite this article: Y. Bugeaud, A. Dubickas, C. R. Acad. Sci. Paris, Ser. I 341 (2005).     

A mapping connected with the Schur–Szegő composition

Every monic polynomial in one variable of the form $(x+1)S$, $\mathrm{deg}S=n?1$, is presentable in a unique way as a Schur–Szeg? composition of $n?1$ polynomials of the form ${(x+1)}^{n?1}(x+a_i)$. We prove geometric properties of the affine mapping associating to the coefficients of S the $(n?1)$-tuple of values of the elementary symmetric functions of the numbers $a_i$. To cite this article: V.P. Kostov, C. R. Acad. Sci. Paris, Ser. I 347 (2009).     

Le problème des diviseurs de zéro pour les groupes de Lie nilpotents

Let G be a non-Abelian, connected, nilpotent Lie group. Then there exist $0\ne \alpha \in C_c(G)$ and $0\ne \xi \in L^2(G)$ such that $\alpha 1\xi =0$, contrary to what happens for the group ${\mathbb{R}}^n$. Moreover, the set of zero divisors is a total subset of $L^2(G)$. This result is first proven for the Heisenberg group $H_n$ where it is based on the existence of non-trivial Schwartz functions f satisfying $f1(X_k+\mathrm{i}{Y}_k)=0$ for $1?k?n$. To cite this article: J. Ludwig et al., C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

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

Families of polytopal digraphs that do not satisfy the shelling property

A polytopal digraph $G(P)$ is an orientation of the skeleton of a convex polytope P. The possible non-degenerate pivot operations of the simplex method in solving a linear program over P can be represented as a special polytopal digraph known as an LP digraph. Presently there is no general characterization of which polytopal digraphs are LP digraphs, although four necessary properties are known: acyclicity, unique sink orientation (USO), the Holt–Klee property and the shelling property. The shelling property was introduced by Avis and Moriyama (2009), where two examples are given in $d=4$ dimensions of polytopal digraphs satisfying the first three properties but not the shelling property. The smaller of these examples has $n=7$ vertices. Avis, Miyata and Moriyama (2009) constructed for each $d?4$ and $n?d+2$, a d-polytope P with n vertices which has a polytopal digraph which is an acyclic USO that satisfies the Holt–Klee property, but does not satisfy the shelling property. The construction was based on a minimal such example, which has $d=4$ and $n=6$. In this paper we explore the shelling condition further. First we give an apparently stronger definition of the shelling property, which we then prove is equivalent to the original definition. Using this stronger condition we are able to give a more general construction of such families. In particular, we show that given any 4-dimensional polytope P with $n_0$ vertices whose unique sink is simple, we can extend P for any $d?4$ and $n?n_0+d?4$ to a d-polytope with these properties that has n vertices. Finally we investigate the strength of the shelling condition for d-crosspolytopes, for which Develin (2004) has given a complete characterization of LP orientations.     

The adversary degree-associated reconstruction number of double-brooms

A vertex-deleted subgraph of a graph G is a card. A dacard specifies the degree of the deleted vertex along with the card. The adversary degree-associated reconstruction number $\mathrm{adrn}(G)$ is the least k such that every set of k dacards determines G. We determine $\mathrm{adrn}(D_{m,n,p})$, where the double-broom $D_{m,n,p}$ with $p\ge 2$ is the tree with $m+n+p$ vertices obtained from a path with p vertices by appending m leaves at one end and n leaves at the other end. We determine $\mathrm{adrn}(D_{m,n,p})$ for all $m,n,p$. For $2\le m\le n$, usually $\mathrm{adrn}(D_{m,n,p})=m+2$, except $\mathrm{adrn}(D_{m,m+1,p})=m+1$ and $\mathrm{adrn}(D_{m,m+2,p})=m+3$. There are exceptions when $(m,n)=(2,3)$ or $p=4$. For $m=1$ the usual value is 4, with exceptions when $p\in \{2,3\}$ or $n=2$.