Separation conditions for conformal iterated function systems

We extend both the weak separation condition and the finite type condition to include finite iterated function systems (IFSs) of injective C ¹ conformal contractions on compact subsets of \mathbbR^d{{\mathbb{R}}^d} . For conformal IFSs satisfying the bounded distortion property, we prove that the finite type condition implies the weak separation condition. By assuming the weak separation condition, we prove that the Hausdorff and box dimensions of the attractor are equal and, if the dimension of the attractor is α, then its α-dimensional Hausdorff measure is positive and finite. We obtain a necessary and sufficient condition for the associated self-conformal measure μ to be singular. By using these we give a first example of a singular invariant measure μ that is associated with a non-linear IFS with overlaps.     

Separation conditions for conformal iterated function systems

We extend both the weak separation condition and the finite type condition to include finite iterated function systems (IFSs) of injective C ¹ conformal contractions on compact subsets of . For conformal IFSs satisfying the bounded distortion property, we prove that the finite type condition implies the weak separation condition. By assuming the weak separation condition, we prove that the Hausdorff and box dimensions of the attractor are equal and, if the dimension of the attractor is α, then its α-dimensional Hausdorff measure is positive and finite. We obtain a necessary and sufficient condition for the associated self-conformal measure μ to be singular. By using these we give a first example of a singular invariant measure μ that is associated with a non-linear IFS with overlaps. The authors are supported in part by an HKRGC grant.     

On Ramsey‐type positional games

Let K denote the graph obtained from the complete graph K_s+t by deleting the edges of some K_t‐subgraph. We prove that for each fixed s and sufficiently large t, every graph with chromatic number s+t has a K minor. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 343–350, 2010     

Invariant measures for parabolic IFS with overlaps and random continued fractions

We study parabolic iterated function systems (IFS) with overlaps on the real line. An ergodic shift-invariant measure with positive entropy on the symbolic space induces an invariant measure on the limit set of the IFS. The Hausdorff dimension of this measure equals the ratio of entropy over Lyapunov exponent if the IFS has no ``overlaps.' We focus on the overlapping case and consider parameterized families of IFS, satisfying a transversality condition. Our main result is that the invariant measure is absolutely continuous for a.e. parameter such that the entropy is greater than the Lyapunov exponent. If the entropy does not exceed the Lyapunov exponent, then their ratio gives the Hausdorff dimension of the invariant measure for a.e. parameter value, and moreover, the local dimension of the exceptional set of parameters can be estimated. These results are applied to a family of random continued fractions studied by R. Lyons. He proved singularity above a certain threshold; we show that this threshold is sharp and establish absolute continuity for a.e. parameter in some interval below the threshold.

     

On the density of 2‐colorable 3‐graphs in which any four points span at most two edges

Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)$. We improve the previously best known lower and upper bounds of 0.25682 and 3/10?ε, respectively, by showing that This implies the following new upper bound for the Turán density of K In order to establish these results we use a combination of the properties of computer‐generated extremal 3‐graphs for small n and an argument based on “super‐saturation”. Our computer results determine the exact values of ex(n, K) for n≤19 and ex₂(n, K) for n≤17, as well as the sets of extremal 3‐graphs for those n. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 105–114, 2010     

On Σ1-definable Functions Provably Total in I ∏

We prove the following theorem: Let φ(x) be a formula in the language of the theory PA^? of discretely ordered commutative rings with unit of the form ?yφ′(x,y) with φ′ and let ∈ Δ₀ and let fφ: ? → ? such that f_φ(x) = y iff φ′(x,y) & (?z < y) φ′(x,z). If I ∏ ∈(?x ≥ 0), φ then there exists a natural number K such that I ∏ ? ?y?x(x > y ? ?φ(x) < x^K). Here I ∏₁^? denotes the theory PA^? plus the scheme of induction for formulas φ(x) of the form ?yφ′(x,y) (with φ′) with φ′ ∈ Δ₀.     

A generalization of Plantholt's theorem

Let K denote the complete graph K_2n+1 with each edge replicated r times and let χ′(G) denote the chromatic index of a multigraph G. A multigraph G is critical if χ′(G) > χ′(G/e) for each edge e of G. Let S be a set of sn – 1 edges of K. We show that, for 0 < s ≦ r, G/S is critical and that χ′ (G/(S ∪{e})) = 2rn + r – s for all e ∈ E(G/S). Plantholt [M. Plantholt, The chromatic index of graphs with a spanning star. J. Graph Theory 5 (1981) 5–13] proved this result in the case when r = 1.     

Cycle decompositions of complete multigraphs

In this paper we establish necessary and sufficient conditions for decomposing the complete multigraph λK_n into cycles of length λ, and the λ‐fold complete symmetric digraph λK into directed cycles of length λ. As a corollary to these results we obtain necessary and sufficient conditions for decomposing λK_n (respectively, λK) into cycles (respectively, directed cycles) of prime length. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 85–93, 2010     

On the structures of generating iterated function systems of Cantor sets

A generating IFS of a Cantor set F is an IFS whose attractor is F. For a given Cantor set such as the middle-3rd Cantor set we consider the set of its generating IFSs. We examine the existence of a minimal generating IFS, i.e. every other generating IFS of F is an iterating of that IFS. We also study the structures of the semi-group of homogeneous generating IFSs of a Cantor set F in under the open set condition (OSC). If dim_HF<1 we prove that all generating IFSs of the set must have logarithmically commensurable contraction factors. From this Logarithmic Commensurability Theorem we derive a structure theorem for the semi-group of generating IFSs of F under the OSC. We also examine the impact of geometry on the structures of the semi-groups. Several examples will be given to illustrate the difficulty of the problem we study.     

Countable Direct Sums of Banach Spaces

Let (X_n) be a sequence of infinite-dimensional BANACH spaces. We prove that has a non-locally complete quotient if X₁ is not quasi-reflexive.     

On series of signed vectors and their rearrangements

Let x₁,…,x_m∈ \input amssym $ \Bbb R$ n be a sequence of vectors with ∥x_i∥₂ ≤ 1 for all i. It is proved that there are signs ε₁,…,ε_m = ±1 such that where C₁, C₂ are some numerical constants. It is also proved that there are signs ε,…,ε = ±1 and a permutation π of {1,…,m} such that where C^′ is some other numerical constant. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Relative isoperimetric inequalities for minimal submanifolds outside a convex set

Let C be a closed convex set in a complete simply connected Riemannian manifold M with sectional curvature bounded above by a positive constant K. Assume that Σ is a compact minimal surface outside C such that Σ is orthogonal to ?C along ?Σ∩?C and ?Σ ～ ?C is radially connected from a point p ∈ ?Σ∩?C. We introduce a modified volume M_p(Σ) of Σ and obtain a sharp isoperimetric inequality where equality holds if and only if Σ is a geodesic half disk with constant Gaussian curvature K. We also prove higher dimensional isoperimetric inequalities for minimal submanifolds outside a closed convex set in a Riemannian manifold using the modified volume.     

Sharp Sobolev Embeddings and Related Hardy Inequalities: The Sub -- Critical Case

The paper deals with sharp embeddings of the spaces B and F into rearrangement-variant spaces and related Hardy inequalities. Here (1/_p, s) belongs to the interior of the shaded invariant spaces region in the Figure     

Commuting decompositions of complete graphs

We say that two graphs G and H with the same vertex set commute if their adjacency matrices commute. In this article, we show that for any natural number r, the complete multigraph K is decomposable into commuting perfect matchings if and only if n is a 2‐power. Also, it is shown that the complete graph K_n is decomposable into commuting Hamilton cycles if and only if n is a prime number. © 2006 Wiley Periodicals, Inc. J Combin Designs     

Longtime behavior for a nonlinear wave equation arising in elasto‐plastic flow

The paper studies the longtime behavior of solutions to the initial boundary value problem (IBVP) for a nonlinear wave equation arising in elasto‐plastic flow u_tt?div{|?u|^m?1?u}?λΔu_t+Δ²u+g(u)=f(x). It proves that under rather mild conditions, the dynamical system associated with above‐mentioned IBVP possesses a global attractor, which is connected and has finite Hausdorff and fractal dimension in the phase spaces X₁=H(Ω) × L²(Ω) and X=(H³(Ω)∩H(Ω)) × H(Ω), respectively. Copyright © 2008 John Wiley & Sons, Ltd.     

NewK-automorphisms and a problem of Kakutani

A property is introduced, for 1-1 measure-preserving transformations of probability spaces, calledloose Bernoulliness (LB), which is invariant under taking factors, inducing, and tower-building. It amounts to replacing, in Ornstein’s definition ofvery weak Bernoulli, the Hamming distance on strings by a coarser metric. The main result is the construction of a transformationT ₀ which is ergodic and of entropy 0 butnot LB. On the other hand, any irrational rotationis LB. Consequently, the equivalence relation generated by inducing and tower-building (which I callKakutani equivalence, and the Russians callmonotone equivalence) has at least two distinct equivalence classes among the ergodic entropy zero transformations. A similar situation exists for ergodic positive-entropy transformations: on the one hand, any Bernoulli shift is LB, while on the other hand a non LBK-automorphism can be made by skewingT ₀ over a Bernoulli base.     

Algorithms for approximation of invariant measures for IFS

We prove convergence of two algorithms approximating invariant measures to iterated function systems numerically. We consider IFSs with finitely many continuous and injective non-overlapping maps on the unit interval. The first algorithm is a version of the Ulam algorithm for IFSs introduced by Strichartz et al. [16]. We obtain convergence in the supremum metric for distribution functions of the approximating eigen-measures to a unique invariant measure for the IFS. We have to make some modifications of the usual way of treating the Ulam algorithm due to a problem concerning approximate eigenvalues, which is part of our more general situation with weights not necessarily being related to the maps of the IFS. The second algorithm is a new recursive algorithm which is an analogue of forward step algorithms in the approximation theory of ODEs. It produces a sequence of approximating measures that converges to a unique invariant measure with geometric rate in the supremum metric. The main advantage of the recursive algorithm is that it runs much faster on a computer (using Maple) than the Ulam algorithm.Mathematics Subject Classification (2000): 37A30, 37C30, 37M25, 47A58Acknowledgement I would like to express my deep gratitude to Andreas Strömbergsson and to the anonymous referee. The referee had several very enlightening comments, which Andreas helped me to deal with. Section 4 is essentially due to Andreas and he also came up with the new Proposition 3 and helped me to improve Lemma 1. Thanks also to Svante Janson, Anders Johansson, Sten Kaijser, Robert Strichartz and Hans Wallin.     

The determining number of a Cartesian product

A set S of vertices is a determining set for a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G, denoted Det(G), is the size of a smallest determining set. This paper begins by proving that if G=G□?□G is the prime factor decomposition of a connected graph then Det(G)=max{Det(G)}. It then provides upper and lower bounds for the determining number of a Cartesian power of a prime connected graph. Further, this paper shows that Det(Q_n)=?log₂n?+1 which matches the lower bound, and that Det(K)=?log₃(2n+1)?+1 which for all n is within one of the upper bound. The paper concludes by proving that if H is prime and connected, Det(Hⁿ)=Θ(logn). © 2009 Wiley Periodicals, Inc. J Graph Theory     

On a conjecture on maximal planar sequences

Let d1 d2 dp denote the nonincreasing sequence d₁, …, d₁, d₂, …, d₂, …, d_p, …, d_p, where the term d_i appears k_i times (i = 1, 2, …, p). In this work the author proves that the maximal 2-sequences: 7³6¹5¹⁵, 7⁵6¹5¹⁷, 7⁷6¹5¹⁹ are planar graphical, in contrast to a conjecture by Schmeichel and Hakimi.     

Word maps and spectra of random graph lifts

We study here the spectra of random lifts of graphs. Let G be a finite connected graph, and let the infinite tree T be its universal cover space. If λ₁ and ρ are the spectral radii of G and T respectively, then, as shown by Friedman (Graphs Duke Math J 118 (2003), 19–35), in almost every n‐lift H of G, all “new” eigenvalues of H are ≤ O(λ ρ^1/2). Here we improve this bound to O(λ ρ^2/3). It is conjectured in (Friedman, Graphs Duke Math J 118 (2003) 19–35) that the statement holds with the bound ρ + o(1) which, if true, is tight by (Greenberg, PhD thesis, 1995). For G a bouquet with d/2 loops, our arguments yield a simple proof that almost every d‐regular graph has second eigenvalue O(d^2/3). For the bouquet, Friedman (2008). has famously proved the (nearly?) optimal bound of . Central to our work is a new analysis of formal words. Let w be a formal word in letters g,…,g. The word map associated with w maps the permutations σ₁,…,σ_k ∈ S_n to the permutation obtained by replacing for each i, every occurrence of g_i in w by σ_i. We investigate the random variable X that counts the fixed points in this permutation when the σ_i are selected uniformly at random. The analysis of the expectation ??(X) suggests a categorization of formal words which considerably extends the dichotomy of primitive vs. imprimitive words. A major ingredient of a our work is a second categorization of formal words with the same property. We establish some results and make a few conjectures about the relation between the two categorizations. These conjectures suggest a possible approach to (a slightly weaker version of) Friedman's conjecture. As an aside, we obtain a new conceptual and relatively simple proof of a theorem of A. Nica (Nica, Random Struct Algorithms 5 (1994), 703–730), which determines, for every fixed w, the limit distribution (as n →∞) of X. A surprising aspect of this theorem is that the answer depends only on the largest integer d so that w = u^d for some word u. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010