Finite dimensional semisimple Q-algebras

A Q-algebra can be represented as an operator algebra on an infinite dimensional Hilbert space. However we don’t know whether a finite n-dimensional Q-algebra can be represented on a Hilbert space of dimension n except n = 1, 2. It is known that a two dimensional Q-algebra is just a two dimensional commutative operator algebra on a two dimensional Hilbert space. In this paper we study a finite n-dimensional semisimple Q-algebra on a finite n-dimensional Hilbert space. In particular we describe a three dimensional Q-algebra of the disc algebra on a three dimensional Hilbert space. Our studies are related to the Pick interpolation problem for a uniform algebra.     

On the Relation Between Two Minor-Monotone Graph Parameters

, where μ and λ are minor-monotone graph invariants introduced by Colin de Verdière [3] and van der Holst, Laurent, and Schrijver [5]. It is also shown that a graph G exists with . The graphs G with maximal planar complement and , characterised by Kotlov, Lovász, and Vempala, are shown to be forbidden minors for . Received: June 13, 1997     

Erds 等人的一个定理的新证明

本文给出定理:“在2n—1个整数中,必有n 个数,它们的和被n 整除”的一个新的证明,它无需先讨论n 为素数。     

满足互补原理的半单复合模型

本文系统分析了SU(N)×SO(M)半单超色群的手征三前子模型.我们发现:SU(3)×SO(5)模型满足互补原理要求;由′tHooft方程及Bars条件可以给出三代夸克、轻子谱;超色群G_(MC)和规范色味子群G_(CF)都是渐近自由的,因此可以构造出具有低的超色禁闭标度A_(MC)的现实模型.我们还发现,本模型中存在二个超色标度.在这两个标度之间,模型类似于费米——玻色模型,这可以简化前子的动力学.     

两非环的根与半单类

所谓两非环即非结合非分配的环,它最先由许永华教授所定义,并建立了它的一般理论.游宏对两非环的可解根做了进一步的研究.本文对两非环建立了 Kurosh 和 Amitsur 意义下的根类与半单类,分别给出它们的几个特征.     

Small Universal Graphs for Bounded-Degree Planar Graphs

For all positive integers N and k, let denote the family of planar graphs on N or fewer vertices, and with maximum degree k. For all positive integers N and k, we construct a -universal graph of size . This construction answers with an explicit construction the previously open question of the existence of such a graph. Received July 8, 1998 RID="*" ID="*" Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013.     

Large Cliques in -Free Graphs

Dedicated to the memory of Paul Erdős A graph is called -free if it contains no cycle of length four as an induced subgraph. We prove that if a -free graph has n vertices and at least edges then it has a complete subgraph of vertices, where depends only on . We also give estimates on and show that a similar result does not hold for H-free graphs––unless H is an induced subgraph of . The best value of is determined for chordal graphs. Received October 25, 1999 RID="*" ID="*" Supported by OTKA grant T029074. RID="**" ID="**" Supported by TKI grant stochastics@TUB and by OTKA grant T026203.     

Improved Bounds for Acyclic Job Shop Scheduling

In acyclic job shop scheduling problems there are n jobs and m machines. Each job is composed of a sequence of operations to be performed on different machines. A legal schedule is one in which within each job, operations are carried out in order, and each machine performs at most one operation in any unit of time. If D denotes the length of the longest job, and C denotes the number of time units requested by all jobs on the most loaded machine, then clearly lb = max[C,D] is a lower bound on the length of the shortest legal schedule. A celebrated result of Leighton, Maggs, and Rao shows that if all operations are of unit length, then there always is a legal schedule of length O(lb), independent of n and m. For the case that operations may have different lengths, Shmoys, Stein and Wein showed that there always is a legal schedule of length , where the notation is used to suppress terms. We improve the upper bound to . We also show that our new upper bound is essentially best possible, by proving the existence of instances of acyclic job shop scheduling for which the shortest legal schedule is of length . This resolves (negatively) a known open problem of whether the linear upper bound of Leighton, Maggs, and Rao applies to arbitrary job shop scheduling instances (without the restriction to acyclicity and unit length operations). Received June 30, 1998 RID="*" ID="*" Incumbent of the Joseph and Celia Reskin Career Development Chair RID="†" ID="†" Research was done while staying at the Weizmann Institute, supported by a scholarship from the Minerva foundation.     

Transversals in Uniform Hypergraphs with Property (p,2)

Dedicated to the memory of Paul Erdős Let f(r,p,t) (p > t >= 1, r >= 2) be the maximum of the cardinality of a minimum transversal over all r-uniform hypergraphs possessing the property that every subhypergraph of with p edges has a transversal of size t. The values of f(r,p,2) for p = 3, 4, 5, 6 were found in [1] and bounds on f(r,7,2) are given in [3]. Here we prove that for large p and huge r. Received September 23, 1999 RID="*" ID="*" This work was partially supported by the grant 99-01-00581 of the Russian Foundation for Fundamental Research and the Dutch–Russian Grant NWO-047-008-006.