A proof of the Erdös-Faber-Lovász conjecture: algorithmic aspects

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

doi:10.1109/FOCS52979.2021.00107

A proof of the Erdös-Faber-Lovász conjecture: algorithmic aspects

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

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

153 Downloads (Pure)

Abstract

The Erdos-Faber-Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. Erdös considered this to be one of his three most favorite combinatorial problems and offered a 500 reward for a proof of this conjecture. We prove this conjecture for every large n. Here, we also provide a randomised algorithm to find such a colouring in polynomial time with high probability.

Original language	English
Title of host publication	2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
Publisher	IEEE Computer Society Press
Pages	1080-1089
Number of pages	10
ISBN (Electronic)	9781665420556
ISBN (Print)	9781665420563 (PoD)
DOIs	https://doi.org/10.1109/FOCS52979.2021.00107
Publication status	Published - 4 Mar 2022
Event	62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 - Virtual, Online, United States Duration: 7 Feb 2022 → 10 Feb 2022

Publication series

Name	Annual IEEE Symposium on Foundations of Computer Science
ISSN (Print)	1523-8288
ISSN (Electronic)	2575-8454

Conference

Conference	62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021
Country/Territory	United States
City	Virtual, Online
Period	7/02/22 → 10/02/22

Bibliographical note

Publisher Copyright:
© 2022 IEEE.

Keywords

Erdös-Faber-Lovász
Hypergraph colouring
Rödl nibble

ASJC Scopus subject areas

General Computer Science

Access to Document

10.1109/FOCS52979.2021.00107

KangD2022proof
D. Y. Kang, T. Kelly, D. Kühn, A. Methuku and D. Osthus, "A proof of the Erdös-Faber-Lovász conjecture: Algorithmic aspects," 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022, pp. 1080-1089, doi: 10.1109/FOCS52979.2021.00107. © 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Accepted author manuscript, 293 KBLicence: Other (please specify with Rights Statement)

Cite this

Kang, D. Y., Kelly, T., Kuhn, D., Methuku, A., & Osthus, D. (2022). A proof of the Erdös-Faber-Lovász conjecture: algorithmic aspects. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (pp. 1080-1089). Article 9719748 (Annual IEEE Symposium on Foundations of Computer Science). IEEE Computer Society Press. https://doi.org/10.1109/FOCS52979.2021.00107

@inproceedings{5d9ba409c3b047e5a3004bf3efcd4f1e,

title = "A proof of the Erd{\"o}s-Faber-Lov{\'a}sz conjecture: algorithmic aspects",

abstract = "The Erdos-Faber-Lov{\'a}sz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. Erd{\"o}s considered this to be one of his three most favorite combinatorial problems and offered a 500 reward for a proof of this conjecture. We prove this conjecture for every large n. Here, we also provide a randomised algorithm to find such a colouring in polynomial time with high probability.",

keywords = "Erd{\"o}s-Faber-Lov{\'a}sz, Hypergraph colouring, R{\"o}dl nibble",

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

note = "Publisher Copyright: {\textcopyright} 2022 IEEE.; 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 ; Conference date: 07-02-2022 Through 10-02-2022",

year = "2022",

month = mar,

day = "4",

doi = "10.1109/FOCS52979.2021.00107",

language = "English",

isbn = "9781665420563 (PoD)",

series = "Annual IEEE Symposium on Foundations of Computer Science",

publisher = "IEEE Computer Society Press",

pages = "1080--1089",

booktitle = "2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)",

}

Kang, DY, Kelly, T, Kuhn, D, Methuku, A & Osthus, D 2022, A proof of the Erdös-Faber-Lovász conjecture: algorithmic aspects. in 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)., 9719748, Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, pp. 1080-1089, 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Virtual, Online, United States, 7/02/22. https://doi.org/10.1109/FOCS52979.2021.00107

A proof of the Erdös-Faber-Lovász conjecture: algorithmic aspects. / Kang, Dong Yeap; Kelly, Tom; Kuhn, Daniela et al.
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, 2022. p. 1080-1089 9719748 (Annual IEEE Symposium on Foundations of Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A proof of the Erdös-Faber-Lovász conjecture

T2 - 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021

AU - Kang, Dong Yeap

AU - Kelly, Tom

AU - Kuhn, Daniela

AU - Methuku, Abhishek

AU - Osthus, Deryk

PY - 2022/3/4

Y1 - 2022/3/4

N2 - The Erdos-Faber-Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. Erdös considered this to be one of his three most favorite combinatorial problems and offered a 500 reward for a proof of this conjecture. We prove this conjecture for every large n. Here, we also provide a randomised algorithm to find such a colouring in polynomial time with high probability.

AB - The Erdos-Faber-Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. Erdös considered this to be one of his three most favorite combinatorial problems and offered a 500 reward for a proof of this conjecture. We prove this conjecture for every large n. Here, we also provide a randomised algorithm to find such a colouring in polynomial time with high probability.

KW - Erdös-Faber-Lovász

KW - Hypergraph colouring

KW - Rödl nibble

UR - http://www.scopus.com/inward/record.url?scp=85127210207&partnerID=8YFLogxK

U2 - 10.1109/FOCS52979.2021.00107

DO - 10.1109/FOCS52979.2021.00107

M3 - Conference contribution

AN - SCOPUS:85127210207

SN - 9781665420563 (PoD)

T3 - Annual IEEE Symposium on Foundations of Computer Science

SP - 1080

EP - 1089

BT - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)

PB - IEEE Computer Society Press

Y2 - 7 February 2022 through 10 February 2022

ER -

A proof of the Erdös-Faber-Lovász conjecture: algorithmic aspects

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this