Summary: Let \(t\geq 1\) be a given integer. Let \({\mathcal F}\) be a family of subsets of \([m]=\{1,2,\ldots ,m\}\). Assume that for every pair of disjoint sets \(S,T\subset [m]\) with \(|S|=|T|=k\), there do not exist \(2t\) sets in \({\mathcal F}\) where \(t\) subsets of \({\mathcal F}\) contain \(S\) and are disjoint from \(T\) and \(t\) subsets of \({\mathcal F}\) contain \(T\) and are disjoint from \(S\). We show that \(|{\mathcal F}|\) is \(O(m^{k})\). Our main new ingredient is allowing, during the inductive proof, multisets of subsets of \([m]\) where the multiplicity of a given set is bounded by \(t-1\). We use a strong stability result of \textit{R. P. Anstee} and \textit{P. Keevash} [Eur. J. Comb. 27, No. 8, 1235--1248 (2006; Zbl 1104.05068)]. This is further evidence for a conjecture of \textit{R. P. Anstee} and \textit{A. Sali} [Combinatorica 25, No. 5, 503--518 (2005; Zbl 1107.05090)]. These problems can be stated in the language of matrices. Let \(t\cdot M\) denote \(t\) copies of the matrix \(M\) concatenated together. We have established the conjecture for those configurations \(t\cdot F\) for any \(k\times 2\;(0,1)\)-matrix \(F\).
- A combinatorial problem; stability and order for models and theories in infinitary languages
- A survey of forbidden configuration results
- Bounding one-way differences
- Forbidden configurations, discrepancy and determinants
- Forbidden submatrices
- scientific article; zbMATH DE number 3717317 (Why is no real title available?)
- On the density of families of sets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Pairwise intersections and forbidden configurations
- Small forbidden configurations. IV: The 3 rowed case
- Unavoidable traces of set systems
This page was built for publication: Repeated columns and an old chestnut
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396909)
