Coloring circle graphs

Circle graph is an intersection graph of chords of a circle. We denote the class of circle graphs by cir. In this paper we investigate the chromatic number of the circle graph as a function of the size of maximum clique $\omega =\omega (G)$. More precisely we investigate $f(k)=\max \{\chi (G)|G\in \text{CIR }\mathrm{\&}\omega (G)⩽k\}$. Kratochvíl and Kostochka showed that $f(k)⩽50\cdot 2^k-32k-64$. The best lower bound is by Kostochka and is $f(k)=\mathrm{\Omega }(k\log k)$. We improve the upper bound to $f(k)⩽21\cdot 2^k-24k-24$. We also present the bound $\chi (G)⩽\omega \cdot \log n$ which shows, that the circle graphs with small maximum clique and large chromatic number must have many vertices.     

A nonlinear Korn inequality on a surface

Let ω be a domain in ${\mathbb{R}}^2$ and let $\mathit{\theta }:\overline{\omega }\to {\mathbb{R}}^3$ be a smooth immersion. The main purpose of this paper is to establish a “nonlinear Korn inequality on the surface $\mathit{\theta }(\overline{\omega })$”, asserting that, under ad hoc assumptions, the ${\mathit{H}}^1(\omega )$-distance between the surface $\mathit{\theta }(\overline{\omega })$ and a deformed surface is “controlled” by the ${\mathit{L}}^1(\omega )$-distance between their fundamental forms. Naturally, the ${\mathit{H}}^1(\omega )$-distance between the two surfaces is only measured up to proper isometries of ${\mathbb{R}}^3$.This inequality implies in particular the following interesting per se sequential continuity property for a sequence of surfaces. Let ${\mathit{\theta }}^k:\omega \to {\mathbb{R}}^3$, $k⩾1$, be mappings with the following properties: They belong to the space ${\mathit{H}}^1(\omega )$; the vector fields normal to the surfaces ${\mathit{\theta }}^k(\omega )$, $k⩾1$, are well defined a.e. in ω and they also belong to the space ${\mathit{H}}^1(\omega )$; the principal radii of curvature of the surfaces ${\mathit{\theta }}^k(\omega )$, $k⩾1$, stay uniformly away from zero; and finally, the fundamental forms of the surfaces ${\mathit{\theta }}^k(\omega )$ converge in ${\mathit{L}}^1(\omega )$ toward the fundamental forms of the surface $\mathit{\theta }(\overline{\omega })$ as $k\to \infty$. Then, up to proper isometries of ${\mathbb{R}}^3$, the surfaces ${\mathit{\theta }}^k(\omega )$ converge in ${\mathit{H}}^1(\omega )$ toward the surface $\mathit{\theta }(\overline{\omega })$ as $k\to \infty$.Such results have potential applications to nonlinear shell theory, the surface $\mathit{\theta }(\overline{\omega })$ being then the middle surface of the reference configuration of a nonlinearly elastic shell.     

The Mixed Binary Euclid Algorithm

We present a new GCD algorithm for two integers that combines both the Euclidean and the binary gcd approaches. We give its worst case time analysis and we prove that its bit-time complexity is still $O(n^2)$ for two n-bit integers in the worst case. Our preliminar experiments show a potential speedup for small integers. A parallel version matches the best presently known time complexity, namely $O(n/\log n)$ time with $O(n^{1+\mathrm{ϵ}})$ processors, for any constant $\mathrm{ϵ}>0$.     

Continuity in H1-norms of surfaces in terms of the L1-norms of their fundamental forms

The main purpose of this Note is to show how a ‘nonlinear Korn's inequality on a surface’ can be established. This inequality implies in particular the following interesting per se sequential continuity property for a sequence of surfaces. Let ω be a domain in ${\mathbb{R}}^2$, let $\mathit{\theta }:\overline{\omega }\to {\mathbb{R}}^3$ be a smooth immersion, and let ${\mathit{\theta }}^k:\overline{\omega }\to {\mathbb{R}}^3$, $k?1$, be mappings with the following properties: They belong to the space ${\mathit{H}}^1(\omega )$; the vector fields normal to the surfaces ${\mathit{\theta }}^k(\omega )$, $k?1$, are well defined a.e. in ω and they also belong to the space ${\mathit{H}}^1(\omega )$; the principal radii of curvature of the surfaces ${\mathit{\theta }}^k(\omega )$ stay uniformly away from zero; and finally, the three fundamental forms of the surfaces ${\mathit{\theta }}^k(\omega )$ converge in ${\mathit{L}}^1(\omega )$ toward the three fundamental forms of the surface $\mathit{\theta }(\omega )$ as $k\to \infty$. Then, up to proper isometries of ${\mathbb{R}}^3$, the surfaces ${\mathit{\theta }}^k(\omega )$ converge in ${\mathit{H}}^1(\omega )$ toward the surface $\mathit{\theta }(\omega )$ as $k\to \infty$. To cite this article: P.G. Ciarlet et al., C. R. Acad. Sci. Paris, Ser. I 341 (2005).     

A fixed parameter algorithm for optimal convex partitions

We present a fixed-parameter algorithm for the Minimum Convex Partition and the Minimum Weight Convex Partition problem. The algorithm is based on techniques developed for the Minimum Weight Triangulation problem. On a set P of n points the algorithm runs in $O(2^k{k}^4{n}^3+n\log n)$ time. The parameter k is the number of points in P lying in the interior of the convex hull of P.     

Monochromatic progressions in random colorings

Let $N^{+}(k)=2^{k/2}{k}^{3/2}f(k)$ and $N^{?}(k)=2^{k/2}{k}^{1/2}g(k)$ where $f(k)\to \infty$ and $g(k)\to 0$ arbitrarily slowly as $k\to \infty$. We show that the probability of a random 2-coloring of $\{1,2,\dots ,N^{+}(k)\}$ containing a monochromatic k-term arithmetic progression approaches 1, and the probability of a random 2-coloring of $\{1,2,\dots ,N^{?}(k)\}$ containing a monochromatic k-term arithmetic progression approaches 0, as $k\to \infty$. This improves an upper bound due to Brown, who had established an analogous result for $N^{+}(k)=2^k\log kf(k)$.     

Higher genus Kashiwara–Vergne problems and the Goldman–Turaev Lie bialgebra

We define a family ${\mathrm{KV}}^{(g,n+1)}$ of Kashiwara–Vergne problems associated with compact connected oriented 2-manifolds of genus g with $n+1$ boundary components. The problem ${\mathrm{KV}}^{(0,3)}$ is the classical Kashiwara–Vergne problem from Lie theory. We show the existence of solutions to ${\mathrm{KV}}^{(g,n+1)}$ for arbitrary g and n. The key point is the solution to ${\mathrm{KV}}^{(1,1)}$ based on the results by B. Enriquez on elliptic associators. Our construction is motivated by applications to the formality problem for the Goldman–Turaev Lie bialgebra ${\mathfrak{g}}^{(g,n+1)}$. In more detail, we show that every solution to ${\mathrm{KV}}^{(g,n+1)}$ induces a Lie bialgebra isomorphism between ${\mathfrak{g}}^{(g,n+1)}$ and its associated graded $\mathrm{gr}{\mathfrak{g}}^{(g,n+1)}$. For $g=0$, a similar result was obtained by G. Massuyeau using the Kontsevich integral. For $g\ge 1$, $n=0$, our results imply that the obstruction to surjectivity of the Johnson homomorphism provided by the Turaev cobracket is equivalent to the Enomoto–Satoh obstruction.