2008/08/29 by Irit Dinur, Ehud Friedgut · 57 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Discrete mathematics #Element (criminal law) #Family of sets #Graph Labeling and Dimension Problems #Interpretation (philosophy) #Limits and Structures in Graph Theory #Mathematics #Order (exchange) #Set (abstract data type)
paper · doi:10.1017/s0963548308009309
published in Combinatorics Probability Computing 18(1-2), 107-122 (Cambridge University Press)
openalex publication_date 2008/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
A family \J of subsets of 1, . . ., n is called a j -junta if there exists J ⊆ 1, . . ., n , with | J | = j , such that the membership of a set S in \J depends only on S ∩ J . In this paper we provide a simple description of intersecting families of sets. Let n and k be positive integers with k < n /2, and let \A be a family of pairwise intersecting subsets of 1, . . ., n , all of size k . We show that such a family is essentially contained in a j -junta \J , where j does not depend on n but only on the ratio k / n and on the interpretation of ‘essentially’. When k = o ( n ) we prove that every intersecting family of k -sets is almost contained in a dictatorship, a 1-junta (which by the Erdős–Ko–Rado theorem is a maximal intersecting family): for any such intersecting family \A there exists an element i ∈ 1, . . ., n such that the number of sets in \A that do not contain i is of order \C n-2k-2 (which is approximately \frac kn-k times the size of a maximal intersecting family). Our methods combine traditional combinatorics with results stemming from the theory of Boolean functions and discrete Fourier analysis.