A proof of the Erdos-Faber-Lovasz conjecture

Dong Yeap Kang; Tom Kelly; Daniela Kuhn; Abhishek Methuku; Deryk Osthus

doi:10.4007/annals.2023.198.2.2

A proof of the Erdos-Faber-Lovasz conjecture

Dong Yeap Kang, Tom Kelly, Daniela Kuhn, Abhishek Methuku, Deryk Osthus

Mathematics

Research output: Contribution to journal › Article › peer-review

123 Downloads (Pure)

Abstract

The Erdos-Faber-Lovasz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this paper, we prove this conjecture for every large n. We also provide stability versions of this result, which confirm a prediction of Kahn.

Original language	English
Pages (from-to)	537-618
Number of pages	82
Journal	Annals of Mathematics
Volume	198
Issue number	2
Early online date	31 Aug 2023
DOIs	https://doi.org/10.4007/annals.2023.198.2.2
Publication status	Published - Sept 2023

Bibliographical note

An article written for high school students about our work:
The Erdős-Faber-Lovász Conjecture: Fifty Exciting Years
January 2024
DOI:10.13140/RG.2.2.14773.45285
Authors: P. Mark Kayll

Keywords

absorption
chromatic index
graph coloring
hypergraph edge coloring
nibble

Access to Document

10.4007/annals.2023.198.2.2

KangD2023Aproof
This is the Accepted Author Manuscript (AAM) of an article to be published in Annals of Mathematics by Princeton University, Institute for Advanced Study.
Accepted author manuscript, 923 KBLicence: None: All rights reserved

Approximate Structure in Large Graphs and Hypergraphs
Osthus, D. (Principal Investigator)
Engineering & Physical Science Research Council
1/01/19 → 31/12/21
Project: Research Councils
H2020_ERC_EXTCOMB
Osthus, D. (Co-Investigator) & Kuhn, D. (Principal Investigator)
European Commission
1/01/19 → 31/12/24
Project: EU
Combinatorics, Probability and Algorithms: Fellowship, Establish Career: Professor D Kuhn
Kuhn, D. (Principal Investigator)
Engineering & Physical Science Research Council
1/09/16 → 31/08/21
Project: Research Councils

Frontiers of Science award
Kelly, T. (Recipient), Kang, D. Y. (Recipient), Kuhn, D. (Recipient), Methuku, A. (Recipient) & Osthus, D. (Recipient), 2024
Prize: Prize (including medals and awards)

Cite this

@article{20952d7d5e0f4ad5bc1a09c5abf919e4,

title = "A proof of the Erdos-Faber-Lovasz conjecture",

abstract = "The Erdos-Faber-Lovasz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this paper, we prove this conjecture for every large n. We also provide stability versions of this result, which confirm a prediction of Kahn.",

keywords = "absorption, chromatic index, graph coloring, hypergraph edge coloring, nibble",

author = "Kang, {Dong Yeap} and Tom Kelly and Daniela Kuhn and Abhishek Methuku and Deryk Osthus",

note = "An article written for high school students about our work: The Erd{\H o}s-Faber-Lov{\'a}sz Conjecture: Fifty Exciting Years January 2024 DOI:10.13140/RG.2.2.14773.45285 Authors: P. Mark Kayll ",

year = "2023",

month = sep,

doi = "10.4007/annals.2023.198.2.2",

language = "English",

volume = "198",

pages = "537--618",

journal = "Annals of Mathematics",

issn = "0003-486X",

publisher = "Princeton University, Department of Mathematics",

number = "2",

}

TY - JOUR

T1 - A proof of the Erdos-Faber-Lovasz conjecture

AU - Kang, Dong Yeap

AU - Kelly, Tom

AU - Kuhn, Daniela

AU - Methuku, Abhishek

AU - Osthus, Deryk

N1 - An article written for high school students about our work: The Erdős-Faber-Lovász Conjecture: Fifty Exciting Years January 2024 DOI:10.13140/RG.2.2.14773.45285 Authors: P. Mark Kayll

PY - 2023/9

Y1 - 2023/9

N2 - The Erdos-Faber-Lovasz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this paper, we prove this conjecture for every large n. We also provide stability versions of this result, which confirm a prediction of Kahn.

AB - The Erdos-Faber-Lovasz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this paper, we prove this conjecture for every large n. We also provide stability versions of this result, which confirm a prediction of Kahn.

KW - absorption

KW - chromatic index

KW - graph coloring

KW - hypergraph edge coloring

KW - nibble

UR - https://www.quantamagazine.org/mathematicians-settle-erdos-coloring-conjecture-20210405/

UR - https://gilkalai.wordpress.com/2021/01/14/to-cheer-you-up-in-difficult-times-17-amazing-the-erdos-faber-lovasz-conjecture-for-large-n-was-proved-by-dong-yeap-kang-tom-kelly-daniela-kuhn-abhishek-methuku-and-deryk-osthus/?fbclid=IwAR1CSdRGDKHLR3RYVL9sihYSLp_mOu_CZ9P4deA_CQ_VYj4pazyRlhmCRuM

UR - https://institucional.us.es/blogimus/en/2021/04/lll/

UR - https://rjlipton.wpcomstaging.com/2021/03/19/closing-an-erdos-problem/?fbclid=IwAR2vPahcAVfe5TmoRDg9NuFBYeOnhLq8uXaR2xxf2I37NvuurZUgjjFXsh0

U2 - 10.4007/annals.2023.198.2.2

DO - 10.4007/annals.2023.198.2.2

M3 - Article

SN - 0003-486X

VL - 198

SP - 537

EP - 618

JO - Annals of Mathematics

JF - Annals of Mathematics

IS - 2

ER -

A proof of the Erdos-Faber-Lovasz conjecture

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Projects

Approximate Structure in Large Graphs and Hypergraphs

H2020_ERC_EXTCOMB

Combinatorics, Probability and Algorithms: Fellowship, Establish Career: Professor D Kuhn

Prizes

Frontiers of Science award

Cite this