Unitary Graphs

Unitary graphs are arc‐transitive graphs with vertices the flags of Hermitian unitals and edges defined by certain elements of the underlying finite fields. They played a significant role in a recent classification of a class of arc‐transitive graphs that admit an automorphism group acting imprimitively on the vertices. In this article, we prove that all unitary graphs are connected of diameter two and girth three. Based on this, we obtain, for any prime power , a lower bound of order on the maximum number of vertices in an arc‐transitive graph of degree and diameter two.     

正规Cayley图

综述了自１９９０年以来１２－传递图研究的一些新成果，正规Ｃａｙｌｅｙ图的相关结论。     

On free semigroups of automaton transformations

It is established that the subset of freek-generated subsemigroups of the semigroup of all automaton transformations over a finite alphabet is a second category set (in the sense of the Baire category approach) in the set of allk-generated subsemigroups. A continuum series of pairs of automaton transformations each of which generates a free semigroup of rank two is indicated. A criterion is established for this semigroup to be a finite-automaton group. Translated fromMatematicheskie Zametki, Vol. 63, No. 2, pp. 248–259, February, 1998. The author wishes to express his deep gratitude to Professor V. I. Sushchans'kii for permanent help and attention to the research. This research was partially supported by the ISSEP under grant No. GSU 051341.     

增长曲线模型中UMRE估计的存在性

对于设计矩阵不满秩，协方差阵任意或具有均匀结构或序列结构的正态增长曲线模型，本文讨论参数矩阵的一致最小风险同变（UMng）估计的存在性．在仿射变换群GI和转移交换群、二次损失和矩阵损失下本文分别获得存在回归系数矩阵的线性可估函数矩阵的UMRE估计的充要条件，推广了由[21]给出的在设计矩阵满秩下估计回归系数矩阵的结果．本文还首次证明了在群G1和二次损失下不存在协方差阵V和trV的UMRE估计．     

拓扑遍历映射的一些性质

本文研究拓扑遍历映射.指出对于由不可约方阵所决定的符号空间有限型子转移而言,或紧致交换群的仿射变换及线段上连续自映射而言,拓扑遍历与拓扑可迁这两个概念是一致的.同时还通过例子,指出拓扑遍历是不同于拓扑可迁与拓扑混合的概念.     

Frames with Transitive Structures

A classical result in the theory of uniform spaces is that any topological space with a base of clopen sets admits a uniformity with a transitive base and the uniform topology of such a space has a base of clopen sets. This paper presents a pointfree generalization of this, both to uniform and quasi-uniform frames, together with various properties concerning total boundedness, compactifications and completions.     

Disjoint Paths in Decomposable Digraphs

The k‐linkage problem is as follows: given a digraph and a collection of k terminal pairs such that all these vertices are distinct; decide whether D has a collection of vertex disjoint paths such that is from to for . A digraph is k‐linked if it has a k‐linkage for every choice of 2k distinct vertices and every choice of k pairs as above. The k‐linkage problem is NP‐complete already for [11] and there exists no function such that every ‐strong digraph has a k‐linkage for every choice of 2k distinct vertices of D [17]. Recently, Chudnovsky et al. [9] gave a polynomial algorithm for the k‐linkage problem for any fixed k in (a generalization of) semicomplete multipartite digraphs. In this article, we use their result as well as the classical polynomial algorithm for the case of acyclic digraphs by Fortune et al. [11] to develop polynomial algorithms for the k‐linkage problem in locally semicomplete digraphs and several classes of decomposable digraphs, including quasi‐transitive digraphs and directed cographs. We also prove that the necessary condition of being ‐strong is also sufficient for round‐decomposable digraphs to be k‐linked, obtaining thus a best possible bound that improves a previous one of . Finally we settle a conjecture from [3] by proving that every 5‐strong locally semicomplete digraph is 2‐linked. This bound is also best possible (already for tournaments) [1].     

Finite Precision Representation of the Conley Decomposition

We present a theoretical basis for a novel way of studying and representing the long-time behavior of finite-dimensional maps. It is based on a finite representation of -pseudo orbits of a map by the sample paths of a suitable Markov chain based on a finite partition of phase space. The use of stationary states of the chain and the corresponding partition elements in approximating the attractors of maps and differential equations was demonstrated in Refs. 7 and 3 and proved for a class of stable attracting sets in Ref. 8. Here we explore the relationship between the communication classes of the Markov chain and basic sets of the Conley decomposition of a dynamical system. We give sufficient conditions for the existence of a chain transitive set and show that basic sets are isolated from each other by neighborhoods associated with closed communication classes of the chain. A partition element approximation of an isolating block is introduced that is easy to express in terms of sample paths. Finally, we show that when the map supports an SBR measure there is a unique closed communication class and the Markov chain restricted to those states is irreducible.     

Correspondence between near-domains and groups

We study into the relationship between an algebraic structure, close to a near-domain, defined on a set B and sharply doubly transitive groups on a subset of B². The results obtained allow us to resolve a problem in the theory of physical structures for range (3, 2). __________ Translated from Algebra i Logika, Vol. 45, No. 2, pp. 239–251, March–April, 2006.     

Planar embeddings with infinite faces

We investigate vertex‐transitive graphs that admit planar embeddings having infinite faces, i.e., faces whose boundary is a double ray. In the case of graphs with connectivity exactly 2, we present examples wherein no face is finite. In particular, the planar embeddings of the Cartesian product of the r‐valent tree with K₂ are comprehensively studied and enumerated, as are the automorphisms of the resulting maps, and it is shown for r = 3 that no vertex‐transitive group of graph automorphisms is extendable to a group of homeomorphisms of the plane. We present all known families of infinite, locally finite, vertex‐transitive graphs of connectivity 3 and an infinite family of 4‐connected graphs that admit planar embeddings wherein each vertex is incident with an infinite face. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 257–275, 2003