A two-vertex counterexample to color-number monotonicity
Statement
(5) Let G be a finite graph with maximum degree ∆. This problem is about choosing a random coloring from the uniform distribution. Work with Glauber dynamics: pick a site at random, choose a color at random, and try to change the color at the chosen site. If this results in a proper coloring, make the change. If not, keep the current coloring. For q ≥ ∆ + 2 it is known that this Markov chain is ergodic, i.e.,
12
that it connects the set of proper colorings. Let t = t(q) be the mixing time: the smallest time such that the total variation distance from the uniform distribution is at most 1 /e from any starting configuration. The question is: does t(q) decrease as
q increases? Even on the square lattice with n sites there are curious gaps in our knowledge: we know that t(3) is polynomial in n (Luby, Randall and Sinclair: Proc. FOCS 1995) and we know that t(q) = O(n log n) for q ≥ 6. But, for q = 4 and q = 5 we do not even have a polynomial upper bound, even though there is overwhelming numerical evidence that there is a finite correlation length, and therefore that the mixing time is O(n log n). (6) Is there a variant of k-SAT that describes the scaling properties of jamming? In other words, is k-SAT a good "Boolean idealization" of the jamming process? Should this involve k-SAT on a lattice? (See Schwartz and Middleton, Phys. Rev. E 70 (2004), 035103(R).) (7) Find a model with constraints and a phase transition, which we can perturb by "soft-ening" the constraints. Study the sensitivity of this model's behavior with respect to this perturbation. (8) In constraint satisfaction problems such as k-SAT, what are the useful response/correlation functions? Do they show singular, or power-law, behavior at the transition, analo-gous to spatial correlations and response functions in lattice systems such as the Ising model? (9) The second moment method in k-SAT gives a highly accurate lower bound for the critical density, when the approach of (Achlioptas and Moore: Proc. FOCS 2002) is refined by (Achlioptas and Peres: Proc. STOC 2003). This refinement can be thought of as adding a finite (not infinitesimal) external field which discourages lit-erals from being true. Is there any physical meaning to this value of the external field? For instance, does it minimize fluctuations in, say, the free energy at zero temperature? (10) We believe (and, in some cases, have proved) that below the satisfiability/unsatisfiability transition in k-SAT there is a "clustering" transition, in which the solutions clump together in isolated groups. It has been conjectured that this clustering phenomenon makes it hard for search algorithms to find solutions. Can we find algorithms which, in simulation, find solutions in, say, linear time, for values of k and densities at which clustering has been rigorously established? (11) (Following up on the previous question) Can we prove that clustering occurs at some density below the satisfiability transition for k = 3, 4, 5? So far we only have proofs of clustering for larger values of k.(12) Prove an order/disorder phase transition for the equilibrium statistical mechanics model of hard spheres (or hard disks). Simulation evidence of such a transition is 3
generally believed to be convincing in both cases, though the nature of the transition is controversial for disks. (13) How should we add friction to jamming? (14) Consider the Ising model on the d-dimensional lattice. Fix β (and perhaps the ex-ternal field strength h) and consider Glauber dynamics. The cutoff phenomenon in Markov chains refers to the existence of a time at which the total variation distance from the stationary (Gibbs) distribution jumps from 1 to 0 in the limit where the size of the lattice goes to infinity. We ask whether this sharp cutoff exists if and only if there is a unique Gibbs state in the infinite system. (15) Give a good definition of the thermodynamic limit of k-SAT. That is, clearly define the mathematical object that corresponds to random formulas Fk(n, m = rn ) with constant density r in the limit n → ∞.(16) Consider the Ising model on a finite box in Zd. Set β > β c and no external field. With fixed boundary conditions where all the boundary sites are set to +1, it is known that Glauber dynamics can take a long time to mix if the initial state consists of a large droplet of −1's. But with a "warm start," where the initial condition consists of all +1's or is random, is the mixing time optimal, i.e., O(n log n) where n is the number of sites in the box?
Record
- Source
- Added
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.