Inspired by issues and intriguing questions surrounding the interplay of combinatorics and statistical physics, a DIMACS/DIMATIA workshop was held at Rutgers University. This title includes proceedings of that meeting. It is suitable for graduate students and research mathematicians interested in probabilistic graph theory and its applications.