Linear dependencies among subsets of a finite set

DOI10.1016/S0195-6698(83)80027-4MaRDI QIDQ788726zbMATH OpenWikidataFDO

Authors Peter Frankl, N. M. Singhi

Publication date 1983

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0195-6698(83)80027-4

zbMATH Keywords

0-designextremal set theoryfamily of sets

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial aspects of block designs (05B05) Extremal set theory (05D05)

Review text

Let integers \(k\) and \(t\) be given so that \(k>t\ge 0\). A family of \(k\)-sets \(F_1,\ldots,F_m\) with rational coefficients \(\alpha_1,\ldots,\alpha_m\) forms a \(0\)-design for \(k\) and \(t\) if, for any \(t\)-set \(G\), \(\sum \alpha_i=0\) (where the sum is taken over all \(i\) such that \(G\subset F_i)\). In this paper, the authors prove that, if \(\binom{t+1}{1}, \ldots, \binom{t+1}{k-t-1}\) have a common divisor \(d\) which does not divide \(\alpha_i\), then there exists an index \(j\) so that \(| F_i\cap F_j| = k-t-1\). Using this result, the authors deduce some other results in extremal set theory relating to problems posed by Erdős.

Recommendations

• An extremal set theoretical characterization of some Steiner systems
• The minimum independence number for designs
• scientific article; zbMATH DE number 3880717
• Using the existence of \(t\)-designs to prove Erdős-Ko-Rado
• The exact bound in the Erdős-Ko-Rado theorem

Cites work

• An intersection problem for finite sets
• Extremal problems and coverings of the space
• scientific article; zbMATH DE number 3561377 (Why is no real title available?)
• scientific article; zbMATH DE number 3639656 (Why is no real title available?)
• Intersection theorems for systems of finite sets
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersection theorems with geometric consequences
• On families of finite sets no two of which intersect in a singleton
• On the Structure oft-Designs
• The module structure of integral designs

Cited in

(8)

• Forbidding just one intersection
• Exact solution of some Turán-type problems
• Non \(t\)-intersecting families of linear spaces over \(GF(q)\)
• Linearly independent set families
• Specified intersections
• On functions of strength t
• On hypergraphs without two edges intersecting in a given number of vertices
• An extremal problem for Graham-Rothschild parameter words

This page was built for publication: Linear dependencies among subsets of a finite set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q788726)