Intersection statements for systems of sets
A collection of sets is called a \(\Delta\)-system if any two sets have the same intersection. Let \(f(k,r)\) be the least integer such that any collelction of \(f(k,r)\) \(k\)-element sets contains a \(\Delta\)-system consisting of \(r\) sets. \textit{P. Erdös} and \textit{R. Rado} [J. Lond. Math. Soc. 44, 467-479 (1969; Zbl 0172.29601)] proved that \((r-1)^k< f(k,r)< k!(r-1)^k\) and conjectured that \(f(k,r)<C^k\) for some constant \(C\). Erdös offered \$1000 for a proof or disproof of this for \(r=3\). The paper under review concerns a related problem. Let \(F(n,r)\) be the greatest integer such that there exists a collection of subsets of an \(n\)-element set which does not contain a \(\Delta\)-system consisting of \(r\) sets. \textit{P. Erdös} and \textit{E. Szemerédi} [J. Comb. Theory, Ser. A 24, 308-313 (1978; Zbl 0383.05002)] showed that \(F(n,3)<2^{n-\sqrt{n}/10}\) and \(F(n,r)>(1+c_r)^n\), where the constant \(c_r\to 1\) as \(r\to\infty\). The authors provide new lower bounds for \(F(n,r)\) which are constructive and improve the previous best probabilistic results. They also prove a new upper bound. Moreover, for certain \(n\) it is shown that \(F(n,3)\geq 1.551^{n-2}\).
- An intersection theorem for systems of sets
- Combinatorial properties of systems of sets
- Forbidden Intersections
- scientific article; zbMATH DE number 970806 (Why is no real title available?)
- Intersection Theorems for Systems of Sets
- Intersection Theorems for Systems of Sets
- Intersection theorems for systems of sets
- Intersection Theorems for Systems of Sets (II)
- Intersection theorems for systems of sets (III)
- On finite \(\Delta\)-systems
- On finite Delta-systems. II
- On set systems not containing delta systems
- Set systems with three intersections
- On set systems not containing delta systems
- Combinatorial properties of systems of sets
- On the size of set systems on \([n]\) not containing weak \((r,\Delta)\)-systems
- Intersecting systems of signed sets
- Intersection Theorems for Systems of Sets
- On sunflowers and matrix multiplication
- scientific article; zbMATH DE number 3657816 (Why is no real title available?)
- Intersection Properties of Systems of Finite Sets
- On Systems of Small Sets with No Large Δ-Subsystems
- An intersection theorem for systems of sets
- scientific article; zbMATH DE number 1420988 (Why is no real title available?)
- Delta-systems and qualitative (in)dependence
- Near-sunflowers and focal families
- Upper bounds for families without weak delta-systems
- Parameterized complexity of deletion to scattered graph classes
- Uniform hypergraphs under certain intersection constraints between hyperedges
- Odd-sunflowers
- Towards odd-sunflowers: temperate families and lightnings
- Probabilistic methods for deriving new lower bounds on the rates of locally thin families and weak superimposed codes
- Odd-sunflowers (extended abstract)
- Focal-free uniform hypergraphs and codes
- On disjointly representable sets
- Constructions and bounds for \((m,t)\)-splitting systems
This page was built for publication: Intersection statements for systems of sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1369684)
