Parameters of connectivity in (a,b)-linear graphs

For some a and b positive rational numbers, a simple graph with n vertices and $m=an-b$ edges is an $(a,b)$-linear graph, when $n>2b$. We characterize non-empty classes of $(a,b)$-linear graphs and determine those which contain connected graphs. For non-empty classes, we build sequences of $(a,b)$-linear graphs and sequences of connected $(a,b)$-linear graphs. Furthermore, for each of these sequences where every graph is bounded by a constant, we show that its correspondent sequence of diameters diverges, while its correspondent sequence of algebraic connectivities converges to zero.     

Histories in Path Graphs

For a given graph G and a positive integer r the r-path graph, $P_r(G)$, has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length $r-1$, and their union forms either a cycle or a path of length $r+1$ in G. Let $P_r^k(G)$ be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of $P_r^k(G)$. The k-history $P_r^{-k}(H)$ is a subgraph of G that is induced by all edges that take part in the recursive definition of H. We present some general properties of k-histories and give a complete characterization of graphs that are k-histories of vertices of 2-path graph operator.     

On mixed codes with covering radius 1 and minimum distance 2: (extended abstract)

Let R, S and T be finite sets with $|R|=r$, $|S|=s$ and $|T|=t$. A code $C\subset R\times S\times T$ with covering radius 1 and minimum distance 2 is closely connected to a certain generalized partial Latin rectangle. We present various constructions of such codes and some lower bounds on their minimal cardinality $K(r,s,t;2)$. These bounds turn out to be best possible in many instances. Focussing on the special case $t=s$ we determine $K(r,s,s;2)$ when r divides s, when $r=s-1$, when s is large, relative to r, when r is large, relative to s, as well as $K(3r,2r,2r;2)$. Finally, a table with bounds on $K(r,s,s;2)$ is given.     

Matched pairs approach to set theoretic solutions of the Yang–Baxter equation

We study set-theoretic solutions $(X,r)$ of the Yang–Baxter equations on a set X in terms of the induced left and right actions of X on itself. We give a characterisation of involutive square-free solutions in terms of cyclicity conditions. We characterise general solutions in terms of abstract matched pair properties of the associated monoid $S(X,r)$ and we show that r extends as a solution $r_S$ on $S(X,r)$ as a set. Finally, we study extensions of solutions both directly and in terms of matched pairs of their associated monoids. We also prove several general results about matched pairs of monoids S of the required type, including iterated products $S?S?S$ equivalent to $r_S$ a solution, and extensions $(S?T,r_{S?T})$. Examples include a general ‘double’ construction $(S?S,r_{S?S})$ and some concrete extensions, their actions and graphs based on small sets.     

Degree Conditions and Degree Bounded Trees

In this paper, we give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and $A\subseteq V(G)$. We denote by ${\sigma }_k(A)$ the minimum value of the degree sum in G of any k pairwise nonadjacent vertices of A, and by $w(G-A)$ the number of components of the subgraph $G-A$ of G induced by $V(G)-A$. Our main results are the following: (i) If ${\sigma }_k(A)⩾|G|-1$, then G contains a tree T with maximum degree ⩽k and $A\subseteq V(T)$. (ii) If ${\sigma }_{k-w(G-A)}(A)⩾|A|-1$, then G contains a spanning tree T with $d_T(x)⩽k$ for any $x\in A$. These are generalizations of the result by S. Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Seminar Univ. Humburg 43 (1975) 263–267] and degree conditions are sharp.     

Degree Sequence of Tight Distance Graphs

A graph G on n vertices is a tight distance graph if there exists a set $D\subseteq \{1,2,\dots ,n-1\}$ such that $V(G)=\{0,1,\dots ,n-1\}$ and $ij\in E(G)$ if and only if $|i-j|\in D$. A characterization of the degree sequences of tight distance graphs is given. This characterization yields a fast method for recognizing and realizing degree sequences of tight distance graphs.     

Some extensions of the Cauchy-Davenport theorem

The Cauchy-Davenport theorem states that, if p is prime and A, B are nonempty subsets of cardinality r, s in $\mathbb{Z}/p\mathbb{Z}$, the cardinality of the sumset $A+B=\{a+b|a\in A,b\in B\}$ is bounded below by $\min (r+s-1,p)$; moreover, this lower bound is sharp. Natural extensions of this result consist in determining, for each group G and positive integers $r,s⩽|G|$, the analogous sharp lower bound, namely the function${\mu }_G(r,s)=\min \{|A+B||A,B\subset G,|A|=r,|B|=s\}.$ Important progress on this topic has been achieved in recent years, leading to the determination of ${\mu }_G$ for all abelian groups G. In this note we survey the history of earlier results and the current knowledge on this function.     

p-Groups acting on Riemann surfaces

Let p be a prime integer and let $r\ge 3$ be an integer so that $p\ge 5r?7$. We show that a closed Riemann surface S of genus $g\ge 2$ has at most one p-group H of conformal automorphisms so that $S/H$ has genus zero and exactly r cone points. This, in particular, asserts that, for $r=3$ and $p\ge 11$, the minimal field of definition of S coincides with that of $(S,H)$. Another application of this fact, for the case that S is pseudo-real, is that $\mathrm{Aut}(S)/H$ must be either trivial or a cyclic group and that r is necessarily even. This generalizes a result due to Bujalance–Costa for the case of pseudo-real cyclic p-gonal Riemann surfaces.     

On Vertex Partitions and the Colin de Verdière Parameter

We study vertex partitions of graphs according to their Colin de Verdiere parameter μ. By a result of Ding et al. [DOSOO] we know that any graph G with $\mu (G)⩾2$ admits a vertex partition into two graphs with μ at most $\mu (G)-1$. Here we prove that any graph G with $\mu (G)⩾3$ admits a vertex partition into three graphs with μ at most $\mu (G)-2$. This study is extended to other minor-monotone graph parameters like the Hadwiger number.     

Estimation du nombre de dérivées d'un processus Gaussien

We consider a real Gaussian process X with unknown smoothness $r_0\in \mathbb{N}$ where the mean-square derivative $X^{(r_0)}$ is supposed to be Hölder continuous in quadratic mean. First, from the discrete observations $X(t_1),\dots ,X(t_n)$, we study reconstruction of $X(t)$, $t\in [0,1]$, with ${\stackrel{?}{X}}_r(t)$, a piecewise polynomial interpolation of degree $r?1$. We show that the mean-square error of interpolation is a decreasing function of r but becomes stable as soon as $r?r_0$. Next, from an interpolation-based empirical criterion, we derive an estimator $\stackrel{?}{r}$ of $r_0$ and prove its strong consistency by giving an exponential inequality for $P(\stackrel{?}{r}\ne r_0)$. Finally, we prove the strong convergence of ${\stackrel{?}{X}}_{\stackrel{?}{r}}(t)$ toward $X(t)$ with a similar rate as in the case ‘$r_0$ known’. To cite this article: D. Blanke, C. Vial, C. R. Acad. Sci. Paris, Ser. I 343 (2006).