On the open set condition for self-similar fractals

For self-similar sets, the existence of a feasible open set is a natural separation condition which expresses geometric as well as measure-theoretic properties. We give a constructive approach by defining a central open set and characterizing those points which do not belong to feasible open sets.

     

The extreme set condition of a graph

Let G be a simple graph. The size of any largest matching in G is called the matching number of G and is denoted by ν(G). Define the deficiency of G, def(G), by the equation def(G)=|V(G)|−2ν(G). A set of points X in G is called an extreme set if def(G−X)=def(G)+|X|. Let c₀(G) denote the number of the odd components of G. A set of points X in G is called a barrier if c₀(G−X)=def(G)+|X|. In this paper, we obtain the following:

(1) Let G be a simple graph containing an independent set of size i, where i2. If X is extreme in G for every independent set X of size i in G, then there exists a perfect matching in G.

(2) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is extreme in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|i, and |Γ(Y)||U|−i+m+1 for any Y U, |Y|=m (1mi−1).

(3) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is a barrier in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|=i, and |Γ(Y)|m+1 for any Y U, |Y|=m (1mi−1).     

Covering the edge set of a directed graph with trees

Let G be a finite directed graph, and s a specified vertex in G, such that the edge set of G can be covered with a collection of spanning arborescences rooted at s. The paper establishes the cardinality m of a minimum such collection. It is also shown that when G is acyclic, m equals the maximum of the invalences of vertices in G.     

A NEGATIVE ANSWER TO A CONJECTURE ON SELF-SIMILAR SETS WITH OPEN SET CONDITION

Zhou and Feng posed a conjecture on self-similar set in 2004. In this paper, a self-similar set is constructed which has a best covering but its natural covering is not a best one. Thus, we indeed give a negative answer to the conjecture.     

When is the union of two unit intervals a self-similar set satisfying the open set condition?

Let U _λ be the union of two unit intervals with gap λ. We show that U _λ is a self-similar set satisfying the open set condition if and only if U _λ can tile an interval by finitely many of its affine copies (admitting different dilations). Furthermore, each such λ can be characterized as the spectrum of an irreducible double word which represents a tiling pattern. Some further considerations of the set of all such λ’s, as well as the corresponding tiling patterns, are given. The first author was partially supported by the RGC grant and the direct grant in CUHK, Fok Ying Tong Education Foundation and NSFC (10571100). The second author was partially supported by NSFC (70371074) and NFSC (10571104).     

Normalized graph Laplacians for directed graphs

We consider the normalized Laplace operator for directed graphs with positive and negative edge weights. This generalization of the normalized Laplace operator for undirected graphs is used to characterize directed acyclic graphs. Moreover, we identify certain structural properties of the underlying graph with extremal eigenvalues of the normalized Laplace operator. We prove comparison theorems that establish a relationship between the eigenvalues of directed graphs and certain undirected graphs. This relationship is used to derive eigenvalue estimates for directed graphs. Finally we introduce the concept of neighborhood graphs for directed graphs and use it to obtain further eigenvalue estimates.     

A sufficient condition for the existence of an anti-directed 2-factor in a directed graph

Let D be a directed graph with vertex set V, arc set A, and order n. The graph underlyingD is the graph obtained from D by replacing each arc (u,v)∈A by an undirected edge {u,v} and then replacing each double edge by a single edge. An anti-directed (hamiltonian) cycleH in D is a (hamiltonian) cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. An anti-directed 2-factor in D is a vertex-disjoint collection of anti-directed cycles in D that span V. It was proved in Busch et al. (submitted for publication) [3] that if the indegree and the outdegree of each vertex of D is greater than then D contains an anti-directed Hamilton cycle. In this paper we prove that given a directed graph D, the problem of determining whether D has an anti-directed 2-factor is NP-complete, and we use a proof technique similar to the one used in Busch et al. (submitted for publication) [3] to prove that if the indegree and the outdegree of each vertex of D is greater than then D contains an anti-directed 2-factor.     

Disjoint directed quadrilaterals in a directed graph

Let D be a directed graph of order 4k, where k is a positive integer. Suppose that the minimum degree of D is at least 6k ? 2. We show that D contains k disjoint directed quadrilaterals with only one exception. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On the exact Hausdorff measure of a class of self-similar sets satisfying open set condition

In this paper,we provide a new effective method for computing the exact value of Hausdorff measures of a class of self-similar sets satisfying the open set condition(OSC).As applications,we discuss a self-similar Cantor set satisfying OSC and give a simple method for computing its exact Hausdorff measure.     

The Myerson value for directed graph games

A directed graph game consists of a cooperative game with transferable utility and a digraph which describes limited cooperation and the dominance relation among the players. Under the assumption that only coalitions of strongly connected players are able to fully cooperate, we introduce the digraph-restricted game in which a non-strongly connected coalition can only realize the sum of the worths of its strong components. The Myerson value for directed graph games is defined as the Shapley value of the digraph-restricted game. We establish axiomatic characterizations of the Myerson value for directed graph games by strong component efficiency and either fairness or bi-fairness.     

A rigid graph for every set

A graph G is called rigid if the identical mapping V(G)→V(G) is the only homomorphism G→G. In this note we give a simple construction of a rigid oriented graph on every set. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 108–110, 2002     

Multifractal formalism for self-similar measures with weak separation condition

For any self-similar measure μ on satisfying the weak separation condition, we show that there exists an open ball U₀ with μ(U₀)>0 such that the distribution of μ, restricted on U₀, is controlled by the products of a family of non-negative matrices, and hence μ|_U0 satisfies a kind of quasi-product property. Furthermore, the multifractal formalism for μ|_U0 is valid on the whole range of dimension spectrum, regardless of whether there are phase transitions. Moreover the dimension spectra of μ and μ|_U0 coincide for q0. This result unifies and improves many of the recent works on the multifractal structure of self-similar measures with overlaps.     

Asymmetric directed graph coloring games

This note generalizes the (a,b)-coloring game and the (a,b)-marking game which were introduced by Kierstead [H.A. Kierstead, Asymmetric graph coloring games, J. Graph Theory 48 (2005) 169-185] for undirected graphs to directed graphs. We prove that the (a,b)-chromatic and (a,b)-coloring number for the class of orientations of forests is b+2 if b≤a, and infinity otherwise. From these results we deduce upper bounds for the (a,b)-coloring number of oriented outerplanar graphs and of orientations of graphs embeddable in a surface with bounded girth.     

A median-type condition for graph tiling

Komlós (2000) determined the asymptotically optimal minimum degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph. We show that the minimum degree condition can be relaxed in the sense that we require only a given fraction of vertices to have the prescribed degree.     

Packing rooted directed cuts in a weighted directed graph

A simple algorithm is described for constructing a maximum packing of cuts directed away from a distinguished vertex, called the root, in a directed graph, each of whose edges has a nonnegative weight, and it is shown that the maximum packing value is equal to the weight of a minimum-weight spanning arborescence directed away from the root.     

Partition of a directed bipartite graph into two directed cycles

Let D = (V₁, V₂; A) be a directed bipartite graph with |V₁| = |V₂| = n 2. Suppose that d_D(x) + d_D(y) 3n + 1 for all x ε V₁ and y ε V₂. Then D contains two vertex-disjoint directed cycles of lengths 2n₁ and 2n₂, respectively, for any positive integer partition n = n₁ + n₂. Moreover, the condition is sharp for even n and nearly sharp for odd n.     

Projections of self-similar sets with no separation condition

Two natural symplectic constructions, the Lagrangian suspension and Seidel’s quantum representation of the fundamental group of the group of Hamiltonian diffeomorphisms, Ham(M), with (M, ω) a monotone symplectic manifold, admit categorifications as actions of the fundamental groupoid Π(Ham(M)) on a cobordism category recently introduced in [BC14] and, respectively, on a monotone variant of the derived Fukaya category. We show that the functor constructed in [BC14] that maps the cobordism category to the derived Fukaya category is equivariant with respect to these actions.