80486极小指令集及其构造性证明

指令集是计算机系统结构的重要研究内容之一,众多学者对指令完全性进行了描述,但至今未见极小指令集的报道。在文中,寻找既具有基本功能,又无法由其它指令编程实现的计算机基本指令,研究计算机现有的最基本的计算行为。提出了指令的功能完全性和独立性概念,并在此基础上定义了极小指令集,这为计算机指令集的优化设计建立了理论基础。还从Intel 80486指令集中选定了一个子集I9,并构造性地证明了I9是IA-32处理器指令集的极小指令集。     

Independence for knights on hexagon and triangle boards

For three kinds of chess-like knights, one on triangle and two on hexagon boards, the independence numbers for their knight graphs are considered. We determine these numbers completely for two kinds of these knights, and for one residue class modulo 4 in the case of the third kind.     

On αrγs(k)-perfect graphs

For some integer k0 and two graph parameters π and τ, a graph G is called πτ(k)-perfect, if π(H)−τ(H)k for every induced subgraph H of G. For r1 let α_r and γ_r denote the r-(distance)-independence and r-(distance)-domination number, respectively. In (J. Graph Theory 32 (1999) 303–310), I. Zverovich gave an ingenious complete characterization of α₁γ₁(k)-perfect graphs in terms of forbidden induced subgraphs. In this paper we study α_rγ_s(k)-perfect graphs for r,s1. We prove several properties of minimal α_rγ_s(k)-imperfect graphs. Generalizing Zverovich's main result in (J. Graph Theory 32 (1999) 303–310), we completely characterize α_2r−1γ_r(k)-perfect graphs for r1. Furthermore, we characterize claw-free α₂γ₂(k)-perfect graphs.     

图的独立数的一个新下界

设α（Ｇ）表示简单图Ｇ＝（Ｖ，Ｅ）的独立数．本文给出了α（Ｇ）的一个新的下界：α（Ｇ）≥∑ｖ∈Ｖ（λｄ（ｖ）＋１）／（ｄ（ｖ）＋λｄ（ｖ）＋１），其中λｄ（ｖ）＝ｍａｘ｛０，βＮ（ｖ）－ｄ（ｖ）｝，ｄ（ｖ）＝｜Ｎ（ｖ）｜，Ｎ（ｖ）＝｛ｗ∈Ｖ｜（ｖ，ｗ）∈Ｅ｝，βＮ（ｖ）＝ｍｉｎｗ∈Ｎ（ｖ）ｄ（ｗ）．     

Karp complexity and classes with the independence property

A class K of structures is controlled if for all cardinals λ, the relation of L_∞,λ-equivalence partitions K into a set of equivalence classes (as opposed to a proper class). We prove that no pseudo-elementary class with the independence property is controlled. By contrast, there is a pseudo-elementary class with the strict order property that is controlled (see Arch. Math. Logic 40 (2001) 69–88).     

Upper domination and upper irredundance perfect graphs

Let β(G), Γ(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. A graph G is called IR-perfect if Γ(H) =IR(H), for every induced subgraph H of G. In this paper, we present a characterization of Γ-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of Γ-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of Γ-perfect graphs. These results imply a number of known theorems on Γ-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be Γ-perfect and IR-perfect which improves a known analogous result.     

Multidimensional dependency measures

The problem of dependency between two random variables has been studied throughly in the literature. Many dependency measures have been proposed according to concepts such as concordance, quadrant dependency, etc. More recently, the development of the Theory of Copulas has had a great impact in the study of dependence of random variables specially in the case of continuous random variables. In the case of the multivariate setting, the study of the strong mixing conditions has lead to interesting results that extend some results like the central limit theorem to the case of dependent random variables.In this paper, we study the behavior of a multidimensional extension of two well-known dependency measures, finding their basic properties as well as several examples. The main difference between these measures and others previously proposed is that these ones are based on the definition of independence among n random elements or variables, therefore they provide a nice way to measure dependency.The main purpose of this paper is to present a sample version of one of these measures, find its properties, and based on this sample version to propose a test of independence of multivariate observations. We include several references of applications in Statistics.     

On the geometric structure of independence systems

A bouquet of matroids is a combinatorial structure that generalizes the properties of matroids. Given an independence system, there exist several bouquets of matroids having the same family of independent sets. We show that the collection of these geometries forms in general a meet semi-lattice and, in some cases, a lattice (for instance, when is the family of the stable sets in a graph). Moreover, one of the bouquets that correspond to the highest elements in the meet semi-lattice provides the smallest decomposition of into matroidal families, such that the rank functions of the different matroids have the same values for common sets. In the last section, we give sharp bounds on the performance of the greedy algorithm, using parameters of some special bouquets in the semi-lattice.     

Regular (2, 2)-systems

Let (E,I) be an independence system over the finite setE = {e ₁, ,e _n }, whose elements are orderede ₁ e _n . (E,I) is called regular, if the independence of {e _l , ,e _{l k} },l ₁ < <l _k , implies that of {e _{m l} , ,e _{m k} }, wherem _l < ··· <m _k andl ₁ m ₁, ,l _k m _k . (E,I) is called a 2-system, if for anyI I,e E I the setI {e } contains at most 2 distinct circuitsC, C I and the number 2 is minimal with respect to this property. If, in addition, for any two independent setsI andJ the family (C J, C C (J, I)), whereC(J, I) denotes {C C:e J I C {e}}, can be partitioned into 2 subfamilies each of which possesses a transversal, then (E,I) is called a (2, 2)-system. In this paper we characterize regular 2-systems and we show that the classes of regular 2-systems resp. regular (2, 2)-systems are identical.     

Optimization of eigenvalue bounds for the independence and chromatic number of graph powers

The $k^{\text{th}}$ power of a graph $G=(V,E)$, $G^k$, is the graph whose vertex set is V and in which two distinct vertices are adjacent if and only if their distance in G is at most k. This article proves various eigenvalue bounds for the independence number and chromatic number of $G^k$ which purely depend on the spectrum of G, together with a method to optimize them. Our bounds for the k-independence number also work for its quantum counterpart, which is not known to be a computable parameter in general, thus justifying the use of integer programming to optimize them. Some of the bounds previously known in the literature follow as a corollary of our main results. Infinite families of graphs where the bounds are sharp are presented as well.