On a strong metric on the space of copulas and its induced dependence measure

Using the one-to-one correspondence between copulas and Markov operators on L¹([0,1]) and expressing the Markov operators in terms of regular conditional distributions (Markov kernels) allows to define a metric D₁ on the space of copulas C that is a metrization of the strong operator topology of the corresponding Markov operators. It is shown that the resulting metric space (C,D₁) is complete and separable and that the induced dependence measure ζ₁, defined as a scalar times the D₁-distance to the product copula Π, has various good properties. In particular the class of copulas that have maximum D₁-distance to the product copula is exactly the class of completely dependent copulas, i.e. copulas induced by Lebesgue-measure preserving transformations on [0,1]. Hence, in contrast to the uniform distance d_∞, Π cannot be approximated arbitrarily well by completely dependent copulas with respect to D₁. The interrelation between D₁ and the so-called ∂-convergence by Mikusinski and Taylor as well as the interrelation between ζ₁ and the mutual dependence measure ω by Siburg and Stoimenov is analyzed. ζ₁ is calculated for some well-known parametric families of copulas and an application to singular copulas induced by certain Iterated Functions Systems is given.     

Longest cycles in k-connected graphs with given independence number

The Chvátal–Erd?s Theorem states that every graph whose connectivity is at least its independence number has a spanning cycle. In 1976, Fouquet and Jolivet conjectured an extension: If G is an n-vertex k-connected graph with independence number a, and a?k, then G has a cycle with length at least . We prove this conjecture.     

Acyclic directed graphs representing independence models

In this paper we study the problem of representing probabilistic independence models, in particular those closed under graphoid properties. We focus on acyclic directed graph (DAG): a new algorithm to build a DAG, given an ordering among random variables, is described and peculiarities and advantages of this approach are discussed. Moreover, we provide a necessary and sufficient condition for the existence of a perfect map representing an independence model and we describe an algorithm based on this characterization.     

Upper Embeddability,Girth and the Degree-Sum of Nonadjacent Vertices

Let G be a 2-edge-connected simple graph with girth g, independence number α(G), and if one of the following two conditions holds

Longest Cycles in 3-connected Graphs with Given Independence Number

Fouquet and Jolivet conjectured that a k-connected graph of order n and independence number α ≥ k has a cycle of length at least [Fouquet and Jolivet, Problèmes combinatoires et théorie des graphes Orsay (1976), Problems, page 438]. Here we prove this conjecture for k=3.     

Generalized homothetic biorders

In this paper, we study the binary relations R on a nonempty N^∗-set A which are h-independent and h-positive (cf. the introduction below). They are called homothetic positive orders. Denote by B the set of intervals of R having the form [r,+∞[ with 0<r≤+∞ or ]q,∞[ with q∈Q_≥0. It is a Q_>0-set endowed with a binary relation > extending the usual one on R_>0 (identified with a subset of B via the map r?[r,+∞[). We first prove that there exists a unique map Φ_R:A×A→B such that (for all and all ) we have Φ(mx,ny)=mn⁻¹⋅Φ(x,y) and . Then we give a characterization of the homothetic positive orders R on A such that there exist two morphisms of N^∗-sets satisfying . They are called generalized homothetic biorders. Moreover, if we impose some natural conditions on the sets u₁(A) and u₂(A), the representation (u₁,u₂) is “uniquely” determined by R. For a generalized homothetic biorder R on A, the binary relation R₁ on A defined by is a generalized homothetic weak order; i.e. there exists a morphism of N^∗-sets u:A→B such that (for all ) we have . As we did in [B. Lemaire, M. Le Menestrel, Homothetic interval orders, Discrete Math. 306 (2006) 1669-1683] for homothetic interval orders, we also write “the” representation (u₁,u₂) of R in terms of u and a twisting factor.     

The Erd?s-Lovász Tihany conjecture for quasi-line graphs

Erd?s and Lovász conjectured in 1968 that for every graph G with χ(G)>ω(G) and any two integers s,t≥2 with s+t=χ(G)+1, there is a partition (S,T) of the vertex set V(G) such that χ(G[S])≥s and χ(G[T])≥t. Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.     

The independence polynomial of rooted products of graphs

A stable (or independent) set in a graph is a set of pairwise nonadjacent vertices thereof. The stability numberα(G) is the maximum size of stable sets in a graph G. The independence polynomial of G is

     

Chain hexagonal cacti: Matchings and independent sets

In this paper we consider three classes of chain hexagonal cacti and study their matching and independence related properties. Explicit recurrences are derived for their matching and independence polynomials, and explicit formulae are presented for the number of matchings and independents sets of certain types. Bivariate generating functions for the number of matchings and independent sets of certain types are also computed and then used to deduce the expected size of matchings and independent sets in chains of given length. It is shown that the extremal chain hexagonal cacti with respect to the number of matchings and of independent sets belong to one of the considered types. Possible directions of further research are discussed.