Discrete Problems

点击翻译按钮获取中文摘要

The project addresses problems covering a rather broadspectrum of discrete mathematics (DM), some drawn from relatedareas such as statistical mechanics (SM), probability, andtheoretical computer science (TCS). A common thread in many of these problems is:one is given a probability distribution on some large discrete space (e.g. independent sets in, or proper colorings of, a graph), and wants to know whether behavior in one part of the system can significantly affect behavior in other, distant parts. The loose term``long range effects" (LRE's) is used for such interactions.Both strong and weak LRE's are of interest:For SM what's wanted is, more often than not,strong LRE's, usually under the name ``phase transition" (PT).In very recent work, the investigator and his student DavidGalvin used mainly combinatorial ideas to settle onemuch-studied question in this area (concerning PT's in the``hard-core lattice gas model"), and a particular hope atpresent is that ideas from this work, and, more generally,the investigator's combinatorial perspective, will lead toprogress on various more or less related questions.From the perspectives of DM and TCS, on the other hand,weak LRE's are often desirable, e.g. because of theirconnections with rapid mixing of Markov chains (a topicof major interest in TCS), and because in combinatorialapplications of probability, systems with sufficientlyweak LRE's can sometimes substitute for probability spacesbased on purely independent choices. (This again involvesthe hard-core model, which arises in surprisingly diversemathematical contexts.)Speaking very generally, the (main part of the) project aimsat understanding the degree of order or disorder in variouslarge random systems, for instance the extent to which theglobal structure of a physical system can be predicted fromknowledge about interactions between neighboring particles.In recent years, random systems similar to those used to modelphysical reality have played increasingly important rolesin TCS and DM, partly because they can be helpful in analyzing(algorithmically and/or theoretically) even non-random problemsin these areas; and there has been an increasing realization ofthe degree to which the issues arising in these three disciplinesare related. One major theme of the present project is an interestin applying ideas and methods across mathematical boundaries:especially in using ideas from the investigator's core area (DM)to attack problems in SM and TCS, but also in bringing an increasing familiarity with techniques from the latter areas tobear on several problems of longstanding interest in DM.