Analytic and Probabilistic Combinatorics, and Long Cycles in Graphs

随着信息时代数据的爆炸性增长，我们需要处理规模不断增长的离散结构。分析与概率组合学是离散数学的一个分支，它利用分析和概率论中的工具来研究大型离散结构的性质。此外，对于应用中出现的许多离散结构，图也是非常有用的模型。在这个建议中，我讨论了分析和概率组合学以及图论中的一些具体问题。许多组合结构都是由支撑物和部件组成的。单词中的游程和排列中的循环是两个众所周知的例子。我的建议中的一个问题涉及一些与零件尺寸相关的随机变量的分布，如最大零件尺寸、不同零件尺寸的数量和给定尺寸的零件数量。*研究随机子集并的大小的问题源于许多应用，如统计抽样和有限域上的多项式。我想研究根据一些分布从给定的集合中选择的子集的并集大小的分布。*曲面地图在许多应用中都是自然出现的。例如，富勒烯(平面三次映射，每个面要么是五边形，要么是六边形)已经被化学家广泛研究，表面映射已经被量子物理学家广泛研究。我想要计算富勒烯，并探索表面地图和二叉树之间的关系。*天际线已成为数据库查询中的一个有用概念，用于在多变量数据样本中选择具有代表性的组。粗略地说，如果数据集中的点p不存在“支配”p的点，那么它就称为天际线。我的提案中提到的问题之一是，从给定的d维集估计n个随机点中天际线的预期数量，并研究d增加时的相变。*由于博彩业(包括彩票和在线博彩)的快速扩张，现在几乎到处都是碰运气的游戏。我的提案中提到的问题之一是分析Hold‘em Poker。为了找到最优(接近最优)的策略，需要进行组合、概率和博弈论分析。这也成为人工智能领域的一个热门话题。在图中寻找长圈是图论中的一个基本问题，它也有很多应用。图G的周长，记为c(G)，是G中最长圈的长度。关于c(G)的最佳下界，有两个长期悬而未决的问题，一个是关于最大度至少为4的3连通图，另一个是关于3连通三次图。目前公布的边界距离最佳边界还很远。我希望这两个问题都能得到更好的界。**

With the explosion of data in our information age,*we need to deal with discrete structures of ever-growing size. Analytic and probabilistic combinatorics is a branch of discrete mathematics which uses tools from analysis and probability theory to study the properties of large discrete structures. Also graphs serve as very useful models for many discrete structures arising from applications. In this proposal I address some specific problems in analytic and probabilistic combinatorics, and graph theory.*******Many combinatorial structures are composed of supports and parts. Runs in words and cycles in permutations are two well-known examples. One of the problems in my proposal deals with the distribution of some random variables associated with part sizes such as the maximum part size, the number of distinct part sizes, and the number of parts of a given size.*******The problem of studying the size of the union of random subsets arises from many applications such as statistical sampling and polynomials over a finite field. I would like to study the distribution of the size of the union of subsets chosen from a given set according to some distributions.*******Surface maps appear naturally in many applications. For example fullerenes (planar cubic maps such that each face is either a pentagon or a hexagon) have been studied extensively by chemists, and surface maps have been studied extensively by quantum physicists. I would like to count fullerenes and also explore relations between surface maps and binary trees.*******Skylines have emerged as a useful notion in database queries for selecting representative groups in multivariate data samples. Roughly speaking, a point p in a data set is called a skyline if there is no point in the data set which "dominates" p. One of the problems addressed in my proposal is about estimating the expected number of skylines in n random points from a given d-dimensional set and studying the phase transition as d increases.*******Due to the rapid expansion of the casino industry (including lotteries and online gaming), games of chance are now almost everywhere. One of the problems addressed in my proposal analyzes Hold'em Poker. Combinatorial, probabilistic, and game theoretical analyses are required to find the optimal (near-optimal) strategies. This has also become a hot topic in artificial intelligence.*******Finding long cycles in a graph is a fundamental problem in graph theory and it also has many applications. The circumference of a graph G, denoted by c(G), is the length of a longest cycle in G. There are two long standing open problems about the best possible lower bound for c(G), one for 3-connected graphs with maximum degree at least 4, and the other for 3-connected cubic graphs. The current published bounds are still far away from the best possible bounds. I would like to obtain better bounds for both problems.**