Rapid mixing of Gibbs sampling on graphs that are sparse on average

Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd?s‐Rényi random graph G(n,d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n,d/n) is d(1 ‐ o(1)), it contains many nodes of degree of order log n/log log n. The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n,p) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature β, the mixing time of Gibbs sampling is at least n^{1+Ω(1/log log n)}. Recall that the Ising model with inverse temperature β defined on a graph G = (V,E) is the distribution over {±}^Vgiven by . High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including the Ising model and coloring. Almost all known sufficient conditions in terms of β or number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work, we show that for every d < ∞ and the Ising model defined on G (n, d/n), there exists a β_d > 0, such that for all β < β_d with probability going to 1 as n →∞, the mixing time of the dynamics on G (n, d/n) is polynomial in n. Our results are the first polynomial time mixing results proven for a natural model on G (n, d/n) for d > 1 where the parameters of the model do not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). Our proof exploits in novel ways the local tree like structure of Erd?s‐Rényi random graphs, comparison and block dynamics arguments and a recent result of Weitz. Our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub‐graph is a tree union at most O(log n) edges and where for each simple path in N(v) the sum of the vertex degrees along the path is O(log n). Moreover, our result apply also in the case of arbitrary external fields and provide the first FPRAS for sampling the Ising distribution in this case. We finally present a non Markov Chain algorithm for sampling the distribution which is effective for a wider range of parameters. In particular, for G(n, d/n) it applies for all external fields and β < β_d, where d tanh(β_d) = 1 is the critical point for decay of correlation for the Ising model on G(n, d/n). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Complete assignments of the 1H and 13C NMR spectra of 9,10-didehydro retinoic acids

A new class of retinoic acids was synthesized containing a 9,10-rigid bond. 1H and 13C NMR spectra were assigned for eight new compounds (all-E, 13Z) containing a carboxylic acid or tertiobutylester polar end group. Assignments were based on the combination of one- and two-dimensional experiments (APT, COSY, HMBC).     

On the 3-restricted edge connectivity of permutation graphs

An edge cut W of a connected graph G is a k-restricted edge cut if G−W is disconnected, and every component of G−W has at least k vertices. The k-restricted edge connectivity is defined as the minimum cardinality over all k-restricted edge cuts. A permutation graph is obtained by taking two disjoint copies of a graph and adding a perfect matching between the two copies. The k-restricted edge connectivity of a permutation graph is upper bounded by the so-called minimum k-edge degree. In this paper some sufficient conditions guaranteeing optimal k-restricted edge connectivity and super k-restricted edge connectivity for permutation graphs are presented for k=2,3.     

Note on the m-step competition numbers of paths and cycles

Since Cohen introduced the competition graph in 1968, the competition graph has been studied widely and many variations of it have been discussed. In 2000, Cho, Kim and Nam defined and studied the m-step competition graph and computed the 2-step competition numbers of paths and cycles. Recently, Ho gave bounds for the m-step competition numbers of paths and cycles. In this paper we continue to study the m-step competition numbers of paths and cycles, partially improve the results of Ho on the upper bounds of the m-step competition numbers of paths and cycles, and show that a conjecture posed by Ho is not true.     

Corrigendum to “Extending homeomorphisms from punctured surfaces to handlebodies” [Topology Appl. 155 (6) (2008) 610–621]

We correct the statements of Theorems 9 and 10 of [A. Cattabriga, M. Mulazzani, Extending homeomorphisms from punctured surfaces to handlebodies, Topology Appl. 155 (2008) 610–621], by adding missing generators, and improve the statement of Theorem 10, by removing some redundant generators.     

Ordinal machines and admissible recursion theory

We generalize standard Turing machines, which work in time ω on a tape of length ω, to α-machines with time α and tape length α, for α some limit ordinal. We show that this provides a simple machine model adequate for classical admissible recursion theory as developed by G. Sacks and his school. For α an admissible ordinal, the basic notions of α-recursive or α-recursively enumerable are equivalent to being computable or computably enumerable by an α-machine, respectively. We emphasize the algorithmic approach to admissible recursion theory by indicating how the proof of the Sacks–Simpson theorem, i.e., the solution of Post’s problem in α-recursion theory, could be based on α-machines, without involving constructibility theory.     

Solutions of Navier equations and their representation structure

Navier equations are used to describe the deformation of a homogeneous, isotropic and linear elastic medium in the absence of body forces. Mathematically, the system is a natural vector -invariant generalization of the classical Laplace equation. In this paper, we decompose the space of polynomial solutions of Navier equations into a direct sum of irreducible -submodules and construct an explicit basis for each irreducible summand. Moreover, we explicitly solve the initial value problems for Navier equations and their wave-type extension—Lamé equations by Fourier expansion and Xu's method of solving flag partial differential equations. Our work might be counted as a continuation of Olver's important work on the algebraic study of elasticity in a certain sense.     

LOCAL TIME ANALYSIS OF ADDITIVE LEVY PROCESSES WITH DIFFERENT L(E)VY EXPONENTS

Let X1 XN be independent, classical Levy processes on R^d with Levy exponents ψ1,…, ψN, respectively. The corresponding additive Levy process is defined as the following N-parameter random field on R^d, X（t） △= X1（t1） ＋ ... ＋ XN（tN）, At∈N. Under mild regularity conditions on the ψi＇s, we derive estimate for the local and uniform moduli of continuity of local times of X = {X（t）; t ∈R^N}.     

Anti-periodic solutions for a class of nonlinear th-order differential equations with delays

In this paper, we use the Leray–Schauder degree theory to establish new results on the existence and uniqueness of anti-periodic solutions for a class of nonlinear nth-order differential equations with delays of the form

x⁽ⁿ⁾(t)+f(t,x⁽ⁿ⁻¹⁾(t))+g(t,x(t−τ(t)))=e(t).