The Intersection Spectrum of 3-Chromatic Intersecting Hypergraphs

Matija Bucić, Stefan Glock, Benny Sudakov

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

For a hypergraph H, define its intersection spectrum I(H) as the set of all intersection sizes | E∩ F| of distinct edges E, F∈ E(H). In their seminal paper from 1973 which introduced the local lemma, Erdős and Lovász asked: how large must the intersection spectrum of a k-uniform 3-chromatic intersecting hypergraph be? They showed that such a hypergraph must have at least three intersection sizes, and conjectured that the size of the intersection spectrum tends to infinity with k. Despite the problem being reiterated several times over the years by Erdős and other researchers, the lower bound of three intersection sizes has remarkably withstood any improvement until now. In this paper, we prove the Erdős–Lovász conjecture in a strong form by showing that there are at least k1 / 2 - o ( 1 ) intersection sizes. In this extended abstract we sketch a simpler argument which gives slightly weaker bound of k1 / 3 - o ( 1 ). Our proof consists of a delicate interplay between Ramsey type arguments and a density increment approach.

Original languageEnglish (US)
Title of host publicationTrends in Mathematics
PublisherSpringer Science and Business Media Deutschland GmbH
Pages136-141
Number of pages6
DOIs
StatePublished - 2021
Externally publishedYes

Publication series

NameTrends in Mathematics
Volume14
ISSN (Print)2297-0215
ISSN (Electronic)2297-024X

All Science Journal Classification (ASJC) codes

  • General Mathematics

Keywords

  • Intersecting hypergraphs
  • Intersection spectrum
  • Property B

Fingerprint

Dive into the research topics of 'The Intersection Spectrum of 3-Chromatic Intersecting Hypergraphs'. Together they form a unique fingerprint.

Cite this