Well-covered circulant graphs

A graph is well-covered if every independent set can be extended to a maximum independent set. We show that it is co-NP-complete to determine whether an arbitrary graph is well-covered, even when restricted to the family of circulant graphs. Despite the intractability of characterizing the complete set of well-covered circulant graphs, we apply the theory of independence polynomials to show that several families of circulants are indeed well-covered. Since the lexicographic product of two well-covered circulants is also a well-covered circulant, our partial characterization theorems enable us to generate infinitely many families of well-covered circulants previously unknown in the literature.     

Dependence between two multivariate extremes

We extend the characterizations given by Takahashi (1988) for the independence and the total dependence of the univariate marginals of a multivariate extreme value distribution to its multivariate marginals. We also deal with the problem of how to measure the strength of the dependence among multivariate extremes. By presenting new definitions for the extremal coefficient, we propose measures that summarize the dependence between two multivariate extreme value distributions and preserve the main properties of the known bivariate coefficient for two univariate extreme value distributions. Finally, we illustrate these contributions to model the dependence among multivariate marginals with examples.     

Independence equivalence classes of cycles

The independence equivalence class of a graph G is the set of graphs that have the same independence polynomial as G. Beaton, Brown and Cameron (2019) found the independence equivalence classes of even cycles, and raised the problem of finding the independence equivalence class of odd cycles. The problem is completely solved in this paper.     

On NP-hardness of the clique partition—Independence number gap recognition and related problems

We show that for a graph G it is NP-hard to decide whether its independence number α(G) equals its clique partition number even when some minimum clique partition of G is given. This implies that any α(G)-upper bound provably better than is NP-hard to compute.To establish this result we use a reduction of the quasigroup completion problem (QCP, known to be NP-complete) to the maximum independent set problem. A QCP instance is satisfiable if and only if the independence number α(G) of the graph obtained within the reduction is equal to the number of holes h in the QCP instance. At the same time, the inequality always holds. Thus, QCP is satisfiable if and only if . Computing the Lovász number ?(G) we can detect QCP unsatisfiability at least when . In the other cases QCP reduces to gap recognition, with one minimum clique partition of G known.     

Complexes of directed trees and independence complexes

First we prove that certain complexes on directed acyclic graphs are shellable. Then we study independence complexes. Two theorems used for breaking and gluing such complexes are proved and applied to generalize the results by Kozlov.An interesting special case is anti-Rips complexes: a subset P of a metric space is the vertex set of the complex, and we include as a simplex each subset of P with no pair of points within distance r. For any finite subset P of R the homotopy type of the anti-Rips complex is determined.     

An Asymptotic Independence Theorem for the Number of Matchings in Graphs

Let z(G) be the number of matchings (independent edge subsets) of a graph G. For a set M of edges and/or vertices, the ratio represents the probability that a randomly picked matching of G does not contain an edge or cover a vertex that is an element of M. We provide estimates for the quotient , depending on the sizes of the disjoint sets A and B, their distance and the maximum degree of the underlying graph G. It turns out that this ratio approaches 1 as the distance of A and B tends to ∞, provided that the size of A and B and the maximum degree are bounded, showing asymptotic independence. We also provide an application of this theorem to an asymptotic enumeration problem related to the dimer-monomer model from statistical physics. This material is based upon work supported by the German Research Foundation DFG under grant number 445 SUA-113/25/0-1 and the South African National Research Foundation under grant number 65972.     

随机变量可加性及在概率论与数理统计教学中的应用

随机变量的可加性是概率论与数理统计中一个非常重要的内容,但是很多教材都没有较系统的对此问题进行讨论。本文给出了二项分布、泊松分布、正态分布、χ2分布、Γ-分布、柯西分布、复合泊松分布以及泊松过程都具有可加性,最后讨论了随机变量可加性在概率论与数理统计教学中的应用。     

Independence relations for exponential fields

We give four different independence relations on any exponential field. Each is a canonical independence relation on a suitable Abstract Elementary Class of exponential fields, showing that two of these are NSOP₁-like and non-simple, a third is stable, and the fourth is the quasiminimal pregeometry of Zilber's exponential fields, previously known to be stable (and uncountably categorical). We also characterise the fourth independence relation in terms of the third, strong independence.