Repeated columns and an old chestnut

zbMATH Open1298.05310arXiv1305.0603MaRDI QIDQ396909FDOQ396909

Authors: Linyuan Lu, R. P. Anstee 

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $tge1$ be a given integer. Let $calF$ be a family of subsets of $[m]=1,2,ldots,m$. Assume that for every pair of disjoint sets $S,Tsubset[m]$ with $|S|=|T|=k$, there do not exist $2t$ sets in $calF$ where $t$ subsets of $calF$ contain $S$ and are disjoint from $T$ and $t$ subsets of $calF$ contain $T$ and are disjoint from $S$. We show that $|calF|$ 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 Anstee and Keevash. This is further evidence for a conjecture of Anstee and Sali. These problems can be stated in the language of matrices Let $tcdotM$ denote $t$ copies of the matrix $M$ concatenated together. We have established the conjecture for those configurations $tcdotF$ for any $kimes2$ (0,1)-matrix $F$.

Full work available at URL: https://arxiv.org/abs/1305.0603

Recommendations

• Forbidden configurations and repeated induction
• A survey of forbidden configuration results
• On forbidden submatrices
• Evidence for a forbidden configuration conjecture: One more case solved
• General forbidden configuration theorems

zbMATH Keywords

traceextremal set theoryforbidden configurationsmultiset\((0,1)\)-matricesextremal hypergraphssubhypergraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Extremal set theory (05D05)

Cites Work

• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Pairwise intersections and forbidden configurations
• Forbidden submatrices
• Bounding one-way differences
• A survey of forbidden configuration results
• Small forbidden configurations. IV: The 3 rowed case
• Forbidden configurations, discrepancy and determinants
• Unavoidable traces of set systems
• Title not available (Why is that?)

Cited In (2)

• Shattered matchings in intersecting hypergraphs
• Remarks on ‘equivalence of stability concepts for discrete time-varying 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)