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.     

Holding Circles and Fixing Frames

A circle $C$ holds a convex body $K \subset \mathbb {R}^3$ if $K$ can’t be moved far away from its position without intersecting $C$ . One of our results says that there is a convex body $K \subset \mathbb {R}^3$ such that the set of radii of all circles holding $K$ has infinitely many components. Another result says that the circle is unique in the sense that every frame different from the circle holds a convex body $K$ (actually a tetrahedron) so that every nontrivial rigid motion of $K$ intersects the frame.     

Inductive topological Hausdorff dimensions and fibers of generic continuous functions

In an earlier paper Buczolich, Elekes and the author introduced a new concept of dimension for metric spaces, the so called topological Hausdorff dimension. They proved that it is precisely the right notion to describe the Hausdorff dimension of the level sets of the generic real-valued continuous function (in the sense of Baire category) defined on a compact metric space $K$ . The goal of this paper is to determine the Hausdorff dimension of the fibers of the generic continuous function from $K$ to $\mathbb {R}^n$ . In order to do so, we define the $n$ th inductive topological Hausdorff dimension, $\dim _{t^nH} K$ . Let $\dim _H K,\,\dim _t K$ and $C_n(K)$ denote the Hausdorff and topological dimension of $K$ and the Banach space of the continuous functions from $K$ to $\mathbb {R}^n$ . We show that $\sup _{y\in \mathbb {R}^n} \dim _{H}f^{-1}(y) = \dim _{t^nH} K -n$ for the generic $f \in C_n(K)$ , provided that $\dim _t K\ge n$ , otherwise every fiber is finite. In order to prove the above theorem we give some equivalent definitions for the inductive topological Hausdorff dimensions, which can be interesting in their own right. Here we use techniques coming from the theory of topological dimension. We show that the supremum is actually attained on the left hand side of the above equation. We characterize those compact metric spaces $K$ for which $\dim _{H} f^{-1}(y)=\dim _{t^nH}K-n$ for the generic $f\in C_n(K)$ and the generic $y\in f(K)$ . We also generalize a result of Kirchheim by showing that if $K$ is self-similar and $\dim _t K\ge n$ then $\dim _{H} f^{-1}(y)=\dim _{t^nH}K-n$ for the generic $f\in C_n(K)$ for every $y\in {{\mathrm{int}}}f(K)$ .     

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

Planar Point Sets With Large Minimum Convex Decompositions

We show the existence of sets with $n$ points ( $n\ge 4$ ) for which every convex decomposition contains more than $\frac{35}{32}n-\frac{3}{2}$ polygons, which refutes the conjecture that for every set of $n$ points there is a convex decomposition with at most $n+C$ polygons. For sets having exactly three extreme points we show that more than $n+\sqrt{2(n-3)}-4$ polygons may be necessary to form a convex decomposition.     

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.     

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.     

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.     

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 .     

The Set of Packing and Covering Densities of Convex Disks

For every convex disk $K$ (a convex compact subset of the plane, with non-void interior), the packing density $\delta (K)$ and covering density ${\vartheta (K)}$ form an ordered pair of real numbers, i.e., a point in $\mathbb{R }^2$ . The set $\varOmega $ consisting of points assigned this way to all convex disks is the subject of this article. A few known inequalities on $\delta (K)$ and ${\vartheta (K)}$ jointly outline a relatively small convex polygon $P$ that contains $\varOmega $ , while the exact shape of $\varOmega $ remains a mystery. Here we describe explicitly a leaf-shaped convex region $\Lambda $ contained in $\varOmega $ and occupying a good portion of $P$ . The sets $\varOmega _T$ and $\varOmega _L$ of translational packing and covering densities and lattice packing and covering densities are defined similarly, restricting the allowed arrangements of $K$ to translated copies or lattice arrangements, respectively. Due to affine invariance of the translative and lattice density functions, the sets $\varOmega _T$ and $\varOmega _L$ are compact. Furthermore, the sets $\varOmega , \,\varOmega _T$ and $\varOmega _L$ contain the subsets $\varOmega ^\star , \,\varOmega _T^\star $ and $\varOmega _L^\star $ respectively, corresponding to the centrally symmetric convex disks $K$ , and our leaf $\Lambda $ is contained in each of $\varOmega ^\star , \,\varOmega _T^\star $ and $\varOmega _L^\star $ .     

Variance asymptotics for random polytopes in smooth convex bodies

Let $K \subset \mathbb R ^d$ be a smooth convex set and let $\mathcal{P }_{\lambda }$ be a Poisson point process on $\mathbb R ^d$ of intensity ${\lambda }$ . The convex hull of $\mathcal{P }_{\lambda }\cap K$ is a random convex polytope $K_{\lambda }$ . As ${\lambda }\rightarrow \infty $ , we show that the variance of the number of $k$ -dimensional faces of $K_{\lambda }$ , when properly scaled, converges to a scalar multiple of the affine surface area of $K$ . Similar asymptotics hold for the variance of the number of $k$ -dimensional faces for the convex hull of a binomial process in $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 .     

Norm-Constrained Determinantal Representations of Multivariable Polynomials

For every multivariable polynomial $p$ , with $p(0)=1$ , we construct a determinantal representation, $ p=\det (I - K Z )$ , where $Z$ is a diagonal matrix with coordinate variables on the diagonal and $K$ is a complex square matrix. Such a representation is equivalent to the existence of $K$ whose principal minors satisfy certain linear relations. When norm constraints on $K$ are imposed, we give connections to the multivariable von Neumann inequality, Agler denominators, and stability. We show that if a multivariable polynomial $q$ , $q(0)=0,$ satisfies the von Neumann inequality, then $1-q$ admits a determinantal representation with $K$ a contraction. On the other hand, every determinantal representation with a contractive $K$ gives rise to a rational inner function in the Schur–Agler class.     

Exact Lagrangian immersions with one double point revisited

We study exact Lagrangian immersions with one double point of a closed orientable manifold $K$ into $\mathbb{C }^{n}$ . We prove that if the Maslov grading of the double point does not equal $1$ then $K$ is homotopy equivalent to the sphere, and if, in addition, the Lagrangian Gauss map of the immersion is stably homotopic to that of the Whitney immersion, then $K$ bounds a parallelizable $(n+1)$ -manifold. The hypothesis on the Gauss map always holds when $n=2k$ or when $n=8k-1$ . The argument studies a filling of $K$ obtained from solutions to perturbed Cauchy–Riemann equations with boundary on the image $f(K)$ of the immersion. This leads to a new and simplified proof of some of the main results of Ekholm and Smith (Exact Lagrangian immersions with a single double point 2011)). which treated Lagrangian immersions in the case $n=2k$ by applying similar techniques to a Lagrange surgery of the immersion, as well as to an extension of these results to the odd-dimensional case.     

Local tensor valuations on convex polytopes

Local versions of the Minkowski tensors of convex bodies in $n$ -dimensional Euclidean space are introduced. An extension of Hadwiger’s characterization theorem for the intrinsic volumes, due to Alesker, states that the continuous, isometry covariant valuations on the space of convex bodies with values in the vector space of symmetric $p$ -tensors are linear combinations of modified Minkowski tensors. We ask for a local analogue of this characterization, and we prove a classification result for local tensor valuations on polytopes, without a continuity assumption.     

A New Topological Helly Theorem and Some Transversal Results

We prove that for a topological space \(X\) with the property that \( H_{*}(U)=0\) for \(*\ge d\) and every open subset \(U\) of \(X\) , a finite family of open sets in \(X\) has nonempty intersection if for any subfamily of size \(j,\,1\le j\le d+1,\) the \((d-j)\) -dimensional homology group of its intersection is zero. We use this theorem to prove new results concerning transversal affine planes to families of convex sets.     

A note on the uniqueness problem of non-Archimedean holomorphic curves

We prove a uniqueness theorem for non-Archimedean linearly nondegenerate holomorphic curves in projective spaces of dimension $n$ with two families of $(2n+2)$ hyperplanes in general position. Our result strongly generalizes the uniqueness theorem with $(3n+1)$ hyperplanes of Ru in [11].     

Yangians and quantum loop algebras

Let $\mathfrak{g }$ be a complex, semisimple Lie algebra. Drinfeld showed that the quantum loop algebra $U_\hbar (L\mathfrak g )$ of $\mathfrak{g }$ degenerates to the Yangian ${Y_\hbar (\mathfrak g )}$ . We strengthen this result by constructing an explicit algebra homomorphism $\Phi $ from $U_\hbar (L\mathfrak g )$ to the completion of ${Y_\hbar (\mathfrak g )}$ with respect to its grading. We show moreover that $\Phi $ becomes an isomorphism when ${U_\hbar (L\mathfrak g )}$ is completed with respect to its evaluation ideal. We construct a similar homomorphism for $\mathfrak{g }=\mathfrak{gl }_n$ and show that it intertwines the actions of $U_\hbar (L\mathfrak gl _{n})$ and $Y_\hbar (\mathfrak gl _{n})$ on the equivariant $K$ -theory and cohomology of the variety of $n$ -step flags in ${\mathbb{C }}^d$ constructed by Ginzburg–Vasserot.     

Functional limit theorems for random regular graphs

Consider $d$ uniformly random permutation matrices on $n$ labels. Consider the sum of these matrices along with their transposes. The total can be interpreted as the adjacency matrix of a random regular graph of degree $2d$ on $n$ vertices. We consider limit theorems for various combinatorial and analytical properties of this graph (or the matrix) as $n$ grows to infinity, either when $d$ is kept fixed or grows slowly with $n$ . In a suitable weak convergence framework, we prove that the (finite but growing in length) sequences of the number of short cycles and of cyclically non-backtracking walks converge to distributional limits. We estimate the total variation distance from the limit using Stein’s method. As an application of these results we derive limits of linear functionals of the eigenvalues of the adjacency matrix. A key step in this latter derivation is an extension of the Kahn–Szemerédi argument for estimating the second largest eigenvalue for all values of $d$ and $n$ .     

The K-theory of free quantum groups

In this paper we study the $K$ -theory of free quantum groups in the sense of Wang and Van Daele, more precisely, of free products of free unitary and free orthogonal quantum groups. We show that these quantum groups are $K$ -amenable and establish an analogue of the Pimsner–Voiculescu exact sequence. As a consequence, we obtain in particular an explicit computation of the $K$ -theory of free quantum groups. Our approach relies on a generalization of methods from the Baum–Connes conjecture to the framework of discrete quantum groups. This is based on the categorical reformulation of the Baum–Connes conjecture developed by Meyer and Nest. As a main result we show that free quantum groups have a $\gamma $ -element and that $\gamma = 1$ . As an important ingredient in the proof we adapt the Dirac-dual Dirac method for groups acting on trees to the quantum case. We use this to extend some permanence properties of the Baum–Connes conjecture to our setting.