Independence equivalence classes of paths

The independence equivalence class of a graph G is the set of graphs that have the same independence polynomial as G. A graph whose independence equivalence class contains only itself, up to isomorphism, is independence unique. Beaton, Brown and Cameron [2] showed that paths with an odd number of vertices are independence unique and raised the problem of finding the independence equivalence class of paths with an even number of vertices. The problem is completely solved in this paper.     

Independence polynomials of circulants with an application to music

The independence polynomial of a graph G is the generating function I(G,x)=∑_k≥0i_kx^k, where i_k is the number of independent sets of cardinality k in G. We show that the problem of evaluating the independence polynomial of a graph at any fixed non-zero number is intractable, even when restricted to circulants. We provide a formula for the independence polynomial of a certain family of circulants, and its complement. As an application, we derive a formula for the number of chords in an n-tet musical system (one where the ratio of frequencies in a semitone is 2^1/n) without ‘close’ pitch classes.     

An algorithm for calculating the independence and vertex-cover polynomials of a graph

The independence polynomial, ω(G,x)=∑w_kx^k, of a graph, G, has coefficients, w_k, that enumerate the ways of selecting k vertices from G so that no two selected vertices share an edge. The independence number of G is the largest value of k for which w_k≠0. Little is known of less straightforward relationships between graph structure and the properties of ω(G,x), in part because of the difficulty of calculating values of w_k for specific graphs. This study presents a new algorithm for these calculations which is both faster than existing ones and easily adaptable to high-level computer languages.     

Derived equivalence of algebras

The derived equivalence and stable equivalence of algebrasR _A ^m and R _B ^m are studied. It is proved, using the tilting complex, thatR _A ^m andR _B ^m are derived-equivalent whenever algebrasA andB are derived-equivalent.     

Determining classes and independence

A class of functions of a random element X is sufficiently rich to determine the distribution of X if and only if it is sufficiently rich to determine whether X is independent of other random functions.     

Log-concavity of some independence polynomials via a partial ordering

Schwenk proved in 1981 that the edge independence polynomial of a graph is unimodal. It has been known since 1987 that the (vertex) independence polynomial of a graph need not be unimodal. Alavi et al. have asked whether the independence polynomial of a tree is unimodal. We apply some results on the log-concavity of combinations of log-concave sequences toward establishing the log-concavity (and, thus, the unimodality) of the independence numbers of some families of trees and related graphs.     

On equivalence of derived categories

Let A be an Abelian category and B be a thick subcategory of A. Let D ^b(B) denote the derived category of cohomologically bounded chain complexes of objects in A and D _B ^b (A) denote the derived category of cohomologically bounded chain complexes of objects in A with cohomology in B. We give two if and only if conditions for equivalence of D(B) and D _B ^b (A), and we give an example where D ^b (B) and D _B ^b (A) are not equivalent.     

Measure equivalence rigidity and bi-exactness of groups

We get three types of results on measurable group theory; direct product groups of Ozawa's class S groups, wreath product groups and amalgamated free products. We prove measure equivalence factorization results on direct product groups of Ozawa's class S groups. As consequences, Monod-Shalom type orbit equivalence rigidity theorems follow. We prove that if two wreath product groups A?G, B?Γ of non-amenable exact direct product groups G, Γ with amenable bases A, B are measure equivalent, then G and Γ are measure equivalent. We get Bass-Serre rigidity results on amalgamated free products of non-amenable exact direct product groups.     

Independence number of de Bruijn graphs

In this paper, we give several exact values of the independence number of a de Bruijn graph UB(d,D) and in the other cases, we establish pertinent lower and upper bounds of this parameter. We show that asymptotically, if d is even, the ratio of the number of vertices of a greatest independent set of UB(d,D) is .     

Limit cycles for two classes of planar polynomial differential systems with uniform isochronous centers

In this article, we study the maximum number of limit cycles for two classes of planar polynomial differential systems with uniform isochronous centers. Using the first-order averaging method, we analyze how many limit cycles can bifurcate from the period solutions surrounding the centers of the considered systems when they are perturbed inside the class of homogeneous polynomial differential systems of the same degree. We show that the maximum number of limit cycles, $m$ and $m+1$, that can bifurcate from the period solutions surrounding the centers for the two classes of differential systems of degree $2m$ and degree $2m+1$, respectively. Both of the bounds can be reached for all $m$.     

2k-系整数可重集伴随等价图的计数

给出了由2k-系的整数组成的可重集的伴随等价图的个数问题,同时也给出了其补图的色等价图的个数.     

On enumeration of polynomial equivalence classes

The isomorphism of polynomials(IP),one of the hard problems in multivariate public key cryptography induces an equivalence relation on a set of systems of polynomials.Then the enumeration problem of IP consists of counting the numbers of different classes and counting the cardinality of each class that is highly related to the scale of key space for a multivariate public key cryptosystem.In this paper we show the enumeration of the equivalence classes containing ∑n-1 i=0 aiX2qi when char(Fq) = 2,which implies that these polynomials are all weak IP instances.Moreover,we study the cardinality of an equivalence class containing the binomial aX 2q i + bX 2qj(i=j) over Fqn without the restriction that char(Fq) = 2,which gives us a deeper understanding of finite geometry as a tool to investigate the enumeration problem of IP.     

Complete analytic equivalence relations

We prove that various concrete analytic equivalence relations arising in model theory or analysis are complete, i.e. maximum in the Borel reducibility ordering. The proofs use some general results concerning the wider class of analytic quasi-orders.

     

Independence concepts in evidence theory

We study three conditions of independence within evidence theory framework. The first condition refers to the selection of pairs of focal sets. The remaining two ones are related to the choice of a pair of elements, once a pair of focal sets has been selected. These three concepts allow us to formalize the ideas of lack of interaction among variables and among their (imprecise) observations. We illustrate the difference between both types of independence with simple examples about drawing balls from urns. We show that there are no implication relationships between both of them. We also study the relationships between the concepts of “independence in the selection” and “random set independence”, showing that they cannot be simultaneously satisfied, except in some very particular cases.     

分布矩阵与随机变量独立性的判定

利用离散型随机变量的联合分布矩阵,得到了离散型随机变量独立性的一种判别方法,并用实例给出了一定的应用。