Analytic and Probabilistic Combinatorics, and Long Cycles in Graphs

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

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

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