Formal proofs of operator identities by a single formal computation

A formal computation proving a new operator identity from known ones is, in principle, restricted by domains and codomains of linear operators involved, since not any two operators can be added or composed. Algebraically, identities can be modelled by noncommutative polynomials and such a formal computation proves that the polynomial corresponding to the new identity lies in the ideal generated by the polynomials corresponding to the known identities. In order to prove an operator identity, however, just proving membership of the polynomial in the ideal is not enough, since the ring of noncommutative polynomials ignores domains and codomains. We show that it suffices to additionally verify compatibility of this polynomial and of the generators of the ideal with the labelled quiver that encodes which polynomials can be realized as linear operators. Then, for every consistent representation of such a quiver in a linear category, there exists a computation in the category that proves the corresponding instance of the identity. Moreover, by assigning the same label to several edges of the quiver, the algebraic framework developed allows to model different versions of an operator by the same indeterminate in the noncommutative polynomials.     

Sufficient Conditions for a Digraph to be Supereulerian

A (di)graph is supereulerian if it contains a spanning eulerian sub(di)graph. This property is a relaxation of hamiltonicity. Inspired by this analogy with hamiltonian cycles and by similar results in supereulerian graph theory, we analyze a number of sufficient Ore type conditions for a digraph to be supereulerian. Furthermore, we study the following conjecture due to Thomassé and the first author: if the arc‐connectivity of a digraph is not smaller than its independence number, then the digraph is supereulerian. As a support for this conjecture we prove it for digraphs that are semicomplete multipartite or quasitransitive and verify the analogous statement for undirected graphs.     

N指标d维广义Wiener过程象集的m项代数和的几个性质

设珮犠（狋）：犚犖＋ →犚犱是犖指标犱维广义Ｗｉｅｎｅｒ过程，对任意紧集犈１，…，犈犿犚犖＞ ，该文研究了犿项代数和珮犠（犈１）…珮犠（犈犿）的Ｈａｕｓｄｏｒｆｆ维数，Ｐａｃｋｉｎｇ维数和正的Ｌｅｂｅｓｇｕｅ测度及内点的存在性． 其结果包含并推广了布朗单的结果．     

Algebraic methods in quantum mechanics: from molecules to polymers

We present a brief review of algebraic techniques developed and applied in molecular spectroscopy in the last five years. We also outline perspectives for new applications of the Lie algebraic method in the first decade of the new century. Received 21 November 2001     

Sparse graph certificates for mixed connectivity

We give a short proof for the Mixed Connectivity Certificate Theorem of Even, Itkis and Rajsbaum and provide an upper bound on the edge number of a certificate of local T-mixed connectivity up to k.     

On the degree of convergence of lemniscates in finite connected domains

For an arbitrary bounded closed set E in the complex plane with complement Ω of finite connectivity, we study the degree of convergence of the lemniscates in Ω.     

The algebraic Bethe ansatz for the Izergin–Korepin model with open boundary conditions

We present the procedure of exactly solving the Izergin–Korepin model with open boundary conditions by using the algebraic Bethe ansatz, which include constructing the multi-particle state and achieving the eigenvalue of the transfer matrix and corresponding Bethe equations. We give a proof about our conclusions on the multi-particle state based on an assumption. When the model is U_q(su(2)) quantum invariant, our results agree with that obtained by analytic Bethe ansatz method.     

The node-edge weighted 2-edge connected subgraph problem: Linear relaxation, facets and separation

Let G=(V,E) be a undirected k-edge connected graph with weights c_e on edges and w_v on nodes. The minimum 2-edge connected subgraph problem, 2ECSP for short, is to find a 2-edge connected subgraph of G, of minimum total weight. The 2ECSP generalizes the well-known Steiner 2-edge connected subgraph problem. In this paper we study the convex hull of the incidence vectors corresponding to feasible solutions of 2ECSP. First, a natural integer programming formulation is given and it is shown that its linear relaxation is not sufficient to describe the polytope associated with 2ECSP even when G is series-parallel. Then, we introduce two families of new valid inequalities and we give sufficient conditions for them to be facet-defining. Later, we concentrate on the separation problem. We find polynomial time algorithms to solve the separation of important subclasses of the introduced inequalities, concluding that the separation of the new inequalities, when G is series-parallel, is polynomially solvable.     

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.

     

The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007