A homological approach to two problems on finite sets (Q1283453)

The paper develops a new, homological approach to prove extremal set theoretical problems on simplexes. A \(d\)-simplex is a \(k\)-uniform set system of \(d+1\) elements with empty total intersection, but no \(d\)-element subsystem has empty intersection. Denote \(S(n,k,d)\) the maximum cardinality of a \(k\)-uniform set system on an \(n\)-element underlying set without \(d\)-complexes. Then the classical Erdős-Ko-Rado theorem states that \(S(n,k,1)={n-1 \choose k-1}\). V. Chvátal conjectured in 1974, that \(S(n,k,d)={n-1 \choose k-1}\) whenever \(d< k \leq {dn \over d+1}\). In the same paper Chvátal proved it for \(k=d+1\). This paper supplies a new proof for Chvátal's result. A special \(d\)-simplex has an even more strict structure. P. Frankl and Z. Füredi proved an analogous theorem for special simplexes for big enough \(n\)'s. They conjectured that the result is valid for every \(k\geq d+1\). This paper proves this later conjecture for the case \(3=k=d+1\).