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 的所有同态的集合。 Erdos 和 Simonovits 的一个臭名昭著且重要的猜想，现在称为 Sidorenko 猜想，如下所示。给定图 G 和 H，其中 H 二部，从 V (H) 到 V (G) 的均匀随机映射是同态的概率至少是该边映射到以下边的概率在所有边上的乘积G.如果这个猜想对于所有图G都成立，则图H被称为Sidorenko图。尽管许多优秀的数学家进行了坚决的攻击，Sidorenko图的类别仍然相当小。阿格尼霍将尝试大大扩大这个类别，或者反驳埃尔多斯-西蒙诺维茨-西多连科猜想。 Agnijo 应该尝试解决极值和概率图论中的其他几个问题。