A note on: “Relaxation oscillators with exact limit cycles”

In this note we give a family of planar polynomial differential systems with a prescribed hyperbolic limit cycle. This family constitutes a corrected and wider version of an example given in the work [M.A. Abdelkader, Relaxation oscillators with exact limit cycles, J. Math. Anal. Appl. 218 (1998) 308-312]. The result given in this note may be used to construct models of Liénard differential equations exhibiting a desired limit cycle.     

Alexander polynomials of doubly primitive knots

We give a formula for Alexander polynomials of doubly primitive knots. This also gives a practical algorithm to determine the genus of any doubly primitive knot.

     

Stochastic Hopf bifurcation and chaos of stochastic Bonhoeffer–van der Pol system via Chebyshev polynomial approximation

In this paper, we analyzed stochastic chaos and Hopf bifurcation of stochastic Bonhoeffer–van der Pol (SBVP for short) system with bounded random parameter of an arch-like probability density function. The modifier ‘stochastic’ here implies dependent on some random parameter. In order to study the dynamical behavior of the SBVP system, Chebyshev polynomial approximation is applied to transform the SBVP system into its equivalent deterministic system, whose response can be readily obtained by conventional numerical methods. Thus, we can further explore the nonlinear phenomena in SBVP system. Stochastic chaos and Hopf bifurcation analyzed here are by and large similar to those in the deterministic mean-parameter Bonhoeffer–van der Pol system (DM–BVP for short) but there are also some featuring differences between them shown by numerical results. For example, in the SBVP system the parameter interval matching chaotic responses diffuses into a wider one, which further grows wider with increasing of intensity of the random variable. The shapes of limit cycles in the SBVP system are some different from that in the DM–BVP system, and the sizes of limit cycles become smaller with the increasing of intensity of the random variable. And some biological explanations are given.     

Balanced optimization problems

Suppose we are given a finite set E, a family F of ‘feasible’ subsets of E and a real weight c(e) associated with every e?E. We consider the problem of finding S?F for which max {c(e)?c(e′): e, e′ ?S} is minimized. In other words, the differenc value between the largest and smallest value used should be as small as possible. We show that if we can efficiently answer the feasibility question then we can efficiently solve the optimization problem. We specialize these results to assignment problems and thereby obtain on O(n⁴) algorithm for ‘balanced’ assignment problems.     

Index of lattices and Hilbert polynomials

An upper bound for the index of a sublattice, which arises in relation to various versions of zero lemmas in the theory of linear forms in logarithms of algebraic numbers, in terms of the Hilbert polynomial is found. Simultaneously, a lower bound for the values of this polynomial is obtained.     

On the enumeration of certain weighted graphs

We enumerate weighted simple graphs with a natural upper bound condition on the sum of the weight of adjacent vertices. We also compute the generating function of the numbers of these graphs, and prove that it is a rational function. In particular, we show that the generating function for connected bipartite simple graphs is of the form p₁(x)/(1-x)^m+1. For nonbipartite simple graphs, we get a generating function of the form p₂(x)/(1-x)^m+1(1+x)^l. Here m is the number of vertices of the graph, p₁(x) is a symmetric polynomial of degree at most m, p₂(x) is a polynomial of degree at most m+l, and l is a nonnegative integer. In addition, we give computational results for various graphs.     

关于微分多项式零点的注记

The value distribution of differential polynomials is studied.The re- suits in this paper improve and generalize some previous theorems given by Yang Chungchun(On deficiencies of differential polynomials,Math.Z.,116(1970),197- 204),H.S.Gopalakrishna and S.S.Bhoosnurmath(On distribution of values of differential polynomials,Indian J.Pure Appl.Math.,17(1986),367-372),I.Lahiri (A note on distribution of nonhomogeneous differential polynomials,Hokkaido Math. J.,31(2002),453-458)and Yi Hongxun(On zeros of differential polynomials,Adv. in Math.,18(1989),335-351)et al.Examples show that the results in this paper are sharp.     

Note on maximal split-stable subgraphs

A multigraph G=(V,R∪B) with red and blue edges is an R/B-split graph if V is the union of a red and a blue stable set. Gavril has shown that R/B-split graphs yield a common generalization of split graphs and König-Egerváry graphs. Moreover, R/B-split graphs can be recognized in linear time. In this note, we address the corresponding optimization problem: identify a set of vertices of maximal cardinality that decomposes into a red and a blue stable set. This problem is NP-hard in general. We investigate the complexity of special and related cases (e.g., (anti-)chains in partial orders and stable matroid bases) and exhibit some NP-hard cases as well as polynomial ones.     

Two algorithms for weighted matroid intersection

Consider a finite setE, a weight functionw:E→R, and two matroidsM ₁ andM ₂ defined onE. The weighted matroid intersection problem consists of finding a setI⊆E, independent in both matroids, that maximizes Σ{w(e):e inI}. We present an algorithm of complexity O(nr(r+c+logn)) for this problem, wheren=|E|,r=min(rank(M ₁), rank (M ₂)),c=max (c ₁,c ₂) and, fori=1,2,c _i is the complexity of finding the circuit ofI∪{e} inM _i (or show that none exists) wheree is inE andI⊆E is independent inM ₁ andM ₂. A related problem is to find a maximum weight set, independent in both matroids, and of given cardinalityk (if one exists). Our algorithm also solves this problem. In addition, we present a second algorithm that, given a feasible solution of cardinalityk, finds an optimal one of the same cardinality. A sensitivity analysis on the weights is easy to perform using this approach. Our two algorithms are related to existing algorithms. In fact, our framework provides new simple proofs of their validity. Other contributions of this paper are the existence of nonnegative reduced weights (Theorem 6), allowing the improved complexity bound, and the introduction of artificial elements, allowing an improved start and flexibility in the implementation of the algorithms. This research was supported in part by NSF grant ECS 8503192 to Carnegie-Mellon University.     

Postponing the choice of the barrier parameter in Mehrotra-type predictor–corrector algorithms

Recently Salahi et al. have considered a variant of Mehrotra’s celebrated predictor–corrector algorithm. By a numerical example they showed that this variant might make very small steps in order to keep the iterate in a certain neighborhood of the central path, that itself implies the inefficiency of the algorithm. This observation motivated them to incorporate a safeguard in their algorithmic scheme that gives a lower bound for the step size at each iteration and thus imply polynomial iteration complexity. In this paper we propose a different approach that enables us to have control on the iterates.