当前位置: 首页 > 新闻中心 > 学术活动 > 正文

Does every countable infinite graph admit an unfriendly partition?

发布日期:2024-11-06点击数:

报告人:向开南 教授(湘潭大学)

时间:2024年11月13日 10:30-

地点:理科楼LA103


摘要:Unfriendly Partition Conjecture. Every countable infinite graph admits an unfriendly partition of its vertex set in the sense that any vertex has at least as many neighbours in the other class as in its own.

This conjecture has a history of about 35 years, and is one of the best-known longstanding open problems in infinite graph theory. From Open Problem Garden (http://www.openproblemgarden.org/),on the conjecture, “It does not appear that there is any consensus among experts as to whether this conjecture should be true or false.”and it together with KPZ Universality Conjecture in probability theory, and The 3n+1 Conjecture (The 3x+1 Problem) in number theory are of high importance with ✭✭✭. Here the highest importance in Open Problem Garden is ✭✭✭✭ (the Riemann hypothesisis 4 stars).

An old theorem of L. Lovasz (1966) asserts that every finite graph has an unfriendly partition. Recall there was an original folklore conjecture that every graph has an unfriendly partition of its vertex set. S. Shelah and E. C. Milner (1990) constructed uncountable graphs without unfriendly partitions by set-theoretic methods and disproved the folklore conjecture, and showed that any graph does have an unfriendly partition into three sets (the number of neighbours of every vertex in its own class is no more than those neighbours not in its class). The aforementioned Unfriendly Partition Conjecture was posed by R. Cowan and W. Emerson before 1990; and there were some important progresses on the conjecture obtained by discrete mathematics experts respectively in 1990, 2010 and 2017.

Currently, unfriendly or friendly partitions have been studied extremely extensively in various contexts such as combinatorics and probabilistic combinatorics (for their inherent interest),computer science (for their NP-hardness/completeness), probability theory and statistical physics (for their connections to spin glasses), and logic and set theory (for their theoretical value).

Recall fom N. Alon & M. Krivelevich (2008. Extremal and probabilistic combinatorics, inThe Princeton Companion to Mathematics), “A wonderful development took place in twentieth-century mathematics when it was realized that it is sometimes possible to use probabilistic reasoning to prove mathematical statements that do not have an obvious probabilistic nature.”

Is there a probabilistic proof for the unproven Unfriendly Partition Conjecture? Our answer is yes. The talk is based on our 5 year exploration [Xiang Kainan, (2019-2024), Every countable infinite graph admits an unfriendly partition, Preprint.], in which site percolation, weak convergence theory of probability measures, together with a novel topology and metric issue, play a key role.


邀请人:周国立


欢迎广大师生积极参与!


关于我们
重庆大学数学与统计学院的前身是始建于1929年的重庆大学理学院和1937年建立的重庆大学商学院,理学院是重庆大学最早设立的三个学院之一,首任院长为数学家何鲁先生。