A localization inequality for set functions

László Lovász, Michael Saks

Research output: Contribution to journalArticle

1 Scopus citations


We prove the following theorem, which is an analog for discrete set functions of a geometric result of Lovász and Simonovits. Given two real-valued set functions f1, f2 defined on the subsets of a finite set S, satisfying ∑X⊆S fi(X) ≥ 0 for i ∈ {1, 2}, there exists a positive multiplicative set function μ over S and two subsets A, B ⊆ S such that for i ∈ {1, 2} μ(A) fi(A) + μ(B) fi(B) + μ(A ∪ B) fi(A ∪ B) + μ(A ∩ B) fi(A ∩ B) ≥ 0. The Ahlswede-Daykin four function theorem can be deduced easily from this.

Original languageEnglish (US)
Pages (from-to)726-735
Number of pages10
JournalJournal of Combinatorial Theory. Series A
Issue number4
StatePublished - May 1 2006

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • Discrete localization
  • Four function theorem
  • Inequalities
  • Set functions

Fingerprint Dive into the research topics of 'A localization inequality for set functions'. Together they form a unique fingerprint.

  • Cite this