Name
Abstract | ||
|---|---|---|
A family 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 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 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 , 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ősKoRado theorem is a maximal intersecting family): for any such intersecting family there exists an element i ∈ {1,…, n} such that the number of sets in that do not contain i is of order (which is approximately 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1017/S0963548308009309 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
boolean function,size k,independent sets,intersecting family,maximal intersecting family,product graphs. ⁄ school of computer science and engineering,ratio k,jerusalem,intersecting families,positive integer,hebrew university,discrete fourier analysis,israel. email: dinuri at cs.huji.ac.il.,k n,pairwise intersecting subsets,element i,independent set,computational science and engineering | Integer,Boolean function,Discrete mathematics,Family of sets,Combinatorics,Existential quantification,Mathematics,Discrete fourier analysis | Journal |
Volume | Issue | ISSN |
18 | 1-2 | 0963-5483 |
Citations | PageRank | References |
16 | 1.37 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irit Dinur | 1 | 1187 | 85.67 |
| Ehud Friedgut | 2 | 440 | 38.93 |