Extensions of the Scherk-Kemperman Theorem

Let Γ=(V,E) be a reflexive relation with a transitive automorphism group. Let F be a finite subset of V containing a fixed element v. We prove that the size of Γ(F) (the image of F) is at least

|F|+|Γ(v)|−|Γ⁻(v)∩F|.     

信息调度中的一个组合问题

研究了多用户信息服务中的实时调度问题,在基于双向扫描调度模型的基础上使用组合分析技术,对使用扫描算法进行调度时造成的服务延迟这一组合问题进行定量分析,推导出了计算延迟的递推公式.数值计算表明平均延迟时间随用户数的增长率近于常数.该公式可用于对双向扫描算法服务性能的评价.     

Structural properties and decomposition of linear balanced matrices

Claude Berge defines a (0, 1) matrix A to be linear ifA does not contain a 2 × 2 submatrix of all ones.A(0, 1) matrixA is balanced ifA does not contain a square submatrix of odd order with two ones per row and column.The contraction of a rowi of a matrix consists of the removal of rowi and all the columns that have a 1 in the entry corresponding to rowi. In this paper we show that if a linear balanced matrixA does not belong to a subclass of totally unimodular matrices, thenA orA ^T contains a rowi such that the submatrix obtained by contracting rowi has a block-diagonal structure.Partial support from NSF grant DMS 8606188, ECS 8800281 and DDM 8800281.     

Subgraph statistics in subcritical graph classes

Let H be a fixed graph and a subcritical graph class. In this paper we show that the number of occurrences of H (as a subgraph) in a graph in of order n, chosen uniformly at random, follows a normal limiting distribution with linear expectation and variance. The main ingredient in our proof is the analytic framework developed by Drmota, Gittenberger and Morgenbesser to deal with infinite systems of functional equations [Drmota, Gittenberger, and Morgenbesser, Submitted]. As a case study, we obtain explicit expressions for the number of triangles and cycles of length 4 in the family of series‐parallel graphs. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 631–673, 2017     

Hochschild (co)homology of exterior algebras using algebraic Morse theory

In [1 Han, Y., Xu, Y. (2007). Hochschild (co)homology of exterior algebras. Comm. Algebra 35(1):115–131.[Web of Science ®] , [Google Scholar]], the authors computed the additive and multiplicative structure of HH*(A;A), where A is the n-th exterior algebra over a field. In this paper, we derive all their results using a different method (AMT) as well as calculate the additive structure of HH_k(A;A) and HH^k(A;A) over ?. We provide concise presentations of algebras HH_?(A;A) and HH*(A;A) as well as determine their generators in the Hochschild complex. Finally, we compute an explicit free resolution (spanned by multisets) of the A^e-module A and describe the homotopy equivalence to its bar resolution.     

从完全基因组出发建立原核生物亲缘关系和分类系统时遇到的数学问题

我们课题组近10年所发展的组分矢量(CVTree)方法,已经成为从完全基因组出发而不使用序列联配来构建细菌亲缘关系的有效手段.在整个生物分类学日益后继乏人的背景下,组分矢量(CVTree)方法伴随着基因组时代的发展,成为人人可以方便使用的微生物分类的定义性工具.本综述不讨论CVTree的生物学结果,而着重从非线性科学的角度,介绍我们在研究过程中所提出和解决的数学问题.这将涉及组合学、图论、形式语言学等离散数学的篇章.我们特别希望,本文所列举的一些尚未解决的数学问题能引发新的研究工作,使CVTree方法的理论基础更为坚实.     

Matrices, graphs and equivalence relations

A suitable equivalence relation is introduced on the set of square matrices with entries of any kind. This allows us to associate to every equivalence class an infinite family of graphs and determine their topological properties. When a given square matrix is the multiplication table of a finite groupoid, some connections between algebraic properties of the groupoid and topological properties of these graphs are proved. Received: May 4, 1999 Published online: December 19, 2001