Geometric graph homomorphisms

A geometric graph is a simple graph drawn on points in the plane, in general position, with straightline edges. A geometric homomorphism from to is a vertex map that preserves adjacencies and crossings. This work proves some basic properties of geometric homomorphisms and defines the geochromatic number as the minimum n so that there is a geometric homomorphism from to a geometric n‐clique. The geochromatic number is related to both the chromatic number and to the minimum number of plane layers of . By providing an infinite family of bipartite geometric graphs, each of which is constructed of two plane layers, which take on all possible values of geochromatic number, we show that these relationships do not determine the geochromatic number. This article also gives necessary (but not sufficient) and sufficient (but not necessary) conditions for a geometric graph to have geochromatic number at most four. As a corollary, we get precise criteria for a bipartite geometric graph to have geochromatic number at most four. This article also gives criteria for a geometric graph to be homomorphic to certain geometric realizations of K_{2, 2} and K_{3, 3}. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:97‐113, 2012     

Variable strength covering arrays

We define and study variable strength covering arrays (also called covering arrays on hypergraphs), which are generalizations of covering arrays and covering arrays on graphs. Variable strength covering arrays have the potential for use in software testing, allowing the engineer to omit the parameter combinations known to not interact in order to reduce the number of tests required. The present paper shows that variable strength covering arrays are relevant combinatorial objects that have deep connections with hypergraph homomorphisms and generalize other important combinatorial designs. We give optimal constructions for special types of hypergraphs, constructions based on columns with uniform occurrence of symbols, and constructions for mixed alphabets.     

广义同态与算子群

设G1,G2是群,映射f:G1→G2叫作G1到G2的广义同态映射,如果a,b∈G1,等式(ab)f=afbf和(ab)f=bfaf至少有一个成立.利用广义同态映射的概念,本文将算子群的算子集进行扩充,得到一系列有关算子群的结果,从而推广经典的算子群理论.     

层次ω-开集及其应用

首先在L-保序算子空间中引入层次ω-开集,讨论了它的一些基本性质;其次用层次ω-开集刻画了（ω_1,ω_2）-连续序同态和（ω_1,ω_2）-开序同态的一些新的特征性质.     

全变换半群Tn 与对称逆半群ISn 之间的同态

刻画了有限集合N上全变换半群T_n 与对称逆半群IS_n 之间的所有同态.     

A reflexive digraph that is retraction trivial but not endomorphism trivial

In this note we give an example of a reflexive digraph that has no non-trivial retractions, but does have non-trivial endomorphisms.     

效应代数的同态

本文研究了维数大于等于3的可分Hillbert空间H的效应代数E(H)上的同态问题.利用投影算子以及线性延拓的方法,获得了效应代数E(H)上每个满的σ-正交完备的强同态?都具有形式?(A)=UAU*,当满足齐次性以及单边保序的条件时可以延拓到交换von-Neumann代数A到B(H)上一个有界*同态的结果.     

Mixing Homomorphisms,Recolorings, and Extending Circular Precolorings

This work brings together ideas of mixing graph colorings, discrete homotopy, and precoloring extension. A particular focus is circular colorings. We prove that all the ‐colorings of a graph G can be obtained by successively recoloring a single vertex provided along the lines of Cereceda, van den Heuvel, and Johnson's result for k‐colorings. We give various bounds for such mixing results and discuss their sharpness, including cases where the bounds for circular and classical colorings coincide. As a corollary, we obtain an Albertson‐type extension theorem for ‐precolorings of circular cliques. Such a result was first conjectured by Albertson and West. General results on homomorphism mixing are presented, including a characterization of graphs G for which the endomorphism monoid can be generated through the mixing process. As in similar work of Brightwell and Winkler, the concept of dismantlability plays a key role.     

幂超格的性质

对幂超格的性质进行了研究.给出了幂超格直积、分配幂超格的概念并讨论了他们的性质.