Analytic and Probabilistic Combinatorics, and Long Cycles in Graphs

分析和概率组合学以及图中的长周期

• 批准号: RGPIN-2015-04010
• 负责人: Gao, Zhicheng
• 金额: $ 1.02万
• 依托单位: Carleton University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=651517
• 关键词: Analytic; Probabilistic; Combinatorics; Long; Cycles

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.**

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