Discrete Problems

离散问题杰夫·卡恩研究者对离散数学和相关领域的一系列不同问题感兴趣。考虑的主题包括：(1)偏序集。(这包括对部分信息下排序的几个经典问题的新方法。一个主要的主题是关注各种新参数的行为，目的是获得对偏序集线性扩展的神秘空间的全面理解。(2)随机矩阵。(这里的中心问题是关于在固定有限域上的高维向量空间中，从固定权值的向量集合中均匀独立绘制的向量之间的第一依赖关系。J. Komlos和研究者最近的工作解决了有限域上稀疏随机矩阵的几个问题，预计在该工作中发展的思想将与当前的问题相关。(3)图属性的随机化复杂度。(这里的基本问题是R.M. Karp关于决策树算法中随机化的威力的一个老猜想。研究者提出了一种方法来解决这个问题，除其他外，这导致了随机图经典领域的一系列新问题。(4)熵与核心模型。(这里的一个主要问题是在d维整数晶格上估计硬核晶格气体模型的临界活度。希望这个问题，以及其他几个问题，可以使用在提议者和他的学生A. Lawrenz的早期工作中开发的熵方法来解决。(5) Kasteleyn的渗流问题。（范登伯格（J. van den Berg）和这位提议者最近的工作为证明卡斯特琳的简单但强大的相关性猜想带来了希望。）(6) Chvatal和Frankl的猜想。（研究者从有限集理论中提出了解决这两个臭名昭著的老“极值”问题的新方法。）这里讨论的许多问题都是计算机科学或统计物理学感兴趣的。特别是，(1)和(3)涉及基本算法问题（如排序和搜索）的内在复杂性（即程序效率的理论限制）的基本问题；而(4)和(5)主要处理的是，粗略地说，物理系统中的信息传播。从纯粹的数学角度来看，所有这些都是有趣的：每一个都集中在一个或多个问题上，而当前的方法已经被证明是严重不足的，因此，重大的进步需要重大的新思想。对于所考虑的大多数问题，提出了新的方法。一个共同的主题是将其他数学领域（如熵、几何、傅立叶分析）的思想应用于离散问题。相反，有一种可能性，特别是在(4)和(5)中，可以把离散的思想引入到迄今为止主要由其他学科的人研究的问题中去。

DISCRETE PROBLEMSJEFF KAHNThe investigator is interested in a diverse set of problems in discrete mathematics and related areas. Topics considered include: (1) Partially ordered sets. (This includes new approaches to several classical questions about sorting under partial information. One main theme focuses on the behavior of various new parameters, with the intention of gaining a global understanding of the mysterious space of linear extensions of a poset.) (2) Random matrices. (Central here are questions about the first dependency among vectors drawn uniformly and independently from the set of vectors of a fixed weight in a high-dimensional vector space over a fixed finite field. Recent work of J. Komlos and the investigator settled several issues concerning sparse random matrices over finite fields, and it is expected that the ideas developed in that work will be relevant to the present questions.) (3) Randomized complexity of graph properties. (The basic problem here is an old conjecture of R.M. Karp concerning the power of randomization in decision tree algorithms. The investigator suggests an approach to this which, inter alia, leads to a range of new questions in the classical area of random graphs.) (4) Entropy and the hard-core model. (One main issue here is estimation of the critical activity for the hard-core lattice gas model on the d-dimensional integer lattice. It is hoped that this, as well as several other problems, can be attacked using an entropy method developed in earlier work of the proposer and his student A. Lawrenz.) (5) A percolation problem of Kasteleyn. (Recent work of J. van den Berg and the proposer gives hope of a proof of Kasteleyn's simple but powerful correlation conjecture.) (6) Conjectures of Chvatal and Frankl. (The investigator suggests novel approaches to these two notorious old "extremal" problems from the theory of finite sets.)Many of the question addressed here are of interest for computer science or statistical physics. In particular, (1) and (3) are concerned with fundamental questions about the intrinsic complexity of (that is, theoretical limits on the efficiency of procedures for) basic algorithmic problems such as sorting and searching; while those in (4) and (5) deal especially with, roughly speaking, the spread of information in physical systems. All are also of interest on purely mathematical grounds: each is centered on one or more problems against which current methods have proved woefully inadequate, so that significant progress requires significant new ideas. New approaches are proposed for most of the problems considered. One common theme is the application ideas from other areas of mathematics (e.g. entropy, geometry, Fourier analysis) to discrete problems. Conversely, there is the possibility, particularly in (4) and (5), of bringing discrete ideas to bear on problems which until now have mainly been studied by people in other disciplines.