Two proofs of the Bermond-Thomassen conjecture for tournaments with bounded minimum in-degree

The Bermond-Thomassen conjecture states that, for any positive integer r, a digraph of minimum out-degree at least 2r−1 contains at least r vertex-disjoint directed cycles. Thomassen proved that it is true when r=2, and very recently the conjecture was proved for the case where r=3. It is still open for larger values of r, even when restricted to (regular) tournaments. In this paper, we present two proofs of this conjecture for tournaments with minimum in-degree at least 2r−1. In particular, this shows that the conjecture is true for (almost) regular tournaments. In the first proof, we prove auxiliary results about union of sets contained in another union of sets, that might be of independent interest. The second one uses a more graph-theoretical approach, by studying the properties of a maximum set of vertex-disjoint directed triangles.     

具有相交性质的近小扭转映射的不变环面的保持性

In this paper we investigate the nearly small twist mappings with intersection property. With a certain non-degenerate condition, we proved that the most of invariant tori of the original small twist mappings will survive afer small perturtations. The persisted invariant tori are close to the unperturbed ones when the perturbation are small. The orbits reduced by those mappings are quasi-periodic in the invariant tori with the frequences closing to the original ones.     

The ratio of the numbers of odd and even cycles in outerplanar graphs

In this paper, we investigate the ratio of the numbers of odd and even cycles in outerplanar graphs. We verify that the ratio generally diverges to infinity as the order of a graph diverges to infinity. We also give sharp estimations of the ratio for several classes of outerplanar graphs, and obtain a constant upper bound of the ratio for some of them. Furthermore, we consider similar problems in graphs with some pairs of forbidden subgraphs/minors, and propose a challenging problem concerning claw-free graphs.     

Intersections of q-ary perfect codes

The intersections of q-ary perfect codes are under study. We prove that there exist two q-ary perfect codes C ₁ and C ₂ of length N = qn + 1 such that |C ₁ ? C ₂| = k · |P _i |/p for each k ∈ {0,..., p · K ? 2, p · K}, where q = p ^r , p is prime, r ≥ 1, $n = \tfrac{{q^{m - 1} - 1}}{{q - 1}}$ , m ≥ 2, |P _i | = p ^nr(q?2)+n , and K = p ^{n(2r?1)?r(m?1)}. We show also that there exist two q-ary perfect codes of length N which are intersected by p ^nr(q?3)+n codewords.     

Topology of complete intersections

Let X _n (d) and X _n (d') be two n-dimensional complete intersections with the same total degree d. In this paper we prove that, if n is even and d has no prime factors less than , then X _n (d) and X _n (d') are homotopy equivalent if and only if they have the same Euler characteristics and signatures. This confirms a conjecture of Libgober and Wood [16]. Furthermore, we prove that, if d has no prime factors less than , then X _n (d) and X _n (d') are homeomorphic if and only if their Pontryagin classes and Euler characteristics agree. Received: September 6, 1996     

综合国力的数学建模

本文考虑社会文明与社会导恶现象的制约机制，建立一个综合国力的非线性数学模型，从数学上讨论了相应的二次微分系统的Ｈｏｐｆ分叉，中心与细焦点的判定，极限环的存在唯一性等问题，并对数学结论予以合理解释，把社会相平面划成社发展区域，社会动荡区域和社会崩溃区域，研讨社会走向，确定纳入社会发展区域的途径。     

Quadrilateral surface meshes without self-intersecting dual cycles for hexahedral mesh generation

Several promising approaches for hexahedral mesh generation work as follows: Given a prescribed quadrilateral surface mesh they first build the combinatorial dual of the hexahedral mesh. This dual mesh is converted into the primal hexahedral mesh, and finally embedded and smoothed into the given domain. Two such approaches, the modified whisker weaving algorithm by Folwell and Mitchell, as well as a method proposed by the author, rely on an iterative elimination of certain dual cycles in the surface mesh. An intuitive interpretation of the latter method is that cycle eliminations correspond to complete sheets of hexahedra in the volume mesh.

Although these methods can be shown to work in principle, the quality of the generated meshes heavily relies on the dual cycle structure of the given surface mesh. In particular, it seems that difficulties in the hexahedral meshing process and poor mesh qualities are often due to self-intersecting dual cycles. Unfortunately, all previous work on quadrilateral surface mesh generation has focused on quality issues of the surface mesh alone but has disregarded its suitability for a high-quality extension to a three-dimensional mesh.

In this paper, we develop a new method to generate quadrilateral surface meshes without self-intersecting dual cycles. This method reuses previous b-matching problem formulations of the quadrilateral mesh refinement problem. The key insight is that the b-matching solution can be decomposed into a collection of simple cycles and paths of multiplicity two, and that these cycles and paths can be consistently embedded into the dual surface mesh.

A second tool uses recursive splitting of components into simpler subcomponents by insertion of internal two-manifolds. We show that such a two-manifold can be meshed with quadrilaterals such that the induced dual cycle structure of each subcomponent is free of self-intersections if the original component satisfies this property. Experiments show that we can achieve hexahedral meshes with a good quality.     

Higher Intersection Theory on Algebraic Stacks: II

This is the second part of our work on the intersection theory of algebraic stacks. The main results here are the following. We provide an intersection pairing for all smooth Artin stacks (locally of finite type over a field) which we show reduces to the known intersection pairing on the Chow groups of smooth Deligne–Mumford stacks of finite type over a field as well as on the Chow groups of quotient stacks associated to actions of linear algebraic groups on smooth quasi-projective schemes modulo torsion. The former involves also showing the existence of Adams operations on the rational étale K-theory of all smooth Deligne–Mumford stacks of finite type over a field. In addition, we show that our definition of the higher Chow groups is intrinsic to the stack for all smooth stacks and also stacks of finite type over the given field. Next we establish the existence of Chern classes and Chern character for Artin stacks with values in our Chow groups and extend these to higher Chern classes and a higher Chern character for perfect complexes on an algebraic stack, taking values in cohomology theories of algebraic stacks that are defined with respect to complexes of sheaves on a big smooth site. As a by-product of our techniques we also provide an extension of higher intersection theory to all schemes locally of finite type over a field. As the higher cycle complex, by itself, is a bit difficult to handle, the stronger results like contravariance for arbitrary maps between smooth stacks and the intersection pairing for smooth stacks are established by comparison with motivic cohomology.     

拓扑空间中的一个非空交定理及其应用

在FC-空间中证明了一新的非空交定理．作为应用,一不动点定理,一极大元定理,一重合点定理和一些极小极大不等式被证明．这些定理推广了近期文献中的结果．     

On the Hardness of Computing Intersection,Union and Minkowski Sum of Polytopes

For polytopes P ₁,P ₂⊂ℝ ^d , we consider the intersection P ₁∩P ₂, the convex hull of the union CH(P ₁∪P ₂), and the Minkowski sum P ₁+P ₂. For the Minkowski sum, we prove that enumerating the facets of P ₁+P ₂ is NP-hard if P ₁ and P ₂ are specified by facets, or if P ₁ is specified by vertices and P ₂ is a polyhedral cone specified by facets. For the intersection, we prove that computing the facets or the vertices of the intersection of two polytopes is NP-hard if one of them is given by vertices and the other by facets. Also, computing the vertices of the intersection of two polytopes given by vertices is shown to be NP-hard. Analogous results for computing the convex hull of the union of two polytopes follow from polar duality. All of the hardness results are established by showing that the appropriate decision version, for each of these problems, is NP-complete.