Analytic and Probabilistic Combinatorics, and Long Cycles in Graphs

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

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.