On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.     

Large Discrepancy In Homogenous Quasi-Arithmetic Progressions

We prove that the class of homogeneous quasi-arithmetic progressions has unbounded discrepancy. That is, we show that given any 2-coloring of the natural numbers and any positive integer D, one can find a real number α≥1 and a set of natural numbers of the form {0, [α], [2α], [3α], . . . , [kα]} so that one color appears at least D times more than the other color. This was already proved by Beck in 1983, but the proof given here is somewhat simpler and gives a better bound on the discrepancy.     

An Enumerative Geometry for Magic and Magilatin Labellings

A magic labelling of a set system is a labelling of its points by distinct positive integers so that every set of the system has the same sum, the magic sum. Examples are magic squares (the sets are the rows, columns, and diagonals) and semimagic squares (the same, but without the diagonals). A magilatin labelling is like a magic labelling but the values need be distinct only within each set. We show that the number of n × n magic or magilatin labellings is a quasipolynomial function of the magic sum, and also of an upper bound on the entries in the square. Our results differ from previous ones because we require that the entries in the square all be different from each other, and because we derive our results not by ad hoc reasoning but from a general theory of counting lattice points in rational inside-out polytopes. We also generalize from set systems to rational linear forms. Dedicated to the memory of Claudia Zaslavsky, 1917–2006 Received August 10, 2005     

条件愈苦,意志愈坚 --记王淦昌早年的科研活动

文章介绍了中国物理学家王淦昌早期的科研工作，特别是在抗日战争时期的科研成绩．王淦昌早期的科研贡献并不是在先进的实验仪器上，在条件优裕的实验室内完成的，而是在实验设备缺乏，科学文献不足等极端困难的环境中完成的．从王淦昌身上，可以看到那个时代中国优秀科学家脚踏实地、执志若金的奋斗精神．     

On the structure of finite coverings of compact connected groups

Finite-sheeted covering mappings onto compact connected groups are studied. We show that for a covering mapping from a connected Hausdorff topological space onto a compact (in general, non-abelian) group there exists a topological group structure on the covering space such that the mapping becomes a homomorphism of groups. To prove this fact we construct an inverse system of covering mappings onto Lie groups which approximates the given covering mapping. As an application, it is shown that a covering mapping onto a compact connected abelian group G must be a homeomorphism provided that the character group of G admits division by degree of the mapping. We also get a criterion for triviality of coverings in terms of means and prove that each finite covering of G is equivalent to a polynomial covering.     

TRANILAST ^1H^13CNMR谱分析及其结构的鉴定

本文用COSY,CHCOR等二维核磁共振技术对TRANILAST,2[]3-(3.4-二甲基苯基)1-氧代-2-丙烯基]氨基]苯甲到进行了~1H、~(13)C NMR谱数据分析及归属,并结合~(13)C弛豫时间T_1 及变温实验对合成产品进行了结构鉴定.     

A study of the effect of ZrO2 on the magnetic properties of FePt/ZrO2 multilayer

Fe_xPt_100−x(30 nm) and [Fe_xPt_100−x(3 nm)/ZrO₂]₁₀ (x = 37, 48, 57, 63, 69) films with different ZrO₂ content were prepared by RF magnetron sputtering technique, then were annealed at 550 °C for 30 min. This work investigates the effect of ZrO₂ doping on the microstructural evolution, magnetic properties, grain size, as well as the ordering kinetics of FePt alloy films. The as-deposited films behaved a disordered state, and the ordered L1₀ structure was obtained by post-annealing. The magnetic properties of the films are changed from soft magnetism to hard magnetism after annealing. The variation of the largest coercivities of [Fe_xPt_100−x/ZrO₂]₁₀ films with the Fe atomic percentage, x and differing amounts of ZrO₂ content reveals that as we increase the ZrO₂ content we must correspondingly increase the amount of Fe. This phenomenon suggests that the Zr or O atoms of ZrO₂ preferentially react with the Fe atoms of FePt alloy to form compounds. In addition, introducing the nonmagnetic ZrO₂ can reduce the intergrain exchange interactions of the FePt/ZrO₂ films, and the interactions are decreased as the ZrO₂ content increases, the dipole interactions are observed in FePt/ZrO₂ films as the ZrO₂ content is more than 15%.     

On the genericity of chaos

Let M be a compact manifold with dimM?2. We prove that some iteration of the generic homeomorphism on M is semiconjugated to the shift map and has infinite topological entropy (Theorem 1.1).     

On dimensional rigidity of bar-and-joint frameworks

Let V={1,2,…,n}. A mapping p:V→R^r, where p¹,…,pⁿ are not contained in a proper hyper-plane is called an r-configuration. Let G=(V,E) be a simple connected graph on n vertices. Then an r-configuration p together with graph G, where adjacent vertices of G are constrained to stay the same distance apart, is called a bar-and-joint framework (or a framework) in R^r, and is denoted by G(p). In this paper we introduce the notion of dimensional rigidity of frameworks, and we study the problem of determining whether or not a given G(p) is dimensionally rigid. A given framework G(p) in R^r is said to be dimensionally rigid iff there does not exist a framework G(q) in R^s for s?r+1, such that ∥qⁱ-q^j∥²=∥pⁱ-p^j∥² for all (i,j)∈E. We present necessary and sufficient conditions for G(p) to be dimensionally rigid, and we formulate the problem of checking the validity of these conditions as a semidefinite programming (SDP) problem. The case where the points p¹,…,pⁿ of the given r-configuration are in general position, is also investigated.     

The minimum span of L(2,1)-labelings of certain generalized Petersen graphs

In the classical channel assignment problem, transmitters that are sufficiently close together are assigned transmission frequencies that differ by prescribed amounts, with the goal of minimizing the span of frequencies required. This problem can be modeled through the use of an L(2,1)-labeling, which is a function f from the vertex set of a graph G to the non-negative integers such that |f(x)-f(y)|? 2 if xand y are adjacent vertices and |f(x)-f(y)|?1 if xand y are at distance two. The goal is to determine the λ-number of G, which is defined as the minimum span over all L(2,1)-labelings of G, or equivalently, the smallest number k such that G has an L(2,1)-labeling using integers from {0,1,…,k}. Recent work has focused on determining the λ-number of generalized Petersen graphs (GPGs) of order n. This paper provides exact values for the λ-numbers of GPGs of orders 5, 7, and 8, closing all remaining open cases for orders at most 8. It is also shown that there are no GPGs of order 4, 5, 8, or 11 with λ-number exactly equal to the known lower bound of 5, however, a construction is provided to obtain examples of GPGs with λ-number 5 for all other orders. This paper also provides an upper bound for the number of distinct isomorphism classes for GPGs of any given order. Finally, the exact values for the λ-number of n-stars, a subclass of the GPGs inspired by the classical Petersen graph, are also determined. These generalized stars have a useful representation on Möebius strips, which is fundamental in verifying our results.