Search

In this paper, we provide generating functions and counting formulas for spanning trees and spanning forests in hypergraphs in two different ways: (1) We represent spanning trees and spanning forests in hypergraphs through Berezin-Grassmann integrals on Zeon algebra and hyper-Hafnians (orders and signs are not considered); (2) We establish a Hyper-Pfaffian-Cactus Spanning Forest Theorem through Berezin-Grassmann integrals on Grassmann algebra (orders and signs are considered), which generalizes the Hyper-Pfaffian-Cactus Theorem by Abdesselam (2004) [1] and Pfaffian matrix tree theorem by Masbaum and Vaintrob (2002) [15]. • We provide generating functions and counting formulas for spanning trees and spanning forests in hypergraphs through Berezin-Grassmann integrals on Zeon algebra and hyper- Hafnians when orders and signs are not considered. • We establish a Hyper-Pfaffian-Cactus Spanning Forest Theorem through Berezin-Grassmann integrals on Grassmann algebra (orders and signs are considered), which generalizes the Hyper-Pfaffian-Cactus Theorem by Abdesselam [Advances in Applied Mathematics (2004) Vol. 33: 51-70] and Pfaffian matrix tree theorem by Masbaum and Vaintrob [Internat. Math. Res. Notices (2002) Vol. 27: 1397-1426]. [ABSTRACT FROM AUTHOR]

The affine general linear group acting on a vector space over a prime field is a well-understood mathematical object. Its elementary abelian regular subgroups have recently drawn attention in applied mathematics thanks to their use in cryptography as a way to hide or detect weaknesses inside block ciphers. This paper is focused on building a convenient representation of their elements which suits better the purposes of the cryptanalyst. Several combinatorial counting formulas and a classification of their conjugacy classes are given as well. [ABSTRACT FROM AUTHOR]

This paper proposes a joint input-state estimation technique that can estimate unknown inputs, states and parameters of dynamic systems with direct feedthrough. The estimation is performed in a minimum variance unbiased manner, based on measurements from the dynamic system. This paper also presents a novel unscented minimum variance unbiased (UMVU) estimation scheme to realize the proposed estimator via unscented transform. Five UMVU variants are implemented and applied in the numerical study. The results have shown successful estimation of unknown inputs and states, and accurate identification of unknown system parameters. The characteristics and performance of the five UMVU variants are also demonstrated through the comparison of the results. [ABSTRACT FROM AUTHOR]

Abstract In Computer Vision, images of dynamic or segmented scenes are modeled as linear projections from P k to P 2. The reconstruction problem consists in recovering the position of the projected objects and the projections themselves from their images, after identifying many enough correspondences between the images. A critical locus for the reconstruction problem is a variety in P k containing the objects for which the reconstruction fails. In this paper, we deal with projections both of points from P 4 to P 2 and of lines from P 3 to P 2. In both cases, we consider 3 projections, minimal number for a uniquely determined reconstruction. In the case of projections of points, we declinate the Grassmann tensors introduced in Hartley and Schaffalitzky (2004) in our context, and we use them to compute the equations of the critical locus. Then, given the ideal that defines this locus, we prove that, in the general case, it defines a Bordiga surface, or a scheme in the same irreducible component of the associated Hilbert scheme. Furthermore, we prove that every Bordiga surface is actually the critical locus for the reconstruction for suitable projections. In the case of projections of lines, we compute the defining ideal of the critical locus, that is the union of 3 α -planes and a line congruence of bi-degree (3 , 6) and sectional genus 5 in the Grassmannian G (1 , 3) ⊂ P 5. This last surface is biregular to a Bordiga surface (Verra, 1988). We use this fact to link the two reconstruction problems by showing how to compute the projections of one of the two settings, given the projections of the other one. The link is effective, in the sense that we describe an algorithm to compute the projection matrices. [ABSTRACT FROM AUTHOR]

This paper considers fast algorithms for operations on linearized polynomials. We propose a new multiplication algorithm for skew polynomials (a generalization of linearized polynomials) which has sub-quadratic complexity in the polynomial degree s , independent of the underlying field extension degree m . We show that our multiplication algorithm is faster than all known ones when s ≤ m . Using a result by Caruso and Le Borgne (2017) , this immediately implies a sub-quadratic division algorithm for linearized polynomials for arbitrary polynomial degree s . Also, we propose algorithms with sub-quadratic complexity for the q -transform, multi-point evaluation, computing minimal subspace polynomials, and interpolation, whose implementations were at least quadratic before. Using the new fast algorithm for the q -transform, we show how matrix multiplication over a finite field can be implemented by multiplying linearized polynomials of degrees at most s = m if an elliptic normal basis of extension degree m exists, providing a lower bound on the cost of the latter problem. Finally, it is shown how the new fast operations on linearized polynomials lead to the first error and erasure decoding algorithm for Gabidulin codes with sub-quadratic complexity. [ABSTRACT FROM AUTHOR]

Abstract We study the interpolation Macdonald functions, remarkable inhomogeneous generalizations of Macdonald functions, and a sequence A 1 , A 2 , ... of commuting operators whose common eigenfunctions are the interpolation Macdonald functions. Such a sequence of operators arises in the projective limit of finite families of commuting q-difference operators studied by Okounkov, Knop and Sahi. The main theorem is an explicit formula for the operators A k. Our formula involves the family of Hall–Littlewood functions and a new family of inhomogeneous Hall–Littlewood functions, for which we give an explicit construction and identify as a degeneration of the interpolation Macdonald functions when q → 0. This article is inspired by the recent papers of Nazarov–Sklyanin on Macdonald and Sekiguchi–Debiard operators, and our main theorem is an extension of their results. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new concept of completely linear degeneracy for quasilinear hyperbolic systems in several space variables, and then get an interesting property for multidimensional hyperbolic conservation laws satisfying our new definition. For applications, we give some examples arising from mathematics and physics at last. [ABSTRACT FROM AUTHOR]

In this paper, we provide several characterizations on weak recurrence of translation operators on weighted Lebesgue spaces and on continuous function spaces. It is shown that the translation operator admits a nonzero nonwandering point if and only if it has a nonzero recurrent point, if and only if it is hypercyclic; that the translation operator admits a nonzero almost periodic point if and only if it is Devaney chaotic. Moreover, every hypercyclic translation operator has infinite topological entropy, but the converse is not true. Finally, we remark that there exists a linear operator which has the specification property on the whole space. [ABSTRACT FROM AUTHOR]

Solution sets of systems of binomial equations are of great interest in applied mathematics. For both theoretic and applied purposes, the degree of a solution set (its maximum number of isolated intersections with an affine space of complementary dimension) often plays an important role in understanding its geometric structure. This paper proposes a specialized parallel algorithm for computing the degree on GPUs that takes advantage of the massively parallel nature of GPU devices. The preliminary implementation shows remarkable efficiency and scalability when compared to the closest CPU-based counterpart. As a case study, the algorithm is applied to the master space problem of N = 1 gauge theories. The GPU-based implementation achieves nearly 30 fold speedup over its CPU-only counterpart enabling the discovery of previously unknown results. [ABSTRACT FROM AUTHOR]

Bicircular lift matroids are a class of matroids defined on the edge set of a graph. For a given graph G , the circuits of its bicircular lift matroid L ( G ) are the edge sets of those subgraphs of G that contain at least two cycles, and are minimal with respect to this property. For each cycle C of G , since L ( G ) / C is graphic and most graphic matroids are not bicircular lift, the class of bicircular lift matroids is not minor-closed. In this paper, we prove that the class of matroids that are graphic or bicircular lift has a finite list of excluded minors. [ABSTRACT FROM AUTHOR]

In this paper, we derive uniqueness and stability results for surface tensors. Further, we develop two algorithms that reconstruct shape of n -dimensional convex bodies. One algorithm requires knowledge of a finite number of surface tensors, whereas the other algorithm is based on noisy measurements of a finite number of harmonic intrinsic volumes. The derived stability results ensure consistency of the two algorithms. Examples that illustrate the feasibility of the algorithms are presented. [ABSTRACT FROM AUTHOR]

The Ish arrangement was introduced by Armstrong to give a new interpretation of the q , t -Catalan numbers of Garsia and Haiman. Armstrong and Rhoades showed that there are some striking similarities between the Shi arrangement and the Ish arrangement and posed some problems. One of them is whether the Ish arrangement is a free arrangement or not. In this paper, we verify that the Ish arrangement is supersolvable and hence free. Moreover, we give a necessary and sufficient condition for the deleted Ish arrangement to be free. [ABSTRACT FROM AUTHOR]

In this paper, we suggest approximate algorithms for the reconstruction of sparse high-dimensional trigonometric polynomials, where the support in frequency domain is unknown. Based on ideas of constructing rank-1 lattices component-by-component, we adaptively construct the index set of frequencies belonging to the non-zero Fourier coefficients in a dimension incremental way. When we restrict the search space in frequency domain to a full grid [ − N , N ] d ∩ Z d of refinement N ∈ N and assume that the cardinality of the support of the trigonometric polynomial in frequency domain is bounded by the sparsity s ∈ N , our method requires O ( d s 2 N ) samples and O ( d s 3 + d s 2 N log ⁡ ( s N ) ) arithmetic operations in the case N ≲ s ≲ N d . Moreover, we discuss possibilities to reduce the number of samples and arithmetic operations by applying methods from compressed sensing and a version of Prony's method. For the latter, the number of samples is reduced to O ( d s + d N ) and the number of arithmetic operations is O ( d s 3 ) . Various numerical examples demonstrate the efficiency of the suggested method. [ABSTRACT FROM AUTHOR]

Otsu’s method is a classic thresholding approach in image segmentation. While the two-dimensional (2D) Otsu’s method performs better than the original one in segmenting images corrupted by noise, it is sensitive to Salt&Pepper noise. In order to solve this problem, we present a robust 2D Otsu’s thresholding method in this paper. Our method builds the 2D histogram based on the image smoothed by both median and average filters, in contrast to the traditional method using averaged image only. Then the optimal threshold vector is determined with two one-dimensional searches on the two dimensions of the 2D histogram. In addition, we introduce a region post-processing step to deal with the pixels of noise and edges. Compared with the traditional 2D Otsu’s method, our method improves the robustness to Salt&Pepper noise and Gaussian noise significantly. Experimental results on both synthetic and real images validate the effectiveness of the proposed MAOTSU_2D method. [ABSTRACT FROM AUTHOR]

Given any set of six positive parameters, the number of tetrahedra, all having these values as their volume, circumradius and four face areas, is studied. We identify all parameters that determine infinitely many tetrahedra. On the other hand, we classify parameters that determine finitely many tetrahedra and find only four different upper bounds, zero, six, eight, and nine, on the numbers of tetrahedra. In each case, the upper bound is sharp in the complex domain. In this paper, the upper bounds are obtained through checking the dimensions of various quotient algebras of ideals by counting monomials. This is done by computing Groebner bases with block orders. Partitioning the parameter space into several cases, we find either the dimension or an upper bound of it for the quotient algebra in each case. From that, various upper bounds on the number of tetrahedra are obtained. To show the upper bounds are sharp, we pick rational parameters and study the number of tetrahedra through Hermite's root counting method. [ABSTRACT FROM AUTHOR]

Glioblastoma multiforme (GBM) is one of the most deadly forms of cancer. Methods of characterizing these tumours are valuable for improving predictions of their progression and response to treatment. A mathematical model called the proliferation-invasion (PI) model has been used extensively in the literature to model the growth of these tumours, though it relies on known values of two key parameters: the tumour cell diffusivity and proliferation rate. Unfortunately, these parameters are difficult to estimate in a patient-specific manner, making personalized tumour forecasting challenging. In this paper, we develop and apply a deep learning model capable of making accurate estimates of these key GBM-characterizing parameters while simultaneously producing a full prediction of the tumour progression curve. Our method uses two sets of multi sequence MRI in order to produce estimations and relies on a preprocessing pipeline which includes brain tumour segmentation and conversion to tumour cellularity. We first apply our deep learning model to synthetic tumours to showcase the model's capabilities and identify situations where prediction errors are likely to occur. We then apply our model to a clinical dataset consisting of five patients diagnosed with GBM. For all patients, we derive evidence-based estimates for each of the PI model parameters and predictions for the future progression of the tumour, along with estimates of the parameter uncertainties. Our work provides a new, easily generalizable method for the estimation of patient-specific tumour parameters, which can be built upon to aid physicians in designing personalized treatments. • Mathematical models are used to predict tumour growth and response to treatment. • Use of models in the clinic requires patient-specific tumour characterizations. • Deep learning algorithms can use MRIs to characterize tumours and inform models. • Deep learning characterization models show advantages over traditional methods. [ABSTRACT FROM AUTHOR]

Multivariate piecewise polynomial functions (or splines) on polyhedral complexes have been extensively studied over the past decades and find applications in diverse areas of applied mathematics including numerical analysis, approximation theory, and computer aided geometric design. In this paper we address various challenges arising in the study of splines with enhanced mixed (super-)smoothness conditions at the vertices and across interior faces of the partition. Such supersmoothness can be imposed but can also appear unexpectedly on certain splines depending on the geometry of the underlying polyhedral partition. Using algebraic tools, a generalization of the Billera–Schenck–Stillman complex that includes the effect of additional smoothness constraints leads to a construction which requires the analysis of ideals generated by products of powers of linear forms in several variables. Specializing to the case of planar triangulations, a combinatorial lower bound on the dimension of splines with supersmoothness at the vertices is presented, and we also show that this lower bound gives the exact dimension in high degree. The methods are further illustrated with several examples. [ABSTRACT FROM AUTHOR]

In this paper, we recover sparse signals from their noisy linear measurements by solving nonlinear differential inclusions, which is based on the notion of inverse scale space (ISS) developed in applied mathematics. Our goal here is to bring this idea to address a challenging problem in statistics, i.e. finding the oracle estimator which is unbiased and sign consistent using dynamics. We call our dynamics Bregman ISS and Linearized Bregman ISS . A well-known shortcoming of LASSO and any convex regularization approaches lies in the bias of estimators. However, we show that under proper conditions, there exists a bias-free and sign-consistent point on the solution paths of such dynamics, which corresponds to a signal that is the unbiased estimate of the true signal and whose entries have the same signs as those of the true signs, i.e. the oracle estimator. Therefore, their solution paths are regularization paths better than the LASSO regularization path, since the points on the latter path are biased when sign-consistency is reached. We also show how to efficiently compute their solution paths in both continuous and discretized settings: the full solution paths can be exactly computed piece by piece, and a discretization leads to Linearized Bregman iteration , which is a simple iterative thresholding rule and easy to parallelize. Theoretical guarantees such as sign-consistency and minimax optimal l 2 -error bounds are established in both continuous and discrete settings for specific points on the paths. Early-stopping rules for identifying these points are given. The key treatment relies on the development of differential inequalities for differential inclusions and their discretizations, which extends the previous results and leads to exponentially fast recovering of sparse signals before selecting wrong ones. [ABSTRACT FROM AUTHOR]

Blade loss from a running turbofan rotor will introduce sudden unbalance into the dynamical system, and as a consequence leads to the rub-impact, the asymmetry of rotor and a series of interesting dynamic characteristics. The paper focuses on the theoretical study on the sudden unbalance and rub-impact caused by blade loss, in particular investigates the response of the rotor on a rotor test rig with sudden unbalance and rub-impact device designed respectively. The results reveal that the sudden unbalance will induce impact effect on the rotor, and critical speed frequency is excited in frequency spectrum. Meantime, the impact effect is more obvious for the rotor operating above critical speed. The influence of rub-impact is considered as additional constraint to the rotor, analyzed by the theory of time-varying system for the first time, and the results are evaluated by experimental tests. The study shows that great attention should be paid to the dynamical design for the overhung rotor system, additional constraint and corresponding analysis method in rub-impact need to be intensively studied. [ABSTRACT FROM AUTHOR]

In this paper, I present an analytical framework for polymorphic evolutionary games suitable for explicitly modeling evolutionary processes in diploid populations with sexual reproduction. The principal aspect of the proposed approach is adding diploid genetics cum sexual recombination to a traditional evolutionary game, and switching from phenotypes to haplotypes as the new game׳s pure strategies. Here, the relevant pure strategy׳s payoffs derived by summing the payoffs of all the phenotypes capable of producing gametes containing that particular haplotype weighted by the pertinent probabilities. The resulting game is structurally identical to the familiar Evolutionary Games with non-linear pure strategy payoffs ( Hofbauer and Sigmund, 1998 . Cambridge University Press), and can be analyzed in terms of an established analytical framework for such games. And these results can be translated into the terms of genotypic, and whence, phenotypic evolutionary stability pertinent to the original game. [ABSTRACT FROM AUTHOR]

An edge-colored graph H is called rainbow if e ( H ) = c ( H ) , where e ( H ) and c ( H ) are the number of edges of H and colors used in H , respectively. For two graphs G and H , the rainbow number r b ( G , H ) is the minimum number of colors k such that for every edge-coloring of G using k colors, G contains a rainbow H . In this paper we prove that for an edge-colored graph G on n vertices with n ≥ k ≥ 4 , if e ( G ) + c ( G ) ≥ ( n 2 ) + t n , k − 2 + 2 , then G contains a rainbow clique K k , where t n , k − 2 is the Turán number. This implies the known result r b ( K n , K k ) = t n , k − 2 + 2 , and moreover, r b ( G , K k ) ≤ e ( G ¯ ) + r b ( K n , K k ) for n ≥ k ≥ 4 . [ABSTRACT FROM AUTHOR]

This paper studies the problem of line spectral estimation in the continuum of a bounded interval with one snapshot of array measurement. The single-snapshot measurement data are turned into a Hankel data matrix which admits the Vandermonde decomposition and is suitable for the MUSIC algorithm. The MUSIC algorithm amounts to finding the null space (the noise space) of the adjoint of the Hankel matrix, forming the noise-space correlation function and identifying the s smallest local minima of the noise-space correlation as the frequency set. In the noise-free case exact reconstruction is guaranteed for any arbitrary set of frequencies as long as the number of measurement data is at least twice the number of distinct frequencies to be recovered. In the presence of noise the stability analysis shows that the perturbation of the noise-space correlation is proportional to the spectral norm of the noise matrix as long as the latter is smaller than the smallest (nonzero) singular value of the noiseless Hankel data matrix. Under the assumption that the true frequencies are separated by at least twice the Rayleigh Length (RL), the stability of the noise-space correlation is proved by means of novel discrete Ingham inequalities which provide bounds on the largest and smallest nonzero singular values of the noiseless Hankel data matrix. The numerical performance of MUSIC is tested in comparison with other algorithms such as BLO-OMP and SDP (TV-min). While BLO-OMP is the stablest algorithm for frequencies separated above 4 RL, MUSIC becomes the best performing one for frequencies separated between 2 RL and 3 RL. Also, MUSIC is more efficient than other methods. MUSIC truly shines when the frequency separation drops to 1 RL or below when all other methods fail. Indeed, the resolution length of MUSIC decreases to zero as noise decreases to zero as a power law with an exponent smaller than an upper bound established by Donoho. [ABSTRACT FROM AUTHOR]

We investigate the dynamics and transitions to extinction of hypercycles governed by periodic orbits. For a large enough number of hypercycle species ( n > 4 ) the existence of a stable periodic orbit has been previously described, showing an apparent coincidence of the vanishing of the periodic orbit with the value of the replication quality factor Q where two unstable (non-zero) equilibrium points collide (named Q SS ). It has also been reported that, for values below Q SS , the system goes to extinction. In this paper, we use a suitable Poincaré map associated to the hypercycle system to analyze the dynamics in the bistability regime, where both oscillatory dynamics and extinction are possible. The stable periodic orbit is identified, together with an unstable periodic orbit. In particular, we are able to unveil the vanishing mechanism of the oscillatory dynamics: a saddle-node bifurcation of periodic orbits as the replication quality factor, Q , undergoes a critical fidelity threshold, Q PO . The identified bifurcation involves the asymptotic extinction of all hypercycle members, since the attractor placed at the origin becomes globally stable for values Q < Q PO . Near the bifurcation, these extinction dynamics display a periodic remnant that provides the system with an oscillating delayed transition. Surprisingly, we found that the value of Q PO is slightly higher than Q SS , thus identifying a gap in the parameter space where the oscillatory dynamics has vanished while the unstable equilibrium points are still present. We also identified a degenerate bifurcation of the unstable periodic orbits for Q =1. [ABSTRACT FROM AUTHOR]

The theory of compressed sensing shows that it is highly possible to recover a sparse signal from few measurements. Due to its wide applications, compressed sensing has drawn attention of many researchers from the fields of signal and image processing, applied mathematics, and statistics. In this paper we are interested in signals which are sparse under redundant tight frames. Some sufficient conditions are provided to guarantee the stable recovery via solving analysis based approaches. Compared with the previous work [12,16] , our sufficient conditions are weaker and the estimations of l 2 bound only depend on the measurement matrix. [ABSTRACT FROM AUTHOR]

The mathematical theory of rigidity of body-bar and body-hinge frameworks provides a useful tool for analyzing the rigidity and flexibility of many articulated structures appearing in engineering, robotics and biochemistry. In this paper we develop a symmetric extension of this theory which permits a rigidity analysis of body-bar and body-hinge structures with point group symmetries. The infinitesimal rigidity of body-bar frameworks can naturally be formulated in the language of the exterior (or Grassmann) algebra. Using this algebraic formulation, we derive symmetry-adapted rigidity matrices to analyze the infinitesimal rigidity of body-bar frameworks with Abelian point group symmetries in an arbitrary dimension. In particular, from the patterns of these new matrices, we derive combinatorial characterizations of infinitesimally rigid body-bar frameworks which are generic with respect to a point group of the form Z / 2Z ×⋯×Z / 2Z. Our characterizations are given in terms of packings of bases of signed-graphic matroids on quotient graphs. Finally, we also extend our methods and results to body-hinge frameworks with Abelian point group symmetries in an arbitrary dimension. [ABSTRACT FROM AUTHOR]

This paper deals with a sub-class of recreational problems which are solved by a simple memorized rule resulting from an elementary arithmetical or algebraic solution, called proto-algebraic rules. Their recreational aspect is derived from a surprise or trick solution which is not immediately obvious to the subjects involved. Around 1560 many such problems wane from arithmetic and algebra textbooks to reappear in the eighteenth century. Several hypotheses are investigated why popular Renaissance recreational problems lost their appeal. We arrive at the conclusion that the emergence of algebra as a general problem solving method changed the scope of what is considered recreational in mathematics. [ABSTRACT FROM AUTHOR]