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.     

Collapsibility and Vanishing of Top Homology in Random Simplicial Complexes

Let $\Delta _{n-1}$ denote the $(n-1)$ -dimensional simplex. Let $Y$ be a random $d$ -dimensional subcomplex of $\Delta _{n-1}$ obtained by starting with the full $(d-1)$ -dimensional skeleton of $\Delta _{n-1}$ and then adding each $d$ -simplex independently with probability $p=\frac{c}{n}$ . We compute an explicit constant $\gamma _d$ , with $\gamma _2 \simeq 2.45$ , $\gamma _3 \simeq 3.5$ , and $\gamma _d=\Theta (\log d)$ as $d \rightarrow \infty $ , so that for $c < \gamma _d$ such a random simplicial complex either collapses to a $(d-1)$ -dimensional subcomplex or it contains $\partial \Delta _{d+1}$ , the boundary of a $(d+1)$ -dimensional simplex. We conjecture this bound to be sharp. In addition, we show that there exists a constant $\gamma _d< c_d <d+1$ such that for any $c>c_d$ and a fixed field $\mathbb{F }$ , asymptotically almost surely $H_d(Y;\mathbb{F }) \ne 0$ .     

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.     

Harmonic mappings and conformal minimal immersions of Riemann surfaces into {\mathbb {R}^{\rm N}}

We prove that for any open Riemann surface ${\mathcal{N}}$ , natural number N ≥ 3, non-constant harmonic map ${h:\mathcal{N} \to \mathbb{R}}$ ^N?2 and holomorphic 2-form ${\mathfrak{H}}$ on ${\mathcal{N}}$ , there exists a weakly complete harmonic map ${X=(X_j)_{j=1,\ldots,{\sc N}}:\mathcal{N} \to \mathbb{R}^{\sc N}}$ with Hopf differential ${\mathfrak{H}}$ and ${(X_j)_{j=3,\ldots,{\sc N}}=h.}$ In particular, there exists a complete conformal minimal immersion ${Y=(Y_j)_{j=1,\ldots,{\sc N}}:\mathcal{N} \to \mathbb{R}^{\sc N}}$ such that ${(Y_j)_{j=3,\ldots,{\sc N}}=h}$ . As some consequences of these results (1) there exist complete full non-decomposable minimal surfaces with arbitrary conformal structure and whose generalized Gauss map is non-degenerate and fails to intersect N hyperplanes of ${\mathbb{CP}^{{\sc N}-1}}$ in general position. (2) There exist complete non-proper embedded minimal surfaces in ${\mathbb{R}^{\sc N},}$ ${\forall\,{\sc N} >3 .}$      

LIM is not slim

In this paper LIM, a recently proposed impartial combinatorial ruleset, is analyzed. A formula to describe the $\mathcal G $ -values of LIM positions is given, by way of analyzing an equivalent combinatorial ruleset LIM’, closely related to the classical nim. Also, an enumeration of $\mathcal P $ -positions of LIM with $n$ stones, and its relation to the Ulam-Warburton cellular automaton, is presented.     

Characterizing Serre Quotients with no Section Functor and Applications to Coherent Sheaves

We prove an analogon of the the fundamental homomorphism theorem for certain classes of exact and essentially surjective functors of Abelian categories $\mathcal{Q}:\mathcal{A} \to \mathcal{B}$ . It states that $\mathcal{Q}$ is up to equivalence the Serre quotient $\mathcal{A} \to \mathcal{A} / \ker \mathcal{Q}$ , even in cases when the latter does not admit a section functor. For several classes of schemes X, including projective and toric varieties, this characterization applies to the sheafification functor from a certain category $\mathcal{A}$ of finitely presented graded modules to the category $\mathcal{B}=\mathfrak{Coh}\, X$ of coherent sheaves on X. This gives a direct proof that $\mathfrak{Coh}\, X$ is a Serre quotient of $\mathcal{A}$ .     

Characterization of some simple groups by the multiplicity pattern

Let $G$ be a finite group and let ${\mathrm{Irr}}(G)$ denote the set of all complex irreducible characters of $G.$ Let ${\mathrm{cd}}(G)$ be the set of all character degrees of $G.$ For each positive integer $d,$ the multiplicity of $d$ in $G$ is defined to be the number of irreducible characters of $G$ having the same degree $d.$ The multiplicity pattern ${\mathrm{mp}}(G)$ is the vector whose first coordinate is $|G:G^{\prime }|$ and for $i\ge 1,$ the $(i+1)$ th-coordinate of ${\mathrm{mp}}(G)$ is the multiplicity of the $i$ th-smallest nontrivial character degree of $G.$ In this paper, we show that every nonabelian simple group with at most $7$ distinct character degrees is uniquely determined by the multiplicity pattern.     

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.     

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

Moment Functions and Central Limit Theorem for Jacobi Hypergroups on [0,\infty [

In this paper, we derive sharp estimates and asymptotic results for moment functions on Jacobi type hypergroups. Moreover, we use these estimates to prove a central limit theorem (CLT) for random walks on Jacobi hypergroups with growing parameters $\alpha ,\beta \rightarrow \infty $ . As a special case, we obtain a CLT for random walks on the hyperbolic spaces ${H}_d(\mathbb F )$ with growing dimensions $d$ over the fields $\mathbb F =\mathbb R ,\ \mathbb C $ or the quaternions $\mathbb H $ .     

On the field of definition of p-torsion points on elliptic curves over the rationals

Let $S_\mathbb Q (d)$ be the set of primes $p$ for which there exists a number field $K$ of degree $\le d$ and an elliptic curve $E/\mathbb Q $ , such that the order of the torsion subgroup of $E(K)$ is divisible by $p$ . In this article we give bounds for the primes in the set $S_\mathbb Q (d)$ . In particular, we show that, if $p\ge 11$ , $p\ne 13,37$ , and $p\in S_\mathbb Q (d)$ , then $p\le 2d+1$ . Moreover, we determine $S_\mathbb Q (d)$ for all $d\le 42$ , and give a conjectural formula for all $d\ge 1$ . If Serre’s uniformity problem is answered positively, then our conjectural formula is valid for all sufficiently large $d$ . Under further assumptions on the non-cuspidal points on modular curves that parametrize those $j$ -invariants associated to Cartan subgroups, the formula is valid for all $d\ge 1$ .     

Maximal partial line spreads of non-singular quadrics

For $n \ge 9$ , we construct maximal partial line spreads for non-singular quadrics of $PG(n,q)$ for every size between approximately $(cn+d)(q^{n-3}+q^{n-5})\log {2q}$ and $q^{n-2}$ , for some small constants $c$ and $d$ . These results are similar to spectrum results on maximal partial line spreads in finite projective spaces by Heden, and by Gács and Sz?nyi. These results also extend spectrum results on maximal partial line spreads in the finite generalized quadrangles $W_3(q)$ and $Q(4,q)$ by Pepe, Rößing and Storme.     

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.     

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 .     

Euclidean Steiner trees optimal with respect to swapping 4-point subtrees

The Steiner tree problem in Euclidean space $E^3$ asks for a minimum length network $T$ , called a Euclidean Steiner Minimum Tree (ESMT), spanning a given set of points. This problem is NP-hard and the hardness is inherently due to the number of feasible topologies (underlying graph structure of $T$ ) which increases exponentially as the number of given points increases. Planarity is a very strong condition that gives a big difference between the ESMT problem in the Euclidean plane $E^2$ and in Euclidean $d$ -space $E^d (d\ge 3)$ : the ESMT problem in the plane is practically solvable whereas the ESMT problem in $d$ -space is really intractable. The simplest tree rearrangement technique is to repeatedly replace a subtree spanning four nodes in $T$ with another subtree spanning the same four nodes. This technique is referred to as the Swapping 4-point Topology/ Tree technique in this paper. An indicator (or quasi-indicator) of $T$ plays a similar role in the optimization of the length $L(T)$ of $T$ in the discrete topology space (the underlying graph structure of $T$ ) to the derivative of a differentiable function which indicates a fastest direction of descent. $T$ will be called S4pT-optimal if it is optimal with respect to swapping 4-point subtrees. In this paper we first make a complete analysis of 4-point trees in Euclidean space exploring all possible types of 4-point trees and their properties. We review some known indicators of 4-point ESMTs in $E^2$ , and give some simple geometric proofs of these indicators. Then, we translate these indicators to $E^3$ , producing eight quasi-indicators in $E^3$ using computational experiments, the best quasi-indicator $\rho _\mathrm{osr}$ is sifted with an effectiveness for randomly generated 4-point sets as high as 98.62 %. Finally we show how $\rho _\mathrm{osr}$ is used to find an S4pT-optimal ESMT on 14 probability vectors in $4d$ -space with a detailed example.     

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 .     

A subelliptic analogue of Aronson–Serrin’s Harnack inequality

We study the Harnack inequality for weak solutions of a class of degenerate parabolic quasilinear PDE $$\begin{aligned} \partial _t u={-}X_i^* A_i(x,t,u,Xu)+ B(x,t,u,Xu), \end{aligned}$$ in cylinders $\Omega \times (0,T)$ where $\Omega \subset M$ is an open subset of a manifold $M$ endowed with control metric $d$ corresponding to a system of Lipschitz continuous vector fields $X=(X_1,\ldots ,X_m)$ and a measure $d\sigma $ . We show that the Harnack inequality follows from the basic hypothesis of doubling condition and a weak Poincaré inequality in the metric measure space $(M,d,d\sigma )$ . We also show that such hypothesis hold for a class of Riemannian metrics $g_\epsilon $ collapsing to a sub-Riemannian metric $\lim _{\epsilon \rightarrow 0} g_\epsilon =g_0$ uniformly in the parameter $\epsilon \ge 0$ .     

Open Gromov–Witten invariants in dimension six

Let $L$ be a closed orientable Lagrangian submanifold of a closed symplectic six-manifold $(X , \omega )$ . We assume that the first homology group $H_1 (L ; A)$ with coefficients in a commutative ring $A$ injects into the group $H_1 (X ; A)$ and that $X$ contains no Maslov zero pseudo-holomorphic disc with boundary on $L$ . Then, we prove that for every generic choice of a tame almost-complex structure $J$ on $X$ , every relative homology class $d \in H_2 (X , L ; \mathbb{Z })$ and adequate number of incidence conditions in $L$ or $X$ , the weighted number of $J$ -holomorphic discs with boundary on $L$ , homologous to $d$ , and either irreducible or reducible disconnected, which satisfy the conditions, does not depend on the generic choice of $J$ , provided that at least one incidence condition lies in $L$ . These numbers thus define open Gromov–Witten invariants in dimension six, taking values in the ring $A$ .     

RENS

This article introduces rens, the relaxation enforced neighborhood search, a large neighborhood search algorithm for mixed integer nonlinear programs (MINLPs). It uses a sub-MINLP to explore the set of feasible roundings of an optimal solution $\bar{x}$ of a linear or nonlinear relaxation. The sub-MINLP is constructed by fixing integer variables $x_j$ with $\bar{x} _{j} \in \mathbb {Z}$ and bounding the remaining integer variables to $x_{j} \in \{ \lfloor \bar{x} _{j} \rfloor , \lceil \bar{x} _{j} \rceil \}$ . We describe two different applications of rens: as a standalone algorithm to compute an optimal rounding of the given starting solution and as a primal heuristic inside a complete MINLP solver. We use the former to compare different kinds of relaxations and the impact of cutting planes on the so-called roundability of the corresponding optimal solutions. We further utilize rens to analyze the performance of three rounding heuristics implemented in the branch-cut-and-price framework scip. Finally, we study the impact of rens when it is applied as a primal heuristic inside scip. All experiments were performed on three publicly available test sets of mixed integer linear programs (MIPs), mixed integer quadratically constrained programs (MIQCPs), and MINLP s, using solely software which is available in source code. It turns out that for these problem classes 60 to 70 % of the instances have roundable relaxation optima and that the success rate of rens does not depend on the percentage of fractional variables. Last but not least, rens applied as primal heuristic complements nicely with existing primal heuristics in scip.     

Precise and fast computation of Jacobian elliptic functions by conditional duplication

We developed a new method to compute the cosine amplitude function, $c\equiv \mathrm{cn}(u|m)$ , by using its double argument formula. The accumulation of round-off errors is effectively suppressed by the introduction of a complementary variable, $b\equiv 1-c$ , and a conditional switch between the duplication of $b$ and $c$ . The sine and delta amplitude functions, $s \equiv \mathrm{sn}(u|m)$ and $d \equiv \mathrm{dn}(u|m)$ , are evaluated from thus computed $b$ or $c$ by means of their identity relations. The new method is sufficiently precise as its errors are less than a few machine epsilons. Also, it is significantly faster than the existing procedures. In case of single precision computation, it runs more than 50 times faster than Bulirsch’s sncndn based on the Gauss transformation and 2.7 times faster than our previous method based on the simultaneous duplication of $s,c$ and $d$ . The ratios change to 7.6 and 3.5 respectively in case of the double precision environment.