图 书 馆
Erdos-Faber-Lovasz猜想的一个证明A proof of the Erdos-Faber-Lovasz conjecture |
|
| 课程网址: | https://videolectures.net/8ecm2021_kuhn_proof_faber/ |
| 主讲教师: | 信息不详。欢迎您在右侧留言补充。 |
| 开课单位: | 8ECM会议 |
| 开课时间: | 2021-07-06 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Graph and hypergraph colouring problems are central to combinatorics, with applications and connections to many other areas, such as geometry, algorithm design, and information theory. However, for hypergraphs even basic problems have turned out to be rather challenging: in particular, the famous Erd˝os-Faber-Lov´asz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. (Here the chromatic index of a hypergraph H is the smallest number of colours needed to colour the edges of H so that any two edges that share a vertex have different colours.) There are also several other equivalent (dual) versions of this conjecture, e.g. in terms of colouring the vertices of nearly disjoint cliques. Erd˝os considered this to be one of his three most favorite combinatorial problems and offered $500 for the solution of the problem. In joint work with Dong-yeap Kang, Tom Kelly, Abhishek Methuku and Deryk Osthus, we prove this conjecture for every large n. We also provide ‘stability versions’ of this result, which confirm a prediction of Kahn. In my talk, I will discuss some background, some of the ideas behind the proof as well as some related open problems. |
| 关 键 词: | 超图着色问题; 组合数学; 算法设计 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2024-05-28：liyq |
| 最后编审: | 2024-05-28：liyq |
| 阅读次数: | 4 |