Pairwise intersections and forbidden configurations

DOI10.1016/J.EJC.2006.05.002MaRDI QIDQ850074zbMATH OpenFDO

Authors Peter Keevash, R. P. Anstee

Publication date 15 November 2006

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

Full work available at URL https://doi.org/10.1016/J.EJC.2006.05.002

zbMATH Keywords

Complete Intersection Theoremconjecture of Anstee and SaliErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Extremal set theory (05D05)

Review text

This interesting paper proves at first a strong stability version of the celebrated complete intersection theorem of Ahlswede and Khachatrian in the spirit of the Hilton-Milner theorem. Then using it the authors prove the following result: let \(f_m(a,b,c,d)\) denote the maximum size of a family of an \(m\)-element underlying set with the property that for all pairs \(A,B\) we have \(| A \cap B| \geq a,\) \(| \overline{A} \cap B| \geq b,\) \(| A \cap \overline{B}| \geq c\) and \(| \overline{A} \cap \overline{B}| \geq d.\) Then \(f_m(a,b,c,d) = \Theta( m^{a+b-1})\) for a wide range of the parameters.

Recommendations

• Pairwise intersections and forbidden configurations
• Around the complete intersection theorem
• Some exact results for multiply intersecting families
• Non-trivial \(d\)-wise intersecting families
• More complete intersection theorems

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• Disjoint representability of sets and their complements
• Forbidding just one intersection
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersection theorems for systems of finite sets
• On a combinatorial conjecture of Erdös
• On intersecting families of finite sets
• On the density of families of sets
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Small forbidden configurations
• Small forbidden configurations. IV: The 3 rowed case
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Stability theorems for cancellative hypergraphs
• The complete intersection theorem for systems of finite sets
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• The Turán number of the Fano plane
• Triple Systems Not Containing a Fano Configuration

Cited in

(22)

• Forbidden configurations, discrepancy and determinants
• Bounds on pairs of families with restricted intersections
• Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
• Forbidding intersection patterns between layers of the cube
• Forbidden families of minimal quadratic and cubic configurations
• Forbidden configurations: boundary cases
• Forbidden configurations: boundary cases
• On the path avoiding forbidden pairs polytope
• Forbidden k‐Sets in the Plane
• Pairwise intersections and forbidden configurations
• Repeated columns and an old chestnut
• Evidence for a forbidden configuration conjecture: One more case solved
• Arrangements of \(k\)-sets with intersection constraints
• scientific article; zbMATH DE number 1556738 (Why is no real title available?)
• Forbidden configurations and product constructions
• Set systems without a simplex or a cluster
• Multivalued matrices and forbidden configurations
• Geometrical sets with forbidden configurations
• Stability for the Complete Intersection Theorem, and the Forbidden Intersection Problem of Erd\H{o}s and S\'os
• Forbidden configurations and Steiner designs
• Two refinements of the bound of Sauer, Perles and Shelah, and of Vapnik and Chervonenkis
• Stability theorems for forbidden configurations

This page was built for publication: Pairwise intersections and forbidden configurations

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