Cutoff for the Ising model on the lattice

Introduced in 1963, Glauber dynamics is one of the most practiced and extensively studied methods for sampling the Ising model on lattices. It is well known that at high temperatures, the time it takes this chain to mix in L ¹ on a system of size n is O(logn). Whether in this regime there is cutoff, i.e. a sharp transition in the L ¹-convergence to equilibrium, is a fundamental open problem: If so, as conjectured by Peres, it would imply that mixing occurs abruptly at (c+o(1))logn for some fixed c>0, thus providing a rigorous stopping rule for this MCMC sampler. However, obtaining the precise asymptotics of the mixing and proving cutoff can be extremely challenging even for fairly simple Markov chains. Already for the one-dimensional Ising model, showing cutoff is a longstanding open problem. We settle the above by establishing cutoff and its location at the high temperature regime of the Ising model on the lattice with periodic boundary conditions. Our results hold for any dimension and at any temperature where there is strong spatial mixing: For ?² this carries all the way to the critical temperature. Specifically, for fixed d≥1, the continuous-time Glauber dynamics for the Ising model on (?/n?) ^d with periodic boundary conditions has cutoff at (d/2λ _∞)logn, where λ _∞ is the spectral gap of the dynamics on the infinite-volume lattice. To our knowledge, this is the first time where cutoff is shown for a Markov chain where even understanding its stationary distribution is limited. The proof hinges on a new technique for translating L ¹-mixing to L ²-mixing of projections of the chain, which enables the application of logarithmic-Sobolev inequalities. The technique is general and carries to other monotone and anti-monotone spin-systems, e.g. gas hard-core, Potts, anti-ferromagentic Ising, arbitrary boundary conditions, etc.     

On the convergence of the modified overrelaxation method

The modified overrelaxation (MSOR) method is applied to a linear system Ax=b, where A has property A. We get bounds for the spectral radius of the iteration matrix of this method, and we achieve convergence conditions for the MSOR method when A is strictly diagonally dominant. We extend our conclusions to another kind of matrices—H,L,M or Stieltjes. In the last section we use the vectorial norms, getting convergence conditions for the MSOR method, when A is a block-H matrix. We also generalize a theorem of Robert's for this kind of matrices.     

Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree

Given an undirected graph with edge weights, we are asked to find an orientation, that is, an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO, and is a restricted variant of the well-known minimum makespan problem. As in previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs, and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tighter thresholds of complexity: We show that MMO is (i) in P for cactus graphs, (ii) weakly NP-hard for outerplanar graphs, and also (iii) strongly NP-hard for graphs which are both planar and bipartite. This implies the NP-hardness for P₄-bipartite, diamond-free or house-free graphs, each of which is a superclass of cactus. We also show (iv) the NP-hardness for series-parallel graphs and multi-outerplanar graphs, and (v) present a pseudo-polynomial time algorithm for graphs with bounded treewidth.     

Hyperbolicity of the invariant sets for the real polynomial maps

In this paper, the conditions under which there exits a uniformly hyperbolic invariant set for the map f_a(x) = ag(x) are studied, where a is a real parameter, and g(x) is a monic real-coefficient polynomial. It is shown that for certain parameter regions, the map has a uniformly hyperbolic invariant set on which it is topologically conjugate to the one-sided subshift of finite type for A, where ∣a∣ is sufficiently large, A is an eventually positive transition matrix, and g has at least two different real zeros or only one real zero. Further, it is proved that there exists an invariant set on which the map is topologically semiconjugate to the one-sided subshift of finite type for a particular irreducible transition matrix under certain conditions, and one type of these maps is not hyperbolic on the invariant set.     

Computing the first eigenvalue of the p-Laplacian via the inverse power method

In this paper, we discuss a new method for computing the first Dirichlet eigenvalue of the p-Laplacian inspired by the inverse power method in finite dimensional linear algebra. The iterative technique is independent of the particular method used in solving the p-Laplacian equation and therefore can be made as efficient as the latter. The method is validated theoretically for any ball in Rn if p>1 and for any bounded domain in the particular case p=2. For p>2 the method is validated numerically for the square.     

On the uniqueness of the Shapley value

L.S. Shapley [1953] showed that there is a unique value defined on the classD of all superadditive cooperative games in characteristic function form (over a finite player setN) which satisfies certain intuitively plausible axioms. Moreover, he raised the question whether an axiomatic foundation could be obtained for a value (not necessarily theShapley value) in the context of the subclassC (respectivelyC′, C″) of simple (respectively simple monotonic, simple superadditive) gamesalone. This paper shows that it is possible to do this. Theorem I gives a new simple proof ofShapley's theorem for the classG ofall games (not necessarily superadditive) overN. The proof contains a procedure for showing that the axioms also uniquely specify theShapley value when they are restricted to certain subclasses ofG, e.g.,C. In addition it provides insight intoShapley's theorem forD itself. Restricted toC′ orC″, Shapley's axioms donot specify a unique value. However it is shown in theorem II that, with a reasonable variant of one of his axioms, a unique value is obtained and, fortunately, it is just theShapley value again.     

Equivariant Pieri Rule for the homology of the affine Grassmannian

An explicit rule is given for the product of the degree two class with an arbitrary Schubert class in the torus-equivariant homology of the affine Grassmannian. In addition a Pieri rule (the Schubert expansion of the product of a special Schubert class with an arbitrary one) is established for the equivariant homology of the affine Grassmannians of SL _n and a similar formula is conjectured for Sp _2n and SO _2n+1. For SL _n the formula is explicit and positive. By a theorem of Peterson these compute certain products of Schubert classes in the torus-equivariant quantum cohomology of flag varieties. The SL _n Pieri rule is used in our recent definition of k-double Schur functions and affine double Schur functions.     

Order-preserving representations of the partitions on the finite set

A partial ordering is defined for monotone projections f: N → N, N = {1, 2,…, n}, such that the class of these mappings is a lattice which is isomorphic to the partition lattice. Thus a partition can be uniquely represented by an element of this class of mappings and the partial ordering of partitions is preserved. Algorithms for computing the join and meet of given partitions are presented.     

A condition for the strong regularity of matrices in the minimax algebra

Columns of a matrix A in the minimax algebra are called strongly linearly independent if for some b the system of equations A?x = b is uniquely solvable (cf. [3]). This paper presents a condition which is necessary and sufficient for the strong linear independence of columns of a given matrix in the minimax algebra based on a dense linearly ordered commutative group. In the case of square matrices an O(n³) method for checking this property as well as for finding at least one b such that A?x = b is uniquely solvable is derived. A connection with the classical assignment problem is formulated.     

On the continuity of the sharp constant in the Jackson-Stechkin inequality in the space L 2

This paper deals with the continuity of the sharp constant K(T,X) with respect to the set T in the Jackson-Stechkin inequality $E(f,L) \leqslant K(T,X)\omega (f,T,X),$ , where E(f,L) is the best approximation of the function f ∈ X by elements of the subspace L ? X, and ω is a modulus of continuity, in the case where the space L ²( $\mathbb{T}^d $ , ?) is taken for X and the subspace of functions g ∈ L ²( $\mathbb{T}^d $ , ?), for L. In particular, it is proved that the sharp constant in the Jackson-Stechkin inequality is continuous in the case where L is the space of trigonometric polynomials of nth order and the modulus of continuity ω is the classical modulus of continuity of rth order.     

Some tests for the covariance matrix with fewer observations than the dimension under non-normality

This article analyzes whether some existing tests for the p×p covariance matrix Σ of the N independent identically distributed observation vectors work under non-normality. We focus on three hypotheses testing problems: (1) testing for sphericity, that is, the covariance matrix Σ is proportional to an identity matrix I_p; (2) the covariance matrix Σ is an identity matrix I_p; and (3) the covariance matrix is a diagonal matrix. It is shown that the tests proposed by Srivastava (2005) for the above three problems are robust under the non-normality assumption made in this article irrespective of whether N≤p or N≥p, but (N,p)→∞, and N/p may go to zero or infinity. Results are asymptotic and it may be noted that they may not hold for finite (N,p).     

On the determination of the coefficients in the viscoelasticity equations

For the integrodifferential viscoelasticity equations, we study the problem of determining the coefficients of the equations and the kernels occurring in the integral terms of the system of equations. The density of the medium is assumed to be given. We suppose that the inhomogeneity support of the sought functions is included in some compact domain B ₀. We consider a series of inverse problems in which an impulse source is concentrated at the points y of the boundary of B ₀. The point y is the parameter of the problem. The given information about the solution is the trace of the solution to the Cauchy problem with zero initial data. This trace is given on the boundary of B ₀ for all y ∈ ?B ₀ and for a finite time interval. The main result of the article consists in obtaining uniqueness theorems for a solution to the initial inverse problem.     

Lower bounds for the clique and the chromatic numbers of a graph

G is any simple graph with m edges and n vertices where these vertices have vertex degrees d(1)≥d(2)≥?≥d(n), respectively. General algorithms for the exact calculation of χ(G), the chromatic number of G, are almost always of ‘branch and bound’ type; this type of algorithm requires an easily constructed lower bound for χ(G). In this paper it is shown that, for a number of such bounds (many of which are described here for the first time), the bound does not exceed cl(G) where cl(G) is the clique number of G.In 1972 Myers and Liu showed that cl(G)≥n?(n?2m?n). Here we show that cl(G)≥ n?[n?(2m?n)(1+c²_v)^{$\text{1}\text{2}$}], where c_v is the vertex degree coefficient of variation in G, that cl(G)≥ Bondy's constructive lower bound for χ(G), and that cl(G)≥n?(n?W(G)), where W(G) is the largest positive integer such that W(G)≤d(W(G)+1) [W(G)+1 is the Welsh and Powell upper bound for χ(G)]. It is also shown that cl(G)+$\text{1}\text{3}$>n?(n?L(G))≥n?(n?λ₁) and that χ(G)≥ n?(n?λ₁); λ₁ is the largest eigenvalue of A, the adjacency matrix of G, and L(G) is a newly defined single-valued function of G similar to W(G) in its construction from the vertex degree sequence of G [L(G)≥W(G)].Finally, a ‘greedy’ lower bound for cl(G) is constructed from A and it is shown that this lower bound is never less than Bondy's bound; thereafter, for 150 random graphs with varying numbers of vertices and edge densities, the values of lower bounds given in this paper are listed, thereby illustrating that this last greedily obtained lower bound is almost always better than each of the other bounds.     

On the completeness of the spherical vector wave functions

The set of the regular and radiating spherical vector wave functions (SVWF) is shown to be complete in L₂(S) where S is a Lyapunov surface. The completeness fails when k² is an eigenvalue of the Dirichlet problem for the Helmholtz equation (▽² + k²)F = 0 in the region D_i bounded by S. On the other hand, the set of radiating SVWF is shown to be complete for all values of k². It is also proved that any vector function, which is continuous in D_i + S and satisfies the Helmholtz equation in D_i., can be approximated uniformly in D_i and in the mean square sense on S by a sequence of linear combinations of the regular SVWF (assuming the set is complete). Similar results are obtained for the exterior problem with the set of radiating SVWF. These results are extended to the set composed of the regular and radiating SVWF on two nonintersecting Lyapunov surfaces, one of which encloses the other.     

On the influence of the prior distribution in image reconstruction

Two measures of the influence of the prior distribution p(θ) in Bayes estimation are proposed. Both involve comparing with alternative prior distributions proportional to p(θ) ^s , for s  ≥  0. The first one, the influence curve for the prior distribution, is simply the curve of parameter values which are obtained as estimates when the estimation is made using p(θ) ^s instead of p(θ). It measures the overall influence of the prior. The second one, it the influence rate for the prior, is the derivative of this curve at s = 1, and quantifies the sensitivity to small changes or inaccuracies in the prior distribution. We give a simple formula for the influence rate in marginal posterior mean estimation, and discuss how the influence measures may be computed and used in image processing with Markov random field priors. The results are applied to an image reconstruction problem from visual field testing and to a stylized image analysis problem.     

On the uniqueness of the lyapunov scaling factors

A conjecture of Hershkowitz and Schneider on the uniqueness of the Lyapunov scaling factors of A ∈ R^n,n is settled by proving it for n ⩽ 3 and giving a counter- example for n ⩾ 4.     

On the biggest maximally generated ideal as the conductor in the blowing up ring

Let (R, M) be a Noetherian one-dimensional local ring.C Gottlieb calls anM-primary idealI maximally generated ifμ(I)=?(R/(r)), or which is the same, ifIM=rI for somer∈M, and he also proves that if there is a maximally generated ideal inR then there is a unique biggest one (see [4]). In this paper each ring (R, M) is a local one-dimensional Cohen-Macaulay ring. LetQ be the total ring of fractions ofR, and letB(M) be the ring obtained by blowing upM, i.e.B (M)=U _i≥1 (M ⁱ :M ⁱ ) _Q . We prove in Theorem 1 that if there are maximally generated ideals inR then they are theM-primary ideals ofR which are ideals ofB(M) too. And the biggest maximally generated idealÎ ofR is the conductor ofR inB(M), i.e.(R∶B(M)) _R . We give in Theorem 3 an algorithm for findingÎ when the integral closure ofR is a local domain with the same residue field asR. In section 3 there are applications to semigroup rings. We prove thatÎ is generated by monomials in Proposition 7, and therefore semigroups are considered in the continuation. Let σ be the reduction exponent ofM, i.e. δ=min{i∶?(M ⁱ /M ⁱ⁺¹) =e(M)} wheree(M) denotes the multiplicity ofM. In Proposition 10, δ is determined, and there is also given a sufficient condition forÎ not to be a power ofM. In Propositions 11 and 12Î is determined for two special cases of semigroup rings whereÎ is a power ofM.     

On an integral equation approach for the exterior Robin problem for the Helmholtz equation

A boundary integral equation for the exterior Robin problem for Helmholtz's equation is analyzed in this paper. This integral operator is not compact. A proof based on a suitable regularization of this integral operator and the Fredholm alternative for the regularized compact operator was given by other authors. In this paper, we will give a direct existence and uniqueness proof for the boundary non-compact integral equation in the space settings C^1,λ(S) and C^0,λ(S), where S is a closed bounded smooth surface.     

On the parity of the partition function

Let N be the set of all positive integers and D a subset of N. Let p(D,n) be the number of partitions of n with parts in D and let |D(x)| denote the number of elements of D not exceeding x. It is proved that if D is an infinite subset of N such that p(D,n) is even for all n?n₀, then |D(x)|?logx/log2−logn₀/log2. Moreover, if D is an infinite subset of N such that p(D,n) is odd for all n?n₀ and , then |D(x)|?logx/log2−logn₀/log2. These lower bounds are essentially the best possible.