A note on parallelism in affine geometry

The uniqueness of the parallel lines is independent from the analogous statement on parallel planes and the usual further axioms of three-dimensional affine geometry. MSC: 51A15, 03F65.     

Beyond abstract elementary classes: On the model theory of geometric lattices

Based on Crapo's theory of one point extensions of combinatorial geometries, we find various classes of geometric lattices that behave very well from the point of view of stability theory. One of them, $({\mathbf{K}}^3,?)$, is ω-stable, it has a monster model and an independence calculus that satisfies all the usual properties of non-forking. On the other hand, these classes are rather unusual, e.g. in $({\mathbf{K}}^3,?)$ the Smoothness Axiom fails, and so $({\mathbf{K}}^3,?)$ is not an AEC.     

Null decomposition of trees

Let $T$ be a tree. We show that the null space of the adjacency matrix of $T$ has relevant information about the structure of $T$. We introduce the Null Decomposition of trees, which is a decomposition into two different types of trees: N-trees and S-trees. N-trees are the trees that have a unique maximum (perfect) matching. S-trees are the trees with a unique maximum independent set. We obtain formulas for the independence number and the matching number of a tree using this decomposition. We also show how the number of maximum matchings and the number of maximum independent sets in a tree are related to its null decomposition.     

Independence polynomials of k-tree related graphs

An independent set of a graph G is a set of pairwise non-adjacent vertices. Let α(G) denote the cardinality of a maximum independent set and f_s(G) for 0≤s≤α(G) denote the number of independent sets of s vertices. The independence polynomial defined first by Gutman and Harary has been the focus of considerable research recently. Wingard bounded the coefficients f_s(T) for trees T with n vertices: for s≥2. We generalize this result to bounds for a very large class of graphs, maximal k-degenerate graphs, a class which includes all k-trees. Additionally, we characterize all instances where our bounds are achieved, and determine exactly the independence polynomials of several classes of k-tree related graphs. Our main theorems generalize several related results known before.     

A DESCRIPTION OF NORMAL SEMIGROUPS OF ENDOMORPHISMS OF PROPER INDEPENDENCE ALGEBRAS

Let A be a strong independence algebra of finite rank with at most one constant, and let G he the group of automorphisms of A. Let α be a singular endomorphism of α^G = 〈{α} U G〉. We describe the elements of α^G and give additional characterisations when A is a proper independence algebra and G is a periodic group.     

Approximating the independence number via theϑ-function

We describe an approximation algorithm for the independence number of a graph. If a graph onn vertices has an independence numbern/k + m for some fixed integerk 3 and somem > 0, the algorithm finds, in random polynomial time, an independent set of size , improving the best known previous algorithm of Boppana and Halldorsson that finds an independent set of size (m ^1/(k–1)) in such a graph. The algorithm is based on semi-definite programming, some properties of the Lovász-function of a graph and the recent algorithm of Karger, Motwani and Sudan for approximating the chromatic number of a graph. If the-function of ann vertex graph is at leastMn ^1–2/k for some absolute constantM, we describe another, related, efficient algorithm that finds an independent set of sizek. Several examples show the limitations of the approach and the analysis together with some related arguments supply new results on the problem of estimating the largest possible ratio between the-function and the independence number of a graph onn vertices. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research supported in part by a USA—Israel BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences and by the Minkowski Minerva Center for Geometry at Tel Aviv University.This work was partly done while the author was at XEROX PARC and partly at DIMACS.     

标准互相关的灰度无关特性及其应用

对用于图像特征定位的标准互相关算子灰度无关特性展开了研究.由于在显微视觉中的大多数图像灰阶较低,接近于三值甚至二值图像;可籍此灰度无关特性对模板匹配的算法进行优化.实验结果表明,标准互相关的灰度无关特性可以在实际中指导设计模板图像,降低相关运算计算速度,以及指导改善照明条件.     

On the ratios between packing and domination parameters of a graph

The relationship ρ_L(G)≤ρ(G)≤γ(G) between the lower packing number ρ_L(G), the packing number ρ(G) and the domination number γ(G) of a graph G is well known. In this paper we establish best possible bounds on the ratios of the packing numbers of any (connected) graph to its six domination-related parameters (the lower and upper irredundance numbers ir and IR, the lower and upper independence numbers i and β, and the lower and upper domination numbers γ and Γ). In particular, best possible constants a_θ, b_θ, c_θ and d_θ are found for which the inequalities and hold for any connected graph G and all θ∈{ir,γ,i,β,Γ,IR}. From our work it follows, for example, that and for any connected graph G, and that these inequalities are best possible.