Constructing uniform designs: A heuristic integer programming method

In this paper, the wrap-around _L2$L_2$-discrepancy (WD) of asymmetrical design is represented as a quadratic form, thus the problem of constructing a uniform design becomes a quadratic integer programming problem. By the theory of optimization, some theoretic properties are obtained. Algorithms for constructing uniform designs are then studied. When the number of runs n$n$ is smaller than the number of all level-combinations m$m$, the construction problem can be transferred to a zero–one quadratic integer programming problem, and an efficient algorithm based on the simulated annealing is proposed. When n≥m$n\ge m$, another algorithm is proposed. Empirical study shows that when n$n$ is large, the proposed algorithms can generate designs with lower WD compared to many existing methods. Moreover, these algorithms are suitable for constructing both symmetrical and asymmetrical designs.     

Quandle cocycles from invariant theory

Let G$G$ be a group. Any G$G$-module M$M$ has an algebraic structure called a G$G$-family of Alexander quandles. Given a 2-cocycle of a cohomology associated with this G$G$-family, topological invariants of (handlebody) knots in the 3-sphere are defined. We develop a simple algorithm to algebraically construct n$n$-cocycles of this G$G$-family from G$G$-invariant group n$n$-cocycles of the abelian group M$M$. We present many examples of 2-cocycles of these G$G$-families using facts from (modular) invariant theory.     

Presenting higher stacks as simplicial schemes

We show that an n$n$-geometric stack may be regarded as a special kind of simplicial scheme, namely a Duskin n$n$-hypergroupoid in affine schemes, where surjectivity is defined in terms of covering maps, yielding Artin n$n$-stacks, Deligne–Mumford n$n$-stacks and n$n$-schemes as the notion of covering varies. This formulation adapts to all HAG contexts, so in particular works for derived n$n$-stacks (replacing rings with simplicial rings). We exploit this to describe quasi-coherent sheaves and complexes on these stacks, and to draw comparisons with Kontsevich’s dg-schemes. As an application, we show how the cotangent complex controls infinitesimal deformations of higher and derived stacks.     

On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence

In many applications it has been observed that hybrid-Monte Carlo sequences perform better than Monte Carlo and quasi-Monte Carlo sequences, especially in difficult problems. For a mixed s$s$-dimensional sequence m$m$, whose elements are vectors obtained by concatenating d$d$-dimensional vectors from a low-discrepancy sequence q$q$ with (s−d)$(s-d)$-dimensional random vectors, probabilistic upper bounds for its star discrepancy have been provided. In a paper of G. Ökten, B. Tuffin and V. Burago [G. Ökten, B. Tuffin, V. Burago, J. Complexity 22 (2006), 435–458] it was shown that for arbitrary ε>0$\epsilon >0$ the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$ is bounded by ε$\epsilon$ with probability at least 1−2exp(−ε²N/2)$1-2exp(-{\epsilon }^{2}N/2)$ for N$N$ sufficiently large. The authors did not study how large N$N$ actually has to be and if and how this actually depends on the parameters s$s$ and ε$\epsilon$. In this note we derive a lower bound for N$N$, which significantly depends on s$s$ and ε$\epsilon$. Furthermore, we provide a probabilistic bound for the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$, which holds without any restrictions on N$N$. In this sense it improves on the bound of Ökten, Tuffin and Burago and is more helpful in practice, especially for small sample sizes N$N$. We compare this bound to other known bounds.     

A new method for computing Moore–Penrose inverse matrices

The Moore–Penrose inverse of an arbitrary matrix (including singular and rectangular) has many applications in statistics, prediction theory, control system analysis, curve fitting and numerical analysis. In this paper, an algorithm based on the conjugate Gram–Schmidt process and the Moore–Penrose inverse of partitioned matrices is proposed for computing the pseudoinverse of an m×n$m\times n$ real matrix A$A$ with m≥n$m\ge n$ and rank r≤n$r\le n$. Numerical experiments show that the resulting pseudoinverse matrix is reasonably accurate and its computation time is significantly less than that of pseudoinverses obtained by the other methods for large sparse matrices.     

Multi-dimensional G-Brownian motion and related stochastic calculus under G-expectation

We develop a notion of nonlinear expectation–G$G$-expectation–generated by a nonlinear heat equation with infinitesimal generator G$G$. We first study multi-dimensional G$G$-normal distributions. With this nonlinear distribution we can introduce our G$G$-expectation under which the canonical process is a multi-dimensional G$G$-Brownian motion. We then establish the related stochastic calculus, especially stochastic integrals of Itô’s type with respect to our G$G$-Brownian motion, and derive the related Itô’s formula. We have also obtained the existence and uniqueness of stochastic differential equations under our G$G$-expectation.     

Quantizations of Kac–Moody algebras

We analyze the extent to which a quantum universal enveloping algebra of a Kac–Moody algebra g$\mathfrak{g}$ is defined by multidegrees of its defining relations. To this end, we consider a class of character Hopf algebras defined by the same number of defining relations of the same degrees as the Kac–Moody algebra g$\mathfrak{g}$. We demonstrate that if the generalized Cartan matrix A$A$ of g$\mathfrak{g}$ is connected then the algebraic structure, up to a finite number of exceptional cases, is defined by just one “continuous” parameter q$q$ related to a symmetrization of A$A$, and one “discrete” parameter m$\mathfrak{m}$ related to the modular symmetrizations of A$A$. The Hopf algebra structure is defined by n(n−1)/2$n(n-1)/2$ additional “continuous” parameters. We also consider the exceptional cases for Cartan matrices of finite or affine types in more detail, establishing the number of exceptional parameter values in terms of the Fibonacci sequence.     

On prime ideals and radicals of polynomial rings and graded rings

We extend some known results on radicals and prime ideals from polynomial rings and Laurent polynomial rings to Z$\mathbb{Z}$-graded rings, i.e, rings graded by the additive group of integers. The main of them concerns the Brown–McCoy radical G$G$ and the radical S$S$, which for a given ring A$A$ is defined as the intersection of prime ideals I$I$ of A$A$ such that A/I$A/I$ is a ring with a large center. The studies are related to some open problems on the radicals G$G$ and S$S$ of polynomial rings and situated in the context of Koethe’s problem.     

Tournaments associated with multigraphs and a theorem of Hakimi

A tournament of order n$n$ is usually considered as an orientation of the complete graph _Kn$K_n$. In this note, we consider a more general definition of a tournament that we call aC$C$-tournament, where C$C$ is the adjacency matrix of a multigraph G$G$, and a C$C$-tournament is an orientation of G$G$. The score vector of a C$C$-tournament is the vector of outdegrees of its vertices. In 1965 Hakimi obtained necessary and sufficient conditions for the existence of a C$C$-tournament with a prescribed score vector R$R$ and gave an algorithm to construct such a C$C$-tournament which required, however, some backtracking. We give a simpler and more transparent proof of Hakimi’s theorem, and then provide a direct construction of such a C$C$-tournament which works even for weighted graphs.     

Strongly quasi-Hamiltonian-connected semicomplete multipartite digraphs

A semicomplete multipartite or semicomplete c$c$-partite digraph D$D$ is a biorientation of a c$c$-partite graph. A semicomplete multipartite digraph D$D$ is called strongly quasi-Hamiltonian-connected, if for any two distinct vertices x$x$ and y$y$ of D$D$, there is a path P$P$ from x$x$ to y$y$ such that P$P$ contains at least one vertex from each partite set of D$D$.     

Weak convergence of censored and reflected stable processes

It is shown that if a sequence of open n$n$-sets _Dk$D_k$ increases to an open n$n$-set D$D$ then reflected stable processes in _Dk$D_k$ converge weakly to the reflected stable process in D$D$ for every starting point x$x$ in D$D$. The same result holds for censored α$\alpha$-stable processes for every x$x$ in D$D$ if D$D$ and _Dk$D_k$ satisfy the uniform Hardy inequality. Using the method in the proof of the above results, we also prove the weak convergence of reflected Brownian motions in unbounded domains.     

Hardness of comparing two run-length encoded strings

In this paper, we consider a commonly used compression scheme called run-length encoding. We provide both lower and upper bounds for the problems of comparing two run-length encoded strings. Specifically, we prove the 3sum-hardness for both the wildcard matching problem and the k$k$-mismatch problem with run-length compressed inputs. Given two run-length encoded strings of m$m$ and n$n$ runs, such a result implies that it is very unlikely to devise an o(mn)$o\left(mn\right)$-time algorithm for either of them. We then present an inplace algorithm running in O(mnlogm)$O(mnlogm)$ time for their combined problem, i.e. k$k$-mismatch with wildcards. We further demonstrate that if the aim is to report the positions of all the occurrences, there exists a stronger barrier of Ω(mnlogm)$\Omega (mnlogm)$-time, matching the running time of our algorithm. Moreover, our algorithm can be easily generalized to a two-dimensional setting without impairing the time and space complexity.     

On topological entropy of commuting tree maps

Let T$T$ be a tree with s$s$ ends and f,g$f,g$ be continuous maps from T$T$ to T$T$ with f°g=g°f$f°g=g°f$. In this note we show that if there exists a positive integer m≥2$m\ge 2$ such that gcd(m,l)=1$gcd(m,l)=1$ for any 2≤l≤s$2\le l\le s$ and f,g$f,g$ share a periodic point which is a km$km$-periodic point of f$f$ for some positive integer k$k$, then the topological entropy of f°g$f°g$ is positive.     

The Quicksort process

Quicksort on the fly returns the input of n$n$ reals in increasing natural order during the sorting process. Correctly normalized the running time up to returning the l$l$-th smallest out of n$n$ seen as a process in l$l$ converges weakly to a limiting process with path in the space of cadlag functions.     

On testing Hamiltonicity of graphs

Let us fix a function f(n)=o(nlnn)$f\left(n\right)=o(nlnn)$ and real numbers 0≤α<β≤1$0\le \alpha <\beta \le 1$. We present a polynomial time algorithm which, given a directed graph G$G$ with n$n$ vertices, decides either that one can add at most βn$\beta n$ new edges to G$G$ so that G$G$ acquires a Hamiltonian circuit or that one cannot add αn$\alpha n$ or fewer new edges to G$G$ so that G$G$ acquires at least e^−f(n)n!$e^{-f\left(n\right)}n!$ Hamiltonian circuits, or both.     

On the second neighborhood conjecture of Seymour for regular digraphs with almost optimal connectivity

The second neighborhood conjecture of Seymour says that every antisymmetric digraph has a vertex whose second neighborhood is not smaller than the first one. The Caccetta–Häggkvist conjecture says that every digraph with n$n$ vertices and minimum out-degree r$r$ contains a cycle of length at most ⌈n/r⌉$\lceil n/r\rceil$. We give a proof of the former conjecture for digraphs with out-degree r$r$ and connectivity r−1$r-1$, and of the second one for digraphs with connectivity r−1$r-1$ and r≥n/3$r\ge n/3$. The main tool is the isoperimetric method of Hamidoune.     

Approximate martingale estimating functions for stochastic differential equations with small noises

An approximate martingale estimating function with an eigenfunction is proposed for an estimation problem about an unknown drift parameter for a one-dimensional diffusion process with small perturbed parameter ε$\epsilon$ from discrete time observations at n$n$ regularly spaced time points k/n$k/n$, k=0,1,…,n$k=0,1,\dots ,n$. We show asymptotic efficiency of an M$M$-estimator derived from the approximate martingale estimating function as ε→0$\epsilon \to 0$ and n→∞$n\to \infty$ simultaneously.     

Products of conjugacy classes in finite and algebraic simple groups

We prove the Arad–Herzog conjecture for various families of finite simple groups — if A$A$ and B$B$ are nontrivial conjugacy classes, then AB$AB$ is not a conjugacy class. We also prove that if G$G$ is a finite simple group of Lie type and A$A$ and B$B$ are nontrivial conjugacy classes, either both semisimple or both unipotent, then AB$AB$ is not a conjugacy class. We also prove a strong version of the Arad–Herzog conjecture for simple algebraic groups and in particular show that almost always the product of two conjugacy classes in a simple algebraic group consists of infinitely many conjugacy classes. As a consequence we obtain a complete classification of pairs of centralizers in a simple algebraic group which have dense product. A special case of this has been used by Prasad to prove a uniqueness result for Tits systems in quasi-reductive groups. Our final result is a generalization of the Baer–Suzuki theorem for p$p$-elements with p≥5$p\ge 5$.     

The effect of predator competition on positive solutions for a predator–prey model with diffusion

A diffusive predator–prey model with predator competition is considered under Dirichlet boundary conditions. Some existence and non-existence results are firstly obtained. Then by investigating the bifurcation of positive solutions, the multiplicity of positive solutions is established for suitably large m$m$. Furthermore, by meticulously analyzing the asymptotic behaviors of positive solutions when k$k$ goes to ∞$\infty$, we find that there is at most a positive solution for any c∈R$c\in R$ when k$k$ is sufficiently large. At last, some numerical simulations are presented to supplement the analytic results in one dimension.