A note on the computational complexity of graph vertex partition

A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstädt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59-73] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such thatG-Sis a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such thatG-Sis a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that G-S is a tree.     

关于矩阵条件数的一些结论

本文讨论了一些矩阵范数达到极小的充要条件,其主要结果如下:1.设?为m×n实矩阵,且具有n个线性无关的列,则求?广义逆谱条件数等于1的充要条件为?=cI,其中c为正常数.2.设?为n阶非异实矩阵,则矩阵A的求逆p-范数条件数等于1的充要条件为A=cpσ,其中c为正常数,σ是置换阵,其对角元都等于 1或-1.3.设?为n阶非异实矩阵,则矩阵4的求逆F-范数条件数等于1的充要条件为?=cU,其中c为正常数,U为正交阵.     

A graphical approach to computing Selmer groups of congruent number curves

Let E _n:y ²=x ³−n ² x denote the family of congruent number elliptic curves. Feng and Xiong (2004) equate the nontriviality of the Selmer groups associated with E _n to the presence of certain types of partitions of graphs associated with the prime factorization of n. In this paper, we extend the ideas of Feng and Xiong in order to compute the Selmer groups of E _n. 2000 Mathematics Subject Classification Primary—11G05; Secondary—14H52, 14H25, 05C90     

One-Element Extensions in the Variety Generated by Tournaments

We investigate congruences in one-element extensions of algebras in the variety generated by tournaments.     

Affine Hecke algebras and the Schubert calculus

Using a combinatorial approach that avoids geometry, this paper studies the structure of K_T(G/B), the T-equivariant K-theory of the generalized flag variety G/B. This ring has a natural basis (the double Grothendieck polynomials), where is the structure sheaf of the Schubert variety X_w. For rank two cases we compute the corresponding structure constants of the ring K_T(G/B) and, based on this data, make a positivity conjecture for general G which generalizes the theorems of M. Brion (for K(G/B)) and W. Graham (for H_T^*(G/B)). Let [X^λ]K_T(G/B) be the class of the homogeneous line bundle on G/B corresponding to the character of T indexed by λ. For general G we prove “Pieri–Chevalley formulas” for the products , , , and , where λ is dominant. By using the Chern character and comparing lowest degree terms the products which are computed in this paper also give results for the Grothendieck polynomials, double Schubert polynomials, and ordinary Schubert polynomials in, respectively K(G/B), H_T^*(G/B) and H^*(G/B).     

Optimally Stable Multivariate Bases

We show that the tensor product B-spline basis and the triangular Bernstein basis are in some sense best conditioned among all nonnegative bases for the spaces of tensor product splines and multivariate polynomials, respectively. We also introduce some new condition numbers which are analogs of component-wise condition numbers for linear systems introduced by Skeel.     

Stark's conjecture over complex cubic number fields

Systematic computation of Stark units over nontotally real base fields is carried out for the first time. Since the information provided by Stark's conjecture is significantly less in this situation than the information provided over totally real base fields, new techniques are required. Precomputing Stark units in relative quadratic extensions (where the conjecture is already known to hold) and coupling this information with the Fincke-Pohst algorithm applied to certain quadratic forms leads to a significant reduction in search time for finding Stark units in larger extensions (where the conjecture is still unproven). Stark's conjecture is verified in each case for these Stark units in larger extensions and explicit generating polynomials for abelian extensions over complex cubic base fields, including Hilbert class fields, are obtained from the minimal polynomials of these new Stark units.

     

未确知数学方法处理物理实验数据

介绍未确知数学方法，并用未确知数学方法分析处理物理实验数据，与传统的数据处理方法比较，未确知数学方法不必对数据作任何假设，因此更合理，也更符合实际。     

二阶循环数列方程的特征根解法

就应用常微分方程的常系数线性微分方程解法的理论解决递归数列中二阶循环数列方程问题进行了论述 ,由此可看到高等数学对初等数学的指导作用 .     

Strengthened semidefinite programming bounds for codes

We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular ∗-representation for matrix ∗-algebras. The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inform. Theory 51:2859–2866, 2005) is located between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with O(n ⁷) variables and thus seems out of reach for interesting values of n, Schrijver’s bound can be computed via a semidefinite program of size O(n ³), a result which uses the explicit block-diagonalization of the Terwilliger algebra. We propose two strengthenings of Schrijver’s bound with the same computational complexity. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.