1981/06/01 by Neil Hindman · 2 citations
Mathematics · #Limits and Structures in Graph Theory #Combinatorics #Mathematics #Conjecture #Integer (computer science) #Discrete mathematics
paper · pdf · doi:10.4153/cjm-1981-046-9
openalex publication_date 1981/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
Let be a finite family of finite sets with the property that | A ∩ B | ≦ 1 whenever A and B are distinct members of . It is a conjecture of Erdös, Faber, and Lovász ([ 1 ] a 50 pound problem and [ 2 ] a 100 dollar problem) that there is an n -coloring of (i.e., a function such that A ∩ B = ∅ whenever A and B are distinct members of with f(A) = f(B) . They actually state the conjecture in a different form. They actually state the conjecture in a different form. Namely, if n is a positive integer and is a family of n sets satisfying (1) | B p | = n for each p and (2) | B p ∩ B q | ≦ 1 when p ≠ q , then there is an n -coloring of the elements of so that each set B p gets all n colors. The equivalence of the two forms is easily seen by interchanging the roles of elements and sets.