DIMACS-DIMATIA Workshop on Graphs, Morphisms and Statistical Physics

March 19 - 21, 2001
DIMACS Center, Rutgers University, Piscataway, NJ

Jarik NesetrilDIMATIA, nesetril@kam-enterprise.ms.mff.cuni.cz
Peter WinklerBell Labs, pw@lucent.com
Presented under the auspices of Exploratory Workshops/Special Programs.



Efficient Local Search Near Phase Transitions

Stefan Boettcher, Emory University

I will introduce Extremal Optimization, a new heuristic for
finding high-quality solutions to hard optimization problems.
For most physical and combinatorial optimization studied, 
Extremal Optimization appears to be particularly successful 
near phase transitions, which is conjectured to harbor some
of the hardest instances.  In particular, numerical results
appear to verify a recent conjecture on the relation between
phase transitions in combinatorial optimization problems and
computational complexity for the case of random graph coloring
and partitioning.

2. Large Subgraphs of Random Graphs Bela Bollobas, University of Memphis and University of Cambridge We shall review a number of results concerning large subgraphs of the complete graph K_n and the cube Q_n, and will present some recent results obtained jointly with Oliver Riordan, Paul Balister, Alan Frieze, David Gamarnik and Benny Sudakov.
3. On Mixing for Random H-Colorings of the Hypercubic Lattice Christian Borgs, Microsoft Research We consider the problem of random H-colorings of rectangular subsets of the hypercubic lattice, with separate weights for each color. For a large class of graphs H we show that the weights can be chosen such that all quasi-local Markov chains have exponentially slow mixing. For most such H we also show that it is possible to find (different) weights for which the Gibbs measure has exponentially fast spatial mixing.
4. Proper Colorings of Regular Trees Graham Brightwell, London School of Economics When considering probability measures on the set of H-colorings of an infinite graph G, one of the simplest scenarios is when H is a complete unlooped graph and G is a regular tree. We concentrate on a particularly nice class of Gibbs measures which are invariant under parity-preserving automorphisms of the tree: we determine when more than one such measure exists. We also discuss the question of when there is a unique Gibbs measure, and consider extentions to other graphs H. Joint work with Peter Winkler, Bell Labs
5. A Phase Transition in the Optimum Partitioning Problem Jennifer Chayes, Microsoft Research The optimum partitioning problem is a canonical NP-complete problem of combinatorial optimization. We show that the model has a phase transition and establish the behavior of the model near the transition. In particular, we show that the phase transition is discontinuous or "first-order", in contrast to the phase transitions established in other combinatorial models such as the random graph and the 2-satisfiability problem. We also discuss recent suggestions that the order of the phase transition may be related to the hardness of the problem. No knowledge of phase transitions or particular models will be assumed in this talk. The talk represents joint work with C. Borgs and B. Pittel.
6. Counting H-homomorphisms Josep Diaz, Universitat Politecnica Catalynya In this talk we survey recent work done jointly with Maria Serna and Dimitrios Thilikos on counting H-colourings for bounded treewith graphs. As a collorary, for constant K, we get the following results: Counting the number of independent sets in a partial K tree; Computing in poly- time the chromatic polynomial of a partial K tree; Deciding the poly time whether a partial k-tree is a core; Counting the number of automorphisms of a core with treewidth at most k. We also consider the case of parametrized H-colorings, where the parameters are in a subject of V(H). We show that under certain restrictions of H, the counting is in FPT and under other restrictions the counting problem is #P-complete. Finally we state thresholds on H, for which to find an H-coloring in FPT or NP-complete.
7. Compatible Sequence and a Slow Winkler Percolation Peter Gacs, Boston University Two infinite 0-1 sequences are called compatible when it is possible to cast out O's from both in such a way that they become complementary to each other. Answering a question of Peter Winkler, we show that if two 0-1 sequences are random i.i.d. and independent from each other, with probability p of 1's, then if p is sufficiently small they are compatible with positive probability. The question is equivalent to a certain dependent percolation with a power-law behavior: the probability that the origin is blocked at distance n but not closer decreases only polynomially fast and not, as usual, exponentially.
8. List Homomorphisms Pavol Hell, Simon Fraser University Given a fixed target graph H and an input graph G together with lists L(g) from V(H), g in V(G), is there a homomorphism f:G -->H such that each f(g) is in L(g)? How many such homomorphisms are there? I will discuss algorithms for these questions and some generalizations.
9. Threshold Phenomena for Interacting or Constraint Particles Irene Hueter, University of Florida The anisotropic branching random walk (BRW) and contact process (CP) on a graph are both well described by functions of a model parameter that capture the event "first passage" of any particle to a site. On many infinite, locally finite graphs of non-Euclidean geometry,the two models exhibit a discontinuous phase transition, as the underlying parameter varies over the survival regime of the population, at which the log of the size of the population has critical exponent at most 1/2 in the symmetric case. Regular trees provide a fruitful "laboratory" for direct analysis of the CP and BRW along with their phase transitions. Studying the former process is quite a bit more challenging than the latter. Perhaps amazingly, the CP and BRW meet again at the same equation which characterizes this phase separation even though the "first passage functions" associated with each of the two models are interrelated differently.
10. Computational Complexity and Phase Transitions? Gabriel Istrate, Los Alamos National Laboratory I study the existence of sharp thresholds for the class of generalized satisfiability problems introduced by Schaefer (STOC'78). Specifically, I investigate this problem for the particular class of clausal constraints, and obtain a complete characterization of such problems that have a sharp threshold. Problems with a coarse threshold can be predicted with high probability outside the critical region by a single,"trivial" satisfiability procedure. Thus, in this case the lack of a phase transition DOES have algorithmic implications.
11. Solution of the Higher Spin Exchange Hamiltonian Jacob Katriel, Technion - Israel Institute of Technology The representation theory of the symmetric group is used to study the spin-S exchange-interaction model of ferromagnetism within the infinite range approximation. The 2S order parameters are determined by the row lengths of the Young diagram that specifies the free energy extrema. The set of solutions of the order parameter equations has been fully explored. Stability analysis shows that one of the solutions represents the absolute minimum and describes the thermodynamically stable state. This solution coincides with the mean-field solution due to Chen (Phys. Rev. B 46, 8323 (1992)). The other non-trivial solutions correspond to saddle points in the free-energy surface, with consecutively increasing indices.
11. Potts Antiferromagnet: The Case of Entropic Contours? Roman Kotecky, Charles University We discuss the idea that the existence of the expected phase transition for 3-colouring of some lattice (for example, 3-dimensional cubic lattice) could be proven with the help of "entropic contours" that are responsible for the "stiffness" when switching between different patterns. An example of a particular planar lattice where this strategy really yields the proof is discussed and the links with low temperature Potts antiferromagnet (possibly with degenerated spins - colouring with a general complete 3-partite graph) and its behaviour in external field are elucidated. Partially based on a joint work with Cris Moore.
12. Cliques and Independent Sets in Graphs and Hypergraphs and Applications Hanno Lefmann, Technische Universitet Chemnitz An independent set in a graph or hypergraph G = $ with vertex set V and edge set E is a subset I of V which does not contain any edges from E. Dually, a clique C within V contains all possible edges or hyperedges. Several optimization problems can be reduced to the problem of finding in an appropriately defined graph or hypergraph an independent set or a clique of maximum cardinality. For certain optimization problems the corresponding graphs or hypergraphs behave in a `pseudorandom' way, and for such instances one can guarantee some least approximation ratio which often gives near-optimal solutions. >From the computational point, approximating reasonably the maximum cardinality of cliques or independent sets is an NP-hard problem. However, if the resulting hypergraphs behave pseudorandomly, the existence of certain large substructures can be proved by probabilistic methods. Moreover, derandomization techniques can be used to obtain in these cases polynomial time algorithms with guaranteed quality of the solutions. One can hope that some of these techniques might be applied also to certain problems in statistical physics and related areas.
13. The Pfaffian Approach to the Ising Problem and the Dimer Problem in 2-Dimensional and 3-Dimensional Lattices Martin Loebl, Georgia Institute of Technology We show that the partition function of the Ising problem and the dimer problem in a finite 3-dimensional cubic lattice may be expressed using expectation of determinants (Pfaffians) naturally associated with the cubic lattice. The main method used in the proof is theory of Pfaffian orientations developed by Galluccio and Loebl. The theory also leads to efficient algorithm for max cut, exact matching and Ising problem for graphs embeddable on arbitrary fixed orientable surface.
14. Information Flow on Trees Elchanan Mossel, Microsoft Research We consider a process in which information is flowing from a given root node on a tree network T, where each edge is an independent copy of some channel M. We focus on the following question: For which chains can one use tree networks in order to distinguish between states? For all b, we'll construct for the 2-level b-ary tree a chain for which: 1. The data at the root is independent from the data at the boundary. 2. When B > b is large, the tree network distinguishes between states for the B-ary tree and any number of levels. These constructions are closely related to classical constructions of secret-sharing protocols. Partially based on a joint work with Yuval Peres.
15. Denial of Service Attacks and the Internet Power Law Kihong Park, Purdue University Denial-of-service (DoS) attack on the Internet is a pressing problem. In this work, we describe and evaluate route-based distributed packet filtering (DPF), a novel approach to distributed DoS (DDoS) attack prevention. We show that there is an intimate relationship between the effectiveness of DPF at mitigating DDoS attacks and power-law network topology. We evaluate performance using Internet autonomous system as well as artificially generated topologies.
16. Rapid Mixing for Glauber Dynamics Without Uniqueness of Gibbs States Yuval Peres, U.C. Berkeley According to conventional wisdome, uniqueness of Gibbs states for the Ising model on an infinite graph is closely related, and perhaps equivalent, to rapid mixing of the Glauber dynamics on finite subgraphs. We show that there is an interval of temperatures where the relaxation time (i.e. the inverse spectral gap) for Glauber dynamics on a finite binary tree of $n$ vertices is of order $n$ (as rapid as can be), yet there are multiple Gibbs states on the infinte tree. Moreover, on finite trees and some other"hyperbolic" graphs, at any positive temperature, the mixing time for Glauber dynamics is polynomial in the number of vertices. Joint work with Claire Kenyon and Elchanan Mossel.
17. Large Independent Sets and 3-Colorings of 4-Regular Hamiltonian Graphs Gert Sabidussi, Universite de Montreal In the spirit of Erdos-Fleischner-Stiebitz "cycle plus triangles theorem" (any 4-regular graph which consists of a hamiltonian cycle and edge-disjoint triangles is 3-colorable) we consider 4-regular hamiltonian graphs (G,H) in which the edges not on the hamiltonian cycle H form non-selfintersecting cycles of equal length. Is such a graph 3-colorable? Does it contain an independent set of size n/3, where n is the order of G? (If G is 3-colorable, it does.) Does it contain an independent set of size K, for fixed K? Not surprisingly, these problems turn out to be NP-complete.
18. A Sharp Threshold for Network Reliability Benny Sudakov, Institute for Advanced Study One of the most popular abstract models in network reliability problems is the following. Given a graph G with n vertices and a real p between 0 and 1, where p may depend on G, a random subgraph G_p of G is obtained by keeping each edge of G with probability p, independently. Denote the probability that G_p is connected by f(G,p). For a fixed positive constant x<1 and a graph G, let p_x denote the (unique) value of p where f(G, p_x)=x. We say that a family (G_i) of graphs satisfies the "sharp threshold" property if for any fixed positive e < 1/2 lim_i p_e (G_i)/ p_{1-e}(G_i)= 1. In this talk we would like to address the following central question: "Which families of graphs possess the sharp threshold property ?" Strengthening a classical result of Margulis we prove that if the edge connectivity k(G) satisfies k(G) >> d/(log n), then the connectivity threshold in G_p is sharp. This result is asymptotically tight. This is joint work with M. Krivelevich and V. Vu
19. The Chromatic Number of the Product of Two Graphs is at Least Half the Minimum of the Fractional Chromatic Numbers of the Factors Claude Tardiff, University of Regina Hedetniemi's conjecture states that the chromatic number of a product of two graphs is equal to the minimum of the chromatic numbers of the factors. The inherent difficulty lies in finding lower bounds for the chromatic number of a product of two graphs. In fact, it is not yet known if there exists a number M such that the chromatic number of the product of any two M-chromatic graphs is at least 5. In this talk, we show that the chromatic number of a product of two graphs can be bounded below in terms of the fractional chromatic numbers of the factors. This leaves open the question as to whether some probabilistic argument can be used to improve this bound or give a lower bound in terms of the chromatic numbers of the factors.
20. Graph Homomorphisms and Long Range Order Peter Winkler, Bell Labs We define a purely combinatorial, non-probabilistic notion of long range order for graph homomorphisms, and consider when this arises in maps from a Cayley tree to a graph H with given chromatic number. This is part of a plan to study combinatorial versions of concepts from statistical physics, and in particular to link graph properties which view a graph as the target of a homomorphism to others in which it is the source.
21. Critical Resonance for Non-Intersecting Lattice Paths with Periodic Boundary David Wilson, Microsoft Research We study the "solid-liquid" phase transition in the planar dimer model, which has been used to model ferro-electric phase transitions, and may be viewed as collections of nonintersecting lattice paths. At the critical point the system has a strong long-range dependence; in particular, periodic boundary conditions give rise to a "resonance" phenomenon, where the partition function and other properties of the system depend sensitively on the shape of the domain. Joint work with Rick Kenyon.

Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on March 15, 2001.