Improved inapproximability results for counting independent sets in the hard‐core model

We study the computational complexity of approximately counting the number of independent sets of a graph with maximum degree Δ. More generally, for an input graph and an activity , we are interested in the quantity defined as the sum over independent sets I weighted as . In statistical physics, is the partition function for the hard‐core model, which is an idealized model of a gas where the particles have non‐negligible size. Recently, an interesting phase transition was shown to occur for the complexity of approximating the partition function. Weitz showed an FPAS for the partition function for any graph of maximum degree Δ when Δ is constant and . The quantity is the critical point for the so‐called uniqueness threshold on the infinite, regular tree of degree Δ. On the other side, Sly proved that there does not exist efficient (randomized) approximation algorithms for , unless , for some function . We remove the upper bound in the assumptions of Sly's result for , that is, we show that there does not exist efficient randomized approximation algorithms for all for and . Sly's inapproximability result uses a clever reduction, combined with a second‐moment analysis of Mossel, Weitz and Wormald which prove torpid mixing of the Glauber dynamics for sampling from the associated Gibbs distribution on almost every regular graph of degree Δ for the same range of λ as in Sly's result. We extend Sly's result by improving upon the technical work of Mossel et al., via a more detailed analysis of independent sets in random regular graphs. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 78–110, 2014     

The mixing time of Glauber dynamics for coloring regular trees

We consider Metropolis Glauber dynamics for sampling proper q‐colorings of the n‐vertex complete b‐ary tree when 3 ≤ q ≤ b/(2lnb). We give both upper and lower bounds on the mixing time. Our upper bound is n^{O(b/ log b)} and our lower bound is n^{Ω(b/(q log b))}, where the constants implicit in the O() and Ω() notation do not depend upon n, q or b. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs

Recent results have shown that the Glauber dynamics for graph colorings has optimal mixing time when (i) the graph is triangle‐free and Δ‐regular and the number of colors k is a small constant fraction smaller than 2Δ, or (ii) the graph has maximum degree Δ and k=2Δ. We extend both these results to prove that the Glauber dynamics has optimal mixing time when the graph has maximum degree Δ and the number of colors is a small constant fraction smaller than 2Δ. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 98–114, 2002     

Mixing of the Glauber dynamics for the ferromagnetic Potts model

We present several results on the mixing time of the Glauber dynamics for sampling from the Gibbs distribution in the ferromagnetic Potts model. At a fixed temperature and interaction strength, we study the interplay between the maximum degree (Δ) of the underlying graph and the number of colours or spins (q) in determining whether the dynamics mixes rapidly or not. We find a lower bound L on the number of colours such that Glauber dynamics is rapidly mixing if at least L colours are used. We give a closely‐matching upper bound U on the number of colours such that with probability that tends to 1, the Glauber dynamics mixes slowly on random Δ‐regular graphs when at most U colours are used. We show that our bounds can be improved if we restrict attention to certain types of graphs of maximum degree Δ, e.g. toroidal grids for Δ = 4. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 21–52, 2016     

Tunneling of the hard‐core model on finite triangular lattices

We consider the hard‐core model on finite triangular lattices with Metropolis dynamics. Under suitable conditions on the triangular lattice sizes, this interacting particle system has 3 maximum‐occupancy configurations and we investigate its high‐fugacity behavior by studying tunneling times, that is, the first hitting times between these maximum‐occupancy configurations, and the mixing time. The proof method relies on the analysis of the corresponding state space using geometrical and combinatorial properties of the hard‐core configurations on finite triangular lattices, in combination with known results for first hitting times of Metropolis Markov chains in the equivalent zero‐temperature limit. In particular, we show how the order of magnitude of the expected tunneling times depends on the triangular lattice sizes in the low‐temperature regime and prove the asymptotic exponentiality of the rescaled tunneling time leveraging the intrinsic symmetry of the state space.     

On large‐girth regular graphs and random processes on trees

We study various classes of random processes defined on the regular tree T_d that are invariant under the automorphism group of T_d. The most important ones are factor of i.i.d. processes (randomized local algorithms), branching Markov chains and a new class that we call typical processes. Using Glauber dynamics on processes we give a sufficient condition for a branching Markov chain to be factor of i.i.d.     

s‐Regular cubic graphs as coverings of the complete bipartite graph K3,3

A graph is s‐regular if its automorphism group acts freely and transitively on the set of s‐arcs. An infinite family of cubic 1‐regular graphs was constructed in [10], as cyclic coverings of the three‐dimensional Hypercube. In this paper, we classify the s‐regular cyclic coverings of the complete bipartite graph K_3,3 for each ≥ 1 whose fibre‐preserving automorphism subgroups act arc‐transitively. As a result, a new infinite family of cubic 1‐regular graphs is constructed. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 101–112, 2004     

Slow dynamics for the hyperbolic Cahn‐Hilliard equation in one‐space dimension

The aim of this paper is to study the metastable properties of the solutions to a hyperbolic relaxation of the classic Cahn‐Hilliard equation in one‐space dimension, subject to either Neumann or Dirichlet boundary conditions. To perform this goal, we make use of an “energy approach," already proposed for various evolution PDEs, including the Allen‐Cahn and the Cahn‐Hilliard equations. In particular, we shall prove that certain solutions maintain a N‐transition layer structure for a very long time, thus proving their metastable dynamics. More precisely, we will show that, for an exponentially long time, such solutions are very close to piecewise constant functions assuming only the minimal points of the potential, with a finitely number of transition layers, which move with an exponentially small velocity.     

Enumerating the orientable 2‐cell imbeddings of complete bipartite graphs

A formula is developed for the number of congruence classes of 2‐cell imbeddings of complete bipartite graphs in closed orientable surfaces. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 77–90, 1999     

Swendsen‐Wang dynamics for general graphs in the tree uniqueness region

The Swendsen‐Wang (SW) dynamics is a popular Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising model on a graph G = (V,E). The dynamics is conjectured to converge to equilibrium in O(|V|^1/4) steps at any (inverse) temperature β, yet there are few results providing o(|V|) upper bounds. We prove fast convergence of the SW dynamics on general graphs in the tree uniqueness region. In particular, when β < β_c(d) where β_c(d) denotes the uniqueness/nonuniqueness threshold on infinite d‐regular trees, we prove that the relaxation time (i.e., the inverse spectral gap) of the SW dynamics is Θ(1) on any graph of maximum degree d ≥ 3. Our proof utilizes a monotone version of the SW dynamics which only updates isolated vertices. We establish that this variant of the SW dynamics has mixing time and relaxation time Θ(1) on any graph of maximum degree d for all β < β_c(d). Our proof technology can be applied to general monotone Markov chains, including for example the heat‐bath block dynamics, for which we obtain new tight mixing time bounds.     

Sharp bounds for the number of 3‐independent partitions and the chromaticity of bipartite graphs

Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let ??^?s(p,q) (resp., ??₂^?s(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph K_p,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ ?? ^?s(p,q) and 0 ≤ s ≤ (p ? 1)(q ? 1) (resp., G ∈ ?? ₂^?s(p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ^?s(p,q) (resp., G ∈ ?? ₂^?s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ??^?s_i(p+i,q?i) where max and s_i = s ? i(p?q+i) (resp., a subset of ??₂^?s(p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from K_p,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001     

Mathematical model for the dynamics of visceral leishmaniasis–malaria co‐infection

A mathematical model to understand the dynamics of malaria–visceral leishmaniasis co‐infection is proposed and analyzed. Results show that both diseases can be eliminated if R₀, the basic reproduction number of the co‐infection, is less than unity, and the system undergoes a backward bifurcation where an endemic equilibrium co‐exists with the disease‐free equilibrium when one of R_m or R_l, the basic reproduction numbers of malaria‐only and visceral leishmaniasis‐only, is precisely less than unity. Results also show that in the case of maximum protection against visceral leishmaniasis (VL), the disease‐free equilibrium is globally asymptotically stable if malaria patients are protected from VL infection; similarly, in the case of maximum protection against malaria, the disease‐free equilibrium is globally asymptotically stable if VL and post‐kala‐azar dermal leishmaniasis patients and the recovered humans after VL are protected from malaria infection. Numerical results show that if R_m and R_l are greater than unity, then we have co‐existence of both disease at an endemic equilibrium, and malaria incidence is higher than visceral leishmaniasis incidence at steady state. Copyright © 2016 John Wiley & Sons, Ltd.     

A note on the girth‐doubling construction for polygonal graphs

A near‐polygonal graph is a graph Γ which has a set ?? of m‐cycles for some positive integer m such that each 2‐path of Γ is contained in exactly one cycle in ??. If m is the girth of Γ then the graph is called polygonal. Given a polygonal graph Γ of valency r and girth m, Archdeacon and Perkel proved the existence of a polygonal graph Γ₂ of valency r and girth 2m. We will show that this construction can be extended to one that yields a polygonal graph Γ₃ of valency r and girth 3m, but that making the cycles any longer with this construction does not yield a polygonal graph. We also show that if Aut(Γ) is 2‐arc transitive, so is Aut(Γ_k) for k = 2, 3. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 246‐254, 2011     

Improvements on the density of maximal 1‐planar graphs

A graph is 1‐planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1‐planar drawing is called 1‐plane. A graph is maximal 1‐planar (1‐plane), if we cannot add any missing edge so that the resulting graph is still 1‐planar (1‐plane). Brandenburg et al. showed that there are maximal 1‐planar graphs with only edges and maximal 1‐plane graphs with only edges. On the other hand, they showed that a maximal 1‐planar graph has at least edges, and a maximal 1‐plane graph has at least edges. We improve both lower bounds to .     

Global dynamics for a model of a class of continuous‐time dynamical systems

In this paper, the global asympotic behavior of solutions of a class of continuous‐time dynamical system is studied. Not only do we obtain the ultimate boundedness of solutions of the system but we also obtain the rate of the trajectories of the system going from the exterior of the trapping set to the interior of the trapping set, which can be applied to study chaotic control and chaotic synchronization of the system. Copyright © 2015 John Wiley & Sons, Ltd.     

Emergent dynamics of the first‐order stochastic Cucker‐Smale model and application to finance

In this paper, we study stochastic aggregation properties of the financial model for the N‐asset price process whose dynamics is modeled by the weakly geometric Brownian motions with stochastic drifts. For the temporal evolution of stochastic components of drift coefficients, we employ a stochastic first‐order Cucker‐Smale model with additive noises. The asset price processes are weakly interacting via the stochastic components of drift coefficients. For the aggregation estimates, we use the macro‐micro decomposition of the fluctuations around the average process and show that the fluctuations around the average value satisfies a practical aggregation estimate over a time‐independent symmetric network topology so that we can control the differences of drift coefficients by tuning the coupling strength. We provide numerical examples and compare them with our analytical results. We also discuss some financial implications of our proposed model.     

Mixing times for the Swapping Algorithm on the Blume‐Emery‐Griffiths model

We analyze the so called Swapping Algorithm, a parallel version of the well‐known Metropolis‐Hastings algorithm, on the mean‐field version of the Blume‐Emery‐Griffiths model in statistical mechanics. This model has two parameters and depending on their choice, the model exhibits either a first, or a second order phase transition. In agreement with a conjecture by Bhatnagar and Randall we find that the Swapping Algorithm mixes rapidly in presence of a second order phase transition, while becoming slow when the phase transition is first order. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 38–77, 2014     

The impact of constant effort harvesting on the dynamics of a discrete‐time contest competition model

In this paper, we study a general discrete‐time model representing the dynamics of a contest competition species with constant effort exploitation. In particular, we consider the difference equation x _{n +1}=x _n f (x _{n ?k} )?h x _n where h >0, k ∈{0,1}, and the density dependent function f satisfies certain conditions that are typical of a contest competition. The harvesting parameter h is considered as the main parameter, and its effect on the general dynamics of the model is investigated. In the absence of delay in the recruitment (k =0), we show the effect of h on the stability, the maximum sustainable yield, the persistence of solutions, and how the intraspecific competition change from contest to scramble competition. When the delay in recruitment is 1 (k =1), we show that a Neimark‐Sacker bifurcation occurs, and the obtained invariant curve is supercritical. Furthermore, we give a characterization of the persistent set.     

Global well‐posedness for free boundary problem of the Oldroyd‐B model fluid flow

In this paper, we prove the global well‐posedness of non‐Newtonian viscous fluid flow of the Oldroyd‐B model with free surface in a bounded domain of N‐dimensional Euclidean space . The assumption of the problem is that the initial data are small enough and orthogonal to rigid motions. Copyright © 2015 John Wiley & Sons, Ltd.