DIMACS-DIMATIA Workshop on Graphs, Morphisms and Statistical Physics

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

Organizers:

Jarik NesetrilDIMATIA, nesetril@kam-enterprise.ms.mff.cuni.cz

Peter WinklerBell Labs, pw@lucent.com

Abstracts:

1.

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