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到Graph G的所有同构的集合。Erdos和Simonovits的臭名昭著而重要的猜想，现在称为Sidorenko猜想，如下所示。给定的图G和H带有H双方，从V（h）到V（g）均匀映射的均匀随机映射的可能性至少是同构的，至少是映射到G的所有概率上的产品上的产物。图形H的映射到G。图仍然很小。 Agnijo将尝试大量扩大该类别，或反驳Erdos-Simonovits-Sidorenko的猜想。 Agnijo应该尝试解决的极端和概率图理论中还有其他一些问题。