pith. sign in

arxiv: 1305.0603 · v1 · pith:WO7B4MHHnew · submitted 2013-05-03 · 🧮 math.CO

Repeated columns and an old chestnut

classification 🧮 math.CO
keywords subsetsdisjointansteecdotconjecturecontaingivenmatrix
0
0 comments X
read the original abstract

Let $t\ge 1$ be a given integer. Let ${\cal 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 ${\cal F}$ where $t$ subsets of ${\cal F}$ contain $S$ and are disjoint from $T$ and $t$ subsets of ${\cal F}$ contain $T$ and are disjoint from $S$. We show that $|{\cal 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 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 $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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.