Torpid mixing of the Wang–Swendsen–Kotecký algorithm for sampling colorings

We study the problem of sampling uniformly at random from the set of k-colorings of a graph with maximum degree Δ. We focus attention on the Markov chain Monte Carlo method, particularly on a popular Markov chain for this problem, the Wang–Swendsen–Kotecký (WSK) algorithm. The second author recently proved that the WSK algorithm quickly converges to the desired distribution when k11Δ/6. We study how far these positive results can be extended in general. In this note we prove the first non-trivial results on when the WSK algorithm takes exponentially long to reach the stationary distribution and is thus called torpidly mixing. In particular, we show that the WSK algorithm is torpidly mixing on a family of bipartite graphs when 3k<Δ/(20logΔ), and on a family of planar graphs for any number of colors. We also give a family of graphs for which, despite their small chromatic number, the WSK algorithm is not ergodic when kΔ/2, provided k is larger than some absolute constant k₀.     

Applications of Feller–Reuter–Riley Transition Functions

A Feller–Reuter–Riley function is a Markov transition function whose corresponding semigroup maps the set of the real-valued continuous functions vanishing at infinity into itself. The aim of this paper is to investigate applications of such functions in the dual problem, Markov branching processes, and the Williams-matrix. The remarkable property of a Feller–Reuter–Riley function is that it is a Feller minimal transition function with a stable q-matrix. By using this property we are able to prove that, in the theory of branching processes, the branching property is equivalent to the requirement that the corresponding transition function satisfies the Kolmogorov forward equations associated with a stable q-matrix. It follows that the probabilistic definition and the analytic definition for Markov branching processes are actually equivalent. Also, by using this property, together with the Resolvent Decomposition Theorem, a simple analytical proof of the Williams' existence theorem with respect to the Williams-matrix is obtained. The close link between the dual problem and the Feller–Reuter–Riley transition functions is revealed. It enables us to prove that a dual transition function must satisfy the Kolmogorov forward equations. A necessary and sufficient condition for a dual transition function satisfying the Kolmogorov backward equations is also provided.     

Interpolation approximations based on Gauss–Lobatto–Legendre–Birkhoff quadrature

We derive in this paper the asymptotic estimates of the nodes and weights of the Gauss–Lobatto–Legendre–Birkhoff (GLLB) quadrature formula, and obtain optimal error estimates for the associated GLLB interpolation in Jacobi weighted Sobolev spaces. We also present a user-oriented implementation of the pseudospectral methods based on the GLLB quadrature nodes for Neumann problems. This approach allows an exact imposition of Neumann boundary conditions, and is as efficient as the pseudospectral methods based on Gauss–Lobatto quadrature for PDEs with Dirichlet boundary conditions.     

On the poisedness of Bojanov–Xu interpolation

In this paper, we consider the bivariate Hermite interpolation introduced by Bojanov and Xu [SIAM J. Numer. Anal. 39(5) (2002) 1780–1793]. The nodes of the interpolation with Π_2k-δ, where δ=0 or 1, are the intersection points of 2k+1 distinct rays from the origin with a multiset of k+1-δ concentric circles. Parameters are the values and successive radial derivatives, whenever the corresponding circle is multiple. The poisedness of this interpolation was proved only for the set of equidistant rays [Bojanov and Xu, 2002] and its counterparts with other conic sections [Hakopian and Ismail, East J. Approx. 9 (2003) 251–267]. We show that the poisedness of this (k+1-δ)(2k+1) dimensional Hermite interpolation problem is equivalent to the poisedness of certain 2k+1 dimensional Lagrange interpolation problems. Then the poisedness of Bojanov–Xu interpolation for a wide family of sets of rays satisfying some simple conditions is established. Our results hold also with above circles replaced by ellipses, hyperbolas, and pairs of parallel lines.Next a conjecture [Hakopian and Ismail, J. Approx. Theory 116 (2002) 76–99] concerning a poisedness relation between the Bojanov–Xu interpolation, with set of rays symmetric about x-axis, and certain univariate lacunary interpolations is established. At the end the poisedness for a wide class of lacunary interpolations is obtained.     

Interpolation of functions from generalized Paley–Wiener spaces

We consider the problem of reconstruction of functions f from generalized Paley–Wiener spaces in terms of their values on complete interpolating sequence {z_n}. We characterize the set of data sequences {f(z_n)} and exhibit an explicit solution to the problem. Our development involves the solution of a particular problem.     

Paley–Wiener and Boas theorems for singular Sturm–Liouville integral transforms

This paper deals with a class of integral transforms arising from a singular Sturm–Liouville problem y″−q(x)y=−λy, x(a,b), in the limit-point case at one end or both ends of the interval (a,b). The paper completely solves the problem of characterization of the image of a function that has compact support (Paley–Wiener theorem) and also of a function that vanishes on some interval (Boas problem) under this class of transforms. The characterizations are obtained with no restriction on q(x) other than being locally integrable.     

Marcinkiewicz–Zygmund inequalities

We study a generalization of the classical Marcinkiewicz–Zygmund inequalities. We relate this problem to the sampling sequences in the Paley–Wiener space and by using this analogy we give sharp necessary and sufficient computable conditions for a family of points to satisfy the Marcinkiewicz–Zygmund inequalities.     

Enumeration and limit laws for series–parallel graphs

We show that the number g_n of labelled series–parallel graphs on n vertices is asymptotically g_ngn^−5/2γⁿn!, where γ and g are explicit computable constants. We show that the number of edges in random series–parallel graphs is asymptotically normal with linear mean and variance, and that it is sharply concentrated around its expected value. Similar results are proved for labelled outerplanar graphs and for graphs not containing K_2,3 as a minor.     

A unifying look at the Apostolico–Giancarlo string-matching algorithm

String matching is the problem of finding all the occurrences of a pattern in a text. We present a new method to compute the combinatorial shift function (“matching shift”) of the well-known Boyer–Moore string matching algorithm. This method implies the computation of the length of the longest suffixes of the pattern ending at each position in this pattern. These values constituted an extra-preprocessing for a variant of the Boyer–Moore algorithm designed by Apostolico and Giancarlo. We give here a new presentation of this algorithm that avoids extra preprocessing together with a tight bound of 1.5n character comparisons (where n is the length of the text).     

Using fractional primal–dual to schedule split intervals with demands

We consider the problem of scheduling jobs that are given as groups of non-intersecting intervals on the real line. Each job j is associated with a t-interval (which consists of up to t segments, for some t≥1), a demand, d_j[0,1], and a weight, w(j). A feasible schedule is a collection of jobs such that, for every , the total demand of the jobs in the schedule whose t-interval contains s does not exceed 1. Our goal is to find a feasible schedule that maximizes the total weight of scheduled jobs.We present a 6t-approximation algorithm for this problem that uses a novel extension of the primal–dual schema called fractional primal–dual. The first step in a fractional primal–dual r-approximation algorithm is to compute an optimal solution, x^*, of an LP relaxation of the problem. Next, the algorithm produces an integral primal solution x, and a new LP, denoted by P′, that has the same objective function as the original problem, but contains inequalities that may not be valid with respect to the original problem. Moreover, x^* is a feasible solution of P′. The algorithm also computes a solution y to the dual of P′. The solution x is r-approximate, since its weight is bounded by the value of y divided by r.We present a fractional local ratio interpretation of our 6t-approximation algorithm. We also discuss the connection between fractional primal–dual and the fractional local ratio technique. Specifically, we show that the former is the primal–dual manifestation of the latter.     

Classical solutions to Navier–Stokes equations for nonhomogeneous incompressible fluids with non-negative densities

We study the Navier–Stokes equations for nonhomogeneous incompressible fluids in a bounded domain Ω of R³. We first prove the existence and uniqueness of local classical solutions to the initial boundary value problem of linear Stokes equations and then we obtain the existence and uniqueness of local classical solutions to the Navier–Stokes equations with vacuum under the assumption that the data satisfies a natural compatibility condition.     

Approximation algorithms for MAX–MIN tiling

The MAX–MIN tiling problem is as follows. We are given A[1,…,n][1,…,n], a two-dimensional array where each entry A[i][j] stores a non-negative number. Define a tile of A to be a subarray A[ℓ,…,r][t,…,b] of A, the weight of a tile to be the sum of all array entries in it, and a tiling of A to be a collection of tiles of A such that each entry A[i][j] is contained in exactly one tile. Given a weight bound W the goal of our MAX–MIN tiling problem is to find a tiling of A such that: (1) each tile is of weight at least W (the MIN condition), and (2) the number of tiles is maximized (the MAX condition). The MAX–MIN tiling problem is known to be NP-hard; here, we present first non-trivial approximations algorithms for solving it.     

Generalization of the Gale–Ryser Theorem

We prove an inequality for the Kostka–Foulkes polynomials K_λ,μ(q) and give a criteria for the existence of a unique configuration of the given type (λ, μ). As a corollary, we obtain a nontrivial lower bound for the Kostka numbers which is a generalization the Gale–Ryser theorem on an existence of a (0,1)-matrix with given sums of rows and columns. A new proof of the Berenstein–Zelevinsky weight-multiplicity-one criteria is given.     

On the thermodynamic limit for Hartree–Fock type models

We continue here our study [10–13] of the thermodynamic limit for various models of Quantum Chemistry, this time focusing on the Hartree–Fock type models. For the reduced Hartree–Fock models, we prove the existence of the thermodynamic limit for the energy per unit volume. We also define a periodic problem associated to the Hartree–Fock model, and prove that it is well-posed.     

Initial–boundary value problems for conservation laws with source terms and the Degasperis–Procesi equation

We consider conservation laws with source terms in a bounded domain with Dirichlet boundary conditions. We first prove the existence of a strong trace at the boundary in order to provide a simple formulation of the entropy boundary condition. Equipped with this formulation, we go on to establish the well-posedness of entropy solutions to the initial–boundary value problem. The proof utilizes the kinetic formulation and the averaging lemma. Finally, we make use of these results to demonstrate the well-posedness in a class of discontinuous solutions to the initial–boundary value problem for the Degasperis–Procesi shallow water equation, which is a third order nonlinear dispersive equation that can be rewritten in the form of a nonlinear conservation law with a nonlocal source term.     

A countable Fréchet–Urysohn space of uncountable character

We shall construct a countable Fréchet–Urysohn α₄ not α₃ space X such that all finite powers of X are Fréchet–Urysohn.     

Generalizations of the Nikodym boundedness and Vitali–Hahn–Saks theorems

Generalizations of the Nikodym boundedness and Vitali–Hahn–Saks theorems for scalar-valued measures on rings of sets that are in general not σ-rings are presented. As a consequence, the rings of subsets of N with density zero and uniform density zero are shown to have the Nikodym property. In addition, vector measure generalizations of the Vitali–Hahn–Saks theorem are given.     

A new proof of the Gasca–Maeztu conjecture for

In the Chung–Yao construction of poised nodes for bivariate polynomial interpolation [K.C. Chung, T.H. Yao, On lattices admitting unique Lagrange interpolations, SIAM J. Numer. Anal. 14 (1977) 735–743], the interpolation nodes are intersection points of some lines. The Berzolari–Radon construction [L. Berzolari, Sulla determinazione di una curva o di una superficie algebrica e su alcune questioni di postulazione, Lomb. Ist. Rend. 47 (2) (1914) 556–564; J. Radon, Zur mechanischen Kubatur, Monatsh. Math. 52 (1948) 286–300] seems to be more general, since in this case the nodes of interpolation lie (almost) arbitrarily on some lines. In 1982 Gasca and Maeztu conjectured that every poised set allowing the Chung–Yao construction is of Berzolari–Radon type. So far, this conjecture has been confirmed only for polynomial spaces of small total degree n≤4, the result being evident for n≤2 and not hard to see for n=3. For the case n=4 two proofs are known: one of J.R. Busch [J.R. Busch, A note on Lagrange interpolation in , Rev. Un. Mat. Argentina 36 (1990) 33–38], and another of J.M. Carnicer and M. Gasca [J.M. Carnicer, M. Gasca, A conjecture on multivariate polynomial interpolation, Rev. R. Acad. Cienc. Exactas Fís. Nat. (Esp.) Ser. A Mat. 95 (2001) 145–153]. Here we present a third proof which seems to be more geometric in nature and perhaps easier. We also present some results for the case of n=5 and for general n which might be useful for later consideration of the problem.     

Uniqueness of solutions to inverse Sturm–Liouville problems with potential using three spectra

The uniqueness of solutions to two inverse Sturm–Liouville problems using three spectra is proven, based on the uniqueness of the solution-pair to an overdetermined Goursat–Cauchy boundary value problem. We discuss the uniqueness of the potential for a Dirichlet boundary condition at an arbitrary interior node, and for a Robin boundary condition at an arbitrary interior node, whereas at the exterior nodes we have Dirichlet boundary conditions in both situations. Here we are particularly concerned with potential functions that are L²(0,a).