Repeated columns and an old chestnut

MaRDI QIDQ396909zbMATH OpenFDO

Authors Linyuan Lu, R. P. Anstee

Publication date 14 August 2014

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

Full work available at URL https://arxiv.org/abs/1305.0603, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p2

zbMATH Keywords

\((0,1)\)-matricesextremal hypergraphsextremal set theoryforbidden configurationsmultisetsubhypergraphtrace

Mathematics Subject Classification ID

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

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$.

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

Cites work

• 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

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)