Extremal and Probabilistic Graph Theory

极值概率图论

• 批准号: 2746743
• 金额: --
• 依托单位: University of Cambridge
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2022
• 资助国家: 英国
• 起止时间: 2022 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2746743
• 关键词: Extremal; Probabilistic; Graph; Theory

Denote by Hom(H, G) the set of all homomorphisms from a graph H to a graph G. A notorious and important conjecture of Erdos and Simonovits, now called the Sidorenko conjecture, is as follows. Given graphs G and H, with H bipartite, the probability that a uniform random mapping from V (H) to V (G) is a homomorphism is at least the product over all edges of the probability that the edge is mapped to an edge of G. A graph H is said to be a Sidorenko graph if this conjecture holds for all graphs G. In spite of determined attacks by many excellent mathematicians, the class of Sidorenko graphs is still rather small. Agnijo will try to enlarge this class considerably, or disprove the Erdos-Simonovits- Sidorenko conjecture. There are several other problems in extremal and probabilistic graph theory that Agnijo should try to solve.

用Hom（H，G）表示从图H到图G的所有同态的集合。一个臭名昭著的和重要的猜想鄂尔多斯和西蒙诺维奇，现在被称为西多连科猜想，如下。给定图G和H，其中H是二分的，从V（H）到V（G）的一致随机映射是同态的概率至少是该边映射到G的边的概率在所有边上的乘积。一个图H称为Sidorenko图，如果这个猜想对所有图G都成立.尽管许多优秀的数学家坚决的攻击，类Sidorenko图仍然是相当小的。Agnijo将试图大大扩大这个类，或者反驳Erdos-Simonovits- Sidorenko猜想。Agnijo应该尝试解决极值和概率图论中的其他几个问题。