1 / <Emphasis Type="Italic">n</Emphasis> Expansion for the Number of Matchings on Regular Graphs and Monomer-Dimer Entropy

Using a 1 / n expansion, that is an expansion in descending powers of n, for the number of matchings in regular graphs with 2n vertices, we study the monomer-dimer entropy for two classes of graphs. We study the difference between the extensive monomer-dimer entropy of a random r-regular graph G (bipartite or not) with 2n vertices and the average extensive entropy of r-regular graphs with 2n vertices, in the limit \(n \rightarrow \infty \). We find a series expansion for it in the numbers of cycles; with probability 1 it converges for dimer density \(p < 1\) and, for G bipartite, it diverges as \(|\mathrm{ln}(1-p)|\) for \(p \rightarrow 1\). In the case of regular lattices, we similarly expand the difference between the specific monomer-dimer entropy on a lattice and the one on the Bethe lattice; we write down its Taylor expansion in powers of p through the order 10, expressed in terms of the number of totally reducible walks which are not tree-like. We prove through order 6 that its expansion coefficients in powers of p are non-negative.     

An Asymptotic Expansion and Recursive Inequalities for the Monomer-Dimer Problem

Let λ _d (p) be the p monomer-dimer entropy on the d-dimensional integer lattice ℤ ^d , where p∈[0,1] is the dimer density. We give upper and lower bounds for λ _d (p) in terms of expressions involving λ _d−1(q). The upper bound is based on a conjecture claiming that the p monomer-dimer entropy of an infinite subset of ℤ ^d is bounded above by λ _d (p). We compute the first three terms in the formal asymptotic expansion of λ _d (p) in powers of  \frac1d\frac{1}{d}. We prove that the lower asymptotic matching conjecture is satisfied for λ _d (p). Converted to a power series in p, our “formal” expansion shows remarkable validity in low dimensions, d=1,2,3, in which dimensions we give some numerical studies.     

Neighborhood preferences in random matching problems

We consider a class of random matching problems where the distance between two points has a probability law which, for a small distance l, goes like l^r. In the framework of the cavity method, in the limit of an infinite number of points, we derive equations for p_k, the probability for some given point to be matched to its kth nearest neighbor in the optimal configuration. These equations are solved in two limiting cases: r = 0 -- where we recover p _k = 1/2^k, as numerically conjectured by Houdayer et al. and recently rigorously proved by Aldous -- and r→ + ∞. For 0 < r < + ∞, we are not able to solve the equations analytically, but we compute the leading behavior of p_k for large k. Received 14 February 2001     

The Replica Symmetric Solution for Potts Models on d-Regular Graphs

We establish an explicit formula for the limiting free energy density (log-partition function divided by the number of vertices) for ferromagnetic Potts models on uniformly sparse graph sequences converging locally to the d-regular tree for d even, covering all temperature regimes. This formula coincides with the Bethe free energy functional evaluated at a suitable fixed point of the belief propagation recursion on the d-regular tree, the so-called replica symmetric solution. For uniformly random d-regular graphs we further show that the replica symmetric Bethe formula is an upper bound for the asymptotic free energy for any model with permissive interactions.     

Monomer-dimer model on a scale-free small-world network

The explicit determination of the number of monomer-dimer arrangements on a network is a theoretical challenge, and exact solutions to monomer-dimer problem are available only for few limiting graphs with a single monomer on the boundary, e.g., rectangular lattice and quartic lattice; however, analytical research (even numerical result) for monomer-dimer problem on scale-free small-world networks is still missing despite the fact that a vast variety of real systems display simultaneously scale-free and small-world structures. In this paper, we address the monomer-dimer problem defined on a scale-free small-world network and obtain the exact formula for the number of all possible monomer-dimer arrangements on the network, based on which we also determine the asymptotic growth constant of the number of monomer-dimer arrangements in the network. We show that the obtained asymptotic growth constant is much less than its counterparts corresponding to two-dimensional lattice and Sierpinski fractal having the same average degree as the studied network, which indicates from another aspect that scale-free networks have a fundamentally distinct architecture as opposed to regular lattices and fractals without power-law behavior.     

Oscillation of the NCO model

We study opinion oscillation of the nonconsensus opinion model (NCO) on graphs, and in particular on bipartite graphs. Using intensive numerical simulations, we investigate the relationship between amplitude A$A$ (the percentage of nodes whose opinions oscillate) and (p,q)$(p,q)$, which are the initial configuration fractions with opinion 1 on two sets of two bipartite graphs. Finally, for the general graph, we present several definitions and develop three propositions as regards whether an oscillation can occur or not on a certain graph.     

On the Coupling Time of the Heat-Bath Process for the Fortuin–Kasteleyn Random–Cluster Model

We consider the coupling from the past implementation of the random–cluster heat-bath process, and study its random running time, or coupling time. We focus on hypercubic lattices embedded on tori, in dimensions one to three, with cluster fugacity at least one. We make a number of conjectures regarding the asymptotic behaviour of the coupling time, motivated by rigorous results in one dimension and Monte Carlo simulations in dimensions two and three. Amongst our findings, we observe that, for generic parameter values, the distribution of the appropriately standardized coupling time converges to a Gumbel distribution, and that the standard deviation of the coupling time is asymptotic to an explicit universal constant multiple of the relaxation time. Perhaps surprisingly, we observe these results to hold both off criticality, where the coupling time closely mimics the coupon collector’s problem, and also at the critical point, provided the cluster fugacity is below the value at which the transition becomes discontinuous. Finally, we consider analogous questions for the single-spin Ising heat-bath process.     

Investigation of continuous-time quantum walk via spectral distribution associated with adjacency matrix

Using the spectral distribution associated with the adjacency matrix of graphs, we introduce a new method of calculation of amplitudes of continuous-time quantum walk on some rather important graphs, such as line, cycle graph C_n, complete graph K_n, graph G_n, finite path and some other finite and infinite graphs, where all are connected with orthogonal polynomials such as Hermite, Laguerre, Tchebichef, and other orthogonal polynomials. It is shown that using the spectral distribution, one can obtain the infinite time asymptotic behavior of amplitudes simply by using the method of stationary phase approximation (WKB approximation), where as an example, the method is applied to star, two-dimensional comb lattices, infinite Hermite and Laguerre graphs. Also by using the Gauss quadrature formula one can approximate the infinite graphs with finite ones and vice versa, in order to derive large time asymptotic behavior by WKB method. Likewise, using this method, some new graphs are introduced, where their amplitudes are proportional to the product of amplitudes of some elementary graphs, even though the graphs themselves are not the same as the Cartesian product of their elementary graphs. Finally, by calculating the mean end to end distance of some infinite graphs at large enough times, it is shown that continuous-time quantum walk at different infinite graphs belong to different universality classes which are also different from those of the corresponding classical ones.     

Dynamics of Nearest-Neighbour Competitions on Graphs

Considering a collection of agents representing the vertices of a graph endowed with integer points, we study the asymptotic dynamics of the rate of the increase of their points according to a very simple rule: we randomly pick an an edge from the graph which unambiguously defines two agents we give a point the the agent with larger point with probability p and to the lagger with probability q such that \(p+q=1\). The model we present is the most general version of the nearest-neighbour competition model introduced by Ben-Naim, Vazquez and Redner. We show that the model combines aspects of hyperbolic partial differential equations—as that of a conservation law—graph colouring and hyperplane arrangements. We discuss the properties of the model for general graphs but we confine in depth study to d-dimensional tori. We present a detailed study for the ring graph, which includes a chemical potential approximation to calculate all its statistics that gives rather accurate results. The two-dimensional torus, not studied in depth as the ring, is shown to possess critical behaviour in that the asymptotic speeds arrange themselves in two-coloured islands separated by borders of three other colours and the size of the islands obey power law distribution. We also show that in the large d limit the d-dimensional torus shows inverse sine law for the distribution of asymptotic speeds.     

Percolation on Infinite Graphs and Isoperimetric Inequalities

We consider the Bernoulli bond percolation process (with parameter p) on infinite graphs and we give a general criterion for bounded degree graphs to exhibit a non-trivial percolation threshold based either on a single isoperimetric inequality if the graph has a bi-infinite geodesic, or two isoperimetric inequalities if the graph has not a bi-infinite geodesic. This new criterion extends previous criteria and brings together a large class of amenable graphs (such as regular lattices) and non-amenable graphs (such trees). We also study the finite connectivity in graphs satisfying the new general criterion and show that graphs in this class with a bi-infinite geodesic always have finite connectivity functions with exponential decay when p is sufficiently close to one. On the other hand, we show that there are graphs in the same class with no bi-infinite geodesic for which the finite connectivity decays sub-exponentially (down to polynomially) in the highly supercritical phase even for p arbitrarily close to one.     

Asymptotic Expansions for λ d of the Dimer and Monomer-Dimer Problems

In the past few years we have derived asymptotic expansions for λ _d of the dimer problem and λ _d (p) of the monomer-dimer problem. The many expansions so far computed are collected herein. We shine a light on results in two dimensions inspired by the work of M.E. Fisher. Much of the work reported here was joint with Shmuel Friedland.     

Quantization of gauge fields,graph polynomials and graph homology

We review quantization of gauge fields using algebraic properties of 3-regular graphs. We derive the Feynman integrand at n$n$ loops for a non-abelian gauge theory quantized in a covariant gauge from scalar integrands for connected 3-regular graphs, obtained from the two Symanzik polynomials.     

Thick skin in neutron/proton-rich sodium isotopes

Nucleon (both neutron and proton) density distributions of the chain of sodium isotopes are calculated using a semi-phenomenological model of nuclear density which incorporates correctly the asymptotic behaviour and the behaviour near the centre. The experimental charge root-mean-square radii and the single neutron and proton separation energies, required as input, are used. The calculated interaction cross-sections using these densities in the Glauber model agree well with the experiment. The calculated neutron rms radii r _n and the nuclear skin thickness ( r _n - r _p) closely agree with the corresponding experimental values and also are consistent with the Relativistic Hartree-Bogoliubov (RHB) calculations. Received: 24 April 2001 / Accepted: 28 June 2001     

Rigorous estimates of general mayer graphs and applications: II: Long range behaviour of graphs with two root-points

We find the asymptotic behaviour of graphs with two root-points for neutral, polar and ionized systems, we prove that the pair correlation function h(r) decays at least as fast as the potential ?(r) at small activities, when $\text{?(r) ? r}{}^{\mathrm{?n}}\text{(n>3)}$. We also describe a new approximate integral equation for h(r), in this case.     

Hadron diffractive processes: the structure of soft pomeron and colour screening

On the basis of the experimental data on diffractive processes in πp, pp and pˉp collisions at intermediate, moderately high and high energies, we restore the scattering amplitude related to the t-channel exchange by vacuum quantum numbers by taking account of the diffractive s-channel rescatterings. At intermediate and moderately high energies, the t-channel exchange amplitude turns, with a good accuracy, into an effective pomeron which renders the results of the additive quark model. At superhigh energies the scattering amplitude provides a Froissart-type behaviour, with an asymptotic universality of cross sections such as σ^tot _πp/σ^tot _pp→ 1 at s→∞. The quark structure of hadrons being taken into account at the level of constituent quarks, the cross sections of pion and proton (antiproton) in the impact parameter space of quarks, σ_π(r _1⊥, r _2⊥; s) and σ_p(r _1⊥, r _2⊥, r _3⊥; s), are found as functions of s. These cross sections implicate the phenomenon of colour screening: they tend to zero at |r _i⊥−r _k⊥|→ 0. The effective colour screening radius for pion (proton) is found for different s. The predictions for the diffractive cross sections at superhigh energies are presented. Received: 15 December 1998     

Hyperbolic Low-Dimensional Invariant Tori¶and Summations of Divergent Series

We consider a class of a priori stable quasi-integrable analytic Hamiltonian systems and study the regularity of low-dimensional hyperbolic invariant tori as functions of the perturbation parameter. We show that, under natural nonresonance conditions, such tori exist and can be identified through the maxima or minima of a suitable potential. They are analytic inside a disc centered at the origin and deprived of a region around the positive or negative real axis with a quadratic cusp at the origin. The invariant tori admit an asymptotic series at the origin with Taylor coefficients that grow at most as a power of a factorial and a remainder that to any order N is bounded by the (N+1)-st power of the argument times a power of N!. We show the existence of a summation criterion of the (generically divergent) series, in powers of the perturbation size, that represent the parametric equations of the tori by following the renormalization group methods for the resummations of perturbative series in quantum field theory. Received: 9 July 2001 / Accepted: 26 October 2001     

Diffusion Limited Aggregation on a Cylinder

We consider the DLA process on a cylinder . It is shown that this process “grows arms”, provided that the base graph G has small enough mixing time. Specifically, if the mixing time of G is at most , the time it takes the cluster to reach the m ^th layer of the cylinder is at most of order . In particular we get examples of infinite Cayley graphs of degree 5, for which the DLA cluster on these graphs has arbitrarily small density. In addition, we provide an upper bound on the rate at which the “arms” grow. This bound is valid for a large class of base graphs G, including discrete tori of dimension at least 3. It is also shown that for any base graph G, the density of the DLA process on a G-cylinder is related to the rate at which the arms of the cluster grow. This implies that for any vertex transitive G, the density of DLA on a G-cylinder is bounded by 2/3.     

Nonlinear and quantum origin of doubly infinite family of modified addition laws for fourmomenta

We show that infinite variety of Poincaré bialgebras with nontrivial classicalr-matrices generate nonsymmetric nonlinear composition laws for the fourmomenta. We also present the problem of lifting the Poincaré bialgebras to quantum Poincaré groups by using e.g. Drinfeld twist, what permits to provide the nonlinear composition law in any order of dimensionfull deformation parameterλ (from physical reasons we can putλ=λ _p whereλ _p is the Planck length). The second infinite variety of composition laws for fourmomentum is obtained by nonlinear change of basis in Poincaré algebra, which can be performed for any choice of coalgebraic sector, with classical or quantum coproduct. In last Section we propose some modification of Hopf algebra scheme with Casimir-dependent deformation parameter, which can help to resolve the problem of consistent passage to macroscopic classical limit. Presented at the 11th Colloquium “Quantum Groups and Integrable Systems”, Prague, 20–22 June 2002. Supported by KBN grant 5PO3B05620     

Extensions of Conformal Nets¶and Superselection Structures

Starting with a conformal Quantum Field Theory on the real line, we show that the dual net is still conformal with respect to a new representation of the M?bius group. We infer from this that every conformal net is normal and conormal, namely the local von Neumann algebra associated with an interval coincides with its double relative commutant inside the local von Neumann algebra associated with any larger interval. The net and the dual net give together rise to an infinite dimensional symmetry group, of which we study a class of positive energy irreducible representations. We mention how superselection sectors extend to the dual net and we illustrate by examples how, in general, this process generates solitonic sectors. We describe the free theories associated with the lowest weight n representations of , showing that they violate 3-regularity for $n > 2. When n≥ 2, we obtain examples of non M?bius-covariant sectors of a 3-regular (non 4-regular) net. Received: 19 March 1997 / Accepted: 1 July 1997     

From 2D hyperbolic forests to 3D Euclidean entangled thickets

A method is developed to construct and analyse a wide class of graphs embedded in Euclidean 3D space, including multiply-connected and entangled examples. The graphs are derived via embeddings of infinite families of trees (forests) in the hyperbolic plane, and subsequent folding into triply periodic minimal surfaces, including the P, D, gyroid and H surfaces. Some of these graphs are natural generalisations of bicontinuous topologies to bi-, tri-, quadra- and octa-continuous forms. Interwoven layer graphs and periodic sets of finite clusters also emerge from the algorithm. Many of the graphs are chiral. The generated graphs are compared with some organo-metallic molecular crystals with multiple frameworks and molecular mesophases found in copolymer melts. Received 10 December 1999