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.     

On a problem of Rolewicz about Banach spaces that admit support sets

We construct an example of a nonseparable Banach space which does not admit a support set.² It is a consistent (and necessarily independent from the axioms of ZFC) example of a space C(K) of continuous functions on a compact Hausdorff K with the supremum norm. The construction depends on a construction of a Boolean algebra with some combinatorial properties. The space is also hereditarily Lindelöf in the weak topology but it doesn't have any nonseparable subspace nor any nonseparable quotient which is a C(K) space for K dispersed.     

En route to Background Independence: Broken split-symmetry,and how to restore it with bi-metric average actions

The most momentous requirement a quantum theory of gravity must satisfy is Background Independence, necessitating in particular an ab initio derivation of the arena all non-gravitational physics takes place in, namely spacetime. Using the background field technique, this requirement translates into the condition of an unbroken split-symmetry connecting the (quantized) metric fluctuations to the (classical) background metric. If the regularization scheme used violates split-symmetry during the quantization process it is mandatory to restore it in the end at the level of observable physics. In this paper we present a detailed investigation of split-symmetry breaking and restoration within the Effective Average Action (EAA) approach to Quantum Einstein Gravity (QEG) with a special emphasis on the Asymptotic Safety conjecture. In particular we demonstrate for the first time in a non-trivial setting that the two key requirements of Background Independence and Asymptotic Safety can be satisfied simultaneously. Carefully disentangling fluctuation and background fields, we employ a ‘bi-metric’ ansatz for the EAA and project the flow generated by its functional renormalization group equation on a truncated theory space spanned by two separate Einstein–Hilbert actions for the dynamical and the background metric, respectively. A new powerful method is used to derive the corresponding renormalization group (RG) equations for the Newton- and cosmological constant, both in the dynamical and the background sector. We classify and analyze their solutions in detail, determine their fixed point structure, and identify an attractor mechanism which turns out instrumental in the split-symmetry restoration. We show that there exists a subset of RG trajectories which are both asymptotically safe and split-symmetry restoring: In the ultraviolet they emanate from a non-Gaussian fixed point, and in the infrared they loose all symmetry violating contributions inflicted on them by the non-invariant functional RG equation. As an application, we compute the scale dependent spectral dimension which governs the fractal properties of the effective QEG spacetimes at the bi-metric level. Earlier tests of the Asymptotic Safety conjecture almost exclusively employed ‘single-metric truncations’ which are blind towards the difference between quantum and background fields. We explore in detail under which conditions they can be reliable, and we discuss how the single-metric based picture of Asymptotic Safety needs to be revised in the light of the new results. We shall conclude that the next generation of truncations for quantitatively precise predictions (of critical exponents, for instance) is bound to be of the bi-metric type.