On the number of zeros of Abelian integrals for a polynomial Hamiltonian irregular at infinity

Up to now, most of the results on the tangential Hilbert 16th problem have been concerned with the Hamiltonian regular at infinity, i.e., its principal homogeneous part is a product of the pairwise different linear forms. In this paper, we study a polynomial Hamiltonian which is not regular at infinity. It is shown that the space of Abelian integral for this Hamiltonian is finitely generated as a R[h] module by several basic integrals which satisfy the Picard-Fuchs system of linear differential equations. Applying the bound meandering principle, an upper bound for the number of complex isolated zeros of Abelian integrals is obtained on a positive distance from critical locus. This result is a partial solution of tangential Hilbert 16th problem for this Hamiltonian. As a consequence, we get an upper bound of the number of limit cycles produced by the period annulus of the non-Hamiltonian integrable quadratic systems whose almost all orbits are algebraic curves of degree k+n, under polynomial perturbation of arbitrary degree.     

Abelian and Hamiltonian groupoids

In this work, we investigate some groupoids that are Abelian algebras and Hamiltonian algebras. An algebra is Abelian if for every polynomial operation and for all elements a, b, [`(c)] \bar{c} , [`(d)] \bar{d} the implication t( a,[`(c)] ) = t( a,[`(d)] ) T t( b,[`(c)] ) = t( b,[`(d)] ) t\left( {a,\bar{c}} \right) = t\left( {a,\bar{d}} \right) \Rightarrow t\left( {b,\bar{c}} \right) = t\left( {b,\bar{d}} \right) holds. An algebra is Hamiltonian if every subalgebra is a block of some congruence on the algebra. R. J. Warne in 1994 described the structure of the Abelian semigroups. In this work, we describe the Abelian groupoids with identity, the Abelian finite quasigroups, and the Abelian semigroups S such that abS = aS and Sba = Sa for all a, b ∈ S. We prove that a finite Abelian quasigroup is a Hamiltonian algebra. We characterize the Hamiltonian groupoids with identity and semigroups under the condition of Abelianity of these algebras.     

The cluster deletion problem for cographs

The min-edge clique partition problem asks to find a partition of the vertices of a graph into a set of cliques with the fewest edges between cliques. This is a known NP-complete problem and has been studied extensively in the scope of fixed-parameter tractability (FPT) where it is commonly known as the Cluster Deletion problem. Many of the recently-developed FPT algorithms rely on being able to solve Cluster Deletion in polynomial time on restricted graph structures.     

Characterization of the generic unfolding of a weak focus

In this paper we prove that the orbital class of a generic real analytic family unfolding a weak focus is determined by the conjugacy class of its Poincaré monodromy and vice versa. We solve the embedding problem by means of quasiconformal surgery on the formal normal form. The surgery yields an integrable abstract almost complex 2-manifold equipped with an elliptic foliation. The monodromy of the latter coincides with the second iterate of a germ of prescribed family of real analytic diffeomorphisms undergoing a flip bifurcation.     

Monodromy Groups and Bilinear Monodromy Invariant Combinations of Generalized Hypergeometric Type Integrals

The problem of determining bilinear combinations of holomorphic and antiholomorphic generalized hypergeometric type integrals left invariant under the action of the monodromy groups of the integrals is studied. In the special cases of simple Pochhammer type integrals and of twofold hypergeometric type integrals the existence and uniqueness of the bilinear invariants are proved, and the bilinear invariants are explicitly computed. Preparing the tools it is shown how to linearize and iterate representations of the braid group B_n as automorphism groups of certain free subgroups of the braid group B_n+1, and how the resulting iterated linear representations of the braid group in a natural way provide an algorithm to compute the monodromy group of generalized hypergeometric type integrals. Explicit formulae for different types of integration contours are given in the case of simple and twofold integrals.     

Abelian and Hamiltonian varieties of groupoids

We study certain groupoids generating Abelian, strongly Abelian, and Hamiltonian varieties. An algebra is Abelian if t( a,[`(c)] ) = t( a,[`(d)] ) ? t( b,[`(c)] ) = t( b,[`(d)] ) t\left( {a,\bar{c}} \right) = t\left( {a,\bar{d}} \right) \to t\left( {b,\bar{c}} \right) = t\left( {b,\bar{d}} \right) for any polynomial operation on the algebra and for all elements a, b, [`(c)] \bar{c} , [`(d)] \bar{d} . An algebra is strongly Abelian if t( a,[`(c)] ) = t( b,[`(d)] ) ? t( e,[`(c)] ) = t( e,[`(d)] ) t\left( {a,\bar{c}} \right) = t\left( {b,\bar{d}} \right) \to t\left( {e,\bar{c}} \right) = t\left( {e,\bar{d}} \right) for any polynomial operation on the algebra and for arbitrary elements a, b, e, [`(c)] \bar{c} , [`(d)] \bar{d} . An algebra is Hamiltonian if any subalgebra of the algebra is a congruence class. A variety is Abelian (strongly Abelian, Hamiltonian) if all algebras in a respective class are Abelian (strongly Abelian, Hamiltonian). We describe semigroups, groupoids with unity, and quasigroups generating Abelian, strongly Abelian, and Hamiltonian varieties.     

Nonintegrability of the Painlevé IV equation in the Liouville–Arnold sense and Stokes phenomena

In this paper we study the integrability of the Hamiltonian system associated with the fourth Painlevé equation. We prove that one two-parametric family of this Hamiltonian system is not integrable in the sense of the Liouville–Arnold theorem. Computing explicitly the Stokes matrices and the formal invariants of the second variational equations, we deduce that the connected component of the unit element of the corresponding differential Galois group is not Abelian. Thus the Morales–Ramis–Simó theory leads to a nonintegrable result. Moreover, combining the new result with our previous one we establish that for all values of the parameters for which the $P_{IV}$ equation has a particular rational solution the corresponding Hamiltonian system is not integrable by meromorphic first integrals which are rational in t.     

Generalized fibonacci cubes are mostly hamiltonian

The Hamiltonian problem is to determine whether a graph contains a spanning (Hamiltonian) path or cycle. Here we study the Hamiltonian problem for the generalized Fibonacci cubes, which are a new family of graphs that have applications in interconnection topologies [J. Liuand W.-J. Hsu, ?Distributed Algorithms for Shortest-Path, Deadlock-Free Routing and Broadcasting in a Class of Interconnection Topologies,”? International Parallel Processing Symposium (1992)]. We show that each member of this family contains a Hamiltonian path. Furthermore, we also characterize the members of this family that contain a Hamiltonian cycle.     

On the nontrivial projection problem

The nontrivial projection problem asks whether every finite-dimensional normed space admits a well-bounded projection of nontrivial rank and corank or, equivalently, whether every centrally symmetric convex body (of arbitrary dimension) is approximately affinely equivalent to a direct product of two bodies of nontrivial dimensions. We show that this is true “up to a logarithmic factor.”     

The structure of Ext(A, Z) and GCH: possible co-Moore spaces

We investigate what can be when A is torsion-free and . We thereby give an answer to a question of Golasiński and Gon?alves which asks for the divisible Abelian groups which can be the type of a co-Moore space. Received: 25 January 2000; in final form: 20 June 2000 / Published online: 25 June 2001     

Integrals in involution for groups of linear symplectic transformations and natural mechanical systems with homogeneous potential

We prove that if a complex Hamiltonian system withn degrees of freedom hasn functionally independent meromorphic first integrals in involution and the monodromy group of the corresponding variational system along some phase curve hasn pairwise skew-orthogonal two-dimensional invariant subspaces, then the restriction of the action of this group to each to these subspaces has a rational first integral. The result thus obtained is applied to natural mechanical systems with homogeneous potential, in particular, to then-body problem. Supported by the program “Leading Scientific Schools,” RFBR grant No. 00-15-96146. Institute of Radiotechnics and Electronics, Russian Academy of Sciences. Translated from Funktsional'nyi Analiz i Ego Prilozheniya, Vol. 34, No. 3, pp. 26–36, July–September, 2000. Translated by A. I. Shtern     

The timetable constrained distance minimization problem

We define the timetable constrained distance minimization problem (TCDMP) which is a sports scheduling problem applicable for tournaments where the total travel distance must be minimized. The problem consists of finding an optimal home-away assignment when the opponents of each team in each time slot are given. We present an integer programming, a constraint programming formulation and describe two alternative solution methods: a hybrid integer programming/constraint programming approach and a branch and price algorithm. We test all four solution methods on benchmark problems and compare the performance. Furthermore, we present a new heuristic solution method called the circular traveling salesman approach (CTSA) for solving the traveling tournament problem. The solution method is able to obtain high quality solutions almost instantaneously, and by applying the TCDMP, we show how the solutions can be further improved.     

A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem

In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation of the minimum-adjacency vertex coloring problem which, given an interference graph $G$ representing the potential interference between the antennas and a set of prespecified colors/channels, asks for a vertex coloring of $G$ minimizing the number of edges receiving adjacent colors. We propose an integer programming model for this problem and present three families of facet-inducing valid inequalities. Based on these results, we implement a branch-and-cut algorithm for this problem, and we provide promising computational results.     

Hamiltonian paths in Cayley graphs

The classical question raised by Lovász asks whether every Cayley graph is Hamiltonian. We present a short survey of various results in that direction and make some additional observations. In particular, we prove that every finite group G has a generating set of size at most log₂|G|, such that the corresponding Cayley graph contains a Hamiltonian cycle. We also present an explicit construction of 3-regular Hamiltonian expanders.     

A new branch-and-cut algorithm for the capacitated vehicle routing problem

We present a new branch-and-cut algorithm for the capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed capacity, generalized capacity, strengthened comb, multistar, partial multistar, extended hypotour inequalities, and classical Gomory mixed-integer cuts. For each of these classes of inequalities we describe our separation algorithms in detail. Also we describe the other important ingredients of our branch-and-cut algorithm, such as the branching rules, the node selection strategy, and the cut pool management. Computational results, for a large number of instances, show that the new algorithm is competitive. In particular, we solve three instances (B-n50-k8, B-n66-k9 and B-n78-k10) of Augerat to optimality for the first time.     

Integrability of Hamiltonian systems and transseries expansions

This paper studies analytic Liouville-nonintegrable and C ^??-Liouville-integrable Hamiltonian systems with two degrees of freedom. We prove the property for a class of Hamiltonians more general than the one studied in Gorni and Zampieri (Differ Geom Appl 22:287?C296, 2005). We also show that a certain monodromy property of an ordinary differential equation obtained as a subsystem of a given Hamiltonian and the transseries expansion of a first integral play an important role in the analysis (cf. (4)). In the former half the analytic Liouville-nonintegrability for a class of Hamiltonians satisfying the above condition is shown. For these analytic nonintegrable Hamiltonians one cannot construct nonanalytic first integrals concretely as in Gorni and Zampieri (Differ Geom Appl 22:287?C296, 2005). In the latter half, the nonanalytic integrability from the viewpoint of a transseries expansion of a first integral is discussed. More precisely, we construct a first integral in a formal transseries expansion in a general situation. Then we show convergence of transseries or existence of the first integral being asymptotically equal to a given formal transseries solution.     

Vassiliev invariants and finite-dimensional approximations of the euler equation in magnetohydrodynamics

We consider Hamiltonian systems that correspond to Vassiliev invariants defined by Chen’s iterated integrals of logarithmic differential forms. We show that Hamiltonian systems generated by first-order Vassiliev invariants are related to the classical problem of motion of vortices on the plane. Using second-order Vassiliev invariants, we construct perturbations of Hamiltonian systems for the classical problem of n vortices on the plane. We study some dynamical properties of these systems.