Many Collinear k-Tuples with no k+1 Collinear Points

For every $k>3$ k > 3 , we give a construction of planar point sets with many collinear $k$ k -tuples and no collinear $(k+1)$ ( k + 1 ) -tuples. We show that there are $n_0=n_0(k)$ n 0 = n 0 ( k ) and $c=c(k)$ c = c ( k ) such that if $n\ge n_0$ n ≥ n 0 , then there exists a set of $n$ n points in the plane that does not contain $k+1$ k + 1 points on a line, but it contains at least $n^{2-({c}/{\sqrt{\log n}})}$ n 2 - ( c / log n ) collinear $k$ k -tuples of points. Thus, we significantly improve the previously best known lower bound for the largest number of collinear $k$ k -tuples in such a set, and get reasonably close to the trivial upper bound $O(n^2)$ O ( n 2 ) .     

Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension

For a polyhedron $P$ P let $B(P)$ B ( P ) denote the polytopal complex that is formed by all bounded faces of $P$ P . If $P$ P is the intersection of $n$ n halfspaces in $\mathbb R ^D$ R D , but the maximum dimension $d$ d of any face in $B(P)$ B ( P ) is much smaller, we show that the combinatorial complexity of $P$ P cannot be too high; in particular, that it is independent of $D$ D . We show that the number of vertices of $P$ P is $O(n^d)$ O ( n d ) and the total number of bounded faces of the polyhedron is $O(n^{d^2})$ O ( n d 2 ) . For inputs in general position the number of bounded faces is $O(n^d)$ O ( n d ) . We show that for certain specific values of $d$ d and $D$ D , our bounds are tight. For any fixed $d$ d , we show how to compute the set of all vertices, how to determine the maximum dimension of a bounded face of the polyhedron, and how to compute the set of bounded faces in polynomial time, by solving a number of linear programs that is polynomial in  $n$ n .     

On Sets Defining Few Ordinary Lines

Let $P$ P be a set of $n$ n points in the plane, not all on a line. We show that if $n$ n is large then there are at least $n/2$ n / 2 ordinary lines, that is to say lines passing through exactly two points of $P$ P . This confirms, for large $n$ n , a conjecture of Dirac and Motzkin. In fact we describe the exact extremisers for this problem, as well as all sets having fewer than $n-C$ n - C ordinary lines for some absolute constant $C$ C . We also solve, for large $n$ n , the “orchard-planting problem”, which asks for the maximum number of lines through exactly 3 points of $P$ P . Underlying these results is a structure theorem which states that if $P$ P has at most $Kn$ K n ordinary lines then all but O(K) points of $P$ P lie on a cubic curve, if $n$ n is sufficiently large depending on $K$ K .     

A Question from a Famous Paper of Erdős

Given a convex body $K$ K , consider the smallest number $N$ N so that there is a point $P\in \partial K$ P ∈ ? K such that every circle centred at $P$ P intersects $\partial K$ ? K in at most $N$ N points. In 1946 Erd?s conjectured that $N=2$ N = 2 for all $K$ K , but there are convex bodies for which this is not the case. As far as we know there is no known global upper bound. We show that no convex body has $N=\infty $ N = ∞ and that there are convex bodies for which $N = 6$ N = 6 .     

Polytopal Affine Semigroups with Holes Deep Inside

Given a positive integer $k$ k , we construct a lattice $3$ 3 -simplex $P$ P with the following property: The affine semigroup $Q_P$ Q P associated to $P$ P is not normal, and every element $q \in \overline{Q}_P \setminus Q_P$ q ∈ Q ¯ P ? Q P has lattice distance at least $k$ k above every facet of $Q_P$ Q P .     

An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains

We present an approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain $\mathcal D $ D , consisting of $n$ n tetrahedra with positive weights, and a real number $\varepsilon \in (0,1)$ ε ∈ ( 0 , 1 ) , our algorithm constructs paths in $\mathcal D $ D from a fixed source vertex to all vertices of $\mathcal D $ D , the costs of which are at most $1+\varepsilon $ 1 + ε times the costs of (weighted) shortest paths, in $O(\mathcal{C }(\mathcal D )\frac{n}{\varepsilon ^{2.5}}\log \frac{n}{\varepsilon }\log ^3\frac{1}{\varepsilon })$ O ( C ( D ) n ε 2.5 log n ε log 3 1 ε ) time, where $\mathcal{C }(\mathcal D )$ C ( D ) is a geometric parameter related to the aspect ratios of tetrahedra. The efficiency of the proposed algorithm is based on an in-depth study of the local behavior of geodesic paths and additive Voronoi diagrams in weighted three-dimensional domains, which are of independent interest. The paper extends the results of Aleksandrov et al. (J ACM 52(1):25–53, 2005), to three dimensions.     

Maximal Equilateral Sets

A subset of a normed space $X$ X is called equilateral if the distance between any two points is the same. Let $m(X)$ m ( X ) be the smallest possible size of an equilateral subset of $X$ X maximal with respect to inclusion. We first observe that Petty’s construction of a $d$ d - $X$ X of any finite dimension $d\ge 4$ d ≥ 4 with $m(X)=4$ m ( X ) = 4 can be generalised to give $m(X\oplus _1\mathbb R )=4$ m ( X ⊕ 1 R ) = 4 for any $X$ X of dimension at least $2$ 2 which has a smooth point on its unit sphere. By a construction involving Hadamard matrices we then show that for any set $\Gamma $ Γ , $m(\ell _p(\Gamma ))$ m ( ? p ( Γ ) ) is finite and bounded above by a function of $p$ p , for all $1\le p<2$ 1 ≤ p < 2 . Also, for all $p\in [1,\infty )$ p ∈ [ 1 , ∞ ) and $d\in \mathbb N $ d ∈ N there exists $c=c(p,d)>1$ c = c ( p , d ) > 1 such that $m(X)\le d+1$ m ( X ) ≤ d + 1 for all $d$ d - $X$ X with Banach–Mazur distance less than $c$ c from $\ell _p^d$ ? p d . Using Brouwer’s fixed-point theorem we show that $m(X)\le d+1$ m ( X ) ≤ d + 1 for all $d$ d - $X$ X with Banach–Mazur distance less than $3/2$ 3 / 2 from $\ell _\infty ^d$ ? ∞ d . A graph-theoretical argument furthermore shows that $m(\ell _\infty ^d)=d+1$ m ( ? ∞ d ) = d + 1 . The above results lead us to conjecture that $m(X)\le 1+\dim X$ m ( X ) ≤ 1 + dim X for all finite-normed spaces $X$ X .     

Approximating Tverberg Points in Linear Time for Any Fixed Dimension

Let $P \subseteq \mathbb{R }^d$ P ? R d be a $d$ d -dimensional $n$ n -point set. A Tverberg partition is a partition of $P$ P into $r$ r sets $P_1, \dots , P_r$ P 1 , ? , P r such that the convex hulls $\hbox {conv}(P_1), \dots , \hbox {conv}(P_r)$ conv ( P 1 ) , ? , conv ( P r ) have non-empty intersection. A point in $\bigcap _{i=1}^{r} \hbox {conv}(P_i)$ ? i = 1 r conv ( P i ) is called a Tverberg point of depth $r$ r for $P$ P . A classic result by Tverberg shows that there always exists a Tverberg partition of size $\lceil n/(d+1) \rceil $ ? n / ( d + 1 ) ? , but it is not known how to find such a partition in polynomial time. Therefore, approximate solutions are of interest. We describe a deterministic algorithm that finds a Tverberg partition of size $\lceil n/4(d+1)^3 \rceil $ ? n / 4 ( d + 1 ) 3 ? in time $d^{O(\log d)} n$ d O ( log d ) n . This means that for every fixed dimension we can compute an approximate Tverberg point (and hence also an approximate centerpoint) in linear time. Our algorithm is obtained by combining a novel lifting approach with a recent result by Miller and Sheehy (Comput Geom Theory Appl 43(8):647–654, 2010).     

Dimension Reduction for Finite Trees in \varvec{\ell _1}

We show that every $n$ -point tree metric admits a $(1+\varepsilon )$ -embedding into $\ell _1^{C(\varepsilon ) \log n}$ , for every $\varepsilon > 0$ , where $C(\varepsilon ) \le O\big ((\frac{1}{\varepsilon })^4 \log \frac{1}{\varepsilon })\big )$ . This matches the natural volume lower bound up to a factor depending only on $\varepsilon $ . Previously, it was unknown whether even complete binary trees on $n$ nodes could be embedded in $\ell _1^{O(\log n)}$ with $O(1)$ distortion. For complete $d$ -ary trees, our construction achieves $C(\varepsilon ) \le O\big (\frac{1}{\varepsilon ^2}\big )$ .     

Improved Enumeration of Simple Topological Graphs

A simple topological graph $T=(V(T), E(T))$ T = ( V ( T ) , E ( T ) ) is a drawing of a graph in the plane where every two edges have at most one common point (an endpoint or a crossing) and no three edges pass through a single crossing. Topological graphs $G$ G and $H$ H are isomorphic if $H$ H can be obtained from $G$ G by a homeomorphism of the sphere, and weakly isomorphic if $G$ G and $H$ H have the same set of pairs of crossing edges. We generalize results of Pach and Tóth and the author’s previous results on counting different drawings of a graph under both notions of isomorphism. We prove that for every graph $G$ G with $n$ n vertices, $m$ m edges and no isolated vertices the number of weak isomorphism classes of simple topological graphs that realize $G$ G is at most $2^{O(n^2\log (m/n))}$ 2 O ( n 2 log ( m / n ) ) , and at most $2^{O(mn^{1/2}\log n)}$ 2 O ( m n 1 / 2 log n ) if $m\le n^{3/2}$ m ≤ n 3 / 2 . As a consequence we obtain a new upper bound $2^{O(n^{3/2}\log n)}$ 2 O ( n 3 / 2 log n ) on the number of intersection graphs of $n$ n pseudosegments. We improve the upper bound on the number of weak isomorphism classes of simple complete topological graphs with $n$ n vertices to $2^{n^2\cdot \alpha (n)^{O(1)}}$ 2 n 2 · α ( n ) O ( 1 ) , using an upper bound on the size of a set of permutations with bounded VC-dimension recently proved by Cibulka and the author. We show that the number of isomorphism classes of simple topological graphs that realize $G$ G is at most $2^{m^2+O(mn)}$ 2 m 2 + O ( m n ) and at least $2^{\Omega (m^2)}$ 2 Ω ( m 2 ) for graphs with $m>(6+\varepsilon )n$ m > ( 6 + ε ) n .     

Tilings of Parallelograms with Similar Right Triangles

We say that a triangle $T$ T tiles the polygon $\mathcal A $ A if $\mathcal A $ A can be decomposed into finitely many non-overlapping triangles similar to $T$ T . A tiling is called regular if there are two angles of the triangles, say $\alpha $ α and $\beta $ β , such that at each vertex $V$ V of the tiling the number of triangles having $V$ V as a vertex and having angle $\alpha $ α at $V$ V is the same as the number of triangles having angle $\beta $ β at $V$ V . Otherwise the tiling is called irregular. Let $\mathcal P (\delta )$ P ( δ ) be a parallelogram with acute angle $\delta $ δ . In this paper we prove that if the parallelogram $\mathcal P (\delta )$ P ( δ ) is tiled with similar triangles of angles $(\alpha , \beta , \pi /2)$ ( α , β , π / 2 ) , then $(\alpha , \beta )=(\delta , \pi /2-\delta )$ ( α , β ) = ( δ , π / 2 - δ ) or $(\alpha , \beta )=(\delta /2, \pi /2-\delta /2)$ ( α , β ) = ( δ / 2 , π / 2 - δ / 2 ) , and if the tiling is regular, then only the first case can occur.     

Singular limits for Liouville-type equations on the flat two-torus

We consider the problem $$\begin{aligned} -\Delta u=\varepsilon ^{2}e^{u}- \frac{1}{|\Omega |}\int _\Omega \varepsilon ^{2} e^{u}+ {4\pi N\over |\Omega |} - 4 \pi N\delta _p, \quad \text{ in} {\Omega }, \quad \int _\Omega u=0 \end{aligned}$$ in a flat two-torus $\Omega $ with periodic boundary conditions, where $\varepsilon >0,\,|\Omega |$ is the area of the $\Omega $ , $N>0$ and $\delta _p$ is a Dirac mass at $p\in \Omega $ . We prove that if $1\le m<N+1$ then there exists a family of solutions $\{u_\varepsilon \}_{\varepsilon }$ such that $\varepsilon ^{2}e^{u_\varepsilon }\rightharpoonup 8\pi \sum _{i=1}^m\delta _{q_i}$ as $\varepsilon \rightarrow 0$ in measure sense for some different points $q_{1}, \ldots , q_{m}$ . Furthermore, points $q_i$ , $i=1,\dots ,m$ are different from $p$ .     

Toric surfaces,K-stability and Calabi flow

Let $X$ be a toric surface and $u$ be a normalized symplectic potential on the corresponding polygon $P$ . Suppose that the Riemannian curvature is bounded by a constant $C_1$ and $ \int _{\partial P} u d \sigma < C_2, $ then there exists a constant $C_3$ depending only on $C_1, C_2$ and $P$ such that the diameter of $X$ is bounded by $C_3$ . Moreoever, we can show that there is a constant $M > 0$ depending only on $C_1, C_2$ and $P$ such that Donaldson’s $M$ -condition holds for $u$ . As an application, we show that if $(X,P)$ is (analytic) relative $K$ -stable, then the modified Calabi flow converges to an extremal metric exponentially fast by assuming that the Calabi flow exists for all time and the Riemannian curvature is uniformly bounded along the Calabi flow.     

Algebraic Boundaries of \mathrm{SO}(2)-Orbitopes

Let $X\subset \mathbb{A }^{2r}$ X ? A 2 r be a real curve embedded into an even-dimensional affine space. We characterise when the $r$ r th secant variety to $X$ X is an irreducible component of the algebraic boundary of the convex hull of the real points $X(\mathbb{R })$ X ( R ) of $X$ X . This fact is then applied to $4$ 4 -dimensional $\mathrm{SO}(2)$ SO ( 2 ) -orbitopes and to the so called Barvinok–Novik orbitopes to study when they are basic closed semi-algebraic sets. In the case of $4$ 4 -dimensional $\mathrm{SO}(2)$ SO ( 2 ) -orbitopes, we find all irreducible components of their algebraic boundary.     

Boundaries of Disk-Like Self-affine Tiles

Let $T:= T(A, \mathcal{D })$ T : = T ( A , D ) be a disk-like self-affine tile generated by an integral expanding matrix $A$ A and a consecutive collinear digit set $\mathcal{D }$ D , and let $f(x)=x^{2}+px+q$ f ( x ) = x 2 + px + q be the characteristic polynomial of $A$ A . In the paper, we identify the boundary $\partial T$ ? T with a sofic system by constructing a neighbor graph and derive equivalent conditions for the pair $(A,\mathcal{D })$ ( A , D ) to be a number system. Moreover, by using the graph-directed construction and a device of pseudo-norm $\omega $ ω , we find the generalized Hausdorff dimension $\dim _H^{\omega } (\partial T)=2\log \rho (M)/\log |q|$ dim H ω ( ? T ) = 2 log ρ ( M ) / log | q | where $\rho (M)$ ρ ( M ) is the spectral radius of certain contact matrix $M$ M . Especially, when $A$ A is a similarity, we obtain the standard Hausdorff dimension $\dim _H (\partial T)=2\log \rho /\log |q|$ dim H ( ? T ) = 2 log ρ / log | q | where $\rho $ ρ is the largest positive zero of the cubic polynomial $x^{3}-(|p|-1)x^{2}-(|q|-|p|)x-|q|$ x 3 ? ( | p | ? 1 ) x 2 ? ( | q | ? | p | ) x ? | q | , which is simpler than the known result.     

Recovering an Homogeneous Polynomial from Moments of Its Level Set

Let $\mathbf{K }:=\left\{ \mathbf{x }: g(\mathbf{x })\le 1\right\} $ K : = x : g ( x ) ≤ 1 be the compact (and not necessarily convex) sub-level set of some homogeneous polynomial $g$ g . Assume that the only knowledge about $\mathbf{K }$ K is the degree of $g$ g as well as the moments of the Lebesgue measure on $\mathbf{K }$ K up to order $2d$ 2 d . Then the vector of coefficients of $g$ g is the solution of a simple linear system whose associated matrix is nonsingular. In other words, the moments up to order $2d$ 2 d of the Lebesgue measure on $\mathbf{K }$ K encode all information on the homogeneous polynomial $g$ g that defines $\mathbf{K }$ K (in fact, only moments of order $d$ d and $2d$ 2 d are needed).     

Nef line bundles on flag bundles on a curve over {\overline{{\mathbb F}}_p}

Let E be a vector bundle of rank r over an irreducible smooth projective curve X defined over the field ${\overline{{\mathbb F}}_p}$ F ¯ p . For fixed integers ${r_1\, , \ldots\, , r_\nu}$ r 1 , ... , r ν with ${1\, \leq\, r_1\, <\, \cdots\, <\, r_\nu\, <\, r}$ 1 ≤ r 1 < ? < r ν < r , let ${\text{Fl}(E)}$ Fl ( E ) be the corresponding flag bundle over X associated to E. Let ${\xi\, \longrightarrow \, {\rm Fl}(E)}$ ξ ? Fl ( E ) be a line bundle such that for every pair of the form ${(C\, ,\phi)}$ ( C , ? ) , where C is an irreducible smooth projective curve defined over ${\overline{\mathbb F}_p}$ F ¯ p and ${\phi\, :\, C\, \longrightarrow\, {\rm Fl}(E)}$ ? : C ? Fl ( E ) is a nonconstant morphism, the inequality ${{\rm degree}(\phi^* \xi)\, > \, 0}$ degree ( ? ? ξ ) > 0 holds. We prove that the line bundle ${\xi}$ ξ is ample.     

Triangle-Free Geometric Intersection Graphs with Large Chromatic Number

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set $X$ X in $\mathbb{R }^2$ R 2 that is not an axis-aligned rectangle and for any positive integer $k$ k produces a family $\mathcal{F }$ F of sets, each obtained by an independent horizontal and vertical scaling and translation of $X$ X , such that no three sets in $\mathcal{F }$ F pairwise intersect and $\chi (\mathcal{F })>k$ χ ( F ) > k . This provides a negative answer to a question of Gyárfás and Lehel for L-shapes. With extra conditions we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries or equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.     

*-Quantizations of Fourier–Mukai Transforms

We study deformations of Fourier–Mukai transforms in general complex analytic settings. Suppose X and Y are complex manifolds, and let P be a coherent sheaf on X ×  Y. Suppose that the Fourier–Mukai transform ${\Phi}$ Φ given by the kernel P is an equivalence between the coherent derived categories of X and of Y. Suppose also that we are given a formal *-quantization ${\mathbb{X}}$ X of X. Our main result is that ${\mathbb{X}}$ X gives rise to a unique formal *-quantization ${\mathbb{Y}}$ Y of Y. For the statement to hold, *-quantizations must be understood in the framework of stacks of algebroids. The quantization ${\mathbb{Y}}$ Y is uniquely determined by the condition that ${\Phi}$ Φ deforms to an equivalence between the derived categories of ${\mathbb{X}}$ X and ${\mathbb{Y}}$ Y . Equivalently, the condition is that P deforms to a coherent sheaf ${\tilde{P}}$ P ~ on the formal *-quantization ${\mathbb{X} \times\mathbb{Y}^{op}}$ X × Y o p of X × Y; here ${\mathbb{Y}^{op}}$ Y o p is the opposite of the quantization ${\mathbb{Y}}$ Y .     

The Euler class group of a polynomial algebra with coefficients in a line bundle

Let $A$ be a commutative Noetherian ring and $P$ be a projective $A$ -module of rank $=(\text {dim}(A)-1)$ . An intriguing open question is to find the precise obstruction for $P$ to split as: $P\simeq Q\oplus A$ for some $A$ -module $Q$ . In this paper we settle this question when $A=R[T]$ for some ring $R$ containing the field of rationals and $P$ is a projective $A$ -module of rank $=\text {dim}(R)$ .