Name
Abstract | ||
|---|---|---|
This paper contains a proof of the following result: ifn≧(t+1)(k−t−1), then any family ofk-subsets of ann-set with the property that any two of the subsets meet in at leastt points contains at most
$$\left( {\begin{array}{*{20}c} {n - t} \\ {k - t} \\ \end{array} } \right)$$
subsets. (By a theorem of P. Frankl, this was known whent≧15.) The bound (t+1)(k-t-1) represents the best possible strengthening of the original 1961 theorem of Erds, Ko, and Rado which reaches the same
conclusion under the hypothesisn≧t+(k−t)
$$\left( {\begin{array}{*{20}c} k \\ t \\ \end{array} } \right)^3 $$
. Our proof is linear algebraic in nature; it may be considered as an application of Delsarte’s linear programming bound,
but somewhat lengthy calculations are required to reach the stated result. (A. Schrijver has previously noticed the relevance
of these methods.) Our exposition is self-contained. |
Year | DOI | Venue |
|---|---|---|
1984 | 10.1007/BF02579226 | Combinatorica |
Keywords | Field | DocType |
linear program,linear algebra | Graph theory,Discrete mathematics,Combinatorics,Erdős–Ko–Rado theorem,Algebraic number,Hypergraph,Mathematics | Journal |
Volume | Issue | ISSN |
4 | 2 | 1439-6912 |
Citations | PageRank | References |
76 | 13.85 | 1 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Richard M. Wilson | 1 | 697 | 340.86 |