f-Vectors Implying Vertex Decomposability

We prove that if a pure simplicial complex $\Delta $ of dimension $d$ with $n$ facets has the least possible number of $(d-1)$ -dimensional faces among all complexes with $n$ faces of dimension $d$ , then it is vertex decomposable. This answers a question of J. Herzog and T. Hibi. In fact, we prove a generalization of their theorem using combinatorial methods.     

On High-Dimensional Acyclic Tournaments

We study a high-dimensional analog for the notion of an acyclic (aka transitive) tournament. We give upper and lower bounds on the number of $d$ -dimensional $n$ -vertex acyclic tournaments. In addition, we prove that every $n$ -vertex $d$ -dimensional tournament contains an acyclic subtournament of $\Omega (\log ^{1/d}n)$ vertices and the bound is tight. This statement for tournaments (i.e., the case $d=1$ ) is a well-known fact. We indicate a connection between acyclic high-dimensional tournaments and Ramsey numbers of hypergraphs. We investigate as well the inter-relations among various other notions of acyclicity in high-dimensional tournaments. These include combinatorial, geometric and topological concepts.     

Explicit Constructions of Centrally Symmetric k-Neighborly Polytopes and Large Strictly Antipodal Sets

We present explicit constructions of centrally symmetric $2$ -neighborly $d$ -dimensional polytopes with about $3^{d/2}\approx (1.73)^d$ vertices and of centrally symmetric $k$ -neighborly $d$ -polytopes with about $2^{{3d}/{20k^2 2^k}}$ vertices. Using this result, we construct for a fixed $k\ge 2$ and arbitrarily large $d$ and $N$ , a centrally symmetric $d$ -polytope with $N$ vertices that has at least $\left( 1-k^2\cdot (\gamma _k)^d\right) \genfrac(){0.0pt}{}{N}{k}$ faces of dimension $k-1$ , where $\gamma _2=1/\sqrt{3}\approx 0.58$ and $\gamma _k = 2^{-3/{20k^2 2^k}}$ for $k\ge 3$ . Another application is a construction of a set of $3^{\lfloor d/2 -1\rfloor }-1$ points in $\mathbb R ^d$ every two of which are strictly antipodal as well as a construction of an $n$ -point set (for an arbitrarily large $n$ ) in $\mathbb R ^d$ with many pairs of strictly antipodal points. The two latter results significantly improve the previous bounds by Talata, and Makai and Martini, respectively.     

Integer-valued polynomials over matrices and divided differences

Let $D$ be an integrally closed domain with quotient field $K$ and $n$ a positive integer. We give a characterization of the polynomials in $K[X]$ which are integer-valued over the set of matrices $M_n(D)$ in terms of their divided differences. A necessary and sufficient condition on $f\in K[X]$ to be integer-valued over $M_n(D)$ is that, for each $k$ less than $n$ , the $k$ th divided difference of $f$ is integral-valued on every subset of the roots of any monic polynomial over $D$ of degree $n$ . If in addition $D$ has zero Jacobson radical then it is sufficient to check the above conditions on subsets of the roots of monic irreducible polynomials of degree $n$ , that is, conjugate integral elements of degree $n$ over $D$ .     

Lattice-free sets,multi-branch split disjunctions,and mixed-integer programming

In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (Discret Optim 5:724–734, 2008). By analyzing $n$ -dimensional lattice-free sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with $n$ integer variables is a $t$ -branch split cut. We use this result to give a finite cutting-plane algorithm to solve mixed-integer programs. We also show that the minimum value $t$ , for which all facets of polyhedral mixed-integer sets with $n$ integer variables can be generated as $t$ -branch split cuts, grows exponentially with $n$ . In particular, when $n=3$ , we observe that not all facet-defining inequalities are 6-branch split cuts.     

Sporadic Reinhardt Polygons

Let $n$ be a positive integer, not a power of two. A Reinhardt polygon is a convex $n$ -gon that is optimal in three different geometric optimization problems: it has maximal perimeter relative to its diameter, maximal width relative to its diameter, and maximal width relative to its perimeter. For almost all $n$ , there are many Reinhardt polygons with $n$ sides, and many of them exhibit a particular periodic structure. While these periodic polygons are well understood, for certain values of $n$ , additional Reinhardt polygons exist, which do not possess this structured form. We call these polygons sporadic. We completely characterize the integers $n$ for which sporadic Reinhardt polygons exist, showing that these polygons occur precisely when $n=pqr$ with $p$ and $q$ distinct odd primes and $r\ge 2$ . We also prove that a positive proportion of the Reinhardt polygons with $n$ sides is sporadic for almost all integers $n$ , and we investigate the precise number of sporadic Reinhardt polygons that are produced for several values of $n$ by a construction that we introduce.     

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

Towards a de Bruijn–Erdős Theorem in the L_1-Metric

A well-known theorem of de Bruijn and Erd?s states that any set of $n$ non-collinear points in the plane determines at least $n$ lines. Chen and Chvátal asked whether an analogous statement holds within the framework of finite metric spaces, with lines defined using the notion of betweenness. In this paper, we prove that the answer is affirmative for sets of $n$ points in the plane with the $L_1$ metric, provided that no two points share their $x$ - or $y$ -coordinate. In this case, either there is a line that contains all $n$ points, or $X$ induces at least $n$ distinct lines. If points of $X$ are allowed to share their coordinates, then either there is a line that contains all $n$ points, or $X$ induces at least $n/37$ distinct lines.     

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 .     

Localization and delocalization of eigenvectors for heavy-tailed random matrices

Consider an $n \times n$ Hermitian random matrix with, above the diagonal, independent entries with $\alpha $ -stable symmetric distribution and $0 < \alpha < 2$ . We establish new bounds on the rate of convergence of the empirical spectral distribution of this random matrix as $n$ goes to infinity. When $1 < \alpha < 2$ and $ p > 2$ , we give vanishing bounds on the $L^p$ -norm of the eigenvectors normalized to have unit $L^2$ -norm. On the contrary, when $0 < \alpha < 2/3$ , we prove that these eigenvectors are localized.     

Canonical subgroups via Breuil–Kisin modules

Let $p>2$ be a rational prime and $K/ \mathbb Q _p$ be an extension of complete discrete valuation fields. Let $\mathcal G $ be a truncated Barsotti–Tate group of level $n$ , height $h$ and dimension $d$ over $\mathcal{O }_K$ with $0<d<h$ . In this paper, we show that if the Hodge height of $\mathcal G $ is less than $1/(p^{n-2}(p+1))$ , then there exists a finite flat closed subgroup scheme of $\mathcal G $ of order $p^{nd}$ over $\mathcal{O }_K$ with standard properties as the canonical subgroup.     

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 .     

Semi-algebraic functions have small subdifferentials

We prove that the subdifferential of any semi-algebraic extended-real-valued function on $\mathbf{R}^n$ has $n$ -dimensional graph. We discuss consequences for generic semi-algebraic optimization problems.     

Global symplectic coordinates on gradient Kähler–Ricci solitons

A classical result of McDuff [14] asserts that a simply connected complete Kähler manifold $(M,g,\omega )$ with non positive sectional curvature admits global symplectic coordinates through a symplectomorphism $\Psi \ : M \rightarrow \mathbb{R }^{2n}$ (where $n$ is the complex dimension of $M$ ), satisfying the following property (proved by E. Ciriza in [4]): the image $\Psi (T)$ of any complex totally geodesic submanifold $T\subset M$ through the point $p$ such that $\Psi (p)=0$ , is a complex linear subspace of $\mathbb C ^n\simeq \mathbb{R }^{2n}$ . The aim of this paper is to exhibit, for all positive integers $n$ , examples of $n$ -dimensional complete Kähler manifolds with non-negative sectional curvature globally symplectomorphic to $\mathbb{R }^{2n}$ through a symplectomorphism satisfying Ciriza’s property.     

Principal graph stability and the jellyfish algorithm

We show that if the principal graph of a subfactor planar algebra of modulus $\delta >2$ is stable for two depths, then it must end in $A_{ finite }$ tails. This result is analogous to Popa’s theorem on principal graph stability. We use these theorems to show that an $n-1$ supertransitive subfactor planar algebra has jellyfish generators at depth $n$ if and only if its principal graph is a spoke graph. This is the published version of arxiv:1208.1564.     

Derived length of solvable groups of local diffeomorphisms

Let $G$ be a solvable subgroup of the group ${\mathrm{Diff}{{\,}_{}(\mathbb{C }^{n},0)}}$ of local complex analytic diffeomorphisms. Analogously as for groups of matrices we bound the solvable length of $G$ by a function of $n$ . Moreover we provide the best possible bounds for connected, unipotent and nilpotent groups.     

On the Degenerate Crossing Number

The degenerate crossing number ${\text{ cr}^{*}}(G)$ of a graph $G$ is the minimum number of crossing points of edges in any drawing of $G$ as a simple topological graph in the plane. This notion was introduced by Pach and Tóth who showed that for a graph $G$ with $n$ vertices and $e \ge 4n$ edges ${\text{ cr}^{*}}(G)=\Omega \big (e^4 / n^4\big )$ . In this paper we completely resolve the main open question about degenerate crossing numbers and show that ${\text{ cr}^{*}}(G)=\Omega \big (e^3 / n^2 \big )$ , provided that $e \ge 4n$ . This bound is best possible (apart for the multiplicative constant) as it matches the tight lower bound for the standard crossing number of a graph.     

Caffarelli–Kohn–Nirenberg inequality on metric measure spaces with applications

We prove that if a metric measure space satisfies the volume doubling condition and the Caffarelli–Kohn–Nirenberg inequality with the same exponent $n \ge 3$ , then it has exactly the $n$ -dimensional volume growth. As an application, if an $n$ -dimensional Finsler manifold of non-negative $n$ -Ricci curvature satisfies the Caffarelli–Kohn–Nirenberg inequality with the sharp constant, then its flag curvature is identically zero. In the particular case of Berwald spaces, such a space is necessarily isometric to a Minkowski space.     

Syzygies and tensor product of modules

We give an application of the New Intersection Theorem and prove the following: let $R$ be a local complete intersection ring of codimension $c$ and let $M$ and $N$ be nonzero finitely generated $R$ -modules. Assume $n$ is a nonnegative integer and that the tensor product $M\otimes _{R}N$ is an $(n+c)$ th syzygy of some finitely generated $R$ -module. If ${{\mathrm{Tor}}}^{R}_{>0}(M,N)=0$ , then both $M$ and $N$ are $n$ th syzygies of some finitely generated $R$ -modules.     

A construction of integer-valued polynomials with prescribed sets of lengths of factorizations

For an arbitrary finite non-empty set $S$ of natural numbers greater $1$ , we construct $f\in \text{ Int }(\mathbb{Z })=\{g\in \mathbb{Q }[x]\mid g(\mathbb{Z })\subseteq \mathbb{Z }\}$ such that $S$ is the set of lengths of $f$ , i.e., the set of all $n$ such that $f$ has a factorization as a product of $n$ irreducibles in $\text{ Int }(\mathbb{Z })$ . More generally, we can realize any finite non-empty multi-set of natural numbers greater 1 as the multi-set of lengths of the essentially different factorizations of $f$ .