Number of Crossing-Free Geometric Graphs vs. Triangulations

We show that there is a constant $\alpha >0$ such that, for any set P of n⩾ 5 points in general position in the plane, a crossing-free geometric graph on P that is chosen uniformly at random contains, in expectation, at least $(\frac{1}{2}+\alpha )M$ edges, where M denotes the number of edges in any triangulation of P. From this we derive (to our knowledge) the first non-trivial upper bound of the form $c^n\cdot \mathsf{tr}(P)$ on the number of crossing-free geometric graphs on P; that is, at most a fixed exponential in n times the number of triangulations of P. (The trivial upper bound of $2^M\cdot \mathsf{tr}(P)$, or $c=2^{M/n}$, follows by taking subsets of edges of each triangulation.) If the convex hull of P is triangular, then $M=3n-6$, and we obtain $c<7.98$.Upper bounds for the number of crossing-free geometric graphs on planar point sets have so far applied the trivial $8^n$ factor to the bound for triangulations; we slightly decrease this bound to $O({343.11}^n)$.     

ON THE COMMUTATORS OF SINGULAR INTEGRAL OPERATORS

Lp(Rn) (1＜p＜∞) boundedness and a weak type endpoint estimate are considered for the commutators of singular integral operators. A condition on the associated kernel is given under which the L2(Rn) boundedness of the singular integral operators implies the Lp(Rn) boundedness (1＜p＜∞) and the weak type (H1(Rn), L1(Rn))boundedness for the corresponding commutators. A new interpolation theorem is also established.     

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.     

Untangling polygons and graphs

Untangling is a process in which some vertices of a plane graph are moved to obtain a straight-line plane drawing. The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph $C_n$ while keeping at least $\mathrm{\Omega }(n^{2/3})$ vertices fixed. For any graph G, we also present an upper bound for the number of fixed vertices in the worst case. The bound is a function of the number of vertices, maximum degree and diameter of G. One of its consequences is the upper bound $O({(n\log n)}^{2/3})$ for all 3-vertex-connected planar graphs.     

New constructions of SSPDs and their applications

We present a new optimal construction of a semi-separated pair decomposition (i.e., SSPD) for a set of n points in ${\mathbb{R}}^d$. In the new construction each point participates in a few pairs, and it extends easily to spaces with low doubling dimension. This is the first optimal construction with these properties.As an application of the new construction, for a fixed $t>1$, we present a new construction of a t-spanner with $O(n)$ edges and maximum degree $O({\log }^{2}n)$ that has a separator of size $O(n^{1?1/d})$.