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

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

Transcendence degree one function fields over a finite field with many automorphisms

Let $\mathbb{K}$ be the algebraic closure of a finite field ${\mathbb{F}}_q$ of odd characteristic p. For a positive integer m prime to p, let $F=\mathbb{K}(x,y)$ be the transcendence degree 1 function field defined by $y^q+y=x^m+x^{?m}$. Let $t=x^{m(q?1)}$ and $H=\mathbb{K}(t)$. The extension $F|H$ is a non-Galois extension. Let K be the Galois closure of F with respect to H. By Stichtenoth [20], K has genus $\mathfrak{g}(K)=(qm?1)(q?1)$, p-rank (Hasse–Witt invariant) $\gamma (K)={(q?1)}^2$ and a $\mathbb{K}$-automorphism group of order at least $2q^{2}m(q?1)$. In this paper we prove that this subgroup is the full $\mathbb{K}$-automorphism group of K; more precisely ${\text{Aut}}_{\mathbb{K}}(K)=\mathrm{\Delta }?D$ where Δ is an elementary abelian p-group of order $q^2$ and D has an index 2 cyclic subgroup of order $m(q?1)$. In particular, $\sqrt{m}|{\text{Aut}}_{\mathbb{K}}(K)|>\mathfrak{g}{(K)}^{3/2}$, and if K is ordinary (i.e. $\mathfrak{g}(K)=\gamma (K)$) then $|{\text{Aut}}_{\mathbb{K}}(K)|>{\mathfrak{g}}^{3/2}$. On the other hand, if G is a solvable subgroup of the $\mathbb{K}$-automorphism group of an ordinary, transcendence degree 1 function field L of genus $\mathfrak{g}(L)\ge 2$ defined over $\mathbb{K}$, then $|{\text{Aut}}_{\mathbb{K}}(K)|\le 34{(\mathfrak{g}(L)+1)}^{3/2}<68\sqrt{2}\mathfrak{g}{(L)}^{3/2}$; see [15]. This shows that K hits this bound up to the constant $68\sqrt{2}$.Since ${\text{Aut}}_{\mathbb{K}}(K)$ has several subgroups, the fixed subfield $F^N$ of such a subgroup N may happen to have many automorphisms provided that the normalizer of N in ${\text{Aut}}_{\mathbb{K}}(K)$ is large enough. This possibility is worked out for subgroups of Δ.     

Pseudo-Taylor expansions and the Carathéodory–Fejér problem

We give a new solvability criterion for the boundary Carathéodory–Fejér problem: given a point $x\in \mathbb{R}$ and, a finite set of target values $a^0,a^1,\dots ,a^n\in \mathbb{C}$, to construct a function f in the Pick class such that the limit of $f^{(k)}(z)/k!$ as $z\to x$ nontangentially in the upper half-plane is $a^k$ for $k=0,1,\dots ,n$. The criterion is in terms of positivity of an associated Hankel matrix. The proof is based on a reduction method due to Julia and Nevanlinna.     

Optimal spanners for axis-aligned rectangles

The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean distance. We consider a generalized version of this notion, where the nodes of the graph are not points but axis-parallel rectangles in the plane. The arcs in the graph are horizontal or vertical segments connecting a pair of rectangles, and the distance measure we use is the $L_1$-distance. The dilation of a pair of points is then defined as the length of the shortest rectilinear path between them that stays within the union of the rectangles and the connecting segments, divided by their $L_1$-distance. The dilation of the graph is the maximum dilation over all pairs of points in the union of the rectangles.We study the following problem: given n non-intersecting rectangles and a graph describing which pairs of rectangles are to be connected, we wish to place the connecting segments such that the dilation is minimized. We obtain four results on this problem: (i) for arbitrary graphs, the problem is NP-hard; (ii) for trees, we can solve the problem by linear programming on $\mathrm{O}(n^2)$ variables and constraints; (iii) for paths, we can solve the problem in time $\mathrm{O}(n^3\log n)$; (iv) for rectangles sorted vertically along a path, the problem can be solved in $\mathrm{O}(n^2)$ time, and a $(1+\varepsilon )$-approximation can be computed in linear time.