Partially isometric dilations of noncommuting -tuples of operators

Given a row contraction of operators on a Hilbert space and a family of projections on the space that stabilizes the operators, we show there is a unique minimal joint dilation to a row contraction of partial isometries that satisfy natural relations. For a fixed row contraction the set of all dilations forms a partially ordered set with a largest and smallest element. A key technical device in our analysis is a connection with directed graphs. We use a Wold decomposition for partial isometries to describe the models for these dilations, and we discuss how the basic properties of a dilation depend on the row contraction.

     

Circular perfect graphs

For 1 ≤ d ≤ k, let K_k/d be the graph with vertices 0, 1, …, k ? 1, in which i ～j if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χ_c(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to K_k/d. The circular clique number ω_c(G) of G is the maximum of those k/d for which K_k/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χ_c(H) = ω_c(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, N_G[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, N_G[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P₅ (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph K_k/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005     

Bit-parallel approximate string matching algorithms with transposition

Using bit-parallelism has resulted in fast and practical algorithms for approximate string matching under Levenshtein edit distance, which permits a single edit operation to insert, delete or substitute a character. Depending on the parameters of the search, currently the fastest non-filtering algorithms in practice are the O(km/wn) algorithm of Wu and Manber, the O((k+2)(m−k)/wn) algorithm of Baeza-Yates and Navarro, and the O(m/wn) algorithm of Myers, where m is the pattern length, n is the text length, k is the error threshold and w is the computer word size. In this paper we discuss a uniform way of modifying each of these algorithms to permit also a fourth type of edit operation: transposing two adjacent characters in the pattern. This type of edit distance is also known as Damerau edit distance. In the end we also present an experimental comparison of the resulting algorithms.     

Line graphs of bipartite graphs with Hamiltonian paths

It is shown that, if t is an integer ≥3 and not equal to 7 or 8, then there is a unique maximal graph having the path P_t as a star complement for the eigenvalue ?2. The maximal graph is the line graph of K_m,m if t = 2m?1, and of K_m,m+1 if t = 2m. This result yields a characterization of L(G ) when G is a (t + 1)‐vertex bipartite graph with a Hamiltonian path. The graphs with star complement P_r ∪ P_s or P_r ∪ C_s for ?2 are also determined. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 137–149, 2003     

四阶非线性边值问题解的存在性与上下解方法

该文讨论四阶常微分方程边值问题u^(4)(t)=f(t,u,u″), t∈［0,1］,u(0)=u(1)=u″(0)=u″(1)=0解的存在性, 其中f(t,u,v):［0,1］×R×R→R为Carathéodory函数. 在不限制f关于u,v的增长阶, 不假定f关于u,v的单调性的一般情形下, 用上下解方法获得了解的存在性结果,并讨论了单调迭代求解的有效性.     

相对论平均场理论中各种有效相互作用对中子星性质的影响

基于相对论平均场理论，研究了各种相互作用参数组(NL1、NL3、NLSH、TM1和GL-97)对中子星物质的性质和中子星整体结构的影响．发现参数组NL1、NL3和NLSH所给出的中子星内部的介子场强度、物质的组成比例、物态方程和中子星的整体特点基本相同，但与TM1和GL-97之间有较大的差别．相对于其他参数组，GL-97给出的介子场强度最弱，中子星的相对数密度最大，物态方程也最软，同时采用GL-97参数组计算的中子星的最大质量也最小．     

基因组重排问题的一个近似算法

分子生物学中基因无方向的反向基因组重排问题在数学上已被证明是一个NP困难问题．基于断点图的概念，给出一个时间复杂性为O(max{b^(π)，nb(π)})，空间复杂性为0(n)的求其近似最优解的算法．其中n为基因组中基因个数，π=(π1,π2，…，πn)表示n个基因的一种排列，b(π)表示排列π中的断点数．数据实验的结果表明，该近似算法可以求得较好的结果．     

期货经纪公司保证金的一种确定方法

本文基于马尔可夫链在存储论中的应用，结合Ergodic定理，得到确定期货经纪公司保证金的Ergodic模型，即一个双目标规划问题，然后应用乘积最大化准则，将该模型转化为单目标规划问题来求解。该方法考虑期货经纪公司承担的风险和对投资者的吸引程度，为保证金的确定提供新的思路。     

障碍拟阵图

Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.     

On the structure of the optimal server control for fluid networks

This paper derives the optimal trajectories in a general fluid network with server control. The stationary optimal policy in the complete state space is constructed. The optimal policy is constant on polyhedral convex cones. An algorithm is derived that computes these cones and the optimal policy. Generalized Klimov indices are introduced, they are used for characterizing myopic and time-uniformly optimal policies.Received: November 2004 / Revised: February 2005The research of this author has been supported by the project ‘‘Stochastic Networks’’ of the Netherlands Organisation for Scientific Research NWO.